标准模型下基于身份第三方受约束匿名加密方案*

明 洋，韩 娟，张 琳，周 俊

(长安大学信息工程学院，陕西 西安 710064)

1 引言

基于身份加密IBE(Identity-Based Encryption)的概念由Shamir A[1]于1984年首次提出，减轻了用户对公钥证书的需要。2001年,Boneh D等[2]提出第一个实用的IBE方案,之后提出了大量基于身份的加密方案[3～6]。

实际应用中IBE体制存在的内在问题是密钥托管问题,目前主要有三种方案来解决该问题：(1)多PKG(Private Key Generator)方案[2]，用户的私钥由多个PKG共同生成，但多PKG的存在使得系统更复杂，通信代价大大增加；(2)无证书公钥密码CL-PKE(CertificateLess Public-Key Encryption)方案[7]，用户的私钥分别由PKG和用户生成的两个部分组成，但是该方案仍然存在一个可信的第三方来计算用户的部分私钥;(3)第三方权利受约束的IBE方案A-IBE(Accountable Authority IBE)方案。

2007年，Goyal V[8]提出A-IBE方案，通过修改用户私钥的生成方式减少用户对PKG的信任需求；2010年，徐鹏等人[9]在Goyal方案基础上，基于离散对数问题，提出一种标准模型下安全的通用A-IBE方案，该方案实现紧密安全归约，但增加了系统参数和通信量；2011年，曹丹等人[10]基于Diffie-Hellman假设，提出安全有效的A-IBE方案；2012年，张方国等人[11]基于TBDHE(Decision Truncated Bilinear Diffie-Hellman Exponent)假设，提出一个弱的黑盒A-IBE方案，在标准模型下说明该方案是CCA2安全的，且具有紧密归约。

应用中IBE体制常需要考虑匿名性问题，匿名性要求由密文不能得到接收者的身份。2006年Boyen X等人[12]提出一个标准模型下安全的匿名IBE方案；2010年，Liu L等人[13]对Boyen X等人[12]的方案进行改进，但没有进行安全性证明；2012年，任艳丽等人[14]基于DBDH(Decisional Bilinear Diffie-Hellman)假设，利用阶为合数的双线性群，提出新的匿名IBE方案，在标准模型下可证安全。

针对IBE中的匿名性和密钥托管问题，本文结合文献[9,14]的思想，提出一个第三方权力受约束的匿名IBE方案，并基于DBDH假设和DL(Discrete Logarithm)假设在标准模型中证明方案的安全性，所提方案不仅可以保护接收者的隐私，同时也解决了密钥托管问题。

2 预备知识

2.1 合数阶双线性群

设p、p′是两个大素数，n=pp′，G、GT是两个阶为n的循环群，g是G的生成元。如果e:G×G→GT是一个双线性映射,满足以下性质：

(1)双线性：e(ga,gb)=e(g,g)ab，对所有a,b∈Zn均成立。

(2)非退化性：∃P,Q∈G，满足e(P,Q)≠1。

(3)可计算性：存在有效算法计算e。

本文中，使用Gp、Gp′分别代表G中阶为p、p′的子群，GT,p、GT,p′代表GT中的阶为p、p′的子群，而且G=Gp×Gp′，GT=GT,p×GT,p′。如果g是G中的一个生成元，则gp′、gp分别是Gp、Gp′中的生成元，使用gp、gp′分别代表Gp、Gp′的生成元。

2.2 困难性问题

DBDH假设：如果t时间内没有敌手能够以至少ε优势解DBDH问题，则DBDH问题是(t,ε)困难的。

(2)离散对数问题(DL)：令群Gp的阶为p，g为生成元，给定ga，a∈Zp，计算a。

DL假设：如果t时间内没有敌手能够以至少ε优势解DL问题，则DL问题是(t,ε)困难的。

2.3 通用A-IBE形式化定义

通用A-IBE方案由五个算法组成，定义如下：

(1)系统建立：输入安全参数k，选定IBE方案I={系统建立，私钥生成，加密，解密}，随机生成系统公开参数PK={PK-I,PK-A}和私钥SK={SK-I,SK-A}，其中PK-I和SK-I分别为方案I的系统公开参数和私钥。

(2)私钥生成协议：输入身份信息ID和系统公开参数PK，PKG和用户通过运行该协议，生成用户私钥dID={dI,dA}。

(3)加密：输入身份信息ID，系统公开参数PK和明文M，在明文空间中随机选取M1、M2，使得M=M1⊕M2,输出密文C={C1,C2},其中，C1是M1的密文，C2是M2的密文。

(4)解密：输入用户私钥dID={dI,dA}，系统公开参数PK和密文C={C1,C2}，输出明文M=M1⊕M2，其中，M1是C1的明文，M2是C2的明文。

(5)跟踪：取用户私钥dID作为输入，输出该私钥的特征信息。

2.4 通用A-IBE安全模型

定义1如果t时间内没有敌手能够以至少ε优势赢得以下三个游戏，则本文所提方案是安全的。

游戏1匿名性：通过挑战者C和敌手A之间的交互游戏进行,具体如下：

系统建立:C执行系统建立算法，并把系统公开参数PK发送给A。

阶段1 A适应性地进行下列询问：

(1)私钥询问:C对身份ID执行私钥询问，并把对应的私钥发送给敌手。

(2)解密询问:C首先对身份ID执行私钥询问，然后用生成的私钥解密密文C，并把明文M或出错信息发送给A。

挑战:A提交身份ID0、ID1和消息M0、M1给C,其中ID0、ID1均没有在询问阶段1中执行过私钥询问，C随机选择β,γ∈{0,1}，计算密文C*=Encrypt(PK,IDβ,Mγ)，并把C*发送给A。

阶段2A继续适应性地进行询问，但是不能对ID0、ID1进行私钥询问，对〈ID0,C*〉和〈ID1,C*〉进行解密询问。

猜测：A输出对β、γ的猜测β′、γ′∈{0,1}，如果β′=β,γ′=γ，A赢得游戏。

称A为ANON-IND-ID-CCA2敌手，其优势定义为|Pr[β′=β∧γ′=γ]|-1/4。

在上述游戏中，如果敌手不能进行解密询问，则被称为ANON-IND-ID-CPA敌手。

定义2如果t时间内没有ANON-IND-ID-CPA敌手在经过q次私钥询问后，能够以至少ε优势赢得上述游戏，则所提方案是(t,q,ε)-ANON-IND-ID-CPA安全的。

游戏2TheFindKeygame：通过挑战者C和敌手A之间的交互游戏进行，具体如下：

系统建立：敌手A(即敌对的PKG)产生系统公开参数，并将系统公开参数及身份ID发送给挑战者C；挑战者C对系统公开参数进行有效性检测，若检测失败，游戏中止。

私钥生成：敌手A和挑战者C通过运行私钥生成协议，挑战者C生成身份ID的私钥dID并输出，并对其进行有效性检测，若检测失败，游戏中止。

游戏3TheComputerNewKeygame：通过挑战者C和敌手A之间的交互游戏进行，具体如下：

系统建立：挑战者C运行系统建立算法，并将系统公开参数发送给敌手A。

私钥生成:敌手A适应性地查询任意用户的私钥，挑战者C将对应的私钥发送给A。

2.5 1/n不经意传输

不经意传输[15]是指允许接收者从发送者所给的n个秘密中选取一个，且发送者无法知道接收者选择了哪一个，同时接收者也无法知道其他的秘密。

3 第三方权力受约束的匿名IBE方案

系统建立：

PK=(gp′,G,G′,U,e(g1,g2),gy,PK-A)

私钥为:

SK=(g1,g2,u′,u,y,SK-A)

私钥生成协议：

(2)对任意i∈SID，当IDi=0时，PKG从矩阵SK-A中选取元素tx,i=th,i，计算并返回ri/th,i给用户；当IDi=1，PKG从矩阵SK-A中选取元素tx,i=t1,i，计算并返回ri/t1,i给用户。

(4)用户计算dA=({ri/tx,i}i∈SID,{ki,ri/tki,i}i∈Ssp)，并检验:

若等式不成立，则用户退出。

(5)用户将dID=(dI,dA)作为私钥。

加密：

解密：

给定密文C=(CI,CA)，

(2)对CA解密之前，首先进行密文有效性检验，即:

若等式成立，计算:

(3)输出M=M1·M2。

跟踪：

取私钥dID作为输入，该确定算法输出Trace(dID)=klID+1‖…‖kl，即私钥特征值为所有的ki串联。

4 方案的安全性证明

定理1(匿名性) 假定(t′,ε′,q)-DBDH在G,GT中成立，那么所提方案是(t,ε,q)-ANON-IND-ID-CPA安全的,其中:

t′=t+O(ε-2ln(ε-1)λ-1ln(λ-1))

证明假定敌手A存在，构建算法B解决DBDH问题，即给定ga、gb、gc∈Gp，判断Z=e(g,g)abc是否成立。

系统建立：

算法B计算m=4q，并随机选择k∈{0,1,…,lID}，x′∈{0,1,…,m-1}，一个lID比特向量x=(xi)，其中xi∈{0,1,…,m-1}，B随机选择y′∈Zn及一个lID比特向量y=(yi)，其中yi∈Zn。

PK=(G,G′,U,e(g1,g2),gy,PK-A)

其中:

私钥为:

SK=(g1,g2,u′,u,y,SK-A)

其中:

阶段1

敌手适应性地对任意身份信息ID进行私钥询问，算法B运行I的私钥生成算法，如果K(ID)=0，B放弃并随机选择ω′，否则，随机选择r∈Zn，计算

挑战：

A提交身份ID0、ID1和消息m0、m1给B，且ID0、ID1均未在阶段1中进行私钥询问。

令t*=c，如果Z=e(g,g)abc，则

阶段2

A继续进行适应性的私钥询问，但不能对身份ID0、ID1进行私钥询问。

猜测：

A输出对β、γ∈{0,1}的猜测β′、γ′∈{0,1}，如果β=β′,γ=γ′，则敌手赢得游戏。

□

系统建立：

敌手A(即敌对的PKG)产生系统公开参数为:

PK=(G,G′,U,e(g1,g2),gy,PK-A)

并将PK及身份ID发送给B，算法B对PK进行有效性检测，若检测失败，算法B中止。

私钥生成：

算法B与敌手A共同运行私钥生成协议，算法B生成身份ID的私钥dID并输出，并对其进行有效性检测，若检测失败，算法B中止。

私钥寻找：

□

定理3假设DL假设成立，则在安全性ComputerNewKeygame定义下，敌手攻破A-IBE方案的优势可忽略。

系统建立：

算法B运行方案的系统建立算法，生成系统公开参数为:

PK=(G,G′,U,e(g1,g2),gy,PK-A)

私钥为：

SK=(g1,g2,u′,u,y,SK-A)

其中,

并将PK发送给敌手A。

私钥询问：

该阶段敌手A通过与算法B运行私钥生成协议，询问到任意用户的私钥。对于敌手A询问的任意身份信息ID,算法B的处理过程如下：

(2)对任意i∈SID，当IDi=0时，算法B计算并返回ri/th,i给A；当IDi=1，算法B计算并返回ri/t1,i给A。

(4)敌手A得到:

dA=({ri/tx,i}i∈SID,{ki,ri/tki,i}i∈Ssp-{l},

{kl,rl/tkl,l:kl≠h},{kl,rl:kl=h})

并进行检验，如果kl≠h，则dA总能通过检测；如果kl=h，则仅在a=1时可通过检测，而由于a=1的概率可忽略，因此此时dA几乎不能通过检测。

(5)若dA未能通过私钥有效性检测，则算法B中止，否则敌手A得到身份ID的私钥dID={dI,dA}。

新私钥生成：

□

5 性能分析比较

由表1可以看出，本文方案和文献[9,14]比较，在标准模型下的Adaptive-ID模型中可证安全;在运算次数方面,和文献[9]相比，次数相同，而且具有匿名性。因此，所提方案不仅实现了匿名性，同时解决了密钥托管问题，具有较高的安全性和效率。

6 结束语

鉴于IBE方案中存在的匿名性和密钥托管问题，本文基于DBDH假设和DL假设，使用阶为合数的双线性群，提出一个第三方权力受约束的匿名IBE方案，实现了IBE中接收者的匿名性，且解决了密钥托管问题。

近几年来，这一领域的研究工作主要是实现弱的黑盒A-IBE方案或完全有效的黑盒型A-IBE方案[16～20]，具有较高的安全性和紧密的规约性，并实现了公开的追踪，从而找到不诚实的PKG或用户。所以，后续工作是对文中方案进行改进，实现黑盒型的匿名A-IBE方案，并在标准模型下可证安全。

Table 1 Performance comparison of schemes

注*，l是关于k的安全多项式

[1] Shamir A.Identity-based cryptosystems and signature scheme[C]∥Proc of Cryptology-CRYPTO’84,1984:47-53.

[2] Boneh D,Franklin M.Identity-based encryption from the weil pairing[C]∥Cryptology-CRYPTO’01,2001:213-229.

[3] Boneh D,Boyen X.Efficient selective-ID identity-based encryption without random oracles[C]∥Proc of Cryptology-EUROCRYPT’04,2004:223-238.

[4] Boneh D,Boyen X.Secure identity-based encryption without random oracles[C]∥Proc of Cryptology-CRYPTO’04,2004:443- 459.

[5] Waters B.Efficient identity-based encryption without random oracles[C]∥Proc of Cryptology-EUROCRYPT’05,2005:114-127.

[6] Gentry C.Practical identity-based encryption without random oracles[C]∥Proc of Cryptology-EUROCRYPT’05,2005:445-464.

[7] Al-Riyami S,Paterson K.Certificateless public key Cryptography[C]∥Proc of Cryptology-ASIACRYPT’03,2003:452-473.

[8] Goyal V.Reducing trust in the PKG in identity-based cryptosystems[C]∥Proc of Cryptology-CRYPTO’07,2007:430-447.

[9] Xu Peng,Cui Guo-hua,Fu Cai,et al. A more efficient reducing trust in the PKG IBE scheme under DL assumption[J].Journal of Science China(Information Science),2010,40(2):285-297.(in Chinese)

[10] Cao Dan,Wang Xiao-feng,Wang Fei. A secure and accountable identity-based encryption scheme[J]. Journal of Electronics & Information Technology, 2011,33(12):2922-2928.(in Chinese)

[11] Zhao Xing-wen,Zhang Fang-guo.Fully CCA2 secure identity-based broadcast encryption with black-box accountable authority[J].Journal of Systems and Software, 2012,85(3):708-716.

[12] Boyen X,Waters B.Anonymous hierarchical identity-based encryption without random oracles[C]∥Proc of Cryptology -CRYPTO’06,2006:290-307.

[13] Liu L,Cao Z.Improvements of one anonymous ID-based encryption[C]∥Proc of ICETC’2010,2010:256-260.

[14] Ren Yan-li,Gu Da-wu,Wang Shuo-zhong, et al.Anonymous identity-based encryption sheme without random oracles[J].Journal of University of Science and Technology of China,2012,42(4):296-301.(in Chinese)

[15] Tzeng W G.Efficient 1-out-of-noblivious transfer with universally usable parameters[J].IEEE Transactions on Computers,2004,53(2):232-240.

[16] Goyal V,Steve L,Sahai A,et al.Black-box accountable authority identity-based encryption[C]∥ Proc of ACM Conference on Computer and Communications Security, 2008:427-436 .

[17] Libert B,Vergnaud D.Towards black-box accountable authority IBE with short ciphertexts and private keys[C]∥Proc of PKC’09,2009:235-255.

[18] Libert B,Vergnaud D.Towards practical black-box accountable authority IBE:Weak black-box traceability with short ciphertexts and private keys[J]. IEEE Transactions on Information Theory, 2011,57(10):7189-7204.

[19] Sahai A,Seyalioglu H.Fully secure accountable-authority identity-based encryption[C]∥Proc of PKC 2011,2011:296-316.

[20] Lai Jun-zuo,Deng R,Zhao Yun-lei,et al. Accountable authority identity-based encryption with public traceability[C]∥Proc of Cryptology-CRYPTO’13,2013:326-342.

附中文参考文献：

[9] 徐鹏，崔国华，付才，等.DL假设下一种更高效的第三方权力受约束的IBE方案[J].中国科学(信息科学)，2010,40(2):285-297.

[10] 曹丹，王小峰，王飞.一种安全可追责的基于身份加密方案[J].电子与信息学报，2011,33(12):2922-2928.

[14] 任艳丽，谷大武，王朔中，等.标准模型中基于身份的匿名加密方案[J].中国科学技术大学学报，2012,42(4):296-301.