无证书体制下的多接收者签密密钥封装机制

孙银霞 李 晖 李小青

(西安电子科技大学计算机网络与信息安全教育部重点实验室 西安 710071)

1 引言

无证书公钥密码体制首先是由Al-Riyami和Paterson于2003年提出的[1]。该密码体制既克服了传统公钥体制需要管理大量公钥证书的缺点，又克服了基于身份公钥体制[2,3]的密钥托管问题。用户私钥由两部分组成，一部分由密钥生成中心KGC生成，另一部分由用户自己选取，因此完整的私钥只有用户自己知道；用户公钥由用户生成，且无需公钥证书。

“签密”是由Zheng于1997年提出的一个概念[4,5]，旨在以小于“签名再加密”的代价同时实现信息的认证性和保密性。基于身份和无证书体制下对签密的研究也已经取得了一些进展，比如文献[6-10]。然而，通常的签密方案要求被传输的消息取自某个特定的集合，这就限制了其应用范围。为了取消这种限制，Dent于2005年提出了混合签密的概念[11,12]。一个混合签密方案由两部分构成：签密密钥封装机制(SC-KEM)和数据封装机制(DEM)。SC-KEM运用公钥技术封装一个对称密钥K，然后DEM运用对称加密技术和对称密钥K加密任意长的消息。由于SC-KEM和DEM各自独立，所以我们可以分别研究SC-KEM和DEM，这不仅有利于构造安全又高效的签密方案，而且可以处理任意长度的消息。近几年，混合签密已引起了广泛的关注，并取得了一些成果比如文献[13-15]。在2009年，Li等人[16]将混合签密的概念推广到无证书体制下，提出了无证书混合签密的概念，指出无证书混合签密可以由无证书签密密钥封装机制(CLSC-KEM)和数据封装机制构成，并且给出了一般构造和一个具体方案。随后，Selvi等人[17]指出Li等人[16]的方案不具有存在不可伪造性，并改进了方案。然而，文献[17]中给出的攻击并不成立，因为对称密钥K'的改变会引起标签τ(=EncK'(m))的改变，从而导致W的改变，所以ψ*=(U, W)不是K'的一个有效封装(从发送者IDA到接收者IDB*)，攻击失败。

现在考虑无证书体制下的这样一种情形：某个用户A给n个用户发送一个消息m (任意长度)。当然，A可以对每个接收者分别运行一次无证书混合签密算法，但这样做的运算量太大，不仅需要进行n次数据封装，而且通常需要计算n个双线性对(根据MIRACL的运行结果，对于80 bit的安全级别，计算一个Tate对需要20 ms，而计算一个素数模指数只需要8.8 ms)，这对于计算资源有限的通信环境(比如Ad hoc网络)而言，负担太重。那么，有没有方法可以简化运算以降低通信开销呢？

针对以上问题，本文提出了一个新的概念：无证书体制下的多接收者签密密钥封装机制(mCLSCKEM)。给出了mCLSC-KEM的定义以及安全模型，并构造了一个高效的方案。由该mCLSC-KEM方案得到的无证书混合签密算法仅需1次双线性对运算和1次数据封装，大大降低了通信开销。在随机预言模型下，基于Gap双线性Diffie-Hellman问题，本文的方案是可证明安全的。

2 预备知识

本节定义无证书体制下的多接收者签密密钥封装机制(mCLSC-KEM)及其安全模型。

2.1 mCLSC-KEM定义

本文把单接收者无证书签密密钥封装机制CLSC-KEM[16]推广到多接收者的情形。无证书的多接收者签密密钥封装机制(mCLSC-KEM)由以下5个算法组成：

系统初始化算法(Setup)：由KGC完成，输入安全参数k，输出主密钥s和系统参数params，其中s保密，params公开。

提取部分私钥算法(Extract-Partial-Private-Key)：由KGC完成，输入params，s和一个用户身份ID，输出该用户的部分私钥DID。

生成用户密钥算法(Generate-User-Keys)：由用户完成，输入params和用户身份ID，输出一个秘密值xID和公钥PKID。秘密值xID和部分私钥DID构成用户的完整私钥SKID。

密钥封装算法(Encap)：由发送者完成，输入params，发送者私钥、身份和公钥，n个接收者的身份{IDi}和公钥{PKi}，以及一个标签τ，输出一个对称密钥K和一个密文ϕ。

解封装算法(Decap)：由接收者IDi(i∈[1,n]∩Z+)完成，输入params，密文ϕ，接收者私钥、身份和公钥，发送者身份和公钥，以及一个标签τ，输出一个对称密钥K或者“拒绝”(表示密文无效)。

2.2 mCLSC-KEM安全模型

存在两类攻击者：第1类攻击者AI和第2类攻击者AII。第1类攻击者是一个普通的攻击者，他不知道KGC的私钥，但是可以替换任何用户公钥；第2类攻击者指好奇但诚实的KGC，他已知任何用户的部分私钥，但是不替换任何用户公钥。

本文通过以下攻击者与挑战者之间的两个游戏来定义mCLSC-KEM的安全性。这两类攻击者在攻击阶段可以作如下询问：

提取部分私钥询问：AI询问用户ID的部分私钥。挑战者运行算法Extract-Partial-Private-Key(params, s, ID) →DID, 并把DID返回给AI。

提取秘密值询问：AI，AII询问用户ID的秘密值。挑战者运行算法Generate-User-Key(params,ID)→xID, 并把xID返回给AI、AII。如果该用户的公钥已被替换，则攻击者不能作此询问。

公钥询问：AI，AII询问用户ID的公钥。挑战者运行算法Generate-User-Key(params, ID)→PKID, 并把PKID返回给攻击者。

替换公钥：AI替换用户ID的公钥。AI可以用任何值替换用户ID的公钥。

Encap询问：AI，AII对(IDs, {IDi},τ)进行Encap询问。挑战者运行算法Encap(params, SKs,IDs, PKs, {IDi},{PKi},τ)→(K,ϕ), 并把(K,ϕ)返回给攻击者。

Decap询问：AI，AII对(IDs, IDi，τ, ϕ)进行Decap询问。挑战者运行算法Decap(params, IDs,PKs, SKi, IDi,PKi,τ,ϕ)→K/“拒绝”，并把K或“拒绝”返回给攻击者。

2.2.1 认证性

初始化：挑战者运行算法Setup，并把params发送给攻击者AI；把params和s同时发送给攻击者AII。

攻击：攻击者作一系列如上询问。

伪造：攻击者输出(τ*,ϕ*,, L*)。若ϕ*有效，则攻击者赢得游戏。AI不能同时询问过的部分私钥和秘密值，或者同时询问过IDs*的部分私钥和替换过的公钥；AII不能询问过IDs*的秘密值。ϕ*不能来源于攻击者对(, L*,τ*)的Encap询问。定义攻击者在以上游戏中获胜的优势为攻击者赢得游戏的概率。

定义1 如果没有任何多项式有界的攻击者在以上游戏中以不可忽略的优势获胜，那么称一个mCLSC-KEM方案在选择消息攻击下具有强不可伪造性(sUF-CMA)。

2.2.2 保密性

初始化：挑战者运行算法Setup，并把params发送给攻击者AI；把params和s同时发送给攻击者AII。

第1阶段攻击：攻击者作一系列如上询问。

第2阶段攻击：攻击者继续进行如第一阶段的询问，但是AII不能同时询问任何∈L*的部分私钥和秘密值，也不能同时询问的部分私钥和替换其公钥；AIII不能询问任何∈L*的秘密值。另外，攻击者不能对(,∈L*,τ*,ϕ*)进行Decap询问，除非替换发送者或者接收者的公钥。

猜测：攻击者输出猜测β∈{0,1}。定义攻击者在以上游戏中获胜的优势为|2Pr[β=0]−1|。

定义2 如果没有任何多项式有界的攻击者在以上游戏中以不可忽略的优势获胜，那么称一个mCLSC-KEM方案在选择密文攻击下具有不可区分性(IND-CCA)。

3 一个高效的mCLSC-KEM方案

本节给出一个高效的mCLSC-KEM方案，具体构造如下：

初始化(Setup)：设G1和G2分别是阶为素数q的加法循环群和乘法循环群，P是G1的一个生成元，: G1×G1→G2是一个双线性对。H1，H2，H3和H4是4个hash函数，其中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。则系统的公共参数为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)：由发送者运行。输入params，发送者私钥(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，发送者身份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次数据封装(DEM)，且随着接收者数量的增加而增加。众所周知，双线性对运算复杂，需要消耗较多的计算资源，所以在实际应用尤其是计算资源有限的通信环境中应当尽量减少双线性对的数量。本文的方案较好地做到了这一点，它仅需计算1个双线性对和1次数据封装，且不随接收者数量的增加而增加。另外，消息的密文长度也比一般性构造短。表1中p表示双线性对，|P|表示G1中一个元素的长度，|m|表示消息m的长度。

5 结束语

本文提出了一个新的概念：无证书体制下的多接收者签密密钥封装机制(mCLSC-KEM)。给出了mCLSC-KEM的定义和安全模型，并且构造了一个高效的方案。与一般性构造相比，本文的方案不仅减少(n-1)次数据封装，而且减少(n-1)次双线性对运算(n指接收者数量)，从而大大提高了通信效率。在随机预言模型和Gap双线性Diffie-Hellman(GBDH)假设下，方案是可证明安全的。

可以运用twinning技术[18]使方案的安全性归结于标准的双线性Diffie-Hellman问题，以避免使用Gap双线性Diffie-Hellman假设，但与此同时计算复杂性增加了。如何在两者之间实现最优化是一个待研究的问题。

[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] 李发根，胡予濮，李刚. 一个高效的基于身份的签密方案[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.