杨小东，杨苗苗，高国娟，李亚楠，鲁小勇，王彩芬



强不可伪造的基于身份服务器辅助验证签名方案

杨小东，杨苗苗，高国娟，李亚楠，鲁小勇，王彩芬

（西北师范大学计算机科学与工程学院，甘肃兰州 730070）

标准模型下的基于身份签名方案大多数是存在性不可伪造的，无法阻止攻击者对已经签名过的消息重新伪造一个合法的签名，并且验证签名需要执行耗时的双线性对运算。为了克服已有基于身份签名方案的安全性依赖强和计算代价大等缺陷，提出了一个强不可伪造的基于身份服务器辅助验证签名方案，并在标准模型下证明了新方案在合谋攻击、自适应选择身份和消息攻击下是安全的。分析结果表明，新方案有效减少了双线性对的计算量，大大降低了签名验证算法的计算复杂度，在效率上优于已有的基于身份签名方案。

基于身份服务器辅助验证签名；强不可伪造性；合谋攻击；标准模型

1 引言

基于身份密码体制是一种将用户身份标识作为公钥的密码体制，用于解决公钥基础设施PKI/CA中数字证书的存储和管理开销等问题[1]。在基于身份的密码体制中，用户的E-mail地址等唯一身份标识作为用户的公钥，密钥生成中心PKG借助主密钥生成相应的用户私钥。由于不再需要使用传统的公钥证书，因而大大减轻了密钥的管理与分发开销。2001年，Boneh和Franklin[2]利用双线性对工具首次构造出高效的基于身份加密方案；随后国内外学者对基于身份密码体制进行了大量的研究，并取得一系列原创性研究成果[3~6]。

然而，大部分基于身份签名方案的签名验证算法都要进行耗时的双线性对计算，不能有效地应用于各类低端计算设备。手机、无线传感器、智能手表等低端计算设备便于携带，但能源供应有限、计算和存储能力较弱。因此，应用于低端计算设备的签名方案必须优先考虑计算量。然而，双线性对是目前比较耗时的密码操作[7]，迫切需要研究新的基于身份签名方案，减少签名验证算法中的双线性对计算量。

基于身份的服务器辅助验证签名将基于身份签名体制和服务器辅助验证签名体制相结合，验证签名合法性的大部分计算量交给服务器执行，验证者只需进行少量的计算，从而有效减轻了验证者的计算负担，提高签名验证的性能，非常适用于低端计算设备。基于身份服务器辅助验证签名的研究才刚刚起步，公开的相关文献较少。2013年，Zhang等[8]设计了一个基于身份的服务器辅助验证签名方案，但其安全依赖于现实世界无法实现的随机预言机假设。一个在随机预言模型下可证明安全的密码系统，在现实中无法确保它的安全性[9]。标准模型下安全的基于身份签名方案能消除理想随机预言机的安全假设，但已有的这类方案[10,11]仅能抵抗攻击者的存在性不可伪造。由于强不可伪造性能同时确保攻击者不能对未签名消息和已签名消息进行伪造签名，被用来设计群签名方案、签密方案及电子现金系统等[12,13]，所以研究强不可伪造的基于身份服务器辅助验证签名方案具有一定的现实意义。

2014年，Kwon[14]构造了一个满足强不可伪造安全属性的基于身份签名方案，在标准模型中具有系统公开参数少、签名短等特点，但签名验证算法需要3个双线性对运算。为了克服已有基于身份签名方案的安全性依赖强和计算代价大等缺陷，本文基于Kwon方案[14]设计了一个强不可伪造的服务器辅助验证签名方案，并证明新方案在合谋攻击和强不可伪造攻击下是安全的。新方案的签名验证算法避免了复杂的双线性对运算，与现有的同类方案相比，具有更低的计算复杂度，可应用于签名验证时间受限或计算能力有限的设备。目前还没有关于标准模型下强不可伪造的基于身份服务器辅助验证签名研究的公开文献。

2 预备知识

2.1 双线性映射

2.2 CDH假设

定义1 计算性Diffie-Hellman（CDH, computational Diffie-Hellman）问题。设是一个大素数，是阶为的循环群，是的任意一个生成元，已知，对于未知的，计算。

定义2 CDH假设。若没有一个多项式时间算法能以不可忽略的概率求解上的CDH问题，那么称群上的CDH问题是困难的[6]。

3 强不可伪造的基于身份服务器辅助验证签名的形式化安全定义

一个强不可伪造的基于身份服务器辅助验证签名方案包括下面6个算法。

6) SAV-Verify (,){0, 1}是服务器辅助验证协议。给定字符串、用户身份和消息签名对，验证者在服务器的协助下验证的正确性，若当是对应于的的合法签名，输出1；否则，输出0。

服务器可以是具有强大计算能力的云服务提供商，验证者是计算能力较弱的云计算终端（如智能手机等），利用SAV-Verify交互协议在服务器的帮助下完成签名的合法性验证。

一个强不可伪造的基于身份服务器辅助验证签名方案至少应满足基于身份签名的强不可伪造性和服务器辅助验证协议SAV-Verify的完备性。强不可伪造性能确保攻击者无法生成一个未签名消息或已签名消息的有效签名，完备性保证服务器不能让验证者确信一个非法签名是合法的。为了改进文献[8]给出的基于身份服务器辅助验证签名的安全模型，假设服务器不仅与合法的签名者合谋，也可以与非法的签名者合谋。由于服务器能获得任何消息的签名，因此无法给出一个统一的安全定义来刻画基于身份服务器辅助验证签名的强不可伪造性和服务器辅助验证协议的完备性。文献[12,14]已给出了基于身份签名方案的强不可伪造性安全定义，下面借助攻击者A和挑战者C之间的安全游戏，给出在合谋攻击和自适应性选择消息攻击下服务器辅助验证协议的完备性安全定义。在这个游戏中，攻击者A拥有主密钥和签名密钥。

建立：挑战者C首先运行系统参数生成算法Setup、密钥提取算法Extract和服务器辅助验证参数生成算法SAV-Setup，生成系统参数、字符串、主密钥和身份/私钥对(,)，然后将发送给A。

定义4 若攻击者A在以上游戏中获胜的概率是可忽略的，则称SAV-Verify协议满足完备性。

利用签名方案的存在不可伪造性和服务器辅助验证协议的完备性，文献[15]给出了服务器辅助验证签名的安全性定义，文献[8]给出了基于身份服务器辅助验证签名的安全性定义。采用类似的方法，下面给出强不可伪造的基于身份服务器辅助验证签名的安全性定义。

定义5 若基于身份签名方案满足强不可伪造性，服务器辅助验证协议满足完备性，则称相应的基于身份服务器辅助验证签名方案是安全的。

4 强不可伪造的基于身份服务器辅助验证签名方案设计

本节在Kwon方案[14]的基础上，设计一个强不可伪造的基于身份服务器辅助验证签名方案，与Kwon方案的主要区别是降低了签名验证者的计算量，将签名验证的大部分计算任务通过服务器辅助验证协议转移给一个不可信的服务器执行。因此，验证者在服务器的协助下完成签名的验证，具有更低的计算复杂度，可应用于签名验证时间受限或计算能力有限的设备。新方案包含的6个算法具体如下。

1) Setup算法

密钥生成中心PKG选择2个素数阶的循环群和，选取一个的生成元，选择一个双线性映射和一个抗碰撞的散列函数；然后随机选取个元素，并随机选取，计算和；最后PKG将作为自己的秘密主密钥，公开相应的系统参数=。

2) Extract算法

3) Sign算法

4) Verify算法

③验证式(2)是否成立。

5) SAV-Setup算法

6) SAV-Verify协议

5 安全性证明与有效性分析

5.1 合理性分析

1) 密钥提取算法的合理性

2) 服务器辅助验证协议的正确性验证

于是有

5.2 安全性分析

本文提出的新方案基于Kwon方案[14]，而文献[14]基于CDH困难问题假设，已在标准模型下证明了Kwon方案满足强不可伪造性。由定义5可知，仅需证明服务器辅助验证协议满足完备性，就可以证明本文方案是安全的。

定理1 本文方案的服务器辅助验证协议能抵抗合谋攻击，并在自适应性选择消息击下满足完备性。

证明 在执行服务器辅助验证协议SAV-Verify中，攻击者A代表服务器，挑战者C代表验证者。A发送给C一个非法的消息签名对，A的目标是让C确信是消息的合法签名。

3) 输出。经过有限次的询问后，攻击者A将伪造的消息签名对发送给挑战者C，这里是对应于用户身份的所有合法签名的集合，。挑战者利用计算，将发送给攻击者A。A首先检查的坐标的最右边比特值，然后计算，，和，并将返回给挑战者C。

在本文方案的服务器辅助验证协议SAV-Verify中，验证者将的幂运算值发送给攻击者，由于参数对服务器是保密的，因而可有效抵抗针对服务器辅助验证签名方案的各类合谋攻击[16,17]。

定理2 在标准模型下，Kwon方案在自适应性选择身份和消息攻击下满足强不可伪造性[14]。

定理3 在标准模型下，本文提出的基于身份服务器辅助验证签名方案在合谋攻击、自适应选择身份和消息攻击下是安全的。

通过定义5、定理1和定理2，很容易得到定理3。

5.3 性能比较

为了表述方便，用PS方案表示Paterson和Schuldt[10]提出的基于身份签名方案，TTS方案表示Tsai等[12]提出的基于身份签名方案，ZS-SAVIDS-1方案和ZS- SAVIDS-2方案分别表示Zhang等[8]提出的第1个和第2个基于身份服务器辅助验证签名方案。假定所有方案选择相同长度的素数，以及相同阶的群和。由于计算量比较大的密码学操作是双线性对与幂运算，因此不再详细讨论其余运算操作。用表示上的幂运算，用表示上的幂运算，用表示双线对运算的数量，所有方案的比较结果如表1所示。

由表1可知，在本文方案中验证者只需进行2次幂运算；但在Kwon方案中，验证者的计算开销是3次双线性对和1次幂运算，因此根据定义3可得知本文方案是计算节约的。

与其他5个方案相比，本文方案的签名验证者的计算开销最小，大大提高了签名的验证速度，具有较高的计算效率，在低端计算设备中具有更好的适应性。虽然Zhang等[8]提出的2个方案具有较短的签名长度，但这2个方案的安全性依赖于理想随机预言机，而本文方案的安全性仅依赖于CDH困难问题，并满足强不可伪造性，具有更高的安全性。本文方案与Kwon方案[14]的系统公开参数长度相同，但小于PS方案[10]和TTS方案[12]的系统参数长度，具有较高的通信代价。

表1 计算开销与安全性能比较

6 结束语

基于Kwon方案和CDH假设，提出了一个强不可伪造的基于身份服务器辅助验证签名方案，其安全性不依赖于理想的随机预言机。验证者在本文方案中不需要执行耗时的双线性对运算，大大降低了验证者的计算开销。本文方案的系统参数小，通信代价低，非常适用于各类低端计算设备。下一步的工作是设计具有更短公开参数的基于身份服务器辅助验证签名方案。

[1] SHAMIR A. Identity-based cryptosystems and signature schemes[C]// CRYPTO 1984, LNCS 0196. Springer Berlin Heidelberg, c1984: 47-53.

[2] BONEH D, FRANKLIN M. Identity-based encryption from the Weil pairing[C]//CRYPTO 2001, LNCS 2139. Springer Berlin Heidelberg, c2001: 213-229.

[3] KAR J. Provably secure on-line/off-line identity-based signature scheme for wireless sensor network[J]. IJ Network Security, 2014, 16(1): 29-39.

[4] TIAN M, HUANG L. Efficient identity-based signature from lattices[M]. ICT Systems Security and Privacy Protection, Springer Berlin Heidelberg, 2014: 321-329.

[5] TSENG Y M, TSAI T T, HUANG S S. Leakage-free ID-based signature[J]. The Computer Journal, 2015, 58(4): 750-757.

[6] ATTRAPADUNG N, EMURA K, HANAOKA G, et al. A revocable group signature scheme from identity-based revocation techniques: achieving constant-size revocation list[C]//Applied Cryptography and Network Security.c2014: 419-437.

[7] HAO S G, LI Z, GHULAM M. A union authentication protocol of cross-domain based on bilinear pairing[J]. Journal of Software, 2013, 8(5): 1094-1100.

[8] ZHANG J, SUN Z. An ID-based server-aided verification short signature scheme avoid key escrow[J]. Journal of Information Science and Engineering, 2013, 29(3): 459-473.

[9] CANETTI R, GOLDREICH O, HALEVI S. The random oracle methodology, revisited[J]. Journal of the ACM, 2004, 51(4): 557-594.

[10] PATERSON K G, SCHULDT J C N. Efficient identity-based signatures secure in the standard model[C]//ACISP, LNCS 4058. Springer Berlin Heidelberg, c2006: 207-222.

[11] WU Q, ZHANG L Y. New strongly unforgeable identity-based signature scheme in the standard model[J]. Journal of Beijing University of Posts and Telecommunications, 2011, 34(3): 71-74.

[12] TSAI T T, TSENG Y M, HUANG S S. Efficient strongly unforgeable ID-based signature without random oracles[J]. Informatica, 2014, 25(3): 505-521.

[13] HUNG Y H, TSAI T T, TSENG Y M, et al. Strongly secure revocable ID-based signature without random oracles[J]. Information Technology and Control, 2014, 43(3): 264-276.

[14] KWON S. An identity-based strongly unforgeable signature without random oracles from bilinear pairings [J]. Information Sciences, 2014, 276(1): 1-9.

[15] WU W, MU Y, SUSILO W, et al. Provably secure server-aided verification signatures[J]. Computers & Mathematics with Applications, 2011, 61(7): 1705-1723.

[16] WANG Z, WANG L, YANG Y, et al. Comment on Wu, et al.'s server-aided verification signature schemes[J]. IJ Network Security, 2010, 10(2): 158-160.

[17] WU H, XU C X, DENG J, et al. On the security of server-aided verification signature schemes[J]. Journal of Computational Information System, 2013, 9(4): 1449-1454.

ID-based server-aided verification signature scheme with strong unforgeability

YANG Xiao-dong, YANG Miao-miao, GAO Guo-juan, LI Ya-nan, LU Xiao-yong, WANG Cai-fen

(College of Computer Science and Engineering, Northwest Normal University, Lanzhou 730070, China)

Most identity-based signature schemes in the standard model are existentially unforgeable, which cannot prevent adversaries from forging valid signatures on messages that have previously been signed. However, signature verification algorithms of ID-based signature schemes in the standard model require expensive bilinear pairing operations. In order to overcome the shortcomings of the existing ID-based signature schemes such as strong security assumption and high computation cost，a strongly unforgeable ID-based server-aided verification signature scheme was presented. This scheme was proven to be secure under collusion attacks, adaptive chosen identity and message attacks in the standard model. Analysis results show that the proposed scheme effectively reduces computation cost of pairing operation, and it greatly reduces computational complexity of signature verification algorithm. The proposed scheme is more efficient than the existing ID-based signature schemes.

ID-based server-aided verification signature, strong unforgeability, collusion attack, standard model

TP309

A

10.11959/j.issn.1000-436x.2016115

2015-07-21；

2015-09-10

国家自然科学基金资助项目（No.61262057）；甘肃省科技计划基金资助项目（No.145RJDA325）；国家档案局科技基金资助项目（No.2014-X-33）；甘肃省高等学校科研基金资助项目（No.2014-A011）；兰州市科技计划基金资助项目（No.2013-4-22）；西北师范大学青年教师科研能力提升计划基金资助项目（No.NWNU-LKQN-13-23, No.NWNU-LKON-14-7）

The National Natural Science Foundation of China (No.61262057), The Natural Science Foundation of Gansu Province (No.145RJDA325), The Science and Technology Project of State Archives Administration of China (No.2014-X-33), Research Fund of Higher Education of Gansu Province (No.2014-A011), Science and Technology Project of Lanzhou City of China (No.2013-4-22), The Foundation for Excellent Young Teachers by Northwest Normal University (No.NWNU-LKQN-13-23, No.NWNU-LKON-14-7)

杨小东（1981-），男，甘肃甘谷人，西北师范大学副教授，主要研究方向为密码学及云计算安全。

杨苗苗（1991-），女，甘肃金昌人，西北师范大学硕士生，主要研究方向为大数据安全。

高国娟（1991-），女，甘肃永登人，西北师范大学硕士生，主要研究方向为信息安全。

李亚楠（1990-），男，山东沂州人，西北师范大学硕士生，主要主要研究方向为网络安全。

鲁小勇（1982-），男，甘肃张掖人，西北师范大学博士生、工程师，主要研究方向为信息系统安全。

王彩芬（1963-），女，河北安国人，西北师范大学教授、博士生导师，主要研究方向为密码学、网络安全和信息安全。