基于身份的指定多个验证者的代理签名方案.doc

2008 年 11 月Journal on CommunicationsNovember 2008 第 29 卷第 11A 期通 信 学 报Vol 29 No 11A 基于身份的指定多个验证者的代理签名方案 唐朝霞 徐秋亮 朱建栋 山东大学 计算机科学与技术学院 山东 济南 250101 摘 要 引入基于身份的签名思想 对指定验证者代理签名方案进行扩展 提出了第一个基于身份的指定多个 验证者的代理签名方案 在此方案中代理签名者可以指定多个验证者 只有指定的多个验证者协作才能验证代 理签名的有效性 通过对方案的分析 证明了方案属于强指定验证者代理签名的范畴 并且满足不可伪造性等 安全性要求 关键词 指定验证者 代理签名 不可伪造 中图分类号 TP309 文献标识码 A 文章编号 1000 436X 2008 11A 0041 05 ID based designated multi verifier proxy signature scheme TANG Zhao xia XU Qiu liang ZHU Jian dong College of Computer Science and Technology Shandong University Ji nan 250101 Abstract Introduced the concept of ID based signature extended the designated verifier proxy signature a ID based designated multi verifier proxy signature scheme was proposed In the proposed scheme the proxy signer designate several verifiers and only when the designated verifiers coorperate they can check the validity of the proxy signatures By analyzing the proposed scheme It proved that the scheme is a strong designated verifier proxy signature scheme and has many properties i e unforeability Key words designated verifier proxy signature unforgeability 1 引言 1996 年 Jakobsson 等提出了第一个指定验证者 签名体制 1 指定验证者签名是指签名只可由签名 者指定的验证者来验证签名体制 它具有许多应 用 如电子投票 软件许可等 1996 年 Mambo Usuda 和 Okamoto 首先提出 了代理签名的概念 2 3 所谓代理签名是指原始签 名者可以将签名权利授权给代理签名者 代理签 名者可以代替原始签名者对消息进行签名 当收 到某一消息的代理签名时 验证者可以通过给定 的验证过程来验证代理签名的正确性 代理签名 的出现解决了数字签名中的签名权的授权问题 指定验证者代理签名方案可以看作是指定验 证者签名和代理签名的结合 在指定验证者代理 签名方案中 原始签名者可以将签名权力授权给 代理签名者 但是只有指定的验证者可以验证代 理签名的正确性 指定验证者代理签名体制最早 由 Dai 等提出 4 后来 Guilin Wang 通过原始签名 者的伪造攻击指出 Dai 的体制不安全 并提出了 一个新的有效的安全的指定验证者代理签名体制 5 2005 年 Guilin Wang 提出两个版本的指定验 收稿日期 2008 09 03 基金项目 山东省自然科学基金资助项目 Y2007G37 山东省科技攻关计划 2007GG10001012 Foundation Items The Natural Science Foundation of Shandong Province Y2007G37 Key Technologies Research and Development Program of Shandong Province 2007GG10001012 42 通 信 学 报第 29 卷 证者代理签名 6 弱 DVPS 和强 DVPS 在两个 版本中 代理签名的合法性只能由指定的验证者 检验 在弱 DVPS 体制中 指定的验证者可以将 代理签名进一步转换为可以公共验证的签名 然 而 强 DVPS 体制没有这样的性质 即使指定验 证者的私钥被故意或不故意地揭漏 1984 年 shamir 提出了基于身份的公钥密码系 统的概念 7 基于身份的公钥密码系统允许使用用 户的公共信息 如名字 地址等 作为其公钥 用户的私钥由密钥生成中心 KGC 生成并通过 安全信道发送给用户 Susilo 等给出了基于身份的 强指定验证者签名体制的一般性构造 8 Kumar 等 提出了一个具有不可授权性的基于身份的强指定 验证者签名体制 9 Cao 等人给出了一个基于身份 的指定验证者代理签名方案 10 在指定验证者代理签名的研究中 大部分只 考虑了指定一个验证者的情况 而在实际应用中 有些情况需要指定多个验证者 本文将对指定验 证者代理签名方案进行扩展 提出第一个基于身 份的指定多个验证者的代理签名方案 使得代理 签名者可以指定多个验证者 并且只有指定的多 个验证者一起才可以验证代理签名的正确性 2 预备知识 2 1 双线性对 令 1 G是阶为q 大素数 的一个加法循环群 P 为 1 G的生成元 2 G是阶为q的乘法循环群 112 e GGG 为满足下列性质的双线性对 1 双线性 对所有 1 P QG 和所有的 q a bZ ab e aP bQe P Q 2 非退化性 存在 1 P QG 使得 1e P Q 3 可计算性 对所有 1 P QG 存在有效算 法可以计算 e P Q 2 2 数学问题及 GDH 群 令 1 G是一个加法群 1 离散对数问题 DLP 任给 1 P QG 求 假设这样的整数存在 QaP q aZ 2 计算性 Diffie Hellman 问题 CDHP 对于 给定 计算 Rq a bZ 1R PG P aP bPabP 3 判定性 Diffie Hellman 问题 DDHP 对于 给定 判断 Rq a b cZ 1R PG P aP bP cP 是否成立 若等式成立 则称 mod cabq 为一个有效的Diffie Hellman 四元组 P aP bP cP 4 Gap Diffie Hellman 问题 GDHP 判定 性 Diffie Hellman 问题 DDHP 容易 计算性 Diffie Hellman 问题 CDHP 困难的一类问题 5 Gap Diffie Hellman 群 GDH 群 如果在 群上 DDHP 是容易的 CDHP 是困难的 那 1 G 么被称为一个 GDH 群 1 G 3 基于身份的指定多个验证者的代理签名 方案 3 1 模型定义 基于身份的指定多验证者代理签名体制的定 义与基于身份的指定验证者代理签名体制的定义 类似 主要包括以下 5 个阶段 1 系统设置 给定安全参数作为输入 生k 成系统参数并在所有用户中公开 2 密钥提取 输入用户 原始签名者 代理 签名者 指定验证者 的身份信息和公共参数 计算他们的私钥 3 代理密钥生成 给定原始签名者支持的签 名体制和代理签名者的私钥 输出代理签名密钥 4 指定多个验证者的代理签名生成 给定代 理签名密钥 指定验证者的公钥和公共参数 输 出一个指定多验证者代理签名 5 代理签名的指定验证 接收到指定多验证 者代理签名和指定的多个验证者的私钥后 本阶 段检验接收到的代理签名的有效性 3 2 具体的基于身份的指定多个验证者代理签名 方案 1 系统设置 PKG 选择q阶循环群 12 GG 设 1 G的 生成元为 P 选择双线性映射 112 e GGG 随机选择 Rq sZ 作为主密钥 令 pub PsP 选择 4 个散列函数 0 1 0 q ZH 1 1 1 0 GH 1 2 1 0 q ZGH 123 GGH 第 11A 期唐朝霞等 基于身份的指定多个验证者的代理签名方案 43 公开 120123 G G P Pub HH HH e 保密s 2 密钥提取 对给定串 0 1ID PKG 计算 1ID QHID 令私钥 IDID dsQ 其中的 s 为主密钥 3 代理密钥生成 同文献 9 相同 本文使用基于 Cha Cheon 体 制 11 的代理密钥生成方法 授权书 w m描述了具体 的代理限制细节 包括授权期限 原始签名者 Alice 和代理签名者 Bob 的身份信息 对授权的签 名权力的限制等信息 Alice 为了将签名权利授权 给 Bob 需要以下几步 Step1 Alice 使用 Cha Cheon 签名体制对 w m签名 随机选择 q rZ 计算 2 AliceAlice IDwID UrQhHm UVrh d 2 AliceAlice IDwID UrQhHm UVrh d 将 w m U V 发送给 Bob Step2 Bob 计算 2 w hHm U 检查等式 Alice pubID e P Ve PUhQ 是否成立 Step3 若 Step2 中的检验成立 则 Bob 计算 代理密钥 2 Bob pwID dVHm U d 2 AliceBob pwIDID QUHm UQQ 4 指定多个验证者的代理签名生成设指定验 证者对消息m 的指定验证者签名如下 12 n c cc Bob 随机选择 123 q r r rZ 计算 11 1 22 31 3 1 320 1 1 310 Ci Ci Ci n ID i p n ID i n IDp i p UrQ Ur Q UrrQ HHe rQd Hm Vr Hr d Hm 对消息m 的指定多验证代理签名即为 123 U U U V Bob 将 w m m U 发送给指 定的验证者 12 n c cc 5 代理签名的指定验证 Step1 计算 0 Ci iID dHm 1 2 i c in 并将其在 n 个验证者中公开 Step2 对于接收到的 验证 1 2 ii jnji C 0 Cj jpubID e Pe PHm Q 是否成立 Step3 若 Step 2 的验证成立 每个 i C 计算 2 AliceBob pwIDID QUHm UQQ 验证 13 1 n ip i e U Ve UHeQ 是否成立 若成立 为关于m 的有效的代 理签名 4 方案分析 4 1 正确性 若是由上面的指定多个验证者代 w m m U 理签名方案生成的关于消息的代理签名 则指m 定的验证者总能接受它 12 n C CC 证明 2 22 22 2 Bob AliceBob AliceBob AliceBo pwID wIDwID wIDwID wIDID p dVHm U d rHm UdHm U d srHm UQHm U Q s UHm UQQ sQ 1 11310 1 1 13110 11 1 30 11 30 1 3 Ci CC ii CC ii Ci C n IDp i nn IDIDp ii nn IDIDp ii n IDp i ID e U Ve rQr Hr d Hm e rQr H e rQr d Hm e rrQH eQHmd e UHe QHmd e UHe sQ 0 1 30 1 3 1 i Ci n p i n IDp i n ip i HmQ e UHe dHmQ e UHeQ 4 2 模拟 个验证者按以下步骤协作可以模拟产生关于n 消息的签名 m Step1 计算 1 2 i C in 0 Ci iID dHm 并将其在 n 个验证者中公开 Step2 每个通过验证 i C j e P 是否成立来检验接收到的每个 0 Cj pubID e PHm Q 的有效性 j Step3 每个随机选择 并将 i C 1 2 3 iiiq rrrZ 44 通 信 学 报第 29 卷 其广播 每个计算 i C 333 1 12 23 3 111 iii iii rrrrrr 11 22 1 31 3 32 1 1 31 1 Ci p n ID i p n ip i n i i UrQ UrQ UrrQ HHe rQ Vr Hr 显然 满足验证 并且以 123 U U U V 上生成的与代理签名者生成的代理签名是不 可区分的 所以第三方不会相信验证者所提供的 代理签名的有效性 但是每个验证者都会相信 的有效性 4 3 安全性 4 3 1 不可伪造性 定理 1 除原始签名者 Alice 授权的代理签名 者 Bob 指定的验证者外 任何人 12 n C CC 包括原始签名者 Alice 都不能伪造一个合法 的代理签名 证明 1 只有原始签名者 Alice 授权的代理签 名者 Bob 可以生成代理签名密钥 p d 提出的方案同文献 10 一样 使用了基于 Cha Cheon 体制 11 的代理密钥生成算法 文献 9 给出了 1 的证明思想 这里作简要描述 Step1 Cha Cheon 的基于身份的签名体制被 证明在随机 oracle 中 在适应性选择消息攻击和 ID 攻击下存在性是不可伪造的 在代理密钥生成 算法中 原始签名者使用 Cha Cheon 的基于身份 的签名体制对包含原始签名者和代理签名者身份 的授权书签名 根据 Cha Cheon 体制的不可 w m 伪造性可知任何不知道原始签名者私钥的人都不 能对生成一个合法的签名 w m Step2 假设原始签名者 Alice 可以产生一个 代理签名密钥 即存在一个三元组 p d wp m U d 其中 则 2 AliceBob pwIDID ds UHm UQQ Alice 可以计算 这样 2 Alcie pwID VdHm U d Alice 就可以伪造一个 Bob 对的签名 w m U V 并且这一签名可以通过下面的等式验证 2 2 Alxie Bob Bob pwID wID pubID e P Ve P dHm U d e P s UHm U Q e PUhQ 这与 Cha Cheon 的体制在适应性选择消息攻 击下是存在性不可伪造的相矛盾 Step3 由于 即的 2 Bob pwID dVHm U d p d 生成使用了代理签名者 Bob 的私钥 因此 Bvob ID d 任何第三方都不能产生代理密钥 p d 由上面三步可知只有代理签名者 Bob 可以生 成代理签名密钥 p d 2 只有具有代理签名密钥的代理签名者 p d Bob 或个指定的验证者可以生成一个有效的代理n 签名 Step1 提出的方案中的代理签名的生成中有 1 310p Vr Hr d Hm 320 1 Ci n IDp i HHe rQd Hm 和的计算都使用了代理密钥 当HV p d 为安全散列函数时 任何不具有代理密钥的 3 H p d 敌手都不能伪造一个满足验证等式 13 1 n ip i e U Ve UHeQ 的和 即不能伪造有效的代理签名HV 123 U U U V Step2 在个指定验证者协作模拟生成关于n 消息的代理签名的副本时 有m 32 1 320 1 320 1 320 1 1 31 1 1 310 1 i i i i n ip i n Cp i n Cp i n Cp i n i i n C i HHe rQ He r d HmQ He dr Q Hm Hedr Q Hm Vr Hr r Hrd Hm 和的计算都必须使用指定验证者的私钥 H V 当为安全散列函数时 任何不具有 i C d 03 HH 个指定验证者的私钥的敌手都n 1 2 Ci ID din 不能伪造一个有效的签名 123 U U U V 第 11A 期唐朝霞等 基于身份的指定多个验证者的代理签名方案 45 由 Step1 和 Step2 可知只有代理签名者 Bob 或 个指定的验证者可以生成一个有效的代理签名 n 由 1 和 2 可以证明 除代理签名者 Bob 指 定的验证者外 任何人 包括原始签 12 n C CC 名者 Alice 都不能伪造一个合法的代理签名 4 3 2 限制的可验证性 定理定理 2 只有个指定的验证者n 协作才可验证代理签名的有效性 12 n C CC 证明 在验证阶段 最后需验证等式 1 e U V 是否成立 其中 3 1 n ip i e UHeQ 是由每个指定验证者使用自己的 0 Ci iID dHm i C 私钥计算得出的 所以只有个指定的验证者协作n 才可以计算出 因此只有个指定 1 n ip i eQ n 的验证者协作才可以验证代理签名的有效性 4 3 3 提出的方案属于强指定验证者代理签名 由 4 2 节的模拟可知 指定的验证者 可以通过计算 生成一个 12 n C CC 123 U U U V 代理签名的副本 满足验证等式且与不可 区分 因此第三方不会相信指定验证者所提供的 代理签名的有效性 即方案属于强指定验证者代 理签名 5 结束语 本文对指定验证者代理签名进行扩展 提出 了首个基于身份的指定多个验证者的代理签名方 案 使得代理签名者可以指定多个不同的验证者 而只有这些指定的验证者一起可以验证代理签名 的有效性 通过对方案的分析 证明的方案满足 不可伪造性 限制的可验证性等安全性要求 并 且属于强指定验证者代理签名 参考文献 1 JAKOBSSON M SAKO K IMPALIAZZO K R Designated verifier proofs and their applications A Eurocrypt 1996 LNCS 1070 C Springer Verlag 1996 142 154 2 MAMBO M USUDA K OKAMOTO E Proxy signatures for delegating signing operation A Proc 3rd ACM Conference on Computer and Communications Security C 1996 48 57 3 MAMBO M USUDA K OKAMOTO E Proxy signatures delegation of the power to sign messages J IEICE Trans Fundam 1996 79 9 1338 1354 4 DAI J Z YANG X H DONG J X Designated receiver proxy signature scheme for electronic commerce A Proc of IEEE International Conference on Systems Man and Cybernetics C 2003 384 389 5 WANG G L Designated verifier proxy signatures for e commerce A IEEE 2004 International Conference on Multimedia and Expo ICME 2004 C Taipei Taiw