具有聚合性质的无证书代理重签名方案*

杨小东,杨 平,高国娟,刘婷婷,王彩芬

(西北师范大学计算机科学与工程学院,甘肃 兰州 730070)

1 引言

代理重签名由Blaze、Bleumer和Strauss[1]在1998年欧洲密码学年会上提出。在这种密码体制中，一个半可信的代理人(Proxy)可将用户Alice的签名转换为用户Bob对同一个消息的签名，而代理人不能随意生成Alice或Bob的签名。但是，现有的代理重签名方案大部分都是基于数字证书的传统密码系统和基于身份的密码体制，存在证书管理开销过大或密钥生成中心完全知道用户的私钥等问题[2,3]。

无证书代理重签名融合了代理重签名和无证书密码体制的优点，不仅能实现签名的转换，还能有效克服用户面临的密钥托管问题和传统公钥密码体制中庞大证书的管理等问题。国内外学者对代理重签名进行了比较深入的研究，但针对无证书代理重签名的研究才刚刚起步。Guo等[4]将具有签名转换功能的代理重签名与无证书密码体系相结合，构造了一个无证书代理重签名方案，但未对方案进行严格的安全性证明。Feng等[5]提出了一个可证安全的无证书盲代理重签名方案，但Hu等[6]指出这类方案存在严重的安全缺陷，受托者能够伪造任意消息的重签名。Chen等[7]设计了一个不依赖于理想随机预言机的无证书代理重签名方案，但不具有聚合的特性[8]。

为了节省带宽和提高签名验证效率，本文将聚合签名和无证书代理重签名相结合，提出了一个具有聚合性质的无证书代理重签名方案，并证明该方案的安全性可规约到k阶多线性计算Diffie-Hellmank-MCDH(Multi-linear Computational Diffie-Hellman)困难问题假设。通过与已有的无证书代理重签名方案比较分析，发现新方案具有较低的计算开销和通信成本，更适合于移动智能终端等计算源受限的设备。通过对相关领域的文献搜索，目前还没有关于具有聚合特性的无证书代理重签名研究的公开文献。

2 预备知识

2.1 多线性映射

对于一个群生成器Γ(1λ,k)，其中1λ为安全参数，k为生成器允许的双线性对运算个数，Γ生成一个群组G=(G1,G2,…,Gk)，每个群的阶均为p>2λ，gi为Gi的生成元，令g=g1。如果存在一个映射集合{ei,j:Gi×Gj→Gi+j|i,j≥1;i+j≤k}，G中的每个映射都是可计算的，并且满足以下条件，则称G是一个多线性映射群[9-11]。

(2)ei,j(gi,gj)=gi+j。

多线性映射可实现双线性映射的所有功能，同时还具有更强大的功能，比如构造任意布尔电路的属性密码体制等。但是，目前实现多线性映射的主要技术是分级编码系统，存在噪声随着编码的等级快速增长等问题，使得分级编码系统效率较低。Zhang等[12]综合分析多线性映射的构造思想后发现，通过“去噪”技术可有效提高多线性映射的效率。

2.2 k-MCDH假设

定义1(k-MCDH假设) 若任何一个多项式时间算法解决k-MCDH问题的概率是可忽略的，则称k-MCDH问题是困难的[8,13]。

2.3 无证书代理重签名

一个无证书代理重签名方案包括以下七个算法[4]：

(1) 系统建立：给定安全参数1λ，生成系统参数MPK和密钥生成中心KGC(Key Generation Center)的主密钥MSK。

(2) 部分私钥提取算法：给定MPK、MSK和用户身份ID，生成ID的部分密钥dID。

(3) 用户密钥生成算法：给定MPK和用户身份ID，生成对应的公私钥对(pkID,skID)。

(4) 重签名密钥生成算法:通过安全信道输入dA,dB,skA,skB，但代理者无法获得dA,dB,skA,skB。该算法为代理者生成重签名密钥rkA→B，其中skA和dA分别为受托者Alice的私钥和部分密钥，skB和dB为委托者Bob的私钥和部分密钥。

(5) 签名算法： 给定消息M、Alice的部分私钥dA和私钥skA，生成M的原始签名σ。

(6) 重签名算法:输入Alice对消息M的签名σA和重签名密钥rkA→B，如果σA是M的有效签名，该算法利用rkA→B将σA转换为Bob对M的签名σB；否则，输出⊥。

(7) 签名验证:输入用户ID和公钥pk对消息M的签名σ，如果签名σ有效，算法输出1，否则输出0。

无证书代理重签名方案的攻击类型可分为两类：第一类敌手ΑΙ无法获取系统的主密钥MSK，但能替换任意用户的公钥；第二类敌手ΑⅡ掌握系统主密钥MSK，但没有替换用户公钥的权限。下面通过挑战者C和敌手A之间的游戏来定义无证书代理重签名的不可伪造性。

安全游戏1

(1)初始化：C通过执行参数生成算法建立系统，生成KGC的主密钥MSK，并给ΑΙ发送参数MPK。

(2)询问阶段：C通过以下预言机来回答敌手ΑΙ的一系列询问。

①部分私钥询问：输入用户身份I，挑战者C运行部分密钥生成算法，输出用户I的部分私钥dI，并返回给敌手ΑΙ。

②公钥询问：输入用户身份I，C运行用户密钥生成算法，生成用户I的公钥pkI和私钥skI，并将pkI返回给敌手ΑΙ。

③私钥询问：输入用户身份I，如果I已进行过公钥询问，则将对应的skI发送给ΑΙ；否则，C运行用户密钥生成算法输出公钥pkI和私钥skI，并将skI返回给敌手ΑΙ。

④公钥替换询问：输入用户的身份I，敌手ΑΙ计算新的公私钥对(pk′,sk′)来替换以前的公私钥对(pkI,skI)。

⑤重签名密钥询问：对于ΑΙ发起的关于身份(IA,IB)的重签名询问，C进行部分私钥询问、公钥询问和私钥询问后，给ΑΙ返回重签名密钥生成算法输出的重签名密钥rkA→B。

⑥签名询问：ΑΙ输入身份I和消息M，C询问部分私钥询问、公钥询问和私钥询问后，将签名算法输出的签名σ返回给敌手ΑΙ。

⑦重签名询问：对于ΑΙ输入的身份IA和IB、消息M以及签名σA，C进行重签名密钥询问后，将重签名算法输出的重签名σB返回给ΑΙ。

(3)伪造阶段：敌手ΑΙ输出(pkI*,M*,σ*)，若满足以下五个条件，则称ΑΙ赢得了第一类安全游戏。

①Verify(σ*,M*,I*,pkI*)=1；

②敌手ΑΙ从未询问过I*的部分私钥；

③敌手ΑΙ从未询问过消息M*的签名询问；

④敌手ΑΙ从未询问过(IA,IB)的重签名密钥；

⑤(σ*,M*,IA,IB)没有进行过重签名询问。

定义2如果敌手ΑΙ在上述游戏中获胜的优势是可忽略的，则称方案能够抵抗第一类攻击者ΑΙ的伪造攻击[4,7]。

安全游戏2

(1) 初始化：挑战者C将建立系统生成的参数MPK和KGC的主密钥MSK发送给敌手ΑⅡ。

(2)ΑⅡ除了不进行部分私钥询问和公钥替换询问外，与安全游戏1相似，对挑战者C发起类似的私钥询问、签名询问、重签名密钥询问和重签名询问。

(3) 伪造阶段：敌手ΑⅡ输出(pkI*,M*,σ*)，若满足以下四个条件，则称ΑⅡ赢得了第二类安全游戏。

①Verify(σ*,M*,I*,pkI*)=1；

②ΑⅡ从未询问过消息M*的签名询问；

③ΑⅡ从未询问过(IA,IB)的重签名密钥；

④ΑⅡ从未询问过(σ*,M*,IA,IB)的重签名。

定义3若敌手ΑⅡ在上述安全游戏中获胜的优势是可忽略的，则称方案能够抵抗第二类攻击者ΑⅡ的伪造攻击[4,7]。

3 具有聚合性质的无证书代理重签名方案

3.1 方案描述

(1)系统建立。

(2)部分私钥生成算法。

(3)用户密钥生成算法。

(4)重签名密钥生成算法。

(5)签名算法。

(6)重签名算法。

(7)签名验证算法。

给定用户身份I、公钥pk、消息M和签名σ，如果e(σ,g)=e(H(I,M),pk)不成立，输出0；否则，说明σ是一个合法签名，输出1。

3.2 安全性分析

下面通过模拟2.3节的两类安全游戏，证明本方案是存在不可伪造的。定理1和定理2说明新方案是安全的，能有效抵抗针对无证书代理重签名的两类伪造攻击。

定理1如果k-MCDH假设成立，那么本文新方案能抵抗第一类攻击者ΑΙ的伪造攻击。

证明假设敌手ΑΙ以不可忽略的概率在2.3节的第一类游戏中获胜，则挑战者B将以不可忽略的概率解决k-MCDH困难问题。

挑战者B获得一个k-MCDH实例(g,gc1,gc2,…,gck)，其中k=n+l，mi表示签名消息的第i位，idi表示用户身份的第i位。敌手ΑΙ和挑战者B的交互过程如下：

(2) 询问阶段：ΑΙ可以向B发起一系列以下预言机的询问。

③ 用户私钥询问：当ΑΙ询问用户I的私钥skI时，如果表T3中存在(I,skI)，则B返回skI给ΑΙ；否则B从表T2中查询相应的值(I,pkI,xi)，令skI=xi，然后将(I,skI)添加到T3中，并将skI返回给ΑΙ。

④ 公钥替换询问：敌手ΑΙ将用户I的公钥pkI替换为pkI′时，B首先在T2中查询(I,pkI,xi)，若含有相应的值，则将公钥替换为pkI=pkI′；否则B对I进行公钥询问，然后令pkI=pkI′，并将改后的值添加到T2中。

⑦ 重签名询问：ΑΙ发起(b,B,M,σ)的重签名询问，如果Verify(Ib,σ,M)=0，B输出⊥；否则，B将进行消息M和身份IB的签名询问结果返回给ΑΙ。

定理2若k-MCDH假设成立，则本文新方案能抵抗第二类攻击者ΑⅡ的伪造攻击。

证明与定理1的证明过程基本相同，唯一的区别是ΑⅡ知道系统主密钥，不需要向挑战者询问部分私钥和用户公钥替换询问。当ΑⅡ成功输出新方案的一个伪造时，攻击者可以利用这个伪造解决k-MCDH问题实例，进而证明新方案能抵抗第二类伪造攻击。

3.3 性能分析

下面将已有的无证书代理重签名方案与本文新方案进行效率和性能比较，如表1所示。假设每个方案选择相同长度的大素数p和群G1，其中L表示群G1中元素的长度，P表示一次双线性对运算，Y表示具有这种性质，N表示不具有这种性质。

Table 1 Comparison of performance and efficiency表1 性能和效率比较

从表1可以看出，本文新方案的公钥长度、签名长度及重签名长度均为L，签名验证需要2次双线对运算。与另外三个方案相比，新方案具有较高的计算效率和较低的存储开销。

4 结束语

基于多线性映射和无证书密码体制，本文设计了一种新的无证书代理重签名方案，实现了签名验证的聚合特性，大大减小了签名验证的工作量。分析结果表明，新方案不仅具有较短的签名和重签名长度，还解决了证书存储和密钥托管等问题[14]。但是，新方案的系统参数较多，如何设计具有更高性能和满足更多安全属性的无证书代理重签名方案，将是我们下一步工作的方向。

[1] Blaze M, Bleumer G,Strauss M.Divertible protocols and atomic proxy cryptography[C]∥Proc of Advances in Cryptology(EUROCRYPT ’98),1998:127-144.

[2] Xun Tian-tian,Yu Jia,Yang Guang-yang,et al.Key-insulated certificateless aggregate signature[J].Acta Electronica Sinica,2016,44(5):1111-1116.(in Chinese)

[3] Hu Jiang-hong, Du Hong-zhen,Zhang Jian-zhong.Analysis and improvement of certificateless aggregate signature scheme[J].Computer Engineering and Applications,2016,52(10):80-84.(in Chinese)

[4] Guo D,Ping W,Dan Y.A certificateless proxy re-signature scheme[C]∥Proc of Computer Science and Information Technology,2010:157-161.

[5] Feng Tao,Liang Yi-xin.Provably secure certificateless blind proxy re-signatures[J].Journal on Communications,2012,33(Z1):58-69.(in Chinese)

[6] Hu Xiao-ming, Yang Yin-chun,Liu Yan.Analysis and improvement of a blind proxy re-signature scheme based on standard model[J].Journal of Chinese Computer Systems,2011,32(10):2008-2011.(in Chinese)

[7] Chen L,Chen X Y,Sun Y,et al. A new certificateless proxy re-signature scheme in the standard modle[C]∥Proc of the 7the International Symposium on Computational Intelligence & Design,2014:202-206.

[8] Wang Z W,Xia A D.ID-based proxy re-signature with aggregate property[J].Journal of Information Science and Engineering,2015,31(1):1199-1211.

[9] Chen Fei,Han Yi-liang,Yang Xiao-yun,et al.A signcryption scheme from multilinear map[J].Journal of Wuhan University(Nat Sci Ed),2016,62(2):165-170.(in Chinese)

[10] Cheon J H,Han K,Lee C,et al.Cryptanalysis of the multilinear map over the integers[J].Journal of Vascular Surgery,2015,28(1):113-122.

[11] Gary S, Gentry C, Halevi S.Candidate multilinear maps from ideal lattices and applications[C]∥Proc of Advances in Cryptology(Eurocrypt 2013),2013:1-17.

[12] Zhang Fang-guo.From bilinear pairings to multilinear maps[J].Journal of Cryptologic Research,2016,3(3):211-228.(in Chinese)

[13] Albrecht M R, Farshim P,Hofheinz D,et al.Multilinear maps from obfuscation[M]∥Theory of Cryptography.Berlin:Springer Berlin Heidelberg,2016:1.

[14] Zhou Yan-wei, Yang Bo,Zhang Wen-zheng.Efficient and provide security certificateless aggregate signature scheme[J].Journal of Software,2015,26(12):3204-3214.(in Chinese)

附中文参考文献：

[2] 寻甜甜,于佳,杨光洋,等.密钥隔离的无证书聚合签名[J].电子学报,2016,44(5):1111-1116.

[3] 胡江红,杜红珍,张建中.一个无证书聚合签名方案的分析与改进[J].计算机工程与应用,2016,52(10):80-84.

[5] 冯涛,梁一鑫.可证安全的无证书盲代理重签名[J].通信学报,2012,33(Z1):58-69.

[6] 胡小明,杨寅春,刘琰.一种基于标准模型的盲代理重签名方案的安全性分析和改进[J].小型微型计算机系统,2011,32(10):2008-2011.

[9] 陈飞,韩益亮,杨晓元,等.一种基于多线性映射的签密方案[J].武汉大学学报(理学版),2016,62(2):165-170.

[12] 张方国.从双线性对到多线性映射[J].密码学报,2016,3(3):211-228.

[14] 周彦伟,杨波,张文政.高效可证安全的无证书聚合签名方案[J].软件学报,2015,26(12):3204-3214.