格上可撤销的基于身份的适应性安全的加密方案

张彦华胡予濮 江明明 来齐齐

(西安电子科技大学综合业务网理论与关键技术国家重点实验室 西安 710071)

格上可撤销的基于身份的适应性安全的加密方案

张彦华*胡予濮 江明明 来齐齐

(西安电子科技大学综合业务网理论与关键技术国家重点实验室 西安 710071)

用户撤销是基于身份的加密(IBE)方案在实际应用中所必须解决的问题。Chen等人在ACISP 2012上给出了第1个格上可撤销的基于身份的加密(RIBE)方案，但其只能达到选择性安全。利用Agrawal等人在欧密2010上给出的IBE方案，该文构造出一个格上适应性安全的RIBE方案，从而解决了Chen等人提出的公开问题；进一步指出利用Singh等人在SPACE 2012上给出的块方法，可以有效地缩短该方案的公钥尺寸。

密码学；基于身份加密；用户撤销；格；适应性身份安全

1 引言

1984年，Shamir[1]首次提出基于身份的公钥密码(Identity Based Encryption, IBE)体制。在此密码体制中，用户的身份标志符(如姓名、e-mail地址等)可以看作公钥，而相应的私钥由可信中心来产生。IBE消除了对用户证书的需求和依赖，极大地简化了密钥管理。基于双线性Diffie-Hellman假设, Boneh等人[2]于2001年给出了第1个有效的IBE方案。自此以后，IBE引起了众多学者的广泛关注，很多基于身份的加密和签名方案被提出[35]-。

系统用户的公私钥因各种原因有时需要被撤销并替换为新的密钥，例如：与公钥相对应的私钥被偷了；用户丢失了私钥或者不再是一个合法用户。为解决密钥撤销和更新问题，文献[2]提出消息的发送者在进行加密时可将当前的有效时间添加到身份信息中，并且消息的接收者周期性地获得新密钥。然而，上述方法需要可信中心执行非撤销用户的线性级别的工作量，并且可信中心需要与每一位非撤销用户建立安全信道来发送更新后的密钥。最近，Boldyreva等人[6]给出了一个选择性安全的可撤销的基于身份的加密(Revocable Identity Based Encryption, RIBE)方案，使得可信中心执行非撤销用户的对数级别的工作量，这有效地减轻了可信中心的负担，并且第1次获得非交互的密钥撤销，发送者和接收者的效率也得以有效提高。随后，Libert和Vergnaud[7]采用类似的密钥撤销方法将文献[6]改进为适应性安全。

近年来，基于格构造新型密码系统因具有较高的渐进效率、运算简单、抗量子攻击和存在最坏情况下的随机实例等特点，成为后量子时代密码领域的研究热点，并取得了一系列研究成果[811]-。Chen等人[12]构造出第1个基于格的RIBE方案，但是他们仅获得选择性安全。该文利用Agrawal等人[13]的IBE方案，构造出一个格上适应性安全的RIBE方案，从而解决了Chen等人提出的如何构造格上适应性安全的RIBE方案的公开问题；进一步指出，利用Singh等人[14]给出的块方法，可以有效地缩短本文方案的公钥尺寸。

2 基础知识

2.1 格

定义1 设b1,b2,···,bm是ℝn上m个线性无关的向量，格Λ定义为所有这些向量的整数线性组合构成的集合，即其中向量组b1,b2,···,bm构成格Λ的一组基B。

定义 3 对任意s＞0，定义以向量c为中心，s为参数的格Λ上的离散高斯分布为

2.2 相关算法和困难问题

引理1[8]存在概率多项式时间(Probabilistic Polynomial Time, PPT)算法SampG，输入格Λ的一组基B，参数s ≥||·ω(log2n )以及中心c∈ℝn，输出一个统计接近的格向量。

引理2[8]设n是正整数，素数q≥2, m≥q，对于除了至多2q-n的部分之外所有的A∈以及任意s≥ω(log2n )，向量u= Aemodq 的分布统计接近上的均匀分布，其中e∈Dℤm,s。

引理3[9]设n是正整数，素数q≥2, m＞5nlog2q，存在PPT算法TrapG(q,n)，输出矩阵其中A在上是统计均匀的，TA是格(A)的陷门基，且满足

引理4[9]设n是正整数，素数q≥2, m＞(n+1)log2q+ω(log2n)，则分布(A,AR,RΤw)和 (A,B,RΤw)是统计不可区分的。其中上的均匀随机矩阵，

引理5[13]设n是正整数，素数q＞2, m≥2nlog2q，存在PPT算法SampL(A,M,TA,u,s)，输出向量e∈ℤm+m1，且e的分布与统计不可区分。其中矩阵TA是格(A)的陷门基，向量u∈，高斯参数s＞|||，矩阵。特别的，

引理 6[13]设n是正整数，素数q＞2, m＞n，存在PPT算法SampR(A,B,R,TB,u,s)，输出向量e∈ℤ2m，且e的分布与DΛuq(F2),s统计不可区分。其中矩阵A,B∈ℤ,R ∈{1,-1}m×m,TB是格(B)的陷门基，向量u∈，高斯参数s＞||||(log2m)，矩阵F2=(AAR+B)。特别地，e∈(F2)。

定义4[15]判定性差错学习问题(Decisional Learning With Errors, DLWE) 设n是正整数，q为素数，对任意α＞0，定义Ψα为中心为0，方差为α/2π的[0,1)上的正态分布，对应的ℤq上的离散分布为。设χ为ℤq上的差错分布，定义As,X为(ui,vi)=(ui,s+xi)∈ℤ×ℤq上的分布，其中ui∈是随机选取的向量，xi∈ℤq依分布X独立随机选取。(ℤq,n,X)-DLWE是指区分伪随机分布As,X和×ℤq上的真随机分布。

2.3 撤销二叉树结构

BT表示二叉树，Root表示根节点，若v是叶子节点，则Path(v)表示v到Root的路径上所有节点的集合(包含v和Root)。若θ非叶子节点，则θl和θr分别表示它的左右子节点，每个用户对应一个叶子节点。算法KUNo用来计算密钥更新时二叉树BT所需要更新的节点的最小集合。算法KUNo(BT, RL,t):X,Y←∅(空集合)；∀(vi,ti)∈RL ，若ti≤t，添加θ∈Path(vi)到集合X; ∀θ∈X，若θl∉X ，添加θl到集合Y；若θr∉X，添加θr到集合Y；若Y=0，添加Root到集合Y；返回Y。

3 格上适应性安全的RIBE方案

3.1 方案构造

系统建立：输入安全参数1n和最大用户数N；运行算法TrapG(q,n)生成随机矩阵A0∈ℤqn×m和格(A0)的陷门基TA0，且；选取l+1个均匀随机矩阵A1,A2,···,Al及B∈，选取n维均匀随机向量u∈，输出公开参数PP= (A0,A1,···,Al,B,u)和主私钥MK=TA0。

用户密钥生成：输入公开参数PP，主私钥MK，用户身份id=(b1,b2,···,bl)∈{1,-1}l，撤销列表RL和状态ST；从BT上选取一个空的叶子节点v，将用户id存储在该节点，令∀θ∈ Path(v)，若uθ,1,uθ,2为空，随机选取uθ,1∈, uθ,2=u-uθ,2，并存储在节点θ；运行算法SampL(A0,Aid,TA0,uθ,1,s)得向量eθ,1∈，输出SKid={(θ,eθ,1)}θ∈Path(v)和ST。

密钥更新：输入公开参数PP，主私钥MK，密钥更新时间t=(t1,t2,…,tl)∈{1,-1}l，撤销列表RL和状态ST；令KUNo(BT,RL,t)，若uθ,1,uθ,2为空，随机选取uθ,1∈,uθ,2=u-uθ,2,并存储在节点θ；运行算法SampL(A0,At,TA0,uθ,2,s )得向量eθ,2∈，输出

解密密钥生成：输入私钥SKid={(i,ei,1)}i∈I和更新密钥KUt={(j,ej,2)}j∈J，其中I和J是节点集；若存在(i,j)使得i=j，则输出DKid,t=(ei,1,ej,2)；否则，DKid,t←⊥。由于i=j，简记DKid,t=(e1,e2)。

加密：输入公开参数PP，用户身份id，密钥更新时间t和消息m∈{0,1}；选取n维均匀随机向量s∈和l个均匀随机矩阵Ri∈{1,-1}m×m,i= 1,2,…,l；令，选取差错量和差错向量；令，输出密文CTid,t,m=(c0,

解密：输入公开参数PP，解密密钥DKid,t= (e1,e2)和密文CTid,t,m=(c0,c1)；令，其中计算，若，输出1；否则，输出0。

用户撤销：输入用户身份id，密钥更新时间t，撤销列表RL和状态ST，添加id对应节点v与时间t到撤销列表RL，并输出新的撤销列表RL。

3.2 参数设置

3.3 安全性证明

解密的正确性显然成立。利用类似文献[13]的Abort-Resistant哈希函数：设q为素数，令()∗:Ηh(id)，其中hi∈ℤq。

定理 若(ℤq,n,)-DLWE假设成立，则本文的RIBE方案是适应性身份选择明文攻击安全的。

证明 将敌手分为两类：第1类，敌手询问过挑战身份id∗，但是要求在时间t∗该用户已被撤销；第2类，敌手从未询问过挑战身份id∗。本文用随机比特k∈{0,1}作为对敌手类型的一个猜测，Wi表示敌手在Gamei中正确猜测出挑战比特这一事件，即在Gamei结束时，r′=r。

Game 0 Game 0是一个攻击本文方案的攻击者与挑战者进行的适应性身份选择明文攻击的游戏。

Game 1 改变矩阵Ai,i=1,2,…,l 的生成方式，挑战者在系统建立阶段选取l个矩阵∈{1, -1}m×m和l个量hi∈ℤq,i=1,2,…,l ，构造矩阵Ai=A0+hiB∈，其中i=1,2,…,l 。矩阵仅用来构造矩阵Ai和挑战密文。令R∗=(||…|)，由引理4可知，(A0,A0·R∗,(R∗)Ty)和统计不可区分，其中

Game 2 在Game 2中，添加一个在敌手看来独立的终止事件，其他与在Game 1中一样。对用户身份集I=(id∗,id1,…,idQ)和密钥更新时间集J= (t∗,t1,…,tQ), Game 2中的挑战者进行如下操作：

(1)系统建立阶段，挑战者随机选择一个哈希函数h∈H并秘密保留，其他与在Game 1中一样。

(2)挑战者对敌手的用户身份，密钥更新询问的应答和挑战密文的生成与在Game 1中一样。

(3)猜测阶段，终止检查：检查是否Hh(id∗)=0,(idi)≠0,H(t∗)=0,H(ti)≠0，若不满足，挑战 h h者返回随机比特r′∈{0,1}，然后终止游戏。人为终止：引入该操作是为了使得游戏终止概率增大，若存在人为终止，挑战者选择随机比特r′∈{0,1}，然后终止游戏。令ε(·)表示没有发生游戏终止的概率，ε(·)∈[εmin,εmax]。

引理7[13]假设Wi表示敌手在Gamei中正确猜测出挑战比特这一事件，即在Gamei结束时，r=r′，则|Pr[W2]-1/2|≥εmin|Pr[W1]-1/2|-1/ 2(εmax-εmin)，若存在人为终止，(εmax-εmin)≤αmin|Pr[W1]-1/2|，因此

Game 3 改变每个节点的uθ,1,uθ,2的生成方式，对用户身份id满足Hh(id)=0和密钥更新时间t满足Hh(t)=0的询问，挑战者作如下返回：若k=0，模拟与第1类敌手的游戏：若θ∈Path(v)，运行算法SampG(Bℤ,s,0)得，令uθ,1=Fid·eθ,1,uθ,2=u-uθ,1,uθ,2= u-uθ,1，并存储在节点θ；若θ∉Path(v)，运行算法SampG(Bℤ,s,0)得，令uθ,2=Ft·eθ,2,uθ,1=u-uθ,2，并存储在节点θ。在密钥更新时间t∗，用户id∗已被撤销，因此KUNo(BT,RL,t∗)∩Path(v∗)=∅，挑战者用{(θ,eθ,1)}θ∈Path(v)和{(θ,eθ,2)}θ∈KUNo(BT,RL,t)作为对用户身份id和密钥更新时间t询问的应答。若k=1，模拟与第2类敌手的游戏：运行算法SampG(Bℤ,s,0)得eθ,2，令uθ,2=Ft·eθ,2,uθ,1=u-uθ,2，并存储在节点θ。由于用户id∗从未被询问过，因此挑战者用{(θ,eθ,2)}θ∈KUNo(BT,RL,t)作为对密钥更新时间t询问的返回。

由引理1可知，eθ,1和eθ,2的分布统计接近,s。Fid和Ft可以看作上的随机矩阵，由引理2可知，uθ,1和uθ,2是上统计均匀的。敌手无法区分挑战者的模拟类型，挑战者有1/2的概率正确模拟，因此，若游戏被正确模拟，Game 2和Game 3是不可区分的。

Game 4 改变A0和B的生成方式，选取随机矩阵∈，运行算法TrapG生成矩阵B∈和格(B)的陷门基TB。Ai,i=1,2,…,l 的构造与在Game 3中一样，即

其中∈ℤq

挑战者用陷门基TB对用户身份id的密钥询问和更新密钥时间t的更新密钥询问进行应答：若H(id)≠0，运行算法SampR(A0,hidB,Rid,TB,uθ,1,s )得eθ,1；若H(t)≠0，运行算法SampR(A0,htB, TB,uθ,2,s)得eθ,2；若H(id)=0或者H(t)=0，与在Game 3中一样生成eθ,1或者eθ,2，并发送给敌手。挑战阶段，挑战者检查挑战身份id∗=(,…,)和密钥更新时间t∗=(,…,)是否满足H(id∗)=0, H(t∗)=0。若不满足，挑战者与在Game 3中一样，终止游戏，并返回一个随机比特r′∈{0,1}。猜测阶段，挑战者与在Game 3中一样，执行人为终止。在敌手看来，Game 3和Game 4统计不可区分，因此，敌手的优势是相同的，即

接下来利用DLWE问题的困难性证明对于PPT敌手来说，Game 4和Game 5是统计不可区分的。

假设存在一个PPT敌手A能以不可忽略的优势区分Game 4和Game 5，本文利用敌手A来构造求解DLWE问题的算法B。模拟者B得到一系列样本(ui,vi)∈×ℤq，其中i=0,1,···,m 。

系统建立：模拟者B利用样本生成随机矩阵A0∈，矩阵A0的第i列是向量ui,i=1,2,…,m ，将样本向量u0作为公共随机矩阵u∈；与Game 4 一样生成矩阵B和利用随机选择的hi和构造公共矩阵Ai,i=1,2,…,l ；将公开参数PP=(A0,A1,…,Al,B,u)发送给敌手A。

询问阶段：模拟者B对敌手A多项式次用户密钥生成，密钥更新和密钥撤销询问的应答与Game 4一样。

挑战阶段：敌手A提交挑战身份id∗，密钥更新时间t∗和信息m∗∈{0,1}，模拟者B操作如下：v0,v1,···,vm表示DLWE问题中的m+1个样本分量，令，盲化消息比特得令；选取随机比特r∈{0,1}，若r=0，将发送给敌手，反之，随机选择，并发送给敌手。

若DLWE问题中的分布是伪随机的，那么c∗的分布与在Game 4 中一样。此时，由样本定义知道其中的分布为。因此，上述定义的满足

上式右端是Game 4中挑战密文的c1；又由v0=s+x ，其中x的分布为，上述定义中的满足=s+x+m∗，是Game 4中挑战密文的c0。

若DLWE问题中的分布是真随机的，则v0是ℤq上均匀的，v∗是上均匀的。由Left over hash引理可知上述定义的是上独立均匀的。因此，挑战密文的分布与在Game 5中一样是ℤq×上均匀的。

猜测阶段：多项式次适应性询问结束之后，敌手A猜测与之交互的是Game 4 还是Game 5。模拟者B输出A的猜测作为对DLWE问题的求解。

因此，B求解DLWE问题的优势与A区分Game 4和Game 5的优势相同。由于Pr[W5]=1/2，可得

由式(3)，式(4)，式(5)和式(6)可得

由于不存在PPT算法有效求解DLWE问题，因此本文的方案是适应性身份选择明文攻击安全的。

Singh等人在文献[14]中利用块方法将Agrawal等人的IBE方案的公钥尺寸有效缩短。利用类似的块方法，可以进一步改善本文的方案，缩短公钥尺寸，构造方法为：

4 结束语

本文利用Agrawal等人的IBE方案和撤销二叉树结构，构造出一个格上适应性安全的RIBE方案。在标准模型下证明了方案的安全性是基于格上DLWE问题，从而解决了Chen等人提出的公开问题；又利用Singh等人的块技术，可以将本文的RIBE方案的公钥尺寸进一步缩短，从而提高效率。

[1] Shamir A. Identity-based crypto systems and signature schemes[C]. Crypto 1984, Lecture Notes in Computer Science, Santa Barbara, USA, 1985, 196: 47-53.

[2] Boneh D and Franklin M. Identity-based encryption from the weil pairing[C]. Crypto 2001, Lecture Notes in Computer Science, California, USA, 2001, 2139: 213-229.

[3] Paterson K G and Schuldt J C N. Efficient identity based signatures secure in the standard model[C]. Proceedings of the 11th Australasian Conference on Information Security and Privacy, Lecture Notes in Computer Science, Melbourne, Australia, 2006, 4058: 207-222.

[4] Boneh D, Raghunathan A, and Segev G. Function-private identity-based encryption: hiding the function in functional encryption[C]. Crypto 2013, Lecture Notes in Computer Science, Santa Barbara, USA, 2013, 8043: 461-478.

[5] Tessaro S and Wilson D A. Bounded-Collusion identitybased encryption from semantically-secure public-key encryption: generic constructions with short ciphertexts[C]. Proceedings of the 17th International Conference on Practice and Theory in Public-Key Cryptography, Buenos Aires, Argentina, 2014, 8383: 257-274.

[6] Boldyreva A, Goyal V, and Kumar V. Identity-basedencryption with efficient revocation[C]. Proceedings of the 15th ACM Conference on Computer and Communications Security, Alexandria, USA, 2008: 417-426.

[7] Libert B and Vergnaud D. Adaptive-ID secure revocable identity-based encryption[C]. Proceedings of the Cryptographers’ Track at the RSA Conference, Lecture Notes in Computer Science, San Francisco, USA, 2009, 5473: 1-15.

[8] Gentry C, Peikert C, and Vaikuntanathan V. Trapdoors for hard lattice and new cryptographic constructions[C]. Proceedings of the Symposium on Theory of Computing, Victoria, Canada, 2008: 197-206.

[9] Alwen J and Peikert C. Generating shorter bases for hard random lattices[C]. Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science, Freiburg, Germany, 2009: 535-553.

[10] Micciancio D and Peikert C. Trapdoors for lattices: simpler, tighter, faster, smaller[C]. Eurocrypt 2012, Lecture Notes in Computer Science, Cambridge, UK, 2012, 7237: 700-718.

[11] Boyen X. Attribute-based functional encryption on lattices [C]. Proceedings of the 10th Theory of Cryptography Conference, Lecture Notes in Computer Science, Tokyo, Japan, 2013, 7785: 122-142.

[12] Chen J, Lim H W, Ling S, et al.. Revocable identity-based encryption from lattices[C]. Proceedings of the 17th Australasian Conference on Information Security and Privacy, Lecture Notes in Computer Science, Wollongong, Australia, 2012, 7372: 390-403.

[13] Agrawal S, Boneh D, and Boyen X. Efficient lattice (H)IBE in the standard model[C]. Eurocrypt 2010, Lecture Notes in Computer Science, Riviera, France, 2010, 6110: 553-572.

[14] Singh K, Pandurangan C, and Banerjee A K. Adaptively secure efficient lattice (H)IBE in standard model with short public parameters[C]. Proceedings of the Second International Conference on Security, Privacy and Applied Cryptography Engineering, Chennai, India, 2012: 153-172.

[15] Regev O. On lattices, learning with errors, random linear codes, and cryptography[C]. Proceedings of the Symposium on Theory of Computing, Baltimore, USA, 2005: 84-93.

张彦华： 男，1989年生，硕博连读生，研究方向为格公钥密码的设计与分析.

胡予濮： 男，1955年生， 博士生导师，教授，研究方向为信息安全、网络安全.

江明明： 男，1984年生， 博士，研究方向为格公钥密码、数字签名.

A Lattice-based Revocable Adaptive-ID Secure Encryption Scheme

Zhang Yan-hua Hu Yu-pu Jiang Ming-ming Lai Qi-qi
(State Key Laboratory of Integrated Service Networks, Xidian University, Xi’an 710071, China)

User revocation is crucial to the practical application of Identity Based Encryption (IBE). The first Revocable Identity Based Encryption (RIBE) scheme from lattice is given by Chen et al. in ACISP 2012, but its security can only be proved in the selective-ID model. Using the IBE scheme suggested by Agrawal et al. in EUROCPYPT 2010, this paper constructs a lattice-based adaptive-ID secure RIBE scheme, so as to solve a problem left open by Chen et al.. This paper also points out that using the blocking technique given by Singh et al. in SPACE 2012, the public key size can be reduced effectively.

Cryptography; Identity Based Encryption (IBE); User revocation; Lattice; Adaptive-ID secure

TP309

A

1009-5896(2015)02-0423-06

10.11999/JEIT140421

2014-03-31收到，2014-06-19改回

国家自然科学基金(61173151, 61173152)资助课题

*通信作者：张彦华 yhzhangxidian@163.com