一种可证明安全的代理聚合签名方案

一种可证明安全的代理聚合签名方案 A Security-Provable Proxy Aggregate Signature Scheme 1 first-author 张青，女，教授，博士，现从事信息安全认证协议方面的研究.E-mail: 823963996@qq.com 张青，女，教授，博士，现从事信息安全认证协议方面的研究.E-mail: 823963996@qq.com 823963996@qq.com 2 1 corresp 戴阔斌, E-mail:daikb6688@163.com 戴阔斌, E-mail:daikb6688@163.com daikb6688@163.com 1 3 黄冈师范学院 计算机学院, 湖北 黄冈 438000 黄冈师范学院 计算机学院, 湖北 黄冈 438000 Computer School, Huanggang Normal University, Huanggang 438000, Hubei, China Computer School, Huanggang Normal University, Huanggang 438000, Hubei, China 中国地质大学 计算机学院, 湖北 武汉 430074 中国地质大学 计算机学院, 湖北 武汉 430074 College of Computer Science, China University of Geosciences, Wuhan 430074, Hubei, China College of Computer Science, China University of Geosciences, Wuhan 430074, Hubei, China 武汉大学 计算机学院, 湖北 武汉 430072 武汉大学 计算机学院, 湖北 武汉 430072 School of Computer, Wuhan University, Wuhan 430072, Hubei, China School of Computer, Wuhan University, Wuhan 430072, Hubei, China 通过对现有的代理聚合签名方案的分析，发现KGC(key generation conter)分发密钥均基于一个假设的安全信道，在实际应用中会有安全漏洞：假设KGC在分发密钥的过程中泄漏了私钥，则敌手可成功伪造任何消息的合法签名.本文提出了一种基于双线性对的可证明安全的代理聚合签名方案，在该方案中, 签名方案的公钥由KGC和用户共同产生，这样即使敌手在通信中获取KGC分发的私钥也不可伪造签名.在随机预言机模型下，证明了即使在对手最大限度获得相关权限的情况下，也可归约为解决CDH(Compute Diffie-Hellman)难题，并对签名方案进行了效率分析.从分析结果可以看出我们设计的方案更加安全和高效. By the analysis of existing proxy aggregate signature schemes, we find that the KGC-distributed key is based on a hypothetic secure channel, which is likely to have security holes in practical applications. If the private key is divulged during KGC key distribution, a valid signature for any information can be successfully forged. Based on bilinear pairings, this paper presents a security-provable proxy aggregate signature scheme, in which the public key is generated by KGC and the user so that the signature will not be forged even if the private key is given away during KGC key distribution. Under random oracle model, a game between the opponent and the challenger proves that the security of the presented scheme can be reduced to CDH (Compute Diffie-Hellman)problem even if the opponent obtains the maximum relevant permissions. At the same time, it's verified that the computational efficiency of the scheme is much higher than that of other schemes. 聚合签名 随机预言机 可证明安全 CDH(Compute Diffie-Hellman)问题 proxy signature random oracle provable security CDH(Compute Diffie-Hellman) problem 引言 1 数字签名算法按照设计原理可分为两大类：一类是依据RSA [ 1 1 ] 、Schnorr [ 2 2 ] 、DSS [ 3 3 ] 等密码算法进行设计的普通签名算法；另一类是像门限签名 [ 4 4 ] 、代理重签名 [ 5 5 ] 、盲签名 [ 6 6 ] 、聚合签名 [ 7 7 ] 等具有特殊功能的数字签名算法. 1996年，Mambo等 [ 8 8 , 9 9 ] 依据委托代理思想提出了一种通过委托代理来实现数字签名的签名算法.2001年，Lee等 [ 10 10 , 11 11 ] 分析了现有代理签名方案在实际应用中的安全隐患, 并指出KGC(key generation conter)存在泄露密钥的风险.2003年，Boldyreva等 [ 12 12 ] 设计了可证明安全的理论模型，通过在敌手和挑战者之间互动过程中得到的信息来分析签名方案的安全性，为后面的数字签名方案的安全性提供了新的理论分析方法. 1997年，Fiat [ 13 13 ] 首次提出对多个待签名信息实现聚合签名的数字签名方案.聚合签名可一次性对 n 个信息实现签名和验证签名，在网络传输中能得到广泛应用.聚合签名的优点引起众多学者的研究：文献[ 14 14 , 15 15 ]分别实现了对原始信息按照一定顺序进行签名和验证签名；使用证书的方式在实际应用中同样存在安全隐患，Al-Riyami等 [ 16 16 ] 提出了一种能使用无证书的聚合签名方案.目前，几种基于无证书的聚合签名方案 [ 17 17 ~ 19 19 17~19 ] 被学者设计出来，广泛应用于相关领域. 2007年，Li等 [ 20 20 ] 采用公钥加密算法来实现批量验证的聚合代理签名方案，该方案能对代理签名的信息进行一次性验证.2011年，王勇兵等 [ 21 21 ] 提出了一个基于身份的代理聚合签名方案.随后陈群山等在文献[ 22 22 ]中证明了王勇兵等 [ 21 21 ] 设计的方案不能防止代理签名者的否认攻击，并在此基础上提出了一种新的代理聚合签名方案，该方案有效解决了否认攻击的问题.但我们对文献[ 22 22 ]的安全性进行详细分析后发现该方案与其他方案一样均存在一个假设的安全信道.针对该安全漏洞，本文提出了一种基于双线性对的可证明安全的代理聚合签名方案，通过改变产生私钥的方法，实现了即使私钥在密钥分发过程中被泄露也无法伪造签名功能. 预备知识 1 双线性对 2 令双线性对映射 e : G 1 × G 1 → G 2 ，其中： G 1 ， G 2 为 q 阶循环加法和循环乘法群， P 为生成元. G 1 ， G 2 在离散对数上有如下性质： 1) 双线性：对所有的 P , Q ∈ G 1 ， a , b ∈ℤ， e ( aP , bQ )= e ( P , Q ) ab ； 2) 非退化：∃ P , Q ∈ G 1 使得 e ( P , Q )≠1； 3) 可计算性：∀ P , Q ∈ G 1 ，存在一个有效的算法来计算 e ( P , Q ). 数学困难问题 2 定义1     Compute Diffie-Hellman (CDH)问题：给定( P , aP , bP )∈ G 1 ， a , b ∈ Z q * ，计算 abP ∈ G 1 是困难的. 定义2     Bilinear Diffie-Hellman问题：∃ a , b , c ∈ Z q * ，由( P , aP , bP , cP )计算 e ( P , P ) ab c 是困难的. 定义3     Discrete Logarithm Problem问题，∀ Q , P ∈ G 1 ，求满足等式 Q = nP 的整数 n ∈ Z q * 是困难的. 随机预言机模型 2 随机预言机(random oracle) [ 23 23 ] 是一种从Hash函数中抽象出来的计算模型.在随机预言机模型中，定义了私钥、公钥和秘密值等多种询问机制，与之对应的有不同的响应机制.攻击者向随机预言机发起相关询问，响应机制反馈的散列值可用于伪造签名，可用攻击者的询问能力来度量计算已知难题的能力. 安全模型 2 在随机预言机模型下，假设存在敌手( A 1 或 A 2 )和挑战者( C 1 或 C 2 )，签名方案的安全性可通过在游戏1和游戏2中能否获胜来证明.假设敌手 A 1 无法获取系统主密钥的相关资源，但能替换相关代理签名者的公钥密码信息；敌手 A 2 可获取系统主密钥的相关资源，但无法替换相关代理签名者的公钥密码信息. 定义4     如果敌手 A 1 和 A 2 分别在游戏1和游戏2中获得成功的概率可忽略不计，则该聚合代理签名方案不可伪造. 游戏1 Step 1     设置代理聚合签名系统的相关参数params，挑战者 C 1 保存代理聚合签名系统主密钥 s ，并将代理聚合签名系统的相关参数params发送给敌手 A 1 . Step 2     敌手 A 1 执行以下询问： 1) Hash询问： A 1 对任意Hash预言机进行Hash值询问. 2) 私钥询问： A 1 询问用户 P i 的私钥， C 1 计算私钥 d ID i 并发送给 A 1 . 3) 公钥询问： A 1 询问用户 P i 的公钥， C 1 计算公钥 U i 并发送给 A 1 . 4) 公钥替换询问： A 1 能任意替换用户 P i 公钥.若公钥已替换，则停止询问. 5) 秘密值询问： A 1 询问用户 P i 的秘密值， C 1 将用户 P i 的秘密值 r i 发送给 A 1 . 6) 代理签名询问： A 1 询问用户 P i 的身份ID i 、公钥 U i 和消息 m i ， C 1 执行代理签名算法并将签名发送给 A 1 . Step 3     签名伪造: A 1 伪造出一个代理签名者 P i ( i =1, 2, …, n )对消息 m * 的有效代理聚合签名 σ * =( U , V )，若 A 1 未对某个 P i 的公钥和私钥进行询问，也未对 P i 对消息 m * 的签名进行询问，且 σ * =( U , V )能通过消息检验者的检验，则 A 1 赢得游戏. 游戏2 Step 1     设置代理聚合签名系统参数params，挑战者 C 2 将代理聚合签名系统主密钥 s 保存，并将代理聚合签名系统参数params发送给敌手 A 2 . Step 2     敌手 A 2 执行以下询问： 1) Hash询问： A 2 任意Hash预言机进行Hash值询问. 2) 私钥询问： A 2 询问用户 P i 的私钥， C 2 计算私钥 d ID i 并发送给 A 2 . 3) 公钥询问： A 2 询问用户 P i 的公钥， C 2 计算公钥 U i 并发送给 A 2 . 4) 秘密值询问： A 2 询问用户 P i 的秘密值， C 2 将用户 P i 的秘密值 r i 发送给 A 2 . 5) 代理签名询问： A 2 询问用户 P i 的身份ID i 、公钥 U i 和消息 m i ， C 2 运行代理签名算法，得到签名并返回给 A 2 . Step 3     签名伪造: A 2 伪造出一个代理签名者 P i ( i =1, 2, …, n )对消息 m * 的有效的代理聚合签名 σ * =( U , V ), 若 A 2 未对某个 P i 的公钥和私钥进行询问，也未对 P i 对消息 m * 的签名进行询问，且 σ * =( U , V )能通过消息检验者的检验，则 A 2 赢得游戏. 相关方案分析 1 文献[ 22 22 ]代理聚合签名方案回顾 2 1) 参数设置.KGC选择 k 和素数 q 作为系统参数， q > 2 k ，KGC选择 q 阶循环群 G 1 和 G 2 ， P 为群 G 1 和 G 2 的生成元，且满足映射 e : G 1 × G 1 → G 2 ，系统用到的Hash函数为 H 1 , H 2 ， H 3 ；KGC选择主密钥∀ s ∈ Z q * 并计算公开密钥 P pub = sP ，公开系统参数params={ G 1 , G 2 , e , q , P , P pub , H 1 , H 2 , H 3 }. 2) 密钥生成阶段.原始签名者 O 和代理签名者 P i ( i =1, 2, …, n )分别将各自的身份信息ID 0 和ID i 发送给KGC.KGC计算 Q ID 0 = H 1 (ID 0 ), d ID 0 = sQ ID 0 , Q ID i = H 1 (ID i ), d ID i = sQ ID i , 其中 i =1, 2, …, n ，并将私钥 d ID 0 和 d ID i ( i =1, 2, …, n )分别发送 O 和 P i . 3) 授权代理阶段. ① 选择∀ r 0 ∈ Z q * , 计算 U 0 = r 0 Q ID 0 ， h 0 = H 2 ( m w , U 0 )， V 0 =( h 0 + r 0 ) d ID 0 ，原始签名者将签名 σ 0 =( U 0 , V 0 )和 m w 发送给 P i . ② P i 收到 σ 0 和 m w ，计算 h 0 = H 2 ( m w , U 0 ), Q 0 = U 0 + h 0 Q ID 0 ，验证 e ( P , V 0 )= e ( P pub , Q 0 )是否成立.若成立，则计算授权密钥 d 0 = H 2 ( m w , V 0 ) Q ID 0 ，并公布 D = H 2 ( m w , V 0 ) P . 4) 代理签名阶段. P i 选择∀ r i ∈ Z q * ，并计算 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458754&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458754&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458754&type=middle 发送 σ i =( m w , U i , V i )给聚合者. 5) 单个代理签名验证.计算 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458807&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458807&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458807&type=middle , h i = H 2 ( m w , m i , U )，签名聚合者验证 e ( P , V i )= e ( P pub U i + h i Q ID i ) e ( D , Q ID i ) n －1 能否成立.若成立，则验证通过. 方案的安全性分析 2 文献[ 21 21 ]和[ 22 22 ]同样存在假设的安全信道，如果攻击者 A 攻击KGC通信信道并获得原签者的密钥 d ID 0 ，则可伪造代理签名.过程如下： ① 攻击者 A 选择∀ r 0 ∈ Z q * ， U 0 = r 0 Q ID 0 ， h 0 = H 2 ( m w , U 0 ), V 0 =( h 0 + r 0 ) d ID 0 , 将签名 σ 0 =( U 0 , V 0 )和 m w 发给代理签名者 P i . ② 代理签名者收到( σ 0 , m w )，计算 h 0 = H 2 ( m w , U 0 )， Q 0 = U 0 + h 0 Q ID i ，验证等式： http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458759&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458759&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458759&type=middle 通过验证， P i 接受攻击者 A 的伪造授权，计算授权密钥 d 0 = H 2 ( m w , V 0 ) Q ID 0 ，并公布 D = H 2 ( m w , V 0 ) P ，选择∀ r i ∈ Z q * ，计算并广播 U i = r i Q ID i , h 0 = H 2 ( m w , U 0 ), http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458807&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458807&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458807&type=middle , h i = H 2 ( m w , m i , U ), V i =( r i + h i ) d ID i + n －1 H 2 ( m w , V 0 ) Q ID i 发送 σ i =( m w , U i , V i )给签名聚合者. ③ 聚合者验证等式： http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458763&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458763&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458763&type=middle 通过验证，聚合者接收代理签名.因此，文献[ 22 22 ]的方案不能抵抗KGC攻击. 本文的方案 1 本文的签名方案中，公钥由KGC和用户共同产生，实现了即使攻击者在通信信道上获取原始签名者的密钥，也无法伪造签名的功能. 具体方案 2 1) 参数设置.KGC选择代理聚合签名系统的参数 k 和素数 q ， q > 2 k ，KGC选择 q 阶循环群 G 1 和 G 2 ，且 P 为 G 1 和 G 2 的生成元，构造双线性映射 e : G 1 × G 1 → G 2 ，系统用到的Hash函数为 H 1 , H 2 ， H 3 ；KGC选择主密钥∀ s ∈ Z q * 并计算公开密钥 P pub = sP ，公开系统参数params={ G 1 , G 2 , e , q , P , P pub , H 1 , H 2 , H 3 }. 2) 密钥生成阶段.原始签名者 O 和代理签名者 P i ( i =1, 2, …, n )分别将各自的身份信息ID 0 和ID i 发送给KGC，KGC通过 Q i = H 1 (ID i ), d i = sQ i ( i =0, 1, …, n )，计算相应的私钥 d 0 和 d i ( i =1, 2, …, n )并返回给 O 和 P i .原始签名者选择∀ x 0 ∈ Z q * ，通过 z = x 0 Q 0 ，( Q 0 , z )来计算原始签名者的公钥；代理签名者 P i 选择∀ r i ∈ Z q * ，通过 C i = r i Q i ，( Q i , C i )来计算代理签名者的公钥. 3) 授权代理阶段.原始签名者将( m w , U 0 , V 0 )发送给代理签名者 P i ( i =1, 2, …, n )， U 0 = x 0 P ， h 0 = H 2 (ID 0 , m w , U 0 )， V 0 = d 0 h 0 + x 0 z . n 份待签消息 m =( m 1 , m 2 , …, m n )由KGC别发送给代理签名者 P i . 4) 代理签名阶段.计算 h 0 = H 2 (ID 0 , m w , U 0 )， Q = H 1 ( P pub )，代理签名者验证等式 e ( P , V i )= e ( P pub , h 0 Q 0 ) e ( U 0 , z )是否成立.如果成立，则选择∀ i ∈ Z q * ，并计算 X i = V 0 + d i h 0 ， R i = r i P ， w i = h 3 ( m w , m i , R i , ID i ), S i =(( w i + C i ) r i + X i ) Q ，代理签名者将代理签名信息( S i , R i , m w , U 0 )发送给签名聚合者. 5) 签名聚合阶段.签名聚合者验证 e ( P , S i )= e ( Q , h 0 P pub ( Q 0 + Q i )+ zU 0 + R i ( w i + C i ))是否成立，如果 n 份验证均成立，则( S , R , m w , U 0 )为消息 m 的聚合签名，其中 h 0 = H 2 (ID 0 , m w , U 0 )， Q = H 1 ( P pub )， http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458810&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458810&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458810&type=middle ， http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458814&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458814&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458814&type=middle . 6) 聚合签名验证阶段.签名验证者验证 e ( P , S i )= e ( Q , h 0 P pub http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458840&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458840&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458840&type=middle ( Q 0 + Q i )+ nzU 0 + http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458840&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458840&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458840&type=middle R i ( w i + C i ))是否成立.若验证成功，则签名( S , R )有效，否则是无效签名，其中 h 0 = H 2 (ID 0 , m w , U 0 ), Q = H 1 ( P pub ), w i = h 3 ( m w , m i , R i , ID i ). 正确性分析 2 1) 代理签名者通过验证 e ( P , V i )= e ( P pub , h 0 Q 0 ) e ( U 0 , z )能否成立来验证授权代理是否有效. 证 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458766&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458766&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458766&type=middle 2) 签名聚合者通过验证 e ( P , S i )= e ( Q , h 0 P pub ( Q 0 + Q i )+ zU 0 + R i ( w i + C i ))能否成立来验证代理签名是否有效. 证 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458769&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458769&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458769&type=middle 3) 聚合签名的验证 证 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458772&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458772&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458772&type=middle 安全性分析 2 在随机预言机模型下，证明本方案在敌手 A 1 和 A 2 攻击下是不可伪造的. 定理1     假设敌手 A 1 在游戏1中可实现在多项式 t 时间内完成如下询问：3次Hash函数询问、 q d 次部分私钥询问、 q p 次公钥询问、 q k 次秘密值询问、 q r 次公钥替换询问和 q s 次签名询问，若敌手 A 1 能在游戏1中获胜，则挑战者 C 1 能在多项式 t 时间内以不可忽略的概率 ζ 解决CDH问题，即给定( aP , bP )能计算出 abP . 证      C 1 选择聚合签名方案的系统参数, 设置 P pub = aP ，把方案参数params={ G 1 , G 2 , e , q , P , P pub , H 1 , H 2 , H 3 }发给敌手 A 1 ，记录表 L i ( i =1, 2, 3)对应着 H i ( i =1, 2, 3)的询问， L kpar 对应着部分私钥的询问， L ks 对应着秘密值的询问. 1) H i 询问：记录表 L 1 包含(ID j , Q ID j )或( P pub , Q )，其中 j ∈(0, 1, …, n ).当 A 1 对ID i 进行Hash函数 H i 询问时， C 1 查询记录表 L 1 ，若能找到满足要求的ID i 项，则将对应的 Q ID i 作为 A 1 的询问结果并回复；若未找到， C 1 选择∀ Q ID i ∈ Z q * ，把(ID j , Q ID j )写入 L 1 记录表中，将 Q ID i 回复给 A 1 .当 A 1 询问 P pub 时， C 1 查询记录表 L 1 ，若查询到 P pub 项，将对应 Q 作为 A 1 的回复，否则 C 1 选择 Q = bP ，将( P pub , Q )写入 L 1 记录表中，将 Q 作为 A 1 的回复. 2) H 2 询问：记录表 L 2 包含(ID 0 , m w , U 0 , h 0 )，当 A 1 对ID 0 进行 H 2 询问时， C 1 查询记录表 L 2 ，若查询到了ID 0 项，将对应的 h 0 作为 A 1 的回复；若未找到ID 0 项， C 1 选择∀ h 0 ∈ Z q * ，∀ U 0 ∈ Z q * ，把(ID 0 , m w , U 0 , h 0 )写入 L 2 记录表，并将 h 0 作为 A 1 的回复. 3) H 3 询问：记录表 L 3 包含( m w , m j , R j , ID j , w j , ζ j )，其中 j ∈(0, 1, …, n ).当 A 1 询问( m w , m j , R j , ID j )时， C 1 的响应如下： ① 查询记录表 L 3 ，若查询到了( m w , m i , R i , ID i , w i , ζ i )项，则将对应的 w i 作为 A 1 的回复. ② C 1 选择∀ ζ i ∈{0, 1}，且满足Pr[ ζ i =1]= δ , Pr[ ζ i =0]=1－ δ ，其中Pr[ ζ =0]表示 ζ =0发生的概率，Pr[ ζ =1]表示 ζ =1发生的概率.Ⅰ：若 ζ =0， C 1 选择∀ w i ∈ Z q * ，Ⅱ：若 ζ =1， C 1 计算 w i =－( U 0 Z + C i R i )/ R i . ③ 将( m w , m i , R i , ID i , w i , ζ i )加入记录表 L 3 ，并将 w i 发送给 A 1 . 4) 部分私钥询问：记录表 L kpar 包含(ID j , d j )其中 j ∈(0, 1, …, n )， A 1 询问ID i 的部分私钥， C 1 的响应如下： ① 查询记录表 L kpar 中存在(ID i , d i )项，则返回对应 d i 给 A 1 . ② 记录表 L kpar 中未找到(ID i , d i )项， C 1 查询记录表 L 3 ，若记录表中对应的 ζ i =1， C 1 选择∀ d i ∈ Z q * ，将(ID i , d i )加入 L kpar 记录表，并发送 d i 给 A 1 ；若记录表中对应的 ζ i =0，则 C 1 选择放弃，并终止. 5) 秘密值询问：记录表 L ks 包含(ID i , r i , C i )其中 j ∈{0, 1, …, n }， A 1 询问ID i 的秘密值， C 1 查询记录表 L ks ，若在记录表 L ks 中找到(ID i , r i , C i )项，则把对应的 r i 作为 A 1 的回复；否则， C 1 选择∀ r i ∈ Z q * ，计算 C i = r i P ，将(ID i , r i , C i )加入 L ks 记录表，并发送 r i 给 A 1 . 6) 公钥询问：当 A 1 询问ID i 的公钥时， C 1 查询记录表 L ks ，若存在(ID i , r i , C i )项，则发送对应 C 1 给 A 1 ；若不存在，则 C 1 选择∀ r i ∈ Z q * ，计算 C i = r i P ，将(ID i , r i , C i )加入 L ks 记录表，并返回 C 1 给 A 1 . 7) 公钥替换询问：当 A 1 对(ID i , C i * )进行公钥替换询问时， C 1 查询更新记录表 L ks ，将(ID i , r i , C i )替换为(ID i , ∅, C i * ). 8) 签名询问：当 A 1 对(ID i , m i )进行签名询问时， C 1 查询记录表 L 1 得(ID i , Q ID i )和( P pub , Q )，查询记录表 L 2 得到(ID 0 , m w , U 0 , h 0 )，查询记录表 L 3 得到( m w , m i , R i , ID i , w i , ζ i )，查询记录表 L kpar 得到(ID i , d i )，查询记录表 L ks 得到(ID i , r i , C i )，有两种情况： ① ζ i =0， C 1 选择放弃，并停止. ② ζ i =1， C 1 选择计算 S i =( w r r r + d 0 h 0 + x 0 Z + d i h 0 + r i C i ) Q . 9) 签名伪造： A 1 发送对{ID i * , C i * , m i * }( n 个用户的身份、公钥及消息集合)伪造的代理聚合签名( S * , R * , m w , U 0 )给挑战者 C 1 ( i =1, 2, …, n ). C 1 查询记录表 L 1 、 L 2 、 L 3 、 L kpar 和 L ks ，若对于 L 3 中的 n 条记录( m w , m i * , R i * , ID i * , w i * , ζ i * )，全部 ζ i =0，则 C 1 选择放弃，并停止；存在至少一个 ζ i =1，则继续，不妨设 i = k ( k ∈{1, 2, …, n })时 ζ i =1，由验证式： e ( P , S * )= e ( Q , h 0 P pub http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458840&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458840&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458840&type=middle ( Q 0 * + Q i * )+ nzU 0 + http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458840&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458840&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458840&type=middle R i * ( w i * + C i * ))可得 i = k 时有： e ( P , S k * )= e ( Q , h 0 P pub ( Q 0 + Q k * )+ zU 0 + R k * ( w k * + C k * ))，此时 w k * =－( U 0 z + C k * R k * )/ R k * ，代入等式有： e ( P , S k * )= e ( Q , h 0 P pub ( Q 0 + Q k * ))，由 Q = bP , P pub = ab ，有 e ( P , S k * )= e ( bP , h 0 aP ( Q 0 + Q k * ))⇒ abP = S k * /( h 0 ( Q 0 + Q k * ))，因此 A 1 若能伪造有效的代理聚合签名，则 C 1 能解决CDH难题. 10) 概率分析：定义如下事件 E 1 :部分私钥询问，返回成功. E 2 : A 1 能伪造一个有效的代理聚合签名. E 3 :在事件 E 2 发生的前提下，存在至少一个 ζ i =1. 三个事件同时发生，则 C 1 能成功破解CDH难题. C 1 成功的概率为： http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458776&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458776&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458776&type=middle 当 ζ i =1时，最多可进行 q d 次部分私钥询问，故Pr( E 1 )≥(Pr[ ζ i =1]) q d ≥ δ q d ，且敌手 A 1 在游戏1中以不可忽略的Pr( E 2 )≥ ζ 概率获胜，即当 ζ k =0( k ∈{1, 2, …, n })， ζ i =1( i ∈{1, 2, …, k －1, k +1, …, n })的概率为 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458780&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458780&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458780&type=middle 如果 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458785&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458785&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458785&type=middle 则 C 1 成功解决CDH难题： http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458787&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458787&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458787&type=middle 当 δ =1－1/ q d + n 时 ζ 取到最大值，即 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458791&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458791&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458791&type=middle 定理2     若敌手 A 2 在游戏2中在有效的多项式时间 t 内能完成如下询问：3次Hash函数询问、 q d 次部分私钥询问、 q p 次公钥询问、 q k 次秘密值询问、 q r 次公钥替换询问和 q s 次签名询问，若敌手 A 2 赢得游戏2的概率 ζ 是不可忽略的，则 C 2 在多项式 t 时间内成功解决CDH难题的概率 ζ 也是不可忽略的，即能有效地伪造签名. 证      C 2 选择聚合签名方案的系统参数, 选择∀ s ∈ Z q * ，计算 P pub = sP ，将系统参数params={ G 1 , G 2 , e , q , P , P pub , H 1 , H 2 , H 3 }和 s 发送给 A 2 ，记录表 L i ( i =1, 2, 3)对应 H i ( i =1, 2, 3)的询问， L kpar 对应部分私钥的询问， L ks 对应秘密值的询问. 1) H 1 询问:记录表 L 1 包含(ID j , Q ID j )其中 j ∈{0, 1, …, n }或( P pub , Q ). A 2 对ID i 进行 H 1 询问， C 2 查询记录表 L 1 ，若查询到ID i 项，则把对应的 Q ID i 回复给 A 2 ，没有ID i 项， C 2 选择∀ Q ID i ∈ Z q * ，将(ID i , Q ID i )写入 L 1 记录表，将 Q ID i 作为 A 2 的回复.当 A 2 询问 P pub 时， C 2 先查询记录表 L 1 ，若查询到 P pub 项，则回复给 A 2 对应的 Q ，否则 C 2 设置 Q = bP ，把( P pub , Q )写入 L 1 记录表中，并将 Q 作为 A 2 的回复. 2) H 2 询问：记录表 L 2 包含(ID 0 , m w , U 0 , h 0 )， A 2 对ID 0 进行 H 2 询问， C 2 查询记录表 L 2 ，若查询到ID 0 项，把对应的 h 0 作为 A 2 的回复；没有ID 0 项， C 2 选择∀ h 0 ∈ Z q * ，设置 U 0 = aP ，把(ID 0 , m w , U 0 , h 0 )写入 L 2 记录表中，并将 h 0 作为 A 2 的回复. 3) H 3 询问：记录表 L 3 包含( m w , m i , R i , ID i , w i , ζ i )，其中 i ∈{0, 1, …, n }.当 A 2 询问( m w , m i , R i , ID i )时， C 2 的响应如下： ① 查询记录表 L 3 ，查询到( m w , m i , R i , ID i , w i , ζ i )项，回复 A 2 对应的 w i . ② C 2 选择∀ Q ID i ∈{0, 1}，且满足Pr[ ζ i =1]= δ , Pr[ ζ i =0]=1－ δ ，其中Pr[ ζ =0]表示 ζ =0发生的概率.Pr[ ζ =1]表示 ζ =1发生的概率，Ⅰ：若 ζ =0， C 2 选择∀ w i ∈ Z q * ，Ⅱ：若 ζ =1， C 2 计算 w k * =－( h 0 sPQ k * + C k * R k )/ R k . ③ C 2 把( m w , m i , R i , ID i , w i , ζ i )加入记录表 L 3 ，并将 w i 发送给 A 2 . 4) 部分私钥询问：记录表 L kpar 包含(ID j , d j )，其中 j ∈{0, 1, …, n }， A 2 询问ID i 的部分私钥， C 2 的响应如下： ① 查询记录表 L kpar 中存在(ID i , d i )项，则返回对应 d i 给 A 2 . ② 记录表 L kpar 中没有(ID i , d i )项，则 C 2 查询记录表 L 3 ，若检测到(ID i , d i )所对应的 ζ i =1，则 C 2 选择∀ d i ∈ Z q * ，将(ID i , d i )加入 L kpar 记录表，并发送 d i 给 A 2 ；若记录表中对应的 ζ i =0，则 C 2 选择放弃，并终止. 5) 秘密值询问：记录表 L ks 包含(ID j , r j , C j )，其中 j ∈{0, 1, …, n }，当 A 2 询问ID i 的秘密值， C 2 查询记录表 L ks ，查询到(ID i , r i , C i )项，则回复 A 2 对应的 r i 值；否则， C 2 选择∀ r i ∈ Z q * ，计算 C i = r i P ，将(ID i , r i , C i )加入 L ks 记录表，并发送 r i 给 A 2 . 6) 公钥询问：当 A 2 询问ID i 的公钥时， C 2 查询记录表 L ks ，查询到(ID i , r i , C i )项，则回复 A 2 对应的 C i ；否则， C 2 选择∀ r i ∈ Z q * ，计算 C i = r i P ，将(ID i , r i , C i )加入 L ks 记录表，并发送 C i 给 A 2 . 7) 签名询问：当 A 2 对(ID i , m i )进行签名询问时， C 2 查询记录表 L 1 得到(ID i , Q ID i )和( P pub , Q )，查询记录表 L 2 得到(ID 0 , m w , U 0 , h 0 )，查询记录表 L 3 得到( m w , m i , R i , ID i , w i , ζ i )，查询记录表 L kpar 得到(ID i , d i )，查询记录表 L ks 得到(ID i , r i , C i )，有两种情况： ① ζ i =0， C 2 选择放弃，并停止. ② ζ i =1， C 2 选择计算 S i =( w i r i + d 0 h 0 + x 0 z + d i h 0 + r i C i ) Q . 8)签名伪造： A 2 输出伪造 n 个用户{ID i * , C i * , m i * }( i =1, 2, …, n )的代理聚合签名( S * , R * , m w , U 0 )， C 2 查询记录表 L 1 、 L 2 、 L 3 、 L kpar 和 L ks ，若所有 L 3 中的 n 条记录( m w , m i * , R i * , ID i * , w i * , ζ i * )的 ζ i =0，则伪造不成功；若至少有一个 ζ i =1，且 i = k ( k ∈{1, 2, …, n })时， e ( P , S * )= e ( Q , h 0 P pub http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458840&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458840&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458840&type=middle ( Q 0 * + Q i * )+ nzU 0 + http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458840&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458840&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458840&type=middle R i * ( w i * + C i * ))可得： e ( P , S k * )= e ( Q , h 0 P pub ( Q 0 + Q k * )+ zU 0 + R k * ( w k * + C k * ))，把 w k * =－( h 0 sPQ k * + C k * R k )/ R k ，代入等式有： e ( P , S k * )= e ( Q , h 0 sPQ 0 + zU 0 )，由 Q = bP ， U 0 = aP ，得： e ( P , S k * )= e ( bP , h 0 sPQ 0 + aPz )⇒ abP =( S k * － h 0 bsPQ 0 )/ z ，因此当 A 2 能成功伪造一个有效的签名，则 C 2 能在有效时间里成功解决CDH难题. 9) 概率分析：用定理1中的分析方法可推导出 C 2 解决CDH难题的概率为： http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458795&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458795&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458795&type=middle 通过定理1与定理2分析可知，挑战者 C 1 与 C 2 在多项式时间 t 内，能以不可忽略的概率 ζ 破解CDH难题是不可能的.因此在该随机预言机模型下，该签名方案是不可伪造的. 效率分析 2 代理聚合签名方案会涉及到加法、乘法、Hash函数和双线性对计算.加法运算和Hash函数运算的时间远小于双线性对运算和乘法运算时间，本文忽略其运算时间对算法效率的影响，为了便于分析，假设代理签名者的数量为 n ，双线性计算为B，群 G 1 的乘法计算为M. 由 表 1 表 1 可知，与文献[ 22 22 , 24 24 ~ 26 26 24~26 ]中的方案相比较，本文方案各阶段的线性对运算次数最少.文献[ 22 22 ]中的方案在乘法运算上优于本方案，但在实际应用中是不安全的. 方案 签名 签名聚合 签名验证 文献[ 24 24 ]方案 4M 3 n M+5B 3 n M+5B 文献[ 25 25 ]方案 3M 1 n M+3B 2 n M+3B 文献[ 26 26 ]方案 4M 3 n M+5B 3 n M+5B 文献[ 22 22 ]方案 3M 2 n M+4B 2 n M+4B 本文方案 4M 3 n M+2B 3 n M+2B 结论 1 代理聚合签名在网络通信中有广泛的应用前景，通过分析发现现有代理聚合签名方案在实际中存在私钥易泄露安全隐患.本文提出的代理聚合签名方案改进了私钥产生方法，将私钥由KGC单方面产生改进为KGC和用户共同产生，使得KGC在分发私钥的过程中即使泄露也无法计算出整个私钥，也不能伪造签名.在随机预言机模型下，证明该方案的安全性可以归约为解决CDH难题，通过计算效率分析，验证了该方案在计算效率上更高效. 参考文献 RIVEST R L, SHAMIR A, ADLEMAN L. A method for obtaining digital signatures and public-key cryptosystems[J]. Communications of the ACM , 1978, 26 (2):96-99.DOI: 10.1145/359340.359342. SCHNORR C P. Efficient identification and signatures for smart cards[C]// Advances in Cryptology-EUROCRYPT '89. Berlin: Springer-Verlag, 1989: 688-689.DOI: 10.1007/0-387-34805-0_22 http://dx.doi.org/10.1007/0-387-34805-0_22 . GALLAGHER P. Digital signature standard (DSS)[J]. Federal Information Processing Standards Publication , 2000, 25 :186-200. DESMEDT Y, FRANKEL Y. Shared generation of authenticators and signatures[C]// Advances in Cryptology-CRYPTO '91(LNCS 576). Berlin: Springer-Verlag, 1992: 457-469.DOI: 10.1007/3-540-46766-1_37 http://dx.doi.org/10.1007/3-540-46766-1_37 . BLAZE M, BLEUMER G, STRAUSS M. Divertible protocols and atomic proxy cryptography[C]// International Conference on the Theory and Applications of Cryptographic Techniques . Berlin: Springer-Verlag, 1998: 127-144.DOI: 10.1007/bfb0054122 http://dx.doi.org/10.1007/bfb0054122 . CHAUM D. Blind Signatures for Untraceable Payments[DB/OL].[2017-02-03] . http: //sceweb.sce. uhcl.edu/yang/teaching/csci5234WebSecurityFall2011/Chaum-blind-signatures.PDF http: //sceweb.sce. uhcl.edu/yang/teaching/csci5234WebSecurityFall2011/Chaum-blind-signatures.PDF . DOI: 10.1007/978-1-4757-0602-4_18 http://dx.doi.org/10.1007/978-1-4757-0602-4_18 . BONEH D, GENTRY C, LYNN B, et al . Aggregate and Verifiably Encrypted Signatures from Bilinear Maps[DB/OL].[2017-07-12] . http://crypto.stanford.edu/~dabo/papers/aggreg.pdf http://crypto.stanford.edu/~dabo/papers/aggreg.pdf .DOI: 10.1007/ 3-540-39200-9_26 http://dx.doi.org/10.1007/3-540-39200-9_26 . MAMBO M, USUDA K, OKAMOTO E. Proxy signatures for delegating signing operation[C]// ACM Conference on Computer and Communications Security . New York: ACM Press, 1996: 48-57.DOI: 10.1145/238168.238185 http://dx.doi.org/10.1145/238168.238185 . MAMBO M, USUDA K, OKAMOTO E. Proxy signatures: Delegation of the power to sign messages[J]. Ieice Trans Fundamentals A , 1996, 79 (9):1338-1354. LEE B, KIM H, KIM K. Strong proxy signature and its applications[C]// The 2001 Symposium on Cryptography and Information Security . Heidelberg: Springer-Verlag, 2001: 23-26. LEE B, KIM H, KIM K. Secure Mobile Agent Using Strong Non-designated Proxy Signature[C]// Information Security and Privacy ( LNCS 2119 ).Berlin : Springer-Verlag, 2001: 474-486.DOI: 10.1007/3-540-47719-5_37 http://dx.doi.org/10.1007/3-540-47719-5_37 . BOLDYREVA A, PALACIO A, WARINSCHI B. Secure proxy signature schemes for delegation of signing rights[J]. Journal of Cryptology , 2012, 25 (1):57-115.DOI: 10.1007/s00145-010-9082-x. FIAT A. Batch RSA[J]. Journal of Cryptology , 1997, 10 (2):75-88.DOI: 10.1007/s001459900021. LYSYANSKAYA A, MICALI S, REYZIN L, et al . Sequential aggregate signatures from trapdoor permutations[C]// Advances in Cryptology-EUROCRYPT(LNCS 3027). Berlin: Springer-Verlag, 2004: 74-90. DOI: 10.1007/978-3-540-24676-3_5 http://dx.doi.org/10.1007/978-3-540-24676-3_5 . LIU J K, BAEK J, ZHOU J. Certificate-based sequential aggregate signature[C]// ACM Conference on Wireless Network Security, WISEC 2009. New York: ACM Press, 2009: 21-28.DOI: 10.1145/1514274.1514278 http://dx.doi.org/10.1145/1514274.1514278 . AL-RIYAMI S S, PATERSON K G. Certificateless Public Key Cryptography[DB/OL].[2017-06-12] . https://eprint.iacr.org/2003/126.pdf https://eprint.iacr.org/2003/126.pdf . GONG Z, LONG Y, HONG X, et al . Two certificateless aggregate signatures from bilinear maps[J]. Journal of Information Science & Engineering , 2007, 26 (6):2093-2106.DOI: 10.1109/snpd.2007.132. ZHANG L, ZHANG F. A new certificateless aggregate signature scheme[J]. Computer Communications , 2009, 32 (6):1079-1085.DOI: 10.1016/j.comcom.2008.12.042. ZHANG L, QIN B, WU Q, et al . Efficient many-to-one authentication with certificateless aggregate signatures[J]. Computer Networks the International Journal of Computer & Telecommunications Networking , 2010, 54 (14): 2482-2491.DOI: 10.1016/j.comnet.2010.04.008. LI J, KIM K, ZHANG F, et al . Aggregate proxy signature and verifiably encrypted proxy signature[C]// International Conference on Provable Security . Berlin: Springer-Verlag, 2007: 208-217.DOI: 10.1007/978-3-540-75670-5_15 http://dx.doi.org/10.1007/978-3-540-75670-5_15 . 王勇兵, 卢晓杰, 张建中.一种基于身份的代理聚合签名方案[J].济南大学学报(自然科学版), 2011, 25 (3): 301-304.DOI:10.3969/j.issn.1671-3559.2011.03.019. WANG Y B, LU X J, ZHANG J Z.An Identity-base proxy aggregate signature scheme[J]. Journal of University of Jinan ( Science and Technology) , 2011, 25 (3): 301-304. DOI:10.3969/j.issn.1671-3559.2011.03.019(Ch). 陈群山, 黄振杰, 郝艳华, 等.基于身份的代理聚合签名方案的分析与改进[J].济南大学学报(自然科学版), 2014, 28 (3):204-208.DOI:10.13349 /j.cnki.Jdxbn.2014.03.012. CHEN Q S, HUANG Z J, HAO Y H, et al . Analysis and modification of identity-based proxy aggregate signature scheme[J]. Journal of University of Jinan (Science and Technology) , 2014, 28 (3):204-208.DOI:10.13349 /j.cnki.Jdxbn.2014.03.012(Ch). Bellare M, Rogaway P. Random oracles are practical: A paradigm for designing efficient protocols[C]// ACM Conference on Computer and Communications Security . New York: ACM, 1993: 62-73.DOI: 10.1145/168588.168596 http://dx.doi.org/10.1145/168588.168596 . 喻琇瑛, 何大可.基于双线性对的聚合代理签名[J].中南大学学报(自然科学版), 2015, 46 (12): 4535-4541.DOI:10.11817/j.issn.1672-7207.2015.12.021. YU X Y, HE D K. A certificate-based aggregate proxy signature scheme[J]. Journal of Central South University (Science and Technology) , 2015, 46 (12):4534-4541. DOI:10.11817/j.issn.1672-7207.2015.12.021(Ch). 陈群山, 黄振杰, 黄茹芬.一个新的基于身份的代理聚合签名方案[J].闽南师范大学学报(自然科学版), 2015, 28 (4):34-40.DOI:10.3969/j.issn.1008-7826.2015.04.005. CHEN Q S, HUANG Z J, HUANG R F. A new id-based proxy aggregate signature scheme[J]. Journal of Minnan Normal University(Natural Science) , 2015, 28 (4):34-40. DOI:10.3969/j.issn.1008-7826.2015.04.005(Ch). 左黎明, 郭红丽, 张婷婷, 等.改进的基于证书的聚合代理签名方案[J].计算机应用, 2016, 36 (10):2758-2761.DOI:10.11772/j.issn.1001-9081.2016.10.2758. ZUO L M, GUO H L, ZHANG T T, et al . Improved certificate-based aggregate proxy signature scheme[J]. Journal of Computer Applications , 2016, 36 (10): 2758-2761. DOI:10.11772/j.issn.1001-9081.2016.10.2758(Ch). 10.14188/j.1671-8836.2018.05.006 TP393 whdxxblxb-64-5-415 湖北省自然科学基金资助项目(2014CFC1100，2013CFB473，2012FFC034) 2017-08-09 2018-10-24 2020-12-09 版权所有© 2018 《武汉大学学报(理学版)》编辑部 Copyright © 2018 Journal of Wuhan University(Natural Science Edition). All rights reserved. 2018 武汉大学学报(理学版) 5 64