高效可证安全的基于证书数字签名方案

黄茹芬，农强，黄振杰

闽南师范大学计算机科学与工程系，福建漳州 363000

高效可证安全的基于证书数字签名方案

黄茹芬，农强，黄振杰

闽南师范大学计算机科学与工程系，福建漳州 363000

1 引言

为了简化传统公钥密码系统的证书管理过程，解决基于身份公钥密码系统[1]固有的密钥托管问题，Gentry[2]在2003年的欧密会上首次提出了基于证书公钥密码系统的概念。随后的2004年，Kang等人[3]将基于证书公钥密码系统扩展到基于证书的数字签名，提出了基于证书数字签名（CBS）的概念及其安全性定义，并构造了两个基于证书的数字签名方案。2007年，Li等[4]给出了基于证书公钥密码系统中攻击敌手的形式化定义，并使用聚合签名的思想提出了效率更高的CBS方案。2008年，Liu等[5]进一步构造了在标准模型下可证明安全的CBS方案。2009年，Wu等在

文献[6]中进一步完善了基于证书数字签名的安全定义。近年来，相继有研究者们提出了一些基于证书的签名方案，包括利用双线性对构造的签名[7-10]、盲签名[11]、短签名[12-13]、指定验证者签名[14-15]，以及不含双线性对的签名[16-17]等方案。基于证书的数字签名结合了传统公钥数字签名和基于身份数字签名的优点，克服了这两类签名系统所存在的问题。在一个CBS中，签名者首先根据自己选定的私钥来生产公钥，随后证书授权中心（Certificate Authority，CA）在证书生成过程中绑定了签名者公钥，CA的证书在签名阶段作为签名私钥的一部分，从而实现了对签名者公钥的隐含验证。因此，CBS系统既简化了传统公钥数字签名系统中证书的管理、存储和发布，解决了基于身份公钥签名系统中的密钥托管问题，还克服了无证书公钥密码系统中存在的信任级别只能达到2级[18]，不能达到Girault 3级和存在拒绝解密（Denial of Decryption，DoD）攻击[19]等缺点。目前，对基于证书加密和签名的研究虽然已取得了一些成果，但为数还相对较少。

本文构造了一个有效的基于证书数字签名方案，并在随机预言机模型下，基于q强Diffie-Hellman问题和扩展的逆计算Diffie-Hellman问题的困难性，证明了所构造签名方案的安全性。新方案的签名算法简单、不需要任何双线性对运算，验证算法也仅仅需要一个双线性对运算，因此，所提方案在计算代价上相当有效。

2 预备知识

2.1 双线性映射

设G1是一个加法群，其阶为素数p，P是G1的任意一个生成元，G2是一个乘法群，其阶数与G1相同。一个双线性对是一个映射e:G1×G1→G2，满足双线性性、非退化性和可计算性。

（1）双线性：对于任意的a,b∈，下列等式成立：e(aP,bQ)=e(P,Q)ab。

（2）非退化性：存在P,Q∈G1，满足e(P,Q)≠1。

（3）可计算性：对于任意的P,Q∈G1，存在有效的多项式时间算法，可以计算出e(P,Q)。

2.2 困难假设

假设1q-SDHA（q-强Diffie-Hellman困难假设）：如果不存在一个概率多项式算法，可以在时间t内，以至少ε的概率解群G上的q-SDHP，则称(t,ε)-q-SDHP困难假设在该群G上成立。

假设2 E-inv-CDHA（扩展的逆计算Diffie-Hellman困难假设）：如果不存在一个概率多项式的算法，可以在时间t内，以至少ε的概率解群G上的E-inv-CDHP，则称(t,ε) E-inv-CDHP困难假设在该群G上成立。

3 基于证书签名的相关定义

3.1 形式化定义

定义3（基于证书的数字签名CBS）一个基于证书的数字签名方案一般由以下五个算法组成。

（1）系统初始化：输入安全参数，输出系统公开参数和系统主私钥。

（2）密钥生成：输入系统公开参数和用户身份，输出用户的私钥和公钥。

（3）证书生成：输入系统公开参数、系统主私钥、用户身份及其公钥，CA输出用户的公钥证书。

（4）签名生成：输入待签消息m、系统公开参数、用户身份、用户私钥及其公钥证书，输出对应于消息m的签名σ。

（5）签名验证：输入消息/签名对(m,σ)、系统公开参数、用户身份及其公钥，输出接受或拒绝签名。

3.2 安全性定义

基于证书的数字签名方案必须满足正确性和存在不可伪造性。正确性是指由签名算法所产生的签名必须能够通过签名验证算法。存在不可伪造性是指所产生的签名在适应性选择消息、选择身份以及替换公钥攻击下是不可伪造的。在基于证书的数字签名中，需要考虑两种类型敌手的攻击：类型I敌手AI和类型II敌手AII。

类型I敌手AI：AI模拟用户攻击，即敌手试图以用户身份伪造合法用户的签名。因此，敌手AI知道用户的私钥，但不知道对应公钥的证书，可以任意替换用户的公钥。

类型II敌手AII：AII模拟CA攻击，即不诚实的证书授权中心试图伪造用户产生签名。因此，敌手AII知道系统主私钥，可以产生用户的公钥证书，但不知道用户的私钥，也不能替换目标用户的公钥。

基于证书签名方案的存在不可伪造性是通过敌手A∈{AI,AII}和挑战者C之间的游戏来定义的。

（1）游戏Game1：类型I敌手AI和挑战者C之间进行的游戏。

系统建立：输入系统安全参数，C执行系统初始化算法，获得系统公开参数和主私钥，并发送系统公开参数给敌手AI。

预言机服务：敌手AI可以在多项式时间内向C发布密钥询问、Hash函数询问、证书询问、私钥询问、替换公钥询问和签名询问。

伪造输出：如果敌手AI在上述游戏Game1中输出的对应于身份ID*和公钥P，在消息m*上的伪造签名σ*能够通过签名验证算法，则敌手AI赢得上述游戏Game1。

注意，在上述Game1中，不能发布对(ID*,P)的证书询问；也不能发布对(ID*,P,m*)的签名询问。

（2）游戏Game2：类型II敌手AII和挑战者C之间进行的游戏。

系统建立：输入系统安全参数，C执行系统初始化算法，获得系统公开参数和主私钥，发送给敌手AII。

预言机服务：敌手AII可以在多项式时间内向C发布密钥询问、Hash函数询问和签名询问。

伪造输出：如果敌手AII在上述游戏Game2中输出的对应于身份ID*和公钥P，在消息m*上的伪造签名σ*能够通过验证算法，则敌手AII赢得上述游戏Game2。

注意，在上述Game2中，不能发布对(ID*,P,m*)的签名询问，其中，PKID*是对应于ID*的密钥询问的输出，而且PKID*所对应的私钥没有被询问过。

最后，如果不存在多项式时间算法C，借助于敌手AI和AII，能够以一个不可忽略的优势赢得敌手A∈{AI,AII}和挑战者C之间的游戏Game∈{Game1,Game2}，则称一个基于证书的签名方案满足存在不可伪造性。

定义4（不可伪造性）一个基于证书签名方案是存在不可伪造的，如果不存在多项式时间算法C，借助于敌手AI和AII，能够以一个不可忽略的优势赢得敌手A∈{AI,AII}和挑战者C之间的游戏Game∈{Game1,Game2}。

定义5（安全性）一个基于证书签名方案是安全的，如果它是正确的并且在适应性选择消息、选择身份以及替换公钥攻击下具有存在不可伪造性。

4 提出的方案

基于双线性对，参照文献[20-21]，本文构造了一个有效的基于证书的数字签名方案，该方案包括系统初始化、密钥提取、证书生成、签名生成和签名验证五个算法。算法具体描述如下：

（1）系统初始化：给定系统安全参数k，CA建立系统参数如下：

（4）签名生成：设待签消息为m，则用户执行如下：

5 安全性与性能分析

5.1 安全性分析

本文的方案在构造时参照了文献[20]的方案，主要的区别在于所构造的方案使用的是双公钥PKA=(XA,YA)，因此，在签名验证时首先必须验证公钥PKA的合法性，一旦公钥验证等式不成立，则直接终止协议，因而可以更好地保障方案的安全性。其次，在生成证书之前，首先生成签名者的私钥SKA及公钥PKA，然后将公钥PKA绑定到证书CertA和签名σ中。这样一来，攻击者在选择好Hash函数H1后，就不能再计算公钥PKA，也无法完成替换公钥，克服了替换公钥的攻击。而且，由于CA将公钥PKA和签名者身份信息IDA一起Hash运算后产生证书CertA，这就使得CA无法针对特定用户生成特定的系统参数，可以有效克服恶意CA的攻击。

（1）正确性

定理1本文定义的基于证书的数字签名方案是正确的。

证明设σ是由签名算法所产生的对应于消息m、身份IDA和公钥PKIDA的签名，则方案的正确性可以容易地验证如下：

首先，通过以下等式验证公钥的合法性：

其次，验证所产生的签名σ=(U,V)满足签名验证等式，具体验证如下：

（2）不可伪造性：正如3.2节所述，基于证书签名方案的不可伪造性是通过敌手A∈{AI,AII}和挑战者C之间的游戏Game∈{Game1,Game2}来定义的。本方案的不可伪造性是在随机预言机模型下证明的，在证明过程中，参考了文献[23-24]的证明技巧。具体证明过程如下。

引理1在随机预言机模型和q-强SDH困难假设下，本文定义的基于证书的数字签名方案具有抵抗类型I敌手AI的存在不可伪造性。

证明假设AI能够以一定的优势攻破本文的方案，则可以构造一个算法C，利用AI解决q-强SDHP。设AI是一个类型I敌手，算法C的目标是对于消息m*和身份ID*，能够伪造有效的签名，解决q-强SDHP。

因此，如果AI能够攻破本文的签名方案，则算法C就可以利用AI获得q-强SDHP的一个解，从而出现矛盾。

引理2在随机预言机模型和E-inv-CDH困难问题假设下，本文定义的基于证书的数字签名方案具有抵抗敌手AII的存在不可伪造性。

证明假设AII能够以一定的优势攻破本文的方案，则可以构造一个算法C，利用AII解决E-inv-CDHP。设AII是一个类型II敌手，算法C的目标是对于消息m*和身份ID*，能够伪造有效的签名，解决E-inv-CDHP。

③H2询问：H2询问与引理1相同。

这样，算法C已成功输出一个E-inv-CDHP的解。

因此，如果AII能够攻破本文的签名方案，则算法C就可以利用AII获得E-inv-CDHP的一个解，从而出现矛盾。

定理2在随机预言机模型，以及q-强SDHP和E-inv-CDHP困难问题假设下，本文定义的基于证书签名方案在适应性选择消息、选择身份攻击下是存在不可伪造的。

证明由引理1和引理2，该定理可证。

结论1本文定义的基于证书的签名方案是安全的。

证明根据3.2节的定义5，显然，从上述定理1和定理2可证。

5.2 性能分析

考虑到对运算在计算时间上是相对比较耗费时间的一种运算，本文构造的方案通过预先计算g=e(P,P)，并将其并入系统参数中一起公开发布，提高了方案的效率，而且方案在签名产生阶段不需要任何对运算，签名验证阶段也仅仅需要一个对运算。下面，将把本文定义的新方案与现有的使用双线性对运算、基于证书数字签名方案进行一个分析比较，比较结果列于表1。其中，M表示标量乘；SM表示形如aP+bQ的同步标量乘；E表示指数运算；P表示双线性对运算。

表1 效率比较

从表1可见，本文定义的基于证书的数字签名方案在整体效率上是比较高的。

6 结束语

本文构造了一个高效的基于证书的数字签名方案，并在随机预言机模型下，以及q-强SDHP和E-inv-CDHP困难假设下，证明了所定义方案的安全性，同时简要分析了方案的性能，并进行了效率比较。由于在基于证书的数字签名系统中，证书管理简单，又不存在密钥的托管问题，因此，如何设计更多可证安全、有效的基于证书的签名方案是一项很有意义的工作，值得进一步的研究和探索。

[1]Shamir A.Identity-based cryptosystems and signature schemes[C]// LNCS 196：CRYPTO 1984.Berlin：Springer-Verlag，1985：47-53.

[2]Gentry C.Certificate-based encryption and the certificate revocation problem[C]//LNCS 2656：EUROCRPYT 2003.Berlin：Springer-Verlag，2003：272-293.

[3]Kang B G，Park J H，Hahn S G.A certificate-based signature scheme[C]//LNCS 2964：CT-RSA 2004.Berlin：Springer-Verlag，2004：99-111.

[4]Li J，Huang X，Mu Y，et al.Certificate-based signature：security model and efficient construction[C]//LNCS 4582：EuroPKI’07. Berlin：Springer，2007：110-125.

[5]Liu K，Baek J，Susilo W，et al.Certificate-based signature schemes without pairings or random oracles[EB/OL].[2013-03-10]. http：//eprint.iacr.org/.

[6]Wu Wei，Mu Yi，Susilo W，et al.Certificate-based signatures revisited[J].Journal of Universal Computer Science，2009，15（8）：1659-1684．

[7]王雯娟，黄振杰，郝艳华.一个高效的基于证书数字签名方案[J].计算机工程与应用，2011，47（6）：89-92.

[8]李志敏，徐馨，李存华.高效的基于证书数字签名设计方案[J].计算机应用研究，2012，19（4）：1430-1433.

[9]杨波，肖自碧.基于证书的签名方案[J].北京邮电大学学报，2012，35（5）：73-76.

[10]陈江山，黄振杰.一个高效的基于证书签名方案[J].计算机工程与应用，2012，48（30）：98-102.

[11]黄茹芬，农强，黄振杰.一类可证安全的基于证书盲签名[J].计算机应用研究，2012，29（12）：4622-4625.

[12]Li J G，Huang X Y，Zhang Y C.An efficient short certificate-based signature scheme[J].Journal of Systems and Software，2012，85（2）：314-322.

[13]吴晨煌，郭瑞景，陈智雄.高效的基于证书短签名方案[J].计算机系统应用，2013，22（2）：129-132.

[14]李继国，钱娜，黄欣沂，等.基于证书强指定验证者签名方案[J].计算机学报，2012，35（8）：1579-1587.

[15]黄茹芬，农强.基于证书的任意指定验证人签名方案[J].太原师范学院学报：自然科学版，2012，11（3）：70-73.

[16]周萍，何大可.高效不含双线性对的基于证书签名方案[J].计算机应用研究，2013，30（5）：1504-1507.

[17]Huang Rufen，Nong Qiang.A new efficient certificate-based signature scheme without bilinear pairings[C]//LNIT 31，2012：101-108.

[18]Girault M.Self-certified public keys[C]//LNCS 547：Eurocrypt 1991.Berlin：Springer-Verlag，1991：490-497.

[19]Liu J，Au M，Susilo W.Self-generated-certificate public key cryptography and certificateless signature/encryption scheme in the standard model[C]//ACM ASIACCS’07.New York：ACM Press，2007：273-283.

[20]张玉磊，王彩芬，张永洁，等.基于双线性对的高效无证书签名方案[J].计算机应用，2009，29（5）：1330-1333.

[21]明洋，王育民.有效的无证书签名方案[J].电子科技大学学报，2008，37（2）：175-177.

[22]Boneh D，Lynn B，Shacham H.Short signatures from the weil pairing[C]//LNCS 2248：Asiacrypt 2001.Berlin：Springer-Verlag，200l：514-532.

[23]Boneh D，Boyen X.Short signatures without random oracles[C]// LNCS 3027：EUROCRYPT 2004.Berlin：Springer-Verlag，2004：56-73.

[24]Choi K Y，Park J H，Hwang J Y，et al.Efficient certificateless signature schemes[C]//LNCS 4521：ACNS 2007.Berlin：Springer-Verlag，2007：443-458.

HUANG Rufen,NONG Qiang,HUANG Zhenjie

Department of Computer Science＆Engineering,Minnan Normal University,Zhangzhou,Fujian 363000,China

The certificate-based encryption is a new public key encryption paradigm which combines public key encryption and identity-based encryption while it preserves their features.This paper proposes an efficient construction of certificate-based signature scheme using bilinear maps,with rigorous security proofs under the random oracle model.The security of the scheme is based on the infeasibility of theq-strong Diffie-Hellman problem and the expand inversed computational Diffie-Hellman problem.The analysis shows that this new scheme satisfies the security requirements such as correctness and unforgeability,and has high security.It not only simplifies the certificate management process,but also overcomes the private key escrow problem.Furthermore,its overall performance is relatively high.

digital signature;certificate-based;random oracle model;provably secure;bilinear pairings

基于证书公钥密码系统是近年来提出的一种新型公钥密码体制，它结合了传统公钥密码体制和基于身份密码体制的优点，克服了其存在的问题。利用双线性映射，提出了一个基于证书的数字签名方案，在随机预言机模型下给出了严格的安全证明。方案的安全性基于q强Diffie-Hellman问题和扩展的逆计算Diffie-Hellman问题的困难性。分析表明，所构造的新方案满足正确性和存在不可伪造性，具有较高的安全性，不仅简化了证书管理过程，克服了密钥托管问题，而且方案的整体性能比较高。

数字签名；基于证书；随机预言模型；可证明安全；双线性对

A

TP309

10.3778/j.issn.1002-8331.1305-0222

HUANG Rufen,NONG Qiang,HUANG Zhenjie.Efficient provably secure certificate-based signature scheme.Computer Engineering and Applications,2013,49（24）：55-60.

国家自然科学基金（No.61170246）；福建省自然科学基金（No.2012J01295）。

黄茹芬（1963—），女，副教授，研究领域为密码学与网络安全；农强（1978—），男，讲师，研究领域为密码学与网络安全；黄振杰（1964—），男，博士后，教授，研究领域为密码学与信息安全。E-mail：zzhrf@126.com

2013-05-17

2013-08-22

1002-8331（2013）24-0055-06

CNKI出版日期：2013-10-11http://www.cnki.net/kcms/detail/11.2127.TP.20131011.1653.010.html