一类安全有效的基于证书聚合签名

黄茹芬,农 强

(闽南师范大学 计算机学院, 福建 漳州 363000)

一类安全有效的基于证书聚合签名

黄茹芬,农 强

(闽南师范大学 计算机学院, 福建 漳州 363000)

聚合签名通过将n个签名者对n个消息的签名聚合为一个签名, 来提高签名与验证的效率．文中给出了基于证书聚合签名方案的形式化定义和安全模型,并构造了一个具体的方案．在计算Diffie-Hellman问题和离散对数问题困难假设下,该方案被证明是安全的．在形式上,方案使用证书作为用户临时签名密钥的一部分,简化了证书的管理和发布,克服了密钥托管问题,而且在签名产生阶段无需任何双线性对运算,在签名验算阶段也只需一个双线性对运算,不受签名人数的影响．与已有的聚合签名方案相比较,所提方案具有签名长度更短和计算代价更少等优点．

聚合签名;基于证书签名;双线性对;计算Diffie-Hellman问题;离散对数问题

0 引言

聚合签名是一种具有特殊性质的签名形式,可以对多个用户、多个消息同时提供不可否认服务[1]．不仅有效减少了签名存储空间,而且极大地降低了对网络传输带宽的要求．聚合签名是由Boneh等人[2]于2003年欧密会上首次提出的,Boneh等人的第一个聚合签名方案是基于BLS短签名方案[3]．在一个聚合签名方案中,n个用户对n个消息分别进行签名,然后聚合成一个单一的短签名,验证者仅仅需要对聚合后的短签名进行验证,即可检验n个消息是否确实是由n个用户分别签署的,显著提高了签名的验证与传输效率[1]．聚合签名具有广泛的应用,例如:在电子政务、电子商务和电子货币等场合,以及在合约签订[4]、级联认证[5]、无线路由[6]和密钥协商[7]等方面．由于聚合签名对很多应用具有良好的支撑,因此,近年来逐渐成为密码学研究者们关注的热点之一．基于证书的密码系统(CBE)是Gentry[8]首次在2003年欧洲密码学会议上提出的,它结合了传统公钥密码系统和基于身份密码系统的特点,简化了传统证书的发布和管理,解决了密钥托管问题．2004年,Kang等基于Gentry[8]的CBE,首次提出基于证书数字签名(CBS)的概念[9],同时给出了CBS的安全性定义和二个签名方案．随后,相继有研究者提了一些基于证书的数字签名方案．

2004年,Cheon等人提出第一个基于身份的聚合签名方案[10];2007年,Gong等人于2007年首次提出了基于无证书的聚合签名方案[11]．然而,他们的聚合签名方案是基于传统公钥密码体制、基于身份的密码体制或者基于无证书密码体制的．或多或少地存在证书发布和管理复杂、密钥托管困难或可信第三方信任级别较低等问题．本文基于证书公钥密码体制,结合基于证书签名的概念和聚合签名的形式,首次提出了基于证书的聚合签名(Certificate-based Aggregate Signature,CBAS),给出了基于证书聚合签名的形式化定义;其次,基于此定义,构造了一个基于证书聚合签名方案;第三,简要分析了所构造的基于证书聚合签名方案的安全性和计算效率．新方案不但不存在密钥托管问题的特点,并且满足聚合签名的安全需求．此外,与现存的聚合签名方案相比,新方案在签名产生阶段不需要任何双线性对运算,在签名验算阶段也仅需要一个双线性对运算．因此,在性能上具有明显的优势．

1 预备知识

简要回顾相关的一些数学问题,包括双线性映射和相关困难假设．

1.1 双线性映射

设G1是一个加法群,其阶为素数q,G2是一个同阶的乘法群,P为G2的一个任意生成元,设离散对数问题在群G1和G2中是难解的．e:G1×G1→G2是一个双线性映射,具有如下三个性质:

(1)双线性:对于任意的P,Q∈G1,a,b∈Zq,有e(P+Q,R)=e(P,R)e(Q,R),且e(P,Q+R)=e(P,Q)e(P,R);

(2)非退化:存在P,Q∈G1,满足e(P,Q)≠1;

(3)可计算:对于所有P,Q∈G1,存在一个计算e(P,Q)的有效算法．

1.2 困难假设

假设1DLP困难假设:若不存在一个概率多项式时间算法A,能够以至少ε的概率,在时间t内解决群G上的DLP问题,则我们称在群G上的离散对数问题是难解的．

假设2CDHP困难假设:若不存在一个概率多项式时间算法A,能够以至少ε的概率,在时间t内解决群G上的CDHP,则我们称群G上的CDH困难问题是难解的．

2 基于证书的聚合签名

2.1 形式化定义

一个基于证书的聚合签名方案由系统参数生成算法(Setup)、用户密钥生成算法(UKeyGen)、用户公钥证书生成算法(CertGen)、基于证书的签名生成算法(CB-Sign)、聚合签名生成算法(Aggregate)和签名验证算法(Verify)组成．

(1)Setup(1k)→(msk,params):给定系统安全参数k,生成系统公共参数params和主密钥msk,公开发布系统公共参数,由证书颁布机构(CA)秘密保管系统主密钥msk．

(2)UKeyGen(params,IDi)→(SKIDi,PKIDi):给定一个用户的身份信息IDi和系统公共参数params,生成用户IDi的密钥对(SKIDi,PKIDi)．

(3)CertGen(params,msk,IDi,PKIDi)→CertIDi:给定系统公共参数params和主密钥msk、一个用户的身份信息IDi及其公钥PKIDi,证书颁布机构CA返回对应于PKIDi的公钥证书CertIDi给用户IDi．

(4)CB-Sign(mi,params,IDi,SKIDi,PKIDi,CertIDi)→σi:给定系统公共参数params、一个用户的身份信息IDi及其私钥SKIDi和公钥证书CertIDi、一个待签消息mi,产生用户IDi对消息mi的基于证书签名σi．

(5)Aggregate(IDi,mi,σi)→δ(i=1,…,n):给定n个用户的身份信息和消息签名对(IDi,mi,σi),输出这n个用户IDi在这n个消息mi上的聚合签名δ,其中i=1,…,n．

(6)Verify(δ,params,mi,IDi,PKIDi,CertIDi)→(Accept,Reject):给定系统公共参数params、n个用户的身份信息及其公钥、消息对(IDi,PKIDi,mi)和聚合签名δ,输出接受(Accept)或拒绝(Reject)．

2.2 攻击者模型

在基于证书的签名系统中,一般需要考虑两种类型的攻击,分别为类型I攻击者AI和类型II攻击者AII的攻击．类似地,一个基于证书聚合签名同样要能够抵御这两类攻击,即AI和AII在适应性选择消息攻击下必须是存在不可伪造的．

(1)AI:AI模拟恶意用户的攻击,即AI不知道系统主密钥,但是可以任意替换用户的公钥;

(2)AII:AII模拟不诚实的证书颁布机构,即AII知道系统的主密钥,但不知道用户的私钥,不能替换任何用户的公钥．

3 一个高效的基于证书聚合签名方案

提出一个高效的基于证书聚合签名方案,由如下6个算法组成:

params={G1,G2,e,P,q,g,mpk,H1,H2}

其中mpk为系统主公钥,秘密保存系统主密钥msk．

4)CB-Sign:输入系统公共参数params、用户IDi的私钥及其对应的证书(SKIDi,CertIDi)和消息mi,按照如下方法计算用户IDi关于消息mi的基于证书签名:

1)计算临时签名钥SIDi=(SKIDi,CertIDi);

2)计算hi=H2(params||IDi||Ri,mi);

3)计算σi=(Zi+hisIDi)-1P．

输出签名σi作为用户IDi对消息mi的基于证书签名．

6)Verify:输入系统公共参数params、n个用户的身份IDi及其公钥PKIDi和n个消息对(IDi,PKIDi,mi)、聚合签名δ,其中i=1,…,n,签名验证如下:

1)对于i=1,…,n,计算:

QIDi=H1(IDi||PKIDi||Ri),hi=H2(params||IDi||Ri,mi);

成立则输出Accept,接受签名,否则输出Reject,拒绝签名．

4 安全性分析

一个基于证书聚合签名方案的安全性包括正确性和存在不可伪造性．本节简要对我们所构造的基于证书聚合签名方案的安全性进行分析．

(1)正确性:我们所构造的基于证书聚合签名方案可以通过Verify算法．验证如下:

=e(P,P)

=g

显然,我们所构造的基于证书聚合签名方案满足正确性．

(2)存在不可伪造性:存在不可伪造性是指在不知道用户集{ID1,ID2,…,IDn}中任何一个用户私钥的情况下,难于伪造一个能够通过签名验证算法Verify的有效聚合签名．只有获得了签名私钥的攻击者产生的聚合签名才能够通过签名验证算法Verify．考虑到基于证书聚合签名存在两类攻击者AI和AII,因此,我们从以下两个方面进行分析．

2) 抗II类攻击者的存在不可伪造:假设AII为II类攻击者,则AII拥有系统主密钥,但AII不知道用户IDi的私钥SKIDi(1≤i≤n)．由于AII拥有系统主密钥,因此,AII能够生成用户IDi的公钥证书,但AII不能替换用户IDi的任何公钥．此外,想要从PKIDi=sIDiP推算出用户IDi的私钥SKIDi,相当于解一个离散对数困难问题．所以,II类攻击者AII由于不知道用户IDi的私钥,因而同样无法成功伪造出一个合法的聚合签名．从而,我们所构造的基于证书聚合签名是抗II类攻击者的存在不可伪造．

从上述分析显然可知,本文构造的基于证书聚合签名方案是存在不可伪造性的．

3)效率分析:由于双线性对是一个计算代价很高的运算,计算一个双线性对运算所耗费的时间,大约是指数运算的2倍,至少是椭圆曲线上点乘运算的20倍[12]．在我们的方案中,通过预先计算g=e(P,P),将g并入系统公共参数中,所以我们的聚合签名方案在产生签名时不需要任何双线性对运算,而在验证签名时也只需要进行一次双线性对运算．因此,我们所构造的基于证书聚合签名方案的整体计算效率比较高,而且在性能上也具有相当的优势,签名长度更短．

5 结束语

本文首先提出了基于证书聚合签名,给出了其形式化定义;其次,利用双线性对构造了一个有效的基于证书聚合签名方案;然后,简要分析了所构造方案的安全性;最后,分析了新方案的效率和性能．与传统的基于公钥密码体制的聚合签名方案和基于身份的聚合签名方案相比,我们的方案不仅简化了证书发布、存储和管理,解决了密钥托管问题,而且具有整体效率上的优势和更短的签名长度．

[1] 杨 涛,孔令波,胡建成,陈 钟.聚合签名及其应研究综述[J].计算机研究与发展,2012(49):192-199

[2] Boneh D,Gentry C.Aggregate and verifiably encrypted signatures from bilinear maps[C]//Proc.Of Advances in Cryptography-Eurocrypt 2003,2656 of LNCS,2003:416-432

[3] Boneh D,Lynn B,Shacham H.Short signatures from the weil Pairing[J].Journal of Cryptology,2004,17(4):297-319

[4] Wang Chi hung,Kuo Yan-sheng.An Efficient Contract Signing Protocol Using the Aggregate Signature Scheme to Protect Signers Privacy and Promote Reliability[C]//Proc.of ACM SIGOPS Operating Systems Review 2005.Brighton,United Kingdom,2005,39:66-79

[5] Yao Dan-fen g,Tamassia R.Cascaded Authorization with Anonymous-signer Aggregate Signatures[C]//Proc.of the 2006 IEEE Workshop on Information Assurance.West Point,New York,2006:84-91

[6] Wang Sheng-bao,Cao Zhen-fu,Wang Qin,et al.Authenticated Key Agreement Protocol Using Bilinear Aggregate Signatures[C]//Proc.of Global Mobile Congress 2005.Delson Group Inc,2005:328-332

[7] Zhu Hua-fei,Bao Feng,Li Tie-yan,et al.Sequential Aggregate Signatures for Wireless Routing Protocols[C]//Proc.of IEEE Wireless Communications and Networking Conference 2005.New Orleans,LA USA,2005:2436-2439

[8] Gentry C.Certificate-based encryption and the certificate revocation problem[C]//Biham E.LNCS 2656:Cryptology-Eurocrypt2003.[S.l.]:Springer-Verlag,2003:272-293

[9] B G Kang,J H. Park and S. G.Hahn. A certificate-based signature scheme[C]//Proc.Of Ct-RSA’04.[S.l.]:Springer,2004:99-111

[10] Jung Hee Cheon,Yongdae Kim,Hyo Jin Yoon.A new ID-based aggregate signature with batch verification[OL].http//eprint.iacr.org/2004/131

[11] Zhang F,Safavi-Naini R,Susilo W.An efficient signature scheme from bilinear pairings and its applications[C]//Lncs:PKC 2004.Singapore:Springer-Verlag,2004

[12] X. Cao,W.Kou,X.Du.A pairing-free identified-based authenticated key agreement protocol with minimal message exchanges[J].Information Sciences,2010,180(15):2895-2903

Secure and Efficient Certificate-based Aggregate Signature

Huang Rufen,Nong Qiang

(College of Computer Science,Minnan Normal University,Zhangzhou 363000, China)

To give the formal definition and security model of certificate-based aggregate signature scheme. The authors also To construct a concrete scheme which is provably secure assuming the computational Diffie-Hellman problem and the discrete logarithm problem are hard. In the form, the certificate in our scheme is implicitly used as part of user’s temporary signing key, so the key escrow problem can be solved and the key management and dissemination can be simplified in our scheme. The proposed certificate-based aggregate signature scheme does not require any bilinear pairing operations in aggregation stage, while requires only one bilinear pairing operation in verify stage which is independent of the number of the signers. Compared with the other existing secure aggregate signature schemes, our scheme enjoys shorter signature length and less running time.

aggregate signature; certificate-based signature; bilinear pairings; CDHP;DLP

2014-10-28

国家自然科学基金资助项目(61170246, 61373140).

黄茹芬(1963-),女,硕士,闽南师范大学副教授,主要从事密码学、网络安全研究.

1672-2027(2015)01-0049-05

TP390

A