高效的可证明安全的无证书数字签名方案

何明星，李鹏程，李 虓

高效的可证明安全的无证书数字签名方案

何明星，李鹏程，李 虓

(西华大学计算机与软件工程学院 成都 610039)

无证书公钥密码体制结合了基于身份和传统PKI公钥密码体制的优势，克服了基于身份公钥密码体制的密钥托管问题及PKI系统的证书管理问题，具有很高的效率。该文提出一个在随机预言机模型下可证明安全的无证书数字签名方案。该方案只需分别在系统初始化阶段、验证阶段预进行一次双线性对运算，而在签名阶段不需要进行计算。计算结果证明该方案比以往的无证书数字签名方案具有更高的计算效率和通信效率，且具有随机预言机模型下的可证明安全性。

双线性对; 无证书数字签名; 可证明安全; 数字签名

文献[1]首次提出了基于身份的数字签名方案。文献[2]第一次提出双线性对的概念，并利用双线性对构造了一个基于身份的数字签名方案。文献[3]首次构造了一个无证书数字签名方案，该方案也是基于双线性对的，但并没有对该方案进行严格的安全性证明和安全性分析。文献[4]论证了文献[3]的不安全性，容易受到公钥替换攻击，敌手可以假冒用户对任意消息进行伪造签名。文献[5-6]中的方案也不能抵抗公钥替换攻击。此外，经过分析发现文献[6]中用户还可以恢复出SEM拥有的对应于该用户私钥的另一部分私钥，使得该签名方案无仲裁性质。文献[7]构造了一个高效的无证书数字签名方案，它基于离散对数困难性假设，该方案在签名中不需要“双线性对”运算，在验证阶段仅需2次“双线性对”运算。但文献[8]发现文献[7]的方案也不能抵抗公钥替换攻击。文献[9-11]也从不同侧面对安全性和有效性进行了更加深入和广泛的讨论。本文在这些成果基础上提出一个新的在随机预言机模型下可证明安全的无证书数字签名方案，且比以往的无证书数字签名方案具有更高的计算效率和通信效率。

1 无证书数字签名模型

1.1 无证书数字签名

一个无证书数字签名系统由密钥生成中心(key generate center, KGC)、签名者(signaturer)、验证者(verifier)3个合法参与者构成。包含7个多项式时间算法：

1) 系统初始化算法：输入系统安全参数1k后，返回KGC的主私钥(master secret key,MSK)以及系统全局参数。

2) 部分私钥提取算法：输入用户身份字符串ID∈{0,1}*({0,1}*表示所有的比特串集合)、系统主私钥MSK及系统公开参数，由KGC返回用户部分私钥D。

3) 设置秘密值算法：用户随机选择一个秘密值x，用于生成用户的公钥及私钥。

4) 用户公钥生成算法：用户输入秘密值x及系统公开参数后，生成自己的公钥PK。

5) 用户私钥生成算法：用户输入秘密值x及由KGC生成的部分私钥D，返回完整的私钥SK。

6) 签名算法：该算法是概率多项式时间算法。签名发送者在执行算法过程中，输入待签名消息m∈MCLS、签名发送者身份IDS、完整私钥SKS和公钥PKS、签名验证方身份IDR、全局参数及一些随机数r∈RCLS。算法执行完毕后，若签名正确则输出消息m∈MCLS对应的签名σ∈ΣCLS；否则输出错误标识“⊥”。

7) 签名验证算法：输入签名σ∈ΣCLS、签名发送者用户身份IDS、公钥PKS、签名验证方身份IDR及系统全局参数。算法由签名验证者执行完毕后，若验证签名正确则输出“接受签名”；否则输出错误标识“⊥”。

1.2 无证书数字签名体制的敌手

无证书数字签名体制的敌手[3]分为两类：1) 敌手IA定义为外部的恶意敌手，是主动敌手，不知道系统的主私钥MSK，但拥有替换用户公钥的能力；2) 敌手IIA是一个诚实但好奇(honest-but- curious)的KGC，是一个被动敌手，拥有系统的主私钥MSK，但不能替换用户的公钥。

在随机预言机模型下，一个无证书数字签名方案的可证明安全性，可通过一个挑战者C与敌手IA或者IIA进行交互来确定。

1.2.1 游戏1(针对敌手IA)

1) 系统初始化：挑战者C输入系统安全参数l，运行初始化算法，获取系统主私钥MSK及全局参数，然后将系统全局参数发送给敌手IA，并对系统主私钥MSK保密。

2) 攻击阶段：敌手IA可以进行多项式次的交互询问。

① 请求公钥询问PK(IDi)：当敌手AI向挑战者提交一个合法的身份IDi并请求询问该IDi的公钥后，挑战者返回提交IDi相对应的公钥PK(IDi)。

② 替换公钥询问PKR(IDi,PK′IDi)：当敌手AI向挑战者提交一个合法的身份IDi以及一个伪造的合符系统格式的公钥PK′IDi后，挑战者应该利用提交的伪造公钥PK′IDi替换掉敌手提交IDi的当前公钥PKIDi。

③ 秘密值询问SV(IDi)：当敌手AI向挑战者提交一个合法的身份IDi并请求询问该IDi的秘密值xi后，如果该IDi的公钥未被替换，那么挑战者向敌手返回该IDi对应的秘密值xIDi；否则模拟失败。

④ 部分私钥提取询问PPK(IDi)：当敌手AI向挑战者提交一个合法的身份IDi并请求询问该IDi的部分私钥后，挑战者返回提交IDi相对应的部分私钥DIDi。

⑤ 私钥提取询问SK(IDi)：当敌手AI向挑战者提交一个合法的身份IDi并请求询问该IDi的私钥后，挑战者返回提交IDi相对应的私钥SKIDi，如果该IDi对应的公钥被替换，则模拟失败。

⑥ 签名询问Sig(Mi,IDi,PKi)：敌手AI可以对任何用户IDi对消息Mi的签名进行询问，挑战者收到一个挑战(Mi,IDi,PKi)后，挑战者C对消息Mi生成一个签名σi作于对敌手AI的回答。这里要求对消息Mi生成签名σi对于用户IDi和其对应的公钥PKIDi是有效的。

3) 伪造阶段：最后，若敌手AI输出一个元组(M*,σ*,ID*,PK)，当且仅当满足以下3个条件，

ID*敌手AI获得该游戏的胜利。

① 对于用户ID*和其对应的公钥PKID*，元组中签名σi是有效的。

② 敌手AI没有对用户ID*进行过部分私钥提取询问。

1.2.2 游戏2

与游戏1不同之处：AII仅有请求公钥询问PK(IDi)、秘密值询问SV(IDi)、私钥提取询问SK(IDi)、签名询问Sig(Mi,IDi,PKi)的能力。AII不像AI具有公钥替换的能力PKR(IDi,PK′ID)：当AI向挑战者提交一个合法的身份IDi及一个伪造的符合系统格式的公钥PK′ID后，挑战者应利用提交的伪造公钥PK′ ID替换AI提交IDi的当前公钥PKIDi。

2 高效的无证书数字签名方案

2.1 无证书数字签名方案描述

系统初始化算法分为以下5个步骤：

1) KGC首先生成素数q阶的加法循环群G1及乘法循环群G2，任意选择一个生成元P∈G1。

3) KGC计算得到系统主公钥P0=sP∈G1。

4) KGC预计算双线性对e( P, P)=g∈G2，e是一个双线性映射。

5) 最后，KGC选择两个密码学安全的Hash函数H1:{0,1}*→(×表示集合间的笛卡尔积)。

部分私钥提取算法分为两个步骤：

用户公钥生成算法执行分为两个步骤：

1) 计算得到身份哈希值：

2) 用户iU计算得到公钥：

2) Alice计算U=H2(M||R|| T)∈。

3) Alice计算得到消息签名V=x( U−1D−

最后，Alice通过公开信道将签名σ=＜R, T, V＞发送给Bob。

签名验证算法执行步骤：Bob在接收到Alice发送的签名σ=＜R, T, V＞后验证签名。

1) Bob首先计算U′=H2(M||R|| T)∈。

2) Bob验证等式：

若成立，则接受签名；否则拒绝签名。

2.2 无证书数字签名方案的正确性分析

在一般的数字签名中，签名的原始消息对于签名发送方以及签名验证方均是公开的，所以如果对消息的签名在传输过程中没有被敌手篡改，那么签名验证方在收到签名后，首先计算出正确的U′=(M||R|| T)∈，有U=U′∈，签名则能通过式(3)的验证，即：

3 无证书数字签名方案的安全性证明

定理 1 无证书数字签名方案在k-CCA困难性假设及随机预言机(Random Oracle)模型下，对敌手AI可抵抗存在性伪造攻击。

证明：挑战者算法C首先与敌手ΑI交互生成k-CCA困难问题的实例。

初始化阶段：设置PPub=sP, g=e( P, P)。值得注意的是系统主私钥是保密的。随后C随机选择一个指数l∈{1,2,…,k }，这里k≤qH1。

1) H1询问

ΑI可以不重复地对每一个身份IDi(i∈{1, 2,…,k})进行询问：

① 若i≠l，C向ΑI返回QID=ti，并将元组(i,ID,QID=ti)添加进一个初始化为空的表L1；

② 若i=l，则C向ΑI返回身份值QID=t0，并将元组(i,ID,QID=t0)添加进H1哈希询问所维护的表L1。

2) H2询问

对于ΑI提起的每一个询问(Mi, R, T)：

① C首先检查表L2，若表中存在一个元组(Mi, R, T, h2)，那么C向ΑI返回相对应的Hash值；

② 否则，C任意选择一个Hash值h2∈Zq*返回给ΑI，并将相应的元组(Mi, R, T, h2)添加进表L2；

③ 提取部分私钥询问，ΑI就一个身份IDi向C提起提取部分私钥询问请求；

④ 若i=l，C终止该预言机的模拟；

⑤ 若i≠l，C首先查表LK={i,ID,xID,DID, PKID}，如果表中存在该IDi对应的元组，则向ΑI返回对应的；否则，挑战者C先以ID作i一次H1哈希询问，并将元组(i,ID,)更新到表L1，然后向ΑI返回对应ID的部分私钥DID=(s+，并将元组{i,ID,⊥,,⊥}更新到表，这里“⊥”表示为空。

3) 秘密值询问

当AI向C以IDi并提起询问后：

① C首先查表LK，如果该表中存在一个元组{i,ID,xID,DID,PKID}该IDi的公钥未被替换，那么C向AI返回该ID对应的秘密值xID，否则输出模拟失败。

② 否则，C先以IDi作一次H1哈希询问，并将元组(i,ID,QID=ti)更新到表L1，然后再作一次部分私钥询问并随机选择一个xID∈Zq*，最后向ΑI返回秘密值xID并将元组{i,ID,xID,DID,PKID}更新到表LK，元组中插入的公钥PKID为C成秘密值后利用公钥生成算法获得的。

4) 请求公钥询问

对于ΑI的每一个询问IDi：

① C首先查表LK，如果该表中存在一个元组{i,ID,xID,DID,PKID}，则返回该ID所对应的公钥PKID；

② 否则，C先以IDi作一次H1哈希询问，并将元组(i,ID,QID=ti)更新到表L1，然后执行一次秘密值询问，执行公钥生成算法为其生成一个新的公钥对返回给ΑI，并将新的元组{i,ID,xID,DID,PKID}添加进该询问维护的表LK。

5) 替换公钥询问

ΑI向挑战者提交一个合法的元组(ID,PK′ID)：

① C首先根据ID搜索表LK，如果表中存在对应ID的元组，则将其内容更新为{i,ID,⊥,DID,PK′ID}；

② 否则，C先以IDi作一次H1哈希询问，并将元组(i,ID,QID=ti)更新到表L1，然后再作一次部分私钥提取，并将新元组{i,ID,⊥,DID,PK′ID}插入进表LK。C并不知道敌手伪造用户公钥所用到的秘密值xI′D。

6) 提取私钥询问

ΑI就一个身份IDi向C起提取私钥询问后：

① 若i=l，挑战者终止该预言机的模拟；

② 若i≠l，分两种情况：

第一，挑战者查表LK，若表中存在该ID对应的元组，但是该用户的公钥已经被替换，挑战者模拟失败；否则返回该用户对应的私钥SKID=(xID,DID)；

第二，若表LK中不存在该ID对应的元组，查表L1，找到该ID对应的身份哈希值QID，如果该ID对应元组不存在，则以该ID作一次H1询问，并将元组(i,ID,QID=ti)更新到表L1，然后执行一次秘密值提取询问，将新元组{i,ID,xID,DID,⊥}插入表LK并向ΑI返回提交ID私钥SKID=(xID,DID)。

7） 签名询问

在预言机询问中，ΑI提交的询问内容为一个元组(Mi,IDi,PKIDi)，无论该ID公钥是否被替换，C均能生成一个合法的签名(通过验证等式)：

① 任意选择两个随机数r, t∈Zq*，计算得到R=gr, T=gt；

② 计算U=H2(Mi||R|| T )；

③ 计算V=rU−1D−PK，并将生成的签名

IDA(V, R, T)返回给ΑI。

8) 伪造阶段

最后，ΑI输出一个成功的伪造元组(M*,σ*= (V*,R*, T*),ID*,PKID*)，元组里的签名σ*是能通过验证等式的，ID*≠IDl，若挑战者终止模拟；否则，利用文献[12]中的的攻击方法，C进行重放攻击，生成另一个伪造元组(M*,σ*=(V*,R*, T*), ID*,PKID*)，这里要求Α及签名σ*需满足：

最后C则通过两次伪造签名的恒等性e( V*+P))获得k-CCA困难性问题的解

定理 2 无证书数字签名方案在kCCA−困难性假设以及随机预言机模型下，对敌手IIA可以抵抗存在性伪造攻击。思路与方法同定理1。

4 无证书数字签名方案的效率分析

表1列举了本文方案与其他无证书数字签名方案在签名以及验证阶段中计算效率和签名规模上的比较。可以看出，本文方案与其他的无证书数字签名方案相比，不但费时的双线性对运算比其他的无证书数字签名方案少，而且指数运算和计算快速的倍点运算也与其他无证书数字签名方案相当，可见本文方案具有更高的运算效率；另外，本文方案的签名规模也和其他方案大致平衡；最后，在协议的执行过程中，本文方案不需要复杂的运行费时的映射到点(map-to-point)的Hash函数。因此，本文方案是一个高效的无证书数字签名方案。

表1 4个无证书数字签名方案的效率对比

5 结 论

本文提出了一个在随机预言机模型下可证明安全的无证书数字签名方案。方案仅需在系统初始化阶段预计算一次双线性对，在验证阶段计算一次双线性对，而在签名阶段不需要进行双线性对运算，因此本方案比以往一些无证书数字签名方案具有更高的计算效率和通信效率。

[1] SHAMIR A. Identity-based cryptosystems and signature schemes[C]//Advances in Cryptology-CRYPTO’84. Berlin: Springer-Verlag, 1984.

[2] SAKAI R, OHGISHI K, KASAHARA M. Cryptosystems based on pairing[C]//Proceedings of Symposium on Cryptography and Information Security. Okinawa, Japan: [s.n.], 2000.

[3] AL-RIYAMI S, PATERSON K G. Certificateless public key cryptography[C]//Advances in Cryptology-ASIACRYPT’03. Berlin: Springer-Verlag, 2003.

[4] HUANG Xin-yi, WILLY SUSILO, YI MU, et al. On the security of a certificateless signature scheme from Asiacrypt 2003[C]//4th International Conference on Cryptology and Network Security. Berlin: Springer-Verlag, 2005.

[5] LI X, CHEN K, SUN L. Certificateless signature and proxy signature schemes from bilinear pairings[J]. Lietuvos Matematikos Rinkinys, 2005, 45(1): 76-83.

[6] JU H, KIM D, LEE D, et al. Efficient revocation of security capability in certificateless public key cryptography [C]//Knowledge-Based Intelligent Information and Engineering Systems. Berlin: Springer-Verlag, 2005.

[7] YAP W, HENG S, GOI B. An efficient certificateless signature scheme[C]//Emerging Directions in Embedded and Ubiquitous Computing, EUC Workshops 2006. Berlin: Springer-Verlag, 2006.

[8] ZHANG Zhen-feng, FENG Deng-guo. Key replacement attack on a certificateless signature scheme[EB/OL]. http:// eprint.iacr.org/2006/453.

[9] ZHANG Z, XU J, FENG D. Certificateless public-key signature: Security model and efficient construction[C]// Advances in ACNS 2006. Berlin: Springer-Verlag, 2006.

[10] HE D, CHEN J, ZHANG R. An efficient and provably-secure certificateless signature scheme without bilinear pairings[J]. International Journal of Communication Systems, 2012, 25(11): 1432-1442.

[11] HE De-biao, CHEN Yi-tao, CHEN Jian-hua. An efficient certificateless proxy signature scheme without pairing[J]. Mathematical and Computer Modelling, 2013(57): 2510-2518.

编 辑 叶 芳

Efficient and Provably Secure Certificateless Signature from Bilinear Pairings

HE Ming-xing, LI Peng-cheng, and LI Xiao

(School of Computer and Software Engineering, Xihua University Chengdu 610039)

Certificateless cryptography aims at combining the advantages of identity based and traditional certificate-based public key cryptography, so as to avoid the key escrow problem inherent in the identity based system and certificate management in public key infrastructure. In this paper, we propose a new efficient certificateless signature scheme and prove its security in the random oracle model. Furthermore, via pre-computing a bilinear pairing in the setup phase, our scheme only needs to compute one pairing in the verify stage. It is more efficient in computation complexity and communication complexity than that of many previous schemes.

bilinear pairing; certificateless signature; provable security; signature

TP309

A

10.3969/j.issn.1001-0548.2015.05.016

2013 − 07 − 21；

2014 − 03 −01

科技部支撑计划(2011BAH26B00)；四川省国际合作项目(2009HH0009)；四川省高校创新团队项目(13TD0005)作者简介：何明星(1964 − )，男，博士，教授，主要从事密码学与信息安全方面的研究.