孫銀霞 李 暉 李小青

(西安電子科技大學計算機網絡與信息安全教育部重點實驗室 西安 710071)

1 引言

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

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

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

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

2 預備知識

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

2.1 mCLSC-KEM定義

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

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

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

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

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

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

2.2 mCLSC-KEM安全模型

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

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

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

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

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

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

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

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

2.2.1 認證性

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

攻擊：攻擊者作一系列如上詢問。

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

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

2.2.2 保密性

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

第1階段攻擊：攻擊者作一系列如上詢問。

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

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

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

3 一個高效的mCLSC-KEM方案

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

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

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

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

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

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

(4)輸入一個標簽τ，計算W = Ds+rH3(U, τ,IDs,PKs)+xsH4(U, τ,IDs,PKs)；

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

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

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

4 安全性和效率分析

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

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

5 結束語

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

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

[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ā)根，胡予濮，李剛. 一個高效的基于身份的簽密方案[J].計算機學報，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.