标准模型下可公开验证的匿名IBE方案

李顺东,杨坤伟，巩林明，毛　庆，刘　新

(陕西师范大学计算机科学学院，陕西西安 710119)



标准模型下可公开验证的匿名IBE方案

李顺东,杨坤伟，巩林明，毛庆，刘新

(陕西师范大学计算机科学学院，陕西西安 710119)

摘要：利用弱困难性假设构造强安全的加密系统在基于身份的加密(Identity-Based Encryption,IBE)中具有重要的理论与实际意义.本文基于弱困难性的判定性双线性Diffie-Hellman假设，构造了一个对于选择明文攻击安全的匿名的身份加密方案，解决了利用弱困难性假设构造强安全的基于身份加密系统的问题，同时也解决了基于身份的加密系统的隐私保护问题.与现有的基于较强困难性假设的方案相比，新方案实现的条件更容易满足，可以公开验证而且效率更高.

关键词:基于身份的加密；匿名；可公开验证；选择密文安全；判定性双线性Diffie-Hellman假设

1引言

基于身份的加密体制是由Shamir[1]于1984年提出.与传统公钥加密体制不同，IBE中用户的身份被转化成公钥，不需要公钥设施(Public Key Infrastructure,PKI)分发公钥证书，这样可以提高加密效率.但发送者用接收者的身份信息作为公钥加密消息，接收者的身份信息容易被敌手获得，因而泄漏接收者的隐私.要保护接收者的身份信息，需要研究匿名的IBE方案.一个匿名IBE方案必须满足以下条件：敌手从密文中无法得到接收者身份的任何信息，也无法通过公钥和密文元组对身份进行验证.

2001年，Boneh和Franklin[2]利用椭圆曲线上的双线性对[3]构造了一个实用的匿名IBE方案，在随机预言机模型下，通过将双线性Diffie-Hellman问题(BDH问题)归约到 IBE方案的破解，证明了方案对于选择密文攻击(Chosen Ciphertext Attack,CCA)是安全的，但他们没有提及方案的匿名性.

Canetti等人[4]指出在随机预言机模型下证明安全的方案实际上未必安全.因为在方案实际执行时，需要寻找具体的哈希函数或伪随机函数来替换方案中的随机预言机.而标准模型下的IBE方案通常只需要抗碰撞的单向函数，其安全性更可靠.因此Boneh和Franklin[2]提出了一个公开问题：能否在标准模型下构造可证明安全的IBE方案.

Abdalla等[5]证明Waters[6]和Boneh-Boyen[7]的IBE方案不能达到匿名性，更进一步提出能否在标准模型下构造匿名IBE.随后出现了第一个不使用随机预言机的匿名IBE方案[8].方案把身份信息随机分成两部分来保证不被识别，基于判定性双线性Diffie-Hellman假设(Decisional Bilinear Diffie-Hellman Problem,DBDH)抵抗选择身份攻击-选择明文攻击(sID-CPA).

2006年，Gentry提出了两个匿名IBE方案[9]，分别达到选择明文安全和选择密文安全.方案的公共参数很短，加密过程不需要进行双线性对计算，并且基于判定的双线性Diffie-Hellman指数的扩展(Decisional Augmented Bilinear Diffie-Hellman Exponent,Decisional ABDHE) 问题实现了紧性归约.但是很难说明q-ABDHE下的紧性归约比DBDH下的松散归约强.

后来不少匿名IBE方案被提出，但很少有方案能基于弱困难问题达到强安全性.例如Wang等[10]提出了一个匿名的IBE方案，方案的安全性基于一些静态的复杂假设，密文的匿名性利用合数阶双线性群的子群性质来保证.方案的缺点是公共参数和密文长度较长，安全性和效率不高.

本文受文献[9]启发，基于DBDH问题构造了一个在标准模型下安全的、可公开验证的匿名IBE方案，解决了Boneh和Franklin提出的公开问题，也解决了Gentry所提出的问题.基于弱困难假设达到了强安全性，实现了CCA 安全性下DBDH问题到匿名IBE方案破解相对紧密的归约，提高了加密效率，这使得方案既实用又安全，在实际应用中更易实现且更有优势.

2预备知识

2.1双线性映射

设G1和G2是阶为大素数p的乘法群，映射e:G1×G1→G2是一个双线性映射，e满足以下性质：

(1)双线性：如果对于任意的P,Q∈G1和任意的a,b∈Z，都有e(aP,bQ)=e(P,Q)ab，我们就说e:G1×G1→G2是双线性的.

(2)非退化性：这个映射不会将G1×G1中的所有对映射为G2的单位元.因为G1,G2同为素数阶群，这意味着如果P是G1的单位元，那么e(P,P)是G2的单位元.

(3)可计算性：对于任意的P,Q∈G1，都有有效的算法来计算e(P,Q).

2.2困难性假设

W=e(P,P)abc∈G2

3基于身份的加密

3.1基于身份的加密的定义

一个基于身份的加密机制由初始化、私钥生成、加密和解密四个随机算法组成.

初始化输入安全参数k，返回系统公开参数params和系统主密钥master-key.系统公开参数包括：有限的消息空间M的描述，有限的密文空间C的描述.系统的公开参数params对外公布，秘密保存系统主密钥master-key，仅由PKG所知.

私钥生成输入params、master-key和一个任意的c=Encrypt(params,ID,m)，返回对应的私钥d.这里ID为一个作为公钥的任意长字符串，d为其对应的私有的解密私钥.Extract算法生成公钥的对应私钥.

加密输入params,ID和明文消息m∈M,输出密文c∈C.

解密输入params,密文c∈C和私钥d，返回明文消息m∈M.

这些算法必须满足一致性约束的标准，也就是说当d是由Extract算法生成的公钥ID对应的私钥时，有下述计算成立：对于任意的m∈M，Decrypt(params,c,d)=m，这里

c=Encrypt(params,ID,m)

3.2安全模型

本节介绍了选择密文攻击下匿名IBE方案的安全模型.安全性证明通过下述游戏进行，其中有两个参与者：A为敌手，B为挑战者.

初始化B执行Setup算法并把系统参数params发送给A.

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

加密询问〈ID〉B对身份ID执行Extract算法，并把对应的私钥返还给敌手.

解密询问〈ID,C〉B首先对身份ID执行Extract算法，然后用生成私钥解密密文C，并把明文M或出错信息返还给A.

挑战A提交身份ID0,ID1和消息M0,M1给B，其中ID0,ID1都没有在阶段1中执行过提取询问，B随即选择j,k∈{0,1}，计算

C*=Encrypt(params,IDj,Mk)

并把C*返还给A.

阶段2A继续适应性地询问，但是不能对ID0,ID1进行提取询问,或者对〈ID0,C*〉和〈ID1,C*〉进行解密询问.

猜测A输出j′,k′∈{0,1}，如果j′=j，k′=k则A赢得游戏.我们称A为匿名的选择性密文安全(ANON-IND-ID-CCA2)敌手，其优势定义为

定义1一个具有(t,q,ε)-ANON-IND-ID-CCA2安全性的IBE系统为在t时间内所有ANON-IND-ID-CCA2挑战者至多产生q次询问，至多有ε的概率取得挑战成功.

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

定义2一个具有(t,q,ε)-ANON-IND-ID-CPA安全性的IBE系统为在t时间内所有ANON-IND-ID-CPA挑战者至多产生q次询问，至多有ε的概率取得挑战成功.

4具体方案

4.1方案介绍

初始化公共参数为{g,g1,g2,H}，主密钥为α.

其中β=H(C1,C2,C3,C4).由于e(g1,g2)和e(g,g1)都可以提前运算，所以加密阶段不需要作对运算.

解密接收者首先计算β=H(C1,C2,C3,C4)，然后验证下式是否成立：

C5=e(gβ,C3)e(C4,g1)β

(1)

若式(1)成立，则接收者可以使用私钥d=(d1,d2,d3)解密.解密如下:

(2)

4.2正确性

如果C=(C1,C2,C3,C4,C5)是使用身份ID对m加密的有效密文，则可以对式(1)、(2)作如下验证：

对于式(1)有:

=e(g,g1)βse(g,g1)βt

=e(g,g1)β(s+t)

=C5

对于式(2)有:

4.3安全性

假设DBDH是困难的，我们证明上一节的IBE方案是ANON-IND-ID-CCA安全的.

定理1如果选取的哈希函数H是一个普通的单向哈希函数，群G1上的DBDH问题是困难的，则我们的IBE方案是ANON-IND-ID-CCA安全的.

证明为了证明定理1，我们假设A能够以ε的优势攻破上述IBE方案.我们可以构建一个模拟器B和一个统计测试，通过调用敌手A的能力来解决G1中的DBDH问题.

方案证明过程中所使用的两个分布R,D的定义如下：

分布R是一个随机的五元组{g,gα,gb,gc,Z}∈G5，其中Z是随机选取的;

分布D是五元组{g,gα,gb,gc,Z}∈G5，其中Z=e(g,g)αbc.

在统计测试中，从分布R或D中选取五元组{g,gα,gb,gc,Z}，进行如下构造：建立一个模拟器B，用B来模拟对上述加密方案进行攻击时敌手A的视图(view)(所谓视图是方案参与方的公共输入，自己的秘密输入、自己选择的随机数，以及整个过程中收到的所有消息序列)分布(隐藏比特k不属于敌手的视图).

如果分布的输入来自D，模拟器可以完美的模拟真实加密方案，此时敌手拥有不可忽略的优势ε猜对隐藏比特k；当分布的输入来自R，敌手的视图与隐藏比特k是相互独立的，即敌手猜对的优势是可忽略的.在运行模拟器和敌手的过程中，模拟器输出一个比特k，敌手输出一个比特k′，如果k=k′则输出1，否则输出0，这意味着统计测试可以区分来自R和D的分布.这里的证明思想借鉴了Cramer,Shoup[11]的证明方法.

下面给出模拟器B的工作模式和挑战游戏过程：

初始化B生成系统参数，令g1=gα,g2=gb，并将系统参数g,g1,g2发给敌手A.

d=(d1,d2,d3)

所以，模拟的私钥d=(d1,d2,d3)是对应身份ID的一个有效私钥.

A继续发起解密询问(ID,C)，B在回答解密询问之前先生成ID对应的私钥.然后，按照之前的解密算法进行解密，并将解密结果发给A.

首先计算：

然后计算：

β=H(C1,C2,C3,C4),C5=e(g,g1)β(c+ρ)

如果模拟器B的输入来自分布D，即Z=e(g,g)αbc，则密文形式为：

C=(C1,C2,C3,C4,C5)

显然，C是明文Mk的一个有效加密密文.

如果模拟器B的输入来自分布R，即Z是G2中的一个随机元素.这种情况下，加密预言机的输出密文不合法，敌手从密文得不到B所选择的比特k的任何信息.

阶段2A继续发起私钥提取询问和解密询问，B的回复同阶段1.

猜测最终，敌手A输出两个猜测j′,k′∈{0,1}.如果j=j′,k=k′，B输出1，否则输出0.

以上完成了模拟描述，下面引入两个引理来证明定理1.

引理1当模拟器B的输入{g,gα,gb,gc,Z}来自D分布，敌手A的视图和隐藏比特{j,k}的联合分布与真实环境统计不可区分.

证明根据以上模拟过程，当模拟不提前结束时，敌手A的视图和隐藏比特{j,k}的联合分布只在挑战密文阶段有效，所以只需证明在该阶段敌手A的视图和隐藏比特{j,k}的联合分布与真实环境统计不可区分.

已知输入来自分布D，则Z=(g,g)abc，敌手A对身份ID发起私钥提取询问和解密询问时，B的模拟都是完全正确的.B的回答不会给A提供任何附加信息.

在多次IND-ID-CCA攻击的模拟构成的统计测试中，每次模拟器的输入都是随机的，且模拟挑战密文时所用的随机数也是随机选取的，所以每次模拟所生成的挑战密文是相互独立的.敌手A的视图和隐藏比特{j,k}的联合分布与真实环境统计不可区分.

引理2当模拟者B的输入来自R分布，敌手的视图和隐藏比特{j,k}的分布是相互独立的.

注意到，当输入来自R分布时，挑战阶段的密文是无效密文，所以解密阶段对有效密文的回答对敌手没有帮助，而对无效密文的回答可能会对敌手有帮助，所以通过以下两个断言证明预言机可以判定密文的有效性.

断言1若在攻击过程中，解密预言机拒绝所有无效密文，则隐藏比特{j,k}的分布与敌手的视图是相互独立的.

已知输入来自分布R，则Z=e(g,g)z.在挑战阶段，挑战密文如下：

由于z是从G1中随机选取的，所以z和敌手A的视图无关，更进一步的说，e(g,g)zMk是一次完美填充.所以隐藏比特{j,k}的分布与敌手的视图是相互独立的.

断言2解密预言机拒绝所有无效密文，接受无效密文的概率是可忽略的.

对于敌手A提交的密文C=(C1,C2,C3,C4,C5)，解密预言机可以通过以下两个等式判断所给密文的有效性：

(3)

5方案对比

本节综合分析计算复杂度、通信复杂度以及安全性方面的性能.表1将现有的匿名IBE方案与我们提出的新方案进行了全面的对比.通过比较可以发现，新方案的主要优势在于降低了困难假设强度，同时提高了安全性，而效率方面几乎没有牺牲.综合来看，新方案具有很大的优势.

表1　方案对比

6结束语

匿名IBE在提高加密效率和保护用户隐私等方面都具有很大的优势.本文针对Gentry提出的公开问题，构建了一个标准模型下CCA安全的匿名IBE方案.新方案有以下优势：基于的DBDH问题困难性较弱，加密复杂度更低，可以公开验证等，弥补了DBDH问题下CCA安全的匿名IBE的空缺.

目前，匿名IBE方案并不是很多.研究在标准模型下基于更自然的困难假设、具有紧性归约的、高效的、抗CCA安全的匿名IBE方案仍然是一个值得深入研究的问题.

参考文献

[1]Shamir A.Identity-based cryptosystems and signature schemes[A].Advances in Cryptology 1984[C].Berlin:Springer-Verlag,1984.47-53.

[2]Boneh D,Franklin M.Identity-based encryption from the Weil pairing[A].Advances in Cryptology-CRYPTO 2001[C].Berlin:Springer-Verlag,2001.213-229.

[3]Menezes A J,Okamoto T,Vanstone S A.Reducing elliptic curve logarithms to logarithms in a finite field[J].IEEE Transactions on Information Theory,1993,39(5):1639-1646.

[4]Canetti R,Goldreich O,Halevi S.The random oracle methodology,revisited[J].Journal of the ACM (JACM),2004,51(4):557-594.

[5]Abdalla M,Bellare M,Catalano D,et al.Searchable encryption revisited:Consistency properties,relation to anonymous IBE,and extensions[J].Journal of Cryptology,2008,21(3):350-391.

[6]Waters B.Efficient identity-based encryption without random oracles[A].Advances in Cryptology-EUROCRYPT 2005[C].Berlin:Springer-Verlag,2005.114-127.

[7]Boneh D,Boyen X.Secure identity based encryption without random oracles[J].Lecture Notes in Computer Science,2004.443-459.

[8]Boyen X,Waters B.Anonymous hierarchical identity-based encryption (without random oracles)[A].Advances in Cryptology-CRYPTO 2006[C].Berlin:Springer-Verlag,2006.290-307.

[9]C Gentry.Practical identity-based encryption without random oracles[A].Advances in Cryptology-EUROCRYPT 2006[C].Berlin:Springer-Verlag,2006.445-464.

[10]王皓,徐秋亮.抗适应性选择身份攻击的匿名HIBE方案[J].计算机学报,2011,34(1):25-37.

WANG Hao,XU Qiu-liang.Anonymous HIBE scheme secure against full adaptive-ID attacks[J].Chinese Journal of Computers,2011,34(1):25-37.(in Chinese)

[11]Cramer R,Shoup V.A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack[A].Advances in Cryptology-CRYPTO 1998 [C].Berlin:Springer-Verlag,1998.13-25.

李顺东男，1963年12月生于河南平顶山.1984、1987年在西安工程大学获工学学士、硕士学位；2003年在西安交通大学获计算机科学与技术工学博士学位.现为陕西师范大学计算机科学学院教授、博士生导师.主要从事密码学与信息安全研究.

E-mail:shundong@snnu.edu.cn

杨坤伟男，1990年5月出生于陕西咸阳.陕西师范大学计算机科学学院硕士研究生.主要研究方向为密码学与信息安全.

E-mail: yangkunwei@163.com

A Publicly Verifiable Anonymous IBE Scheme in the Standard Model

LI Shun-dong，YANG Kun-wei，GONG Lin-ming，MAO Qing，LIU Xin

(SchoolofComputerScience,ShaanxiNormalUniversity，Xi′an,Shaanxi710119,China)

Abstract:Constructing a stronger security encryption system based on a weaker computationally hard assumption is of great theoretical and practical importance in identity-based encryption.To solve this problem,we,based on a weaker assumption that the decisional bilinear Diffie-Hellman problem is hard,construct an anonymous identity-based encryption scheme which is secure against adaptively chosen ciphertext attack.This scheme can prevent an identity-based encryption system from disclosing privacy.Compared with the existing schemes based on stronger computationally hard assumption,the prerequisite of our scheme can be satisfied more easily,besides,it is publicly verifiable and more efficient.

Key words:identity-based encryption;anonymous;publicly verifiable;chosen ciphertext attack;decisional bilinear Diffie-Hellman assumption

作者简介

DOI:电子学报URL:http://www.ejournal.org.cn10.3969/j.issn.0372-2112.2016.03.027

中图分类号:TP309

文献标识码：A

文章编号：0372-2112 (2016)03-0673-06

基金项目:国家自然科学基金(No.61070189,No.61272435,No.61373020)

收稿日期:2014-10-28;修回日期:2015-4-23；责任编辑：覃怀银