高效的可证安全短代理签名方案

左黎明，陈祚松，夏萍萍，易传佳

(1.华东交通大学 理学院，南昌 330013； 2.华东交通大学 系统工程与密码学研究所，南昌 330013)(*通信作者电子邮箱limingzuo@126.com)

0 引言

1996年，Mambo等[1-2]首次提出了代理签名的概念。在一个代理签名方案中，包含了原始签名人、代理签名人和验证人，原始签名人授权给代理签名人后，代理签名人可以代表原始签名人生成一个有效的代理签名，验证人验证时要同时验证代理签名的有效性和原始签名人的授权。这种方案很好地解决了特殊数字签名权力的代理问题，在分布式系统、电子商务、电子政务等领域有着广泛的应用。2012年，杨力等[3]针对可信计算组织 (Trusted Computing Group, TCG)的直接匿名证明方案不能实现跨域可信认证的不足，提出了一个新的代理签名方案，实现对移动终端在多可信域之间漫游时的可信计算平台认证，并证明了方案能够抵抗平台伪装攻击和重放攻击。2013年，Wen等[4]指出随着计算机能力的增强，现有的电子支付系统将逐渐变得不安全，为此提出了一个基于量子代理盲签名的银行支付系统，与传统的电子支付系统相比，不仅能够保护用户的匿名性，还可以实现电子支付的高安全性。2014年，Gao等[5]针对无线mesh网络中存在的隐私泄漏隐患，提出了一个基于代理群签名的匿名访问认证方案，能在认证过程中很好地保护用户的隐私。2015年，Wang等[6]针对数据云存储和共享服务中用户组成员撤销后，数据块签名更新过程复杂的问题，提出了一个基于代理重签名方案的公共审计机制，显著地提高用户撤销的效率。2016年,张新鹏等[7]提出了一个较Wang等[6]方案通信开销和计算代价更低的单向代理重签名方案，但当用户处于无线网络环境下，用户撤销时的数据传输负荷仍然是很大的。2017年，Chiou等[8]提出了一个基于代理签名方案的电子投票系统，并能够在智能手机端通过该方案安全和方便地进行投票。同年，Hong等[9]提出了一个基于属性的代理签名方案，能够保证存储在云中的数据的安全和实现细粒度的认证。2018年，Xu等[10]提出了一个具有可重授权和重撤销特性的代理签名方案，并应用到一个在线的车辆订购系统中，在保证系统安全的同时提高了系统的随需应变能力。

随着无线网络的普及，在无线网络环境下，使用代理签名实现各类数据完整性保护和身份认证变得越来越普遍[11-13]，这也给如何降低网络数据流量和避免网络阻塞带来了巨大的挑战。而短签名方案由于其签名长度短的优势，能够很好地解决这些问题。对此本文构造了一个高效的短代理签名方案，并在计算Diffie-Hellman(Computational Diffie-Hellman, CDH)困难问题假设、k-碰撞攻击算法(Collusion Attack Algorithm with k traitors, k-CAA)困难问题假设和随机预言机模型下证明了方案的安全性。

1 预备知识

1.1 安全性假设

定义3 双线性映射。设G1是循环加法群，G2是循环乘法群，它们的阶同为安全大素数q，群G1和G2中的离散对数问题是困难问题，则称映射e:G1×G1→G2为满足以下性质的双线性映射。

2)非退化性：e(P,P)≠1；

3)易计算性：∀M,N∈G1,存在有效算法计算e(M,N)。

1.2 代理签名定义

1)系统参数建立：系统密钥生成中心(Key Generation Center,KGC)，输入安全参数k，输出系统公开参数params。

2)密钥对生成：系统密钥生成中心KGC，输入用户身份ID和系统公开参数params，输出用户私钥xID和公钥yID。

3)代理授权：输入系统公开参数params、原始签名人A密钥对和授权文件w，输出代理授权证书W。其中：w包含了原始签名人和代理签名人的身份信息、授权关系的描述、允许签署的消息范围及期限等。

4)代理授权验证：输入系统公开参数params、原始签名人A身份IDA和代理授权证书W，验证者验证W是否为一个有效的代理授权证书。

5)代理密钥生成：代理签名人B输入系统公开参数params、代理授权证书W，输出xAB作为代理签名私钥。

6)代理签名：输入系统公开参数params、代理授权文件W、代理签名私钥xAB和待签名消息m，输出签名信息S。

7)代理签名验证：输入系统公开参数params、原始签名人A身份IDA、代理签名人B身份IDB、授权证书W和签名信息S，返回“1”说明验证通过，返回“0”说明验证失败。

1.3 敌手模型

代理签名方案主要存在以下三类攻击者：

1)类型1：攻击者A1同时知道原始签名人的公钥和代理签名人的公钥。

2)类型2：攻击者A2不仅知道原始签名人的公钥和代理签名人的公钥，还知道原始签名人的私钥，但不知道代理签名人的私钥。

3)类型3：攻击者A3不仅知道原始签名人的公钥和代理签名人的公钥，还知道代理签名人的私钥，但不知道原始签名人私钥。

从上述三类攻击者所拥有的能力描述可知，当代理签名方案对于攻击者A2和攻击者A3是存在不可伪造的，那么，对于攻击者A1也是存在不可伪造的。所以本文在后续的安全模型和安全证明中，仅考虑类型2的攻击者A2和类型3的攻击者A3。

1.4 安全模型

定义3 安全模型。如果不存在一个敌手可以在概率多项式时间内以一个不可忽略的优势在图1和图2的游戏中获胜(其中敌手的优势指其获胜的概率)，则证明这个代理签名方案是存在性不可伪造的。

图1 攻击者A2与挑战者C之间的博弈Fig. 1 Game between attacker A2 and challenger C

2 签名方案构造

签名方案构造的步骤如下：

4)代理授权验证：代理签名人B接收到授权许可后，输入系统公开参数params，验证e(dAB,g)=e(h1,yA+R)是否成立，如果等式成立则接受授权许可。

5)代理密钥生成。代理签名人B，根据系统公开参数params，计算xAB=dAB+xBh1，输出xAB作为代理签名密钥。

6)代理签名： 代理签名人B对给定消息m∈{0,1}*，进行如下操作：

①计算h2=H2(IDA,IDB,m,R)；

②计算S=xAB/(h2+xB)，则S为代理签名人B对消息m的签名。

7)签名验证。对给定的消息/签名对(m,S)，通过以下步骤进行验证：

①计算h1=H1(IDA,IDB,wAB,R)；

②计算h2=H2(IDA,IDB,m,R)；

③验证等式e(S,h2g+yB)=e(h1,yA+yB+R)是否成立，若等式成立，则签名验证通过；若等式不成立，则签名验证失败。

图2 攻击者A3与挑战者C之间的博弈Fig. 2 Game between attacker A3 and challenger C

3 方案分析

3.1 正确性分析

授权许可正确性分析如下：

e(dAB,g)=e((xA+r)h1,g)=e(h1,(xA+r)g)=

e(h1,yA+R)

签名验证等式正确性分析如下：

e(S,h2g+yB)=e(S,(h2+xB)g)=

e(xAB/(h2+xB),(h2+xB)g)=

e((xA+xB+r)h1,g)=e(h1,yA+yB+R)

3.2 安全性证明

定理1 针对第二类攻击者，在随机预言机模型以及k-CAA困难问题假设下，本文方案是存在性不可伪造的。

为叙述简便，假设A2不会对预言机作相同的询问，而且在进行签名询问和伪造签名时已经作了H1和H2询问，所有的记录列表初始化为空。C允许A2作以下适应性询问：

3)H2询问：C维护一个记录结构为数组(IDA,IDB,m,R,h2)的列表LH2。当A2提交一个关于(IDA,IDB,m,R)的H2询问时，C检查列表LH2是否已经存在询问对应值(IDA,IDB,m,R,h2)，存在则返回相应的h2给A2；否则均匀地随机选择h2∈Ω返回给A2同时将(IDA,IDB,m,R,h2)记录到列表LH2。显然这里h2∈E的概率为k/qH2，h2∈F的概率为(qH2-k)/qH2。

4)代理签名询问：当A2提交关于(m,IDA,IDB,R)的代理签名询问时，则C从列表LH1中获取记录(IDA,IDB,wAB,R,v,h1)，C从列表LH2中获取相应记录(IDA,IDB,m,R,h2)，C从列表LR中获取记录(IDA,IDB,wAB,r,R)，然后：

①如果h2∈E，即存在ej=h2∈E,计算S=v(xA+r)g/(b+ej),将S返回给A2；

②如果h2∈F，返回“⊥”，记此事件为Event1，“⊥”表示空。

值得注意的是，如果h2∈E，构造的代理签名能够通过验证等式，其合理性由以下等式保证：

e(S,h2g+yB)=e(v(xA+r)g/(b+ej),ejg+yB)=

e(vg,yA+yB+R);R=rg-yB

即输出S*/((xA+r*)v*)作为对困难问题的解答，从而C解决了k-CAA问题的实例。

以下分析C成功解决困难问题需要的时间和优势：

当A2没有作H2询问而伪造一个有效签名其发生的概率为1/2λ，所以C在游戏中的优势估计满足：

运行时间满足：

t′

因此C以不可忽略的优势ε′在多项式时间t′内成功地解决了一个k-CAA问题的实例，这与k-CAA问题困难性矛盾。所以本文方案针对于第二类敌手是存在性不可伪造的。

定理2 针对第三类攻击者，在随机预言机模型以及CDH困难问题假设下，本文方案是存在性不可伪造的。

引理2 假设敌手A3经过有限次询问后在多项式时间t内以不可忽略的优势ε攻破了本文方案，记qHi和tHi分别为敌手A3询问Hi(i=1,2)预言机的次数和一次询问所需时间，记qR和tR分别为授权识别码询问次数和一次询问所需时间,记qS和tS分别为代理签名询问次数和一次询问所需时间，δ∈(0,1/2)，则存在算法C，在概率多项式时间t′

为叙述简便，假设A3不会对预言机作相同的询问，且在进行签名询问和伪造签名时已经作了H1和H2询问，所有的记录列表初始化为空。C允许A3作以下适应性询问：

4)代理签名询问。当A3提交关于(m,IDA,IDB,R,xAB)的代理签名询问时，则C从列表LH2中获取相应记录h2，C从列表LR中获得(IDA,IDB,wAB,c,r,R)。若c=0则计算S=(xB+r)vbg/(xB+h2)，将S返回给A3；否则，返回“⊥”，记此事件为Event1。

构造的代理签名能够通过验证等式，其合理性由以下等式保证：

e(S,h2g+yB)=e((xBvbg+rvbg)/(xB+h2),h2g+yB)=

e(vg,yA+yB+R);R=rg-yA

所以C可以成功计算：

以下分析C成功解决困难问题需要的时间和优势：

2)只有当模拟阶段Event1和Event2一直都不发生时，则C能解决CDH问题的一个实例。Event1一直不发生的概率为(1-δ)qs，Event2不发生的概率为δ，则可得Event1、Event2都不发生的概率为：

当A3没有询问H1而伪造一个有效签名时，这种模拟是存在漏洞的,其发生的概率为1/2λ，所以C在游戏中的优势满足：

ε′≥δ(1-δ)qs(ε-1/2λ)

运行时间满足：

t′

因此C以不可忽略的优势ε′在多项式时间t′内成功地解决了一个CDH问题的实例，这与CDH问题困难性矛盾。所以本文方案针对于第三类敌手是存在性不可伪造的。

4 方案实现与效率分析

4.1 方案实现

本文方案是以PBC(Pairing-Based Cryptography library)[14]为基础，在操作系统为 Windows 7旗舰版 64位，处理器为 Intel i3-4170 3.70 GHz,主板为华硕B85M-F PLUS,内存为威刚 DDR3 1 600 MHz 8 GB的实验基准测试环境中，通过Visual Studio 2012开发平台，进行了方案实现。

其具体实现的核心代码如下：

pairing_tpairing;

//初始化双线性对

if (pairing_init_set_buf(pairing,eparam, strlen(eparam)))

printf("pairing init failed");

element_txA,yA,xB,yB,g,r,R,h1,h2;

//1)系统参数建立

element_init_G1(g,pairing);element_random(g);

//2)密钥对生成

element_init_Zr(xA,pairing);

element_init_G1(yA,pairing);

element_init_Zr(xB,pairing);

element_init_G1(yB,pairing);

element_mul(yA,xA,g);

//计算yA=xA*g

element_mul(yB,xB,g);

//计算yB=xB*g

//3)代理授权

element_init_G1(R,pairing);element_init_Zr(r,pairing);

element_mul(R,r,g);

//计算R=r*g

element_init_G1(h1,pairing);

element_from_hash(h1,IDA,strlen(IDA));

element_ttemp1,dAB;

element_init_Zr(temp1,pairing);

element_add(temp1,xA,r);

element_init_G1(dAB,pairing);

element_mul(dAB,temp1,h1);

//dAB=(xA+r)h1

//4)代理授权验证

element_tLp,Rp,yA_R;

element_init_GT(Lp,pairing);

element_init_GT(Rp,pairing);

element_init_G1(yA_R,pairing);

element_mul(yA_R,temp1,g);

//授权验证左边：e(dAB,g)

element_pairing(Lp,dAB,g);

// 授权验证右边：e(h1,yA+R)

element_pairing(Rp,h1,yA_R);

if(element_cmp(Lp,Rp)) return 0;

//5)代理密钥合成

element_txAB,temp3;

element_init_Zr(temp3,pairing);

element_add(temp3,xB,temp1);

element_init_G1(xAB,pairing);

element_mul(xAB,temp3,h1);

//计算xAB

//6)代理签名生成

charm[100]="sign_message_czs";

strcat(m,IDA);strcat(m,IDB);

strcat(m,WAB);element_init_Zr(h2,pairing);

element_from_hash(h2,m,strlen(m));

element_tS,temp4,temp5;

element_init_G1(S,pairing);

element_init_Zr(temp4,pairing);

element_init_Zr(temp5,pairing);

element_add(temp4,xB,h2);

element_invert(temp5,temp4);

element_mul(S,temp5,xAB);

//(h2+xB)^(-1)*xAB

//7)代理签名验证

element_tleft,right,temp6,temp7;

element_init_GT(left,pairing);

element_init_GT(right,pairing);

element_init_G1(temp6,pairing);

element_mul(temp6,temp4,g);

//h2g+yB

element_pairing(left,S,temp6);

//e(S,h2g+yB)

element_init_G1(temp7,pairing);

element_mul(temp7,temp3,g);

//计算yA+yB+R

element_pairing(right,h1,temp7);

//e(h1,yA+yB+R)

element_printf("e(S,h2g+yB)= %B ",left);

element_printf("e(h1,yA+yB+R)= %B ",right);

if (!element_cmp(left,right))

printf("验证成功! ");

如图3所示，为根据签名生成等式S=xAB/(h2+xB)，对长度为71 B的消息m进行签名的结果,整个签名生成耗时为0.014 s。

图3 签名结果Fig. 3 Signature result

图4为根据相应参数和代理签名验证等式e(S,h2g+yB)=e(h1,yA+yB+R)对消息m的签名进行验证的结果。由图4中可知，代理签名验证过程只需要0.028 s，并且方案的整体耗时为0.127 s，能够较高效地实现消息的代理签名和验证签名。

图4 验证结果Fig. 4 Verification result

4.2 计算效率分析

表1 不同方案的计算效率和签名长度比较Tab. 1 Comparison of computation efficiency and signature length of different schemes

4.3 运行效率分析

在相同的实验测试基准环境下，对本文方案和现有几个代理签名方案进行了实现，并将多次运行后的运行效率进行比较，结果如表2所示。

表2 不同方案运行50次平均耗时比较 sTab. 2 Average time consumption comparison of different schemes with running 50 times s

从表2可知，本文方案签名平均耗时为0.014 s，签名验证平均耗时为0.029 s，方案平均总耗时为0.129 s。本文方案与文献[15]方案相比方案平均总耗时减少了约28.7%，与文献[16]方案相比方案平均总耗时减少了约33.8%，与文献[17]方案相比方案平均总耗时减少了约9.8%，与文献[18]方案相比方案平均总耗时减少了约27.9%，与文献[19]方案相比方案平均总耗时减少了约17.8%。从以上分析可知，本文方案不仅签名长度短、理论计算效率高，而且在实际运行效率上也优于文献[15-19]方案。

5 结语

针对无线设备应用中存在的计算能力和传输能力较弱的问题，本文提出了一个代理短签名方案。然后，在CDH困难问题假设和随机预言机模型下证明了本文方案的安全性。最后，对本文方案进行了实现和实验比较，实验结果和分析表明本文方案计算量小、效率较高，能较好地适用于计算能力较弱和传输能力受限的应用场景。在下一步的研究中，将在利用短签名构造安全传输协议的思想[20]上，基于本文代理短签名方案设计出一套适用于移动端应用软件在线版权保护的安全认证协议。