一類安全有效的基于證書聚合簽名

黃茹芬,農(nóng) 強(qiáng)

(閩南師范大學(xué) 計算機(jī)學(xué)院, 福建 漳州 363000)

一類安全有效的基于證書聚合簽名

黃茹芬,農(nóng) 強(qiáng)

(閩南師范大學(xué) 計算機(jī)學(xué)院, 福建 漳州 363000)

聚合簽名通過將n個簽名者對n個消息的簽名聚合為一個簽名, 來提高簽名與驗證的效率．文中給出了基于證書聚合簽名方案的形式化定義和安全模型,并構(gòu)造了一個具體的方案．在計算Diffie-Hellman問題和離散對數(shù)問題困難假設(shè)下,該方案被證明是安全的．在形式上,方案使用證書作為用戶臨時簽名密鑰的一部分,簡化了證書的管理和發(fā)布,克服了密鑰托管問題,而且在簽名產(chǎn)生階段無需任何雙線性對運算,在簽名驗算階段也只需一個雙線性對運算,不受簽名人數(shù)的影響．與已有的聚合簽名方案相比較,所提方案具有簽名長度更短和計算代價更少等優(yōu)點．

聚合簽名;基于證書簽名;雙線性對;計算Diffie-Hellman問題;離散對數(shù)問題

0 引言

聚合簽名是一種具有特殊性質(zhì)的簽名形式,可以對多個用戶、多個消息同時提供不可否認(rèn)服務(wù)[1]．不僅有效減少了簽名存儲空間,而且極大地降低了對網(wǎng)絡(luò)傳輸帶寬的要求．聚合簽名是由Boneh等人[2]于2003年歐密會上首次提出的,Boneh等人的第一個聚合簽名方案是基于BLS短簽名方案[3]．在一個聚合簽名方案中,n個用戶對n個消息分別進(jìn)行簽名,然后聚合成一個單一的短簽名,驗證者僅僅需要對聚合后的短簽名進(jìn)行驗證,即可檢驗n個消息是否確實是由n個用戶分別簽署的,顯著提高了簽名的驗證與傳輸效率[1]．聚合簽名具有廣泛的應(yīng)用,例如:在電子政務(wù)、電子商務(wù)和電子貨幣等場合,以及在合約簽訂[4]、級聯(lián)認(rèn)證[5]、無線路由[6]和密鑰協(xié)商[7]等方面．由于聚合簽名對很多應(yīng)用具有良好的支撐,因此,近年來逐漸成為密碼學(xué)研究者們關(guān)注的熱點之一．基于證書的密碼系統(tǒng)(CBE)是Gentry[8]首次在2003年歐洲密碼學(xué)會議上提出的,它結(jié)合了傳統(tǒng)公鑰密碼系統(tǒng)和基于身份密碼系統(tǒng)的特點,簡化了傳統(tǒng)證書的發(fā)布和管理,解決了密鑰托管問題．2004年,Kang等基于Gentry[8]的CBE,首次提出基于證書數(shù)字簽名(CBS)的概念[9],同時給出了CBS的安全性定義和二個簽名方案．隨后,相繼有研究者提了一些基于證書的數(shù)字簽名方案．

2004年,Cheon等人提出第一個基于身份的聚合簽名方案[10];2007年,Gong等人于2007年首次提出了基于無證書的聚合簽名方案[11]．然而,他們的聚合簽名方案是基于傳統(tǒng)公鑰密碼體制、基于身份的密碼體制或者基于無證書密碼體制的．或多或少地存在證書發(fā)布和管理復(fù)雜、密鑰托管困難或可信第三方信任級別較低等問題．本文基于證書公鑰密碼體制,結(jié)合基于證書簽名的概念和聚合簽名的形式,首次提出了基于證書的聚合簽名(Certificate-based Aggregate Signature,CBAS),給出了基于證書聚合簽名的形式化定義;其次,基于此定義,構(gòu)造了一個基于證書聚合簽名方案;第三,簡要分析了所構(gòu)造的基于證書聚合簽名方案的安全性和計算效率．新方案不但不存在密鑰托管問題的特點,并且滿足聚合簽名的安全需求．此外,與現(xiàn)存的聚合簽名方案相比,新方案在簽名產(chǎn)生階段不需要任何雙線性對運算,在簽名驗算階段也僅需要一個雙線性對運算．因此,在性能上具有明顯的優(yōu)勢．

1 預(yù)備知識

簡要回顧相關(guān)的一些數(shù)學(xué)問題,包括雙線性映射和相關(guān)困難假設(shè)．

1.1 雙線性映射

設(shè)G1是一個加法群,其階為素數(shù)q,G2是一個同階的乘法群,P為G2的一個任意生成元,設(shè)離散對數(shù)問題在群G1和G2中是難解的．e:G1×G1→G2是一個雙線性映射,具有如下三個性質(zhì):

(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 困難假設(shè)

假設(shè)1DLP困難假設(shè):若不存在一個概率多項式時間算法A,能夠以至少ε的概率,在時間t內(nèi)解決群G上的DLP問題,則我們稱在群G上的離散對數(shù)問題是難解的．

假設(shè)2CDHP困難假設(shè):若不存在一個概率多項式時間算法A,能夠以至少ε的概率,在時間t內(nèi)解決群G上的CDHP,則我們稱群G上的CDH困難問題是難解的．

2 基于證書的聚合簽名

2.1 形式化定義

一個基于證書的聚合簽名方案由系統(tǒng)參數(shù)生成算法(Setup)、用戶密鑰生成算法(UKeyGen)、用戶公鑰證書生成算法(CertGen)、基于證書的簽名生成算法(CB-Sign)、聚合簽名生成算法(Aggregate)和簽名驗證算法(Verify)組成．

(1)Setup(1k)→(msk,params):給定系統(tǒng)安全參數(shù)k,生成系統(tǒng)公共參數(shù)params和主密鑰msk,公開發(fā)布系統(tǒng)公共參數(shù),由證書頒布機(jī)構(gòu)(CA)秘密保管系統(tǒng)主密鑰msk．

(2)UKeyGen(params,IDi)→(SKIDi,PKIDi):給定一個用戶的身份信息IDi和系統(tǒng)公共參數(shù)params,生成用戶IDi的密鑰對(SKIDi,PKIDi)．

(3)CertGen(params,msk,IDi,PKIDi)→CertIDi:給定系統(tǒng)公共參數(shù)params和主密鑰msk、一個用戶的身份信息IDi及其公鑰PKIDi,證書頒布機(jī)構(gòu)CA返回對應(yīng)于PKIDi的公鑰證書CertIDi給用戶IDi．

(4)CB-Sign(mi,params,IDi,SKIDi,PKIDi,CertIDi)→σi:給定系統(tǒng)公共參數(shù)params、一個用戶的身份信息IDi及其私鑰SKIDi和公鑰證書CertIDi、一個待簽消息mi,產(chǎn)生用戶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):給定系統(tǒng)公共參數(shù)params、n個用戶的身份信息及其公鑰、消息對(IDi,PKIDi,mi)和聚合簽名δ,輸出接受(Accept)或拒絕(Reject)．

2.2 攻擊者模型

在基于證書的簽名系統(tǒng)中,一般需要考慮兩種類型的攻擊,分別為類型I攻擊者AI和類型II攻擊者AII的攻擊．類似地,一個基于證書聚合簽名同樣要能夠抵御這兩類攻擊,即AI和AII在適應(yīng)性選擇消息攻擊下必須是存在不可偽造的．

(1)AI:AI模擬惡意用戶的攻擊,即AI不知道系統(tǒng)主密鑰,但是可以任意替換用戶的公鑰;

(2)AII:AII模擬不誠實的證書頒布機(jī)構(gòu),即AII知道系統(tǒng)的主密鑰,但不知道用戶的私鑰,不能替換任何用戶的公鑰．

3 一個高效的基于證書聚合簽名方案

提出一個高效的基于證書聚合簽名方案,由如下6個算法組成:

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

其中mpk為系統(tǒng)主公鑰,秘密保存系統(tǒng)主密鑰msk．

4)CB-Sign:輸入系統(tǒng)公共參數(shù)params、用戶IDi的私鑰及其對應(yīng)的證書(SKIDi,CertIDi)和消息mi,按照如下方法計算用戶IDi關(guān)于消息mi的基于證書簽名:

1)計算臨時簽名鑰SIDi=(SKIDi,CertIDi);

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

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

輸出簽名σi作為用戶IDi對消息mi的基于證書簽名．

6)Verify:輸入系統(tǒng)公共參數(shù)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 安全性分析

一個基于證書聚合簽名方案的安全性包括正確性和存在不可偽造性．本節(jié)簡要對我們所構(gòu)造的基于證書聚合簽名方案的安全性進(jìn)行分析．

(1)正確性:我們所構(gòu)造的基于證書聚合簽名方案可以通過Verify算法．驗證如下:

=e(P,P)

=g

顯然,我們所構(gòu)造的基于證書聚合簽名方案滿足正確性．

(2)存在不可偽造性:存在不可偽造性是指在不知道用戶集{ID1,ID2,…,IDn}中任何一個用戶私鑰的情況下,難于偽造一個能夠通過簽名驗證算法Verify的有效聚合簽名．只有獲得了簽名私鑰的攻擊者產(chǎn)生的聚合簽名才能夠通過簽名驗證算法Verify．考慮到基于證書聚合簽名存在兩類攻擊者AI和AII,因此,我們從以下兩個方面進(jìn)行分析．

2) 抗II類攻擊者的存在不可偽造:假設(shè)AII為II類攻擊者,則AII擁有系統(tǒng)主密鑰,但AII不知道用戶IDi的私鑰SKIDi(1≤i≤n)．由于AII擁有系統(tǒng)主密鑰,因此,AII能夠生成用戶IDi的公鑰證書,但AII不能替換用戶IDi的任何公鑰．此外,想要從PKIDi=sIDiP推算出用戶IDi的私鑰SKIDi,相當(dāng)于解一個離散對數(shù)困難問題．所以,II類攻擊者AII由于不知道用戶IDi的私鑰,因而同樣無法成功偽造出一個合法的聚合簽名．從而,我們所構(gòu)造的基于證書聚合簽名是抗II類攻擊者的存在不可偽造．

從上述分析顯然可知,本文構(gòu)造的基于證書聚合簽名方案是存在不可偽造性的．

3)效率分析:由于雙線性對是一個計算代價很高的運算,計算一個雙線性對運算所耗費的時間,大約是指數(shù)運算的2倍,至少是橢圓曲線上點乘運算的20倍[12]．在我們的方案中,通過預(yù)先計算g=e(P,P),將g并入系統(tǒng)公共參數(shù)中,所以我們的聚合簽名方案在產(chǎn)生簽名時不需要任何雙線性對運算,而在驗證簽名時也只需要進(jìn)行一次雙線性對運算．因此,我們所構(gòu)造的基于證書聚合簽名方案的整體計算效率比較高,而且在性能上也具有相當(dāng)?shù)膬?yōu)勢,簽名長度更短．

5 結(jié)束語

本文首先提出了基于證書聚合簽名,給出了其形式化定義;其次,利用雙線性對構(gòu)造了一個有效的基于證書聚合簽名方案;然后,簡要分析了所構(gòu)造方案的安全性;最后,分析了新方案的效率和性能．與傳統(tǒng)的基于公鑰密碼體制的聚合簽名方案和基于身份的聚合簽名方案相比,我們的方案不僅簡化了證書發(fā)布、存儲和管理,解決了密鑰托管問題,而且具有整體效率上的優(yōu)勢和更短的簽名長度．

[1] 楊 濤,孔令波,胡建成,陳 鐘.聚合簽名及其應(yīng)研究綜述[J].計算機(jī)研究與發(fā)展,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

國家自然科學(xué)基金資助項目(61170246, 61373140).

黃茹芬(1963-),女,碩士,閩南師范大學(xué)副教授,主要從事密碼學(xué)、網(wǎng)絡(luò)安全研究.

1672-2027(2015)01-0049-05

TP390

A