無(wú)證書體制下的多接收者簽密密鑰封裝機(jī)制

孫銀霞 李 暉 李小青

(西安電子科技大學(xué)計(jì)算機(jī)網(wǎng)絡(luò)與信息安全教育部重點(diǎn)實(shí)驗(yàn)室 西安 710071)

1 引言

無(wú)證書公鑰密碼體制首先是由Al-Riyami和Paterson于2003年提出的[1]。該密碼體制既克服了傳統(tǒng)公鑰體制需要管理大量公鑰證書的缺點(diǎn)，又克服了基于身份公鑰體制[2,3]的密鑰托管問(wèn)題。用戶私鑰由兩部分組成，一部分由密鑰生成中心KGC生成，另一部分由用戶自己選取，因此完整的私鑰只有用戶自己知道；用戶公鑰由用戶生成，且無(wú)需公鑰證書。

“簽密”是由Zheng于1997年提出的一個(gè)概念[4,5]，旨在以小于“簽名再加密”的代價(jià)同時(shí)實(shí)現(xiàn)信息的認(rèn)證性和保密性?；谏矸莺蜔o(wú)證書體制下對(duì)簽密的研究也已經(jīng)取得了一些進(jìn)展，比如文獻(xiàn)[6-10]。然而，通常的簽密方案要求被傳輸?shù)南⑷∽阅硞€(gè)特定的集合，這就限制了其應(yīng)用范圍。為了取消這種限制，Dent于2005年提出了混合簽密的概念[11,12]。一個(gè)混合簽密方案由兩部分構(gòu)成：簽密密鑰封裝機(jī)制(SC-KEM)和數(shù)據(jù)封裝機(jī)制(DEM)。SC-KEM運(yùn)用公鑰技術(shù)封裝一個(gè)對(duì)稱密鑰K，然后DEM運(yùn)用對(duì)稱加密技術(shù)和對(duì)稱密鑰K加密任意長(zhǎng)的消息。由于SC-KEM和DEM各自獨(dú)立，所以我們可以分別研究SC-KEM和DEM，這不僅有利于構(gòu)造安全又高效的簽密方案，而且可以處理任意長(zhǎng)度的消息。近幾年，混合簽密已引起了廣泛的關(guān)注，并取得了一些成果比如文獻(xiàn)[13-15]。在2009年，Li等人[16]將混合簽密的概念推廣到無(wú)證書體制下，提出了無(wú)證書混合簽密的概念，指出無(wú)證書混合簽密可以由無(wú)證書簽密密鑰封裝機(jī)制(CLSC-KEM)和數(shù)據(jù)封裝機(jī)制構(gòu)成，并且給出了一般構(gòu)造和一個(gè)具體方案。隨后，Selvi等人[17]指出Li等人[16]的方案不具有存在不可偽造性，并改進(jìn)了方案。然而，文獻(xiàn)[17]中給出的攻擊并不成立，因?yàn)閷?duì)稱密鑰K'的改變會(huì)引起標(biāo)簽τ(=EncK'(m))的改變，從而導(dǎo)致W的改變，所以ψ*=(U, W)不是K'的一個(gè)有效封裝(從發(fā)送者IDA到接收者IDB*)，攻擊失敗。

現(xiàn)在考慮無(wú)證書體制下的這樣一種情形：某個(gè)用戶A給n個(gè)用戶發(fā)送一個(gè)消息m (任意長(zhǎng)度)。當(dāng)然，A可以對(duì)每個(gè)接收者分別運(yùn)行一次無(wú)證書混合簽密算法，但這樣做的運(yùn)算量太大，不僅需要進(jìn)行n次數(shù)據(jù)封裝，而且通常需要計(jì)算n個(gè)雙線性對(duì)(根據(jù)MIRACL的運(yùn)行結(jié)果，對(duì)于80 bit的安全級(jí)別，計(jì)算一個(gè)Tate對(duì)需要20 ms，而計(jì)算一個(gè)素?cái)?shù)模指數(shù)只需要8.8 ms)，這對(duì)于計(jì)算資源有限的通信環(huán)境(比如Ad hoc網(wǎng)絡(luò))而言，負(fù)擔(dān)太重。那么，有沒(méi)有方法可以簡(jiǎn)化運(yùn)算以降低通信開(kāi)銷呢？

針對(duì)以上問(wèn)題，本文提出了一個(gè)新的概念：無(wú)證書體制下的多接收者簽密密鑰封裝機(jī)制(mCLSCKEM)。給出了mCLSC-KEM的定義以及安全模型，并構(gòu)造了一個(gè)高效的方案。由該mCLSC-KEM方案得到的無(wú)證書混合簽密算法僅需1次雙線性對(duì)運(yùn)算和1次數(shù)據(jù)封裝，大大降低了通信開(kāi)銷。在隨機(jī)預(yù)言模型下，基于Gap雙線性Diffie-Hellman問(wèn)題，本文的方案是可證明安全的。

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

本節(jié)定義無(wú)證書體制下的多接收者簽密密鑰封裝機(jī)制(mCLSC-KEM)及其安全模型。

2.1 mCLSC-KEM定義

本文把單接收者無(wú)證書簽密密鑰封裝機(jī)制CLSC-KEM[16]推廣到多接收者的情形。無(wú)證書的多接收者簽密密鑰封裝機(jī)制(mCLSC-KEM)由以下5個(gè)算法組成：

系統(tǒng)初始化算法(Setup)：由KGC完成，輸入安全參數(shù)k，輸出主密鑰s和系統(tǒng)參數(shù)params，其中s保密，params公開(kāi)。

提取部分私鑰算法(Extract-Partial-Private-Key)：由KGC完成，輸入params，s和一個(gè)用戶身份ID，輸出該用戶的部分私鑰DID。

生成用戶密鑰算法(Generate-User-Keys)：由用戶完成，輸入params和用戶身份ID，輸出一個(gè)秘密值xID和公鑰PKID。秘密值xID和部分私鑰DID構(gòu)成用戶的完整私鑰SKID。

密鑰封裝算法(Encap)：由發(fā)送者完成，輸入params，發(fā)送者私鑰、身份和公鑰，n個(gè)接收者的身份{IDi}和公鑰{PKi}，以及一個(gè)標(biāo)簽τ，輸出一個(gè)對(duì)稱密鑰K和一個(gè)密文?。

解封裝算法(Decap)：由接收者IDi(i∈[1,n]∩Z+)完成，輸入params，密文?，接收者私鑰、身份和公鑰，發(fā)送者身份和公鑰，以及一個(gè)標(biāo)簽τ，輸出一個(gè)對(duì)稱密鑰K或者“拒絕”(表示密文無(wú)效)。

2.2 mCLSC-KEM安全模型

存在兩類攻擊者：第1類攻擊者AI和第2類攻擊者AII。第1類攻擊者是一個(gè)普通的攻擊者，他不知道KGC的私鑰，但是可以替換任何用戶公鑰；第2類攻擊者指好奇但誠(chéng)實(shí)的KGC，他已知任何用戶的部分私鑰，但是不替換任何用戶公鑰。

本文通過(guò)以下攻擊者與挑戰(zhàn)者之間的兩個(gè)游戲來(lái)定義mCLSC-KEM的安全性。這兩類攻擊者在攻擊階段可以作如下詢問(wèn)：

提取部分私鑰詢問(wèn)：AI詢問(wèn)用戶ID的部分私鑰。挑戰(zhàn)者運(yùn)行算法Extract-Partial-Private-Key(params, s, ID) →DID, 并把DID返回給AI。

提取秘密值詢問(wèn)：AI，AII詢問(wèn)用戶ID的秘密值。挑戰(zhàn)者運(yùn)行算法Generate-User-Key(params,ID)→xID, 并把xID返回給AI、AII。如果該用戶的公鑰已被替換，則攻擊者不能作此詢問(wèn)。

公鑰詢問(wèn)：AI，AII詢問(wèn)用戶ID的公鑰。挑戰(zhàn)者運(yùn)行算法Generate-User-Key(params, ID)→PKID, 并把PKID返回給攻擊者。

替換公鑰：AI替換用戶ID的公鑰。AI可以用任何值替換用戶ID的公鑰。

Encap詢問(wèn)：AI，AII對(duì)(IDs, {IDi},τ)進(jìn)行Encap詢問(wèn)。挑戰(zhàn)者運(yùn)行算法Encap(params, SKs,IDs, PKs, {IDi},{PKi},τ)→(K,?), 并把(K,?)返回給攻擊者。

Decap詢問(wèn)：AI，AII對(duì)(IDs, IDi，τ, ?)進(jìn)行Decap詢問(wèn)。挑戰(zhàn)者運(yùn)行算法Decap(params, IDs,PKs, SKi, IDi,PKi,τ,?)→K/“拒絕”，并把K或“拒絕”返回給攻擊者。

2.2.1 認(rèn)證性

初始化：挑戰(zhàn)者運(yùn)行算法Setup，并把params發(fā)送給攻擊者AI；把params和s同時(shí)發(fā)送給攻擊者AII。

攻擊：攻擊者作一系列如上詢問(wèn)。

偽造：攻擊者輸出(τ*,?*,, L*)。若?*有效，則攻擊者贏得游戲。AI不能同時(shí)詢問(wèn)過(guò)的部分私鑰和秘密值，或者同時(shí)詢問(wèn)過(guò)IDs*的部分私鑰和替換過(guò)的公鑰；AII不能詢問(wèn)過(guò)IDs*的秘密值。?*不能來(lái)源于攻擊者對(duì)(, L*,τ*)的Encap詢問(wèn)。定義攻擊者在以上游戲中獲勝的優(yōu)勢(shì)為攻擊者贏得游戲的概率。

定義1 如果沒(méi)有任何多項(xiàng)式有界的攻擊者在以上游戲中以不可忽略的優(yōu)勢(shì)獲勝，那么稱一個(gè)mCLSC-KEM方案在選擇消息攻擊下具有強(qiáng)不可偽造性(sUF-CMA)。

2.2.2 保密性

初始化：挑戰(zhàn)者運(yùn)行算法Setup，并把params發(fā)送給攻擊者AI；把params和s同時(shí)發(fā)送給攻擊者AII。

第1階段攻擊：攻擊者作一系列如上詢問(wèn)。

第2階段攻擊：攻擊者繼續(xù)進(jìn)行如第一階段的詢問(wèn)，但是AII不能同時(shí)詢問(wèn)任何∈L*的部分私鑰和秘密值，也不能同時(shí)詢問(wèn)的部分私鑰和替換其公鑰；AIII不能詢問(wèn)任何∈L*的秘密值。另外，攻擊者不能對(duì)(,∈L*,τ*,?*)進(jìn)行Decap詢問(wèn)，除非替換發(fā)送者或者接收者的公鑰。

猜測(cè)：攻擊者輸出猜測(cè)β∈{0,1}。定義攻擊者在以上游戲中獲勝的優(yōu)勢(shì)為|2Pr[β=0]?1|。

定義2 如果沒(méi)有任何多項(xiàng)式有界的攻擊者在以上游戲中以不可忽略的優(yōu)勢(shì)獲勝，那么稱一個(gè)mCLSC-KEM方案在選擇密文攻擊下具有不可區(qū)分性(IND-CCA)。

3 一個(gè)高效的mCLSC-KEM方案

本節(jié)給出一個(gè)高效的mCLSC-KEM方案，具體構(gòu)造如下：

初始化(Setup)：設(shè)G1和G2分別是階為素?cái)?shù)q的加法循環(huán)群和乘法循環(huán)群，P是G1的一個(gè)生成元，: G1×G1→G2是一個(gè)雙線性對(duì)。H1，H2，H3和H4是4個(gè)hash函數(shù)，其中H1:{0,1}*→G1，H2:{0,1}*→{0,1}n，H3:{0,1}*→G1和H4:{0,1}*→G1，這里n表示DEM的密鑰長(zhǎng)度。隨機(jī)選擇s∈Zq*作為KGC的私鑰，并計(jì)算其公鑰P0= sP。則系統(tǒng)的公共參數(shù)為params = {G1,G2,q，P，，H1，H2，H3，H4，n，P0}。

提取部分私鑰(Extract-Partial-Private-Key)：輸入一個(gè)用戶身份ID，KGC計(jì)算QID=H1(ID)，再用自己的私鑰s計(jì)算該用戶的部分私鑰DID=sH1(ID)。

生成用戶密鑰(Generate-User-Keys)：用戶ID隨機(jī)選擇xID∈Zq*作為其秘密值，并計(jì)算其公鑰PKID= xIDP。則該用戶的完整私鑰為(DID,xID)。

密鑰封裝(Encap)：由發(fā)送者運(yùn)行。輸入params，發(fā)送者私鑰(Ds, xs)、身份IDs和公鑰PKs，n個(gè)接收者的身份{IDi}和公鑰{PKi}，該算法按如下步驟進(jìn)行：

(3)計(jì)算對(duì)稱密鑰K=H2(U, T, rY,{IDi},{PKi})；

(4)輸入一個(gè)標(biāo)簽τ，計(jì)算W = Ds+rH3(U, τ,IDs,PKs)+xsH4(U, τ,IDs,PKs)；

(5)輸出(K，?)，這里?=(U, W,{Vi},{Yi})。

解封裝(Decap)：由接收者運(yùn)行。輸入params，接收者私鑰(Di, xi)、身份IDi和公鑰PKi，發(fā)送者身份IDs和公鑰PKs，標(biāo)簽τ，以及密文?= (U, W,{Vi},{Yi})，該算法按如下步驟進(jìn)行：

(1)計(jì)算H=H3(U, τ,IDs,PKs)和H'=H4(U, τ,IDs,PKs)，并驗(yàn)證等式是否成立。

4 安全性和效率分析

在隨機(jī)預(yù)言模型下，基于GDH′問(wèn)題、CDH問(wèn)題和GBDH問(wèn)題[16]，本文的mCLSC-KEM方案滿足sUF-CMA安全性和IND-CCA安全性。

在無(wú)證書公鑰體制下，當(dāng)一個(gè)用戶給n個(gè)用戶簽密一個(gè)消息m(任意長(zhǎng)度)時(shí)，他可以對(duì)每個(gè)用戶分別使用無(wú)證書混合簽密算法[16]，如表1所示，共需計(jì)算n個(gè)雙線性對(duì)(p)和n次數(shù)據(jù)封裝(DEM)，且隨著接收者數(shù)量的增加而增加。眾所周知，雙線性對(duì)運(yùn)算復(fù)雜，需要消耗較多的計(jì)算資源，所以在實(shí)際應(yīng)用尤其是計(jì)算資源有限的通信環(huán)境中應(yīng)當(dāng)盡量減少雙線性對(duì)的數(shù)量。本文的方案較好地做到了這一點(diǎn)，它僅需計(jì)算1個(gè)雙線性對(duì)和1次數(shù)據(jù)封裝，且不隨接收者數(shù)量的增加而增加。另外，消息的密文長(zhǎng)度也比一般性構(gòu)造短。表1中p表示雙線性對(duì)，|P|表示G1中一個(gè)元素的長(zhǎng)度，|m|表示消息m的長(zhǎng)度。

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

本文提出了一個(gè)新的概念：無(wú)證書體制下的多接收者簽密密鑰封裝機(jī)制(mCLSC-KEM)。給出了mCLSC-KEM的定義和安全模型，并且構(gòu)造了一個(gè)高效的方案。與一般性構(gòu)造相比，本文的方案不僅減少(n-1)次數(shù)據(jù)封裝，而且減少(n-1)次雙線性對(duì)運(yùn)算(n指接收者數(shù)量)，從而大大提高了通信效率。在隨機(jī)預(yù)言模型和Gap雙線性Diffie-Hellman(GBDH)假設(shè)下，方案是可證明安全的。

可以運(yùn)用twinning技術(shù)[18]使方案的安全性歸結(jié)于標(biāo)準(zhǔn)的雙線性Diffie-Hellman問(wèn)題，以避免使用Gap雙線性Diffie-Hellman假設(shè)，但與此同時(shí)計(jì)算復(fù)雜性增加了。如何在兩者之間實(shí)現(xiàn)最優(yōu)化是一個(gè)待研究的問(wèn)題。

[1] Al-Riyami S S and Paterson K G. Certificateless public key cryptography[C]. ASIACRYPT 2003, Berlin: Springer-Verlag,2003, LNCS 2894: 452-473.

[2] Shamir A. Identity-based cryptosystems and signature schemes[C]. CRYPTO 1984, Berlin: Springer-Verlag, 1984,LNCS 196: 47-53.

[3] Boneh D and Franklin M. Identity-based encryption from the Weil pairing[C]. CRYPTO 2001, Berlin: Springer-Verlag,2001, LNCS 2139: 213-229.

[4] Zheng Y. Digital signcryption or how to achieve cost(Signature & encryption) << cost(Signature) + cost(Encryption) [C]. CRYPTO 1997, Berlin: Springer-Verlag,1997, LNCS 1294: 165-179.

[5] An JH, Dodis Y, and Rabin T. On the security of joint signature and encryption[C]. EUROCRYPT 2002, Berlin:Springer-Verlag, 2002, LNCS 2332: 83-107.

[6] Boyen X. Multipurpose identity-based signcryption: a swiss army knife for identity-based cryptography[C]. Cryptology-CRYPTO 2003, Berlin: Springer-Verlag, 2003, LNCS 2729:383-399.

[7] Barreto PSLM, Libert B, McCullagh N, and Quisquater J J.Efficient and provably-secure identity-based signatures and signcryption from bilinear maps[C]. Asiacrypt 2005, Berlin:Springer-Verlag, 2005, LNCS 3788: 515-532.

[8] 李發(fā)根，胡予濮，李剛. 一個(gè)高效的基于身份的簽密方案[J].計(jì)算機(jī)學(xué)報(bào)，2006, 29(9): 1641-1647.Li Fa-gen, HuYu-pu, and Li Gang. An efficient identity-based signcryption scheme. Chinese Journal of Computers, 2006,29(9): 1641-1647.

[9] Barbosa M and Farshim P. Certificateless signcryption[C].ACM Symposium on Information, Computer and Communications Security-ASIACCS 2008, Tokyo, Japan,2008: 369-372.

[10] Wu Chen-huang and Chen Zhi-xiong. A new efficient certificateless signcryption scheme[C]. International Symposium on Information Science and Engieering, Shanghai,China, IEEE Computer Society, 2008: 661-664.

[11] Dent A W. Hybrid signcryption schemes with outsider security[C]. ISC 2005, Berlin: Springer-Verlag, 2005, LNCS 3650: 203-217.

[12] Dent A W. Hybrid signcryption schemes with insider security[C]. ACISP 2005, Berlin: Springer-Verlag, 2005,LNCS 3574: 253-266.

[13] Bj?rstad T E and Dent A W. Building better signcryption schemes with tag-kEMs[C]. PKC 2006, Berlin: Springer-Verlag, 2006, LNCS 3958: 491-507.

[14] Tan C H. Insider-secure signcryption KEM/tag-KEM schemes without random oracles[C]. The Third International Conference on Availability, Reliability and Security-ARES 2008, Barcelona, Spain, 2008: 1275-1281.

[15] Li Fa-gen, Shirase M, and Takagi T. Efficient signcryption key encapsulation without random oracles[C]. Information Security and Cryptology 2009, Berlin: Springer-Verlag, 2009,LNCS 5487: 47-59.

[16] Li Fa-gen, Shirase M, and Takagi T. Certificateless hybrid signcryption[C]. ISPEC 2009, Berlin: Springer-Verlag, 2009,LNCS 5451: 112-123.

[17] Selvi SSD, Vivek S S, and PanduRangan C. Breaking and re-building a certificateless hybrid signcryption scheme.Cryptology ePrint Archive, Report 2009/462, 2009.

[18] Cash D, Kiltz E, and Shoup V. The twin Diffie-Hellman problem and applications[J]. Journal of Cryptology, 2009,22(4): 470-504.