电子邮件系统中支持关键字搜索的代理重加密方案

牛淑芬,陈俐霞,刘文科,王彩芬,杜小妮

(西北师范大学 a.计算机科学与工程学院; b.数学与统计学院,兰州 730070)

0 概述

在电子邮件系统中,当数据发送者发给用户的邮件因用户的私人原因而无法及时处理时,用户希望将该邮件共享给被委托者,并由对方帮助其处理该邮件。一般情况下,用户先下载某个邮件,用其私钥解密该邮件并使用被委托者的公钥进行加密处理,最后发送给被委托者,该方式需要较大的计算代价和通信代价,而代理重加密(Proxy Re-Encryption,PRE)技术可有效解决这一问题。

1998年,BLAZE等人[1]提出PRE的概念,主要内容是委托者通过一个半可信的代理者将密文授权给被委托者,且在这个过程中,代理者得不到消息的任何信息。文献[2]提出一个单向的PRE方案,但是该方案只能达到选择明文安全的要求,文献[3]提出第一个满足IND-CCA2的双向PRE方案。文献[4]在文献[5]的基础上,改进了方案的安全模型,并构造一个安全的IND-CCA2单向的PRE方案。文献[6]提出多跳PRE方案,同年,文献[7]提出电子病历中带关键字搜索的公钥加密方案。为解决复杂证书问题和密钥管理问题,文献[8]提出新的基于证书条件的PRE方案。文献[9]构造管理云端数据访问授权确定性更新的PRE方案。为解决云端数据共享问题,文献[10]提出标准模型下CPA安全的格上PRE方案。

随着电子邮件服务器上数据的增加,为了实现密文搜索和数据共享2个功能,文献[11]提出带关键字搜索的PRE的概念,且构造在随机预言模型下可证明安全的PRES方案,但文献[12]指出文献[11]存在使用了一次性强不可伪造签名来保证方案安全性的限制。文献[13]构造出有效且不使用一次性强不可伪造签名的PRE方案,并证明该方案可使选择密文安全。为提高方案的效率,文献[14]依据文献[11,15]构造出只对部分文件的密文进行重加密的方案模型。为抵抗由不可信服务器执行的关键字猜测攻击,文献[16]提出新的支持关键字搜索的加密方案,文献[17]提出基于关键字搜索属性的PRE方案。

现有的支持关键字搜索的PRE方案存在一些问题需要解决,如抵抗关键字猜测攻击和数据篡改等。在文献[18-19]中,验证等式的信息都是公开信息或对方发送的信息,易遭受篡改攻击。针对这一问题,本文提出在加密电子邮件背景下支持关键字搜索的PRE方案。在该方案中,服务器、邮箱网关与被委托者的验证方式均不同,并且其采用更加高效的对称加密方式,以提高搜索效率和解密效率。

1 基础知识

1.1 双线性对

令(G1,+)和(G2,×)是阶为素数p、q的循环群,双线性映射e:G1×G1→G2满足以下性质:

2)非退化性:存在P,Q∈G1,满足e(P,Q)≠1。

3)可计算性:对于任意的P,Q∈G1,存在有效的算法计算e(P,Q)。

1.2 相关的困难问题

1)判定Diffie-Hellman(Decisional Diffie-Hellman,DDH)问题。

2)双线性判定Diffie-Hellman(Decisional Bilinear Diffie-Hellman,DBDH)问题。

3)商判定Bilinear Diffie-Hellman(Quotient Decisional Bilinear Diffie-Hellman,QDBDH)问题。

2 方案模型和安全模型

2.1 方案摸型

本节提出面向电子邮件高效支持关键字搜索的PRE方案。本方案实现了密文授权和密文搜索的功能,具体如下:邮件发送者将已加密的邮件发送给用户i,而用户i希望将该邮件授权给用户j处理,便由加密邮箱服务器作为代理者对密文进行重加密,将邮箱网关搜索重加密邮件密文,并发送给用户j解密。该方案包括如下算法:

1)Setup(I):输入安全参数Il,输出系统参数Params。

2)KeyGen(Params):输入系统参数Params,输出用户和加密邮箱服务器S的公私钥对。

3)ReKeyGen(Xi,Xj):输入用户i的私钥Xi和用户j的私钥Xj,加密邮箱服务器S生成重加密密钥RKi→j。

4)Enc(Yi,YS,w,m):输入用户i的公钥Yi、加密邮箱服务器S的公钥YS、关键字w和明文m∈{0,1}*,输出基于用户i公钥的密文CTi。

5)ReEnc(CTi,Yi,XS):输入基于用户i公钥的密文CTi、用户i的公钥Yi、加密邮箱服务器S的私钥XS、重加密密钥RKi→j,加密邮箱服务器S输出基于用户j公钥的密文CTj。

6)Trapdoor(Xj,Ys,w,CTj):输入用户j的私钥Xj、加密邮箱服务器S的公钥YS、基于用户j公钥的密文CTj和关键字w,用户j生成陷门T。

7)Test(CTj,T):输入基于公钥的密文CTj和关键字陷门T,邮件网关通过算法Test(CTj,T)验证陷门与密文是否匹配。若陷门与密文相匹配,邮件网关发送基于用户j公钥的密文给用户j,否则,邮箱网关输出⊥。

8)Dec(CTj):输入密文CTj和私钥Xj,用户j输出明文m。

2.2 安全模型

在标准模型下,本文方案满足关键字密文隐私安全和陷门隐私安全[20-22]。

2.2.1 关键字密文隐私安全

为满足关键字密文的不可区分性,本文方案考虑敌手Ai(i=1,2)和挑战者B之间的2个游戏。

游戏1该游戏的目的是证明密文的不可区分性。在游戏中,本文方案假设敌手A1是恶意的邮箱服务器。

系统建立挑战者B产生公共参数并将其给敌手A1。

询问阶段1敌手A1进行如下询问:

1)公钥预言询问OYi(i):挑战者B模拟算法KeyGen产生公私钥对(Yi,Xi)并将公钥Yi公开;敌手A1模拟算法KeyGen产生它的公私钥对(Yj,Xj)并将公钥Yj公开。

2)重加密密钥询问阶段ORK(Xi,Xj):挑战者B模拟ReKeyGen算法产生重加密密钥RKi→j并输出给敌手A1。

3)重加密预言阶段ORe(Yi,Yj,CTi):挑战者B模拟重加密算法生成基于被委托者公钥的密文CTj并将其发送给敌手A1。

4)陷门预言阶段OT(w,Xj):敌手进行询问,挑战者B则回应相对应的陷门。

5)解密预言阶段ODec(Yi,CTj):挑战者B输出Dec(CTj)给敌手A1。

挑战当询问阶段1完毕,敌手A1选择2个明文(m0,m1)发送给挑战者B。挑战者B随机选取δ∈{0,1},并设置嵌入困难问题的挑战密文发送给敌手A1。

询问阶段2除了不能询问挑战密文及其衍生外,其他询问同询问阶段1一致。

游戏2该游戏的目的是证明关键字的不可区分性。在游戏中,本文方案假设敌手A2是外部攻击者,在游戏中,挑战者B和敌手A2进行如下交互:

系统建立挑战者B产生公共参数并将其给敌手A2。

询问阶段1重复游戏1中的询问阶段1。

挑战当询问阶段1结束,敌手A2选择2个关键字(w1,w2)、明文m和公钥Y*一起发送给挑战者B。挑战者B随机选择δ∈{0,1},并设置嵌入困难问题的挑战密文发送给敌手A2。

询问阶段2敌手A2进行询问时,除了不能询问挑战密文及其衍生外,其他询问同询问阶段1一致。

2.2.2 陷门隐私安全

为了抵抗关键字猜测攻击,文献[12]引入了陷门不可区分性。

游戏3假设敌手A3是外部攻击者,在游戏中,挑战者B和敌手A3进行如下交互:

系统建立挑战者B产生公共参数并公开。

询问阶段1敌手A3对关键字w进行陷门询问,挑战者B回应陷门。

挑战阶段敌手A3选择2个关键字(w1,w2)、明文m和公钥Y*一起发送给挑战者B。挑战者B随机选取δ∈{0,1},并计算陷门发送给敌手A3。

询问阶段2除了不能询问挑战关键字及其衍生外,其他询问同询问阶段1一致。

3 方案设计

3.1 方案构造

本文提出的方案包括8个部分,具体设计如下:

4)Enc(Yi,YS,w,m):输入用户i的公钥Yi、加密邮箱服务器S的公钥YS、关键字w和明文m∈{0,1}*,用户i进行如下操作:

(4)输出基于用户i公钥的密文CTi=(t,A,B,C,D,D1,E,F,G)。

5)ReEnc(CTi,Yi,XS):输入密文CTi、用户i的公钥Yi、加密邮件服务器S的私钥XS和重加密密钥RKi→j,邮件服务器S计算h=H1(A,C,E),并验证式(1)是否成立:

(1)

7)Test(CTj,T):输入基于用户j公钥的密文CTj=(t,A,B′,C,D,D1,E,F,G)和关键字w的陷门T,加密邮件网关验证式(2)是否成立:

e(B′,T)=D1

(2)

若式(2)成立,用加密邮件网关将基于用户j公钥的密文CTj发送给用户j;否则输出⊥。

8)Dec(CTj):输入密文CTj,用户j计算h=H1(A,C,E),并验证式(3)是否成立:

(3)

若式(3)成立,用户j通过式(4)计算对称密钥K′,则明文m=DecK′(C);否则输出⊥。

(4)

3.2 正确性证明

本文方案满足正确性。在重加密过程中,邮件服务器验证式(1)是为了证明密文CTi在传输过程中并没有被篡改。在搜索过程中,加密邮件网关通过验证式(2)来实现关键字与密文之间的匹配。在解密过程中,用户j通过式(3)验证重加密密文是否被篡改,通过式(4)解密密文。验证过程如下:

因此本文方案是正确的。

4 安全性证明

4.1 关键字密文隐私安全

定理1假设解决QDBDH和DBDH问题困难,本文方案在标准模型下可证明IND-CCA和IND-CKA是安全的。

引理1假设解决QDBDH问题困难,本文方案在标准模型下可证明IND-CCA是安全的。

系统建立挑战者B选取随机数a0,a1,a2,a3,b1,b2,b3,计算系统参数g2=Ma0,h=Mb,u=ga1Nb1,v=ga2Nb2,d=ga3Nb3。

询问阶段1敌手A1进行如下询问:

2)重加密密钥询问阶段ORK(Xi,Xj):从列表Llist中调用三元组(Yi,Xi,ci),并查询Xi和Xj是否存在三元组中,若不存在,则调用公钥预言询问OYi(i),否则进行如下操作:

(3)否则,挑战者B输出⊥。

3)陷门预言阶段OT(w,Xj):挑战者B从列表Llist中调用三元组(Yi,Xi,ci)并查询Xj是否存在三元组中,若不存在,则调用公钥预言询问OYi(i),否则进行如下操作:

4)重加密预言阶段ORE(Yi,Yj,CTi):若式(1)验证失败,则挑战者B输出⊥;否则挑战者B从列表Llist中恢复三元组(Yi,Xi,ci)并执行如下操作:

(1)若ci和cj均为1或均为0,则挑战者B调用重加密密钥询问ORK(Xi,Xj),生成重加密密钥RKi→j,然后将ReEnc(CTi,RKi→j)返回给敌手A1。

(5)

(3)若ci=1∧cj=0,则意味着用户i的私钥为aXi和用户j的私钥为Xj,挑战者B计算B′=gaXjr=(Mr)Xj=AaXj。

5)解密预言阶段ODec(Yi,CTj):挑战者B从列表Llist中恢复三元组(Yi,Xi,ci)并执行如下操作:

(2)若cj=1,则用户j的私钥为Xj,挑战者B将输出Dec(CTj)给敌手。

询问阶段2敌手A1进行询问,除了挑战密文及其衍生不能询问外,其他与询问阶段1一致。

猜测最后敌手返回猜测δ′,如果δ′=δ,则挑战成功,输出1;否则输出0。

引理2假设解决DBDH问题困难。本文方案在标准模型下可证明IND-CKA是安全的。

系统建立挑战者B随机选取数a0,a1,a2,a3,b1,b2,b3,计算系统参数g2=Ma0,h=Mb,u=ga1Nb1,v=ga2Nb2,d=ga3Nb3。

询问阶段1敌手A2进行如下询问:

5)解密预言阶段ODec(Yi,CTj):挑战者B输出Dec(CTj)给敌手A2。

询问阶段2敌手A2进行询问,除了挑战密文及其衍生不能询问外,其他同询问阶段1一致。

猜测敌手返回猜测δ′,若δ′=δ,则挑战成功,输出1;否则输出0。

4.2 陷门隐私安全

定理2假设解决DDH问题困难。本文方案可证明在陷门上是安全的。

系统建立挑战者B选取随机数a0、a1、a2、a3、b1、b2、b3、并计算系统参数g2=Ma0,h=Mb。

询问阶段1敌手A3进行如下询问:

2)陷门预言阶段OT(w,Xj):挑战者B从列表Llist中调用三元组(Yi,Xi,ci)并查询Xj是否存在三元组中,若不存在,则调用公钥预言询问OYi(i),否则进行如下操作:

询问阶段2敌手A3进行询问,除了不能询问挑战关键字及其衍生外,其他同询问阶段1一致。

猜测敌手A3返回猜测δ′,若δ′=δ,则挑战成功,输出1;否则输出0。

5 效率分析

通过理论和数值实验对dPRES[18]方案和本文方案进行分析。首先从理论上对计算开销进行分析,dPRES方案和本文方案效率比较结果见表1,其中Tp、TF、Th、Te、Teo分别为双线性运算、伪随机函数族运算、哈希运算、指数运算和异或运算的计算代价。

表1 dPRES方案与本文方案的效率比较

由表1可知,在搜索阶段,本文方案比dPRES方案少一个指数运算和两个哈希运算。此外,在解密阶段,本文方案比dPRES方案少一个双线性对运算。因此,与dPRES方案相比,本文方案在计算效率上有较大的提高。

为了更直观地显示结果,本节从数值分析上对方案的计算成本进行了模拟。在Linux系统上使用PBC库,基于C语言编程实现dPRES方案和本方案。数值环境配置参数如表2所示。

表2 环境配置参数

本文方案和dPRES方案均能实现密文授权和搜索功能。在数值实验中,加密和解密阶段两方案均加密相同数量的关键字,随着关键字数量的变化,统计在不同数量关键字下的加密时间,结果如图1所示。

图1 关键字数量对加密时间的影响

由图1可知,在加密阶段,本文方案的时间开销较dPRES方案高。搜索阶段是统计搜索不同数量关键字的时间开销,如图2所示。

图2 关键字数量对搜索时间的影响

由图2可知,在搜索阶段,当关键字数量为10个时,本文方案的时间开销为42 ms,而dPRES方案的时间开销为164.4 ms;当关键字数量为30个时,本文方案的时间开销为122.4 ms,而dPRES方案的时间开销为456.2 ms;当关键字数量为50个时,本文方案的时间开销为198.9 ms,而dPRES方案的时间开销为762.2 ms。随着关键字数量的增加,dPRES方案的时间开销增长速率比本文方案大,说明本文方案的搜索效率优于dPRES方案。

统计在不同数量关键字下的解密开销时间,如图3所示。

图3 关键字数量对解密时间的影响

由图3可以看出,在解密阶段,随着关键字数量的增大,本文方案的时间开销几乎保持不变;当关键字数量为10个时,dPRES方案的时间开销为85.7 ms;当关键字数量为30个时,dPRES方案的时间开销为236.5 ms;当关键字数量为50个时,dPRES方案的时间开销为390.8 ms,说明dPRES方案的时间开销与关键字数量之间呈线性增长。因此,本文方案的解密效率优于dPRES方案。

由图1～图3可知,虽然在加密阶段,本文方案的时间开销较dPRES方案高,但是在搜索阶段,本文方案时间开销远远小于dPRES方案,且在解密阶段,本文方案时间开销也低于dPRES方案。因此,本文方案在解密算法和搜索算法的计算代价上有明显优势,减少了电子邮箱服务器和用户之间的通信代价,提高了系统的性能。

6 结束语

为解决密文授权和密文搜索问题,本文提出一种面向电子邮件支持高效关键字搜索的PRE方案。该方案在搜索过程中只用了一个双线性对,因此搜索效率较高。同时,本文方案在标准模型下关键字隐私、密文隐私和陷门隐私是安全的,还可以抵抗篡改攻击和关键字猜测攻击。分析结果表明,相对dPRES方案,本文方案在搜索效率上有较大的提升。目前,支持关键字搜索的PRE方案还有一些问题需要解决,如进一步减少时间开销,提高方案的计算效率和通信效率等,这将是下一步的研究方向。