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

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

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

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

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

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

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

0 引言

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

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

1 預(yù)備知識(shí)

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

1.1 雙線性映射

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

(1)雙線性:對(duì)于任意的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)可計(jì)算:對(duì)于所有P,Q∈G1,存在一個(gè)計(jì)算e(P,Q)的有效算法．

1.2 困難假設(shè)

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

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

2 基于證書的聚合簽名

2.1 形式化定義

一個(gè)基于證書的聚合簽名方案由系統(tǒng)參數(shù)生成算法(Setup)、用戶密鑰生成算法(UKeyGen)、用戶公鑰證書生成算法(CertGen)、基于證書的簽名生成算法(CB-Sign)、聚合簽名生成算法(Aggregate)和簽名驗(yàn)證算法(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):給定一個(gè)用戶的身份信息IDi和系統(tǒng)公共參數(shù)params,生成用戶IDi的密鑰對(duì)(SKIDi,PKIDi)．

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

(4)CB-Sign(mi,params,IDi,SKIDi,PKIDi,CertIDi)→σi:給定系統(tǒng)公共參數(shù)params、一個(gè)用戶的身份信息IDi及其私鑰SKIDi和公鑰證書CertIDi、一個(gè)待簽消息mi,產(chǎn)生用戶IDi對(duì)消息mi的基于證書簽名σi．

(5)Aggregate(IDi,mi,σi)→δ(i=1,…,n):給定n個(gè)用戶的身份信息和消息簽名對(duì)(IDi,mi,σi),輸出這n個(gè)用戶IDi在這n個(gè)消息mi上的聚合簽名δ,其中i=1,…,n．

(6)Verify(δ,params,mi,IDi,PKIDi,CertIDi)→(Accept,Reject):給定系統(tǒng)公共參數(shù)params、n個(gè)用戶的身份信息及其公鑰、消息對(duì)(IDi,PKIDi,mi)和聚合簽名δ,輸出接受(Accept)或拒絕(Reject)．

2.2 攻擊者模型

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

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

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

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

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

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

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

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

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

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

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

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

6)Verify:輸入系統(tǒng)公共參數(shù)params、n個(gè)用戶的身份IDi及其公鑰PKIDi和n個(gè)消息對(duì)(IDi,PKIDi,mi)、聚合簽名δ,其中i=1,…,n,簽名驗(yàn)證如下:

1)對(duì)于i=1,…,n,計(jì)算:

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

成立則輸出Accept,接受簽名,否則輸出Reject,拒絕簽名．

4 安全性分析

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

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

=e(P,P)

=g

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

(2)存在不可偽造性:存在不可偽造性是指在不知道用戶集{ID1,ID2,…,IDn}中任何一個(gè)用戶私鑰的情況下,難于偽造一個(gè)能夠通過簽名驗(yàn)證算法Verify的有效聚合簽名．只有獲得了簽名私鑰的攻擊者產(chǎn)生的聚合簽名才能夠通過簽名驗(yàn)證算法Verify．考慮到基于證書聚合簽名存在兩類攻擊者AI和AII,因此,我們從以下兩個(gè)方面進(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)于解一個(gè)離散對(duì)數(shù)困難問題．所以,II類攻擊者AII由于不知道用戶IDi的私鑰,因而同樣無(wú)法成功偽造出一個(gè)合法的聚合簽名．從而,我們所構(gòu)造的基于證書聚合簽名是抗II類攻擊者的存在不可偽造．

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

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

5 結(jié)束語(yǔ)

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

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

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

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

1672-2027(2015)01-0049-05

TP390

A