面向云存储的带关键词搜索的公钥加密方案

郭丽峰 李智豪 胡 磊

1(山西大学计算机与信息技术学院 太原 030006)2(山西大学大数据科学与产业研究院 太原 030006)3(信息安全国家重点实验室(中国科学院信息工程研究所) 北京 100093)

云存储由于其低成本、具有无限数据存储空间的特点，已受到广泛重视和应用.用户可以将大量数据存储在云服务器上.但是云服务器并不完全可信，为了保证用户数据的安全，用户的敏感数据通常需要加密后再存储在云服务器上.但是在传统的密文存储和查询服务中，由于云服务器没有检索功能，不能根据用户需求查找数据.带关键词搜索的公钥加密体制解决了在云服务器不可信的条件下加密数据检索的问题.其主要思想是：发送者首先分别加密数据和关键词上传至云服务器；然后接收者发送一个由关键词生成的陷门给云服务器；最后云服务器执行关键词密文和陷门的匹配算法.云服务器判断密文和陷门是否包含相同的关键字，若是则将密文数据发送给接收方，此过程云服务器不能获得关键词和明文数据的任何信息.

Boneh等人[1]在2004年首次提出了带关键词搜索的公钥加密方案(public key encryption with keyword search， PEKS)(下文中的公钥加密算法记为PEKS)，该方案是通过基于身份的加密方案(identity-based encryption， IBE)[2]所构造，其基本思想是：将PEKS中的关键词w替代IBE中用户的身份ID，将PEKS中接收者给服务器的陷门替代IBE用户的私钥，所以要求基于身份的加密方案必须具有匿名性才能转换成带关键词搜索的公钥加密方案.文献[1]在接收者给云服务器传输陷门时，需要安全信道，导致昂贵的开销，而且方案的安全性是在随机预言模型(random oracle model， RO)下进行证明的.Baek等人[3]提出了无安全信道的可搜索加密方案(secure channel free PEKS， SCF-PEKS)，其方法是通过引入云服务器的公私钥对来消除安全信道，只有指定的服务器才能够对关键词密文与陷门进行匹配.但是其方案也是在随机预言模型下进行的安全性证明，而且在安全性证明中当云服务器为攻击者时，云服务器的公私钥对却由模拟器来产生，这样不符合实际要求，因为在公钥加密体制中，公私钥对应该由自己产生，而不应该由第三方产生.此后Rhee等人[4-5]加强了Baek等人的安全模型，即攻击者的公私钥对由其自己产生，这样符合实际情况，并提出了一系列指定检验者的关键词搜索方案(designated tester PEKS， dPEKS)，但是这些方案也是在随机预言模型下可证明安全且不能抵制选择密文攻击.Fang等人[6]利用Gentry[7]的基于身份加密方案构造了标准模型下的带关键词搜索方案.随后在文献[8]中，通过引入一次性强签名方案，能够抵制选择关键词和密文攻击.但文献[8]在安全性证明中，敌手的公私钥对也是由模拟器来产生.

2006年Byun等人[9]首次提出外部的离线关键词猜测攻击(resist external keyword guessing attack, REKGA)的概念，并对文献[1，10]的PEKS方案进行了离线关键词猜测攻击;Jeong等人[11]指出:满足一致性的PEKS方案一定不能够抵制关键词猜测攻击;在文献[12]的安全性证明中，指出仅当敌手能得到陷门且自己能进行验证的前提下，该结论才成立，所以得出满足一致性的PEKS方案一定不能够抵制内部关键词猜测攻击，因为对于服务器来说，既能得到陷门又能自己进行陷门和关键词密文的匹配验证;Rhee等人[4]提出了陷门不可区分性的概念，并证明陷门不可区分性是抵抗外部关键词猜测攻击的充分条件，并提出了一个具体的方案抵制外部离线关键词猜测攻击;Guo等人[13]和Fang等人[8]构造出一个可抵抗外部敌手进行关键词猜测攻击的方案，并在标准模型下证明方案的安全性，但文献[8，13]都不能抵制内部服务器进行离线关键词猜测攻击.

2013年Yau等人[14]提出文献[12]不能抵制内部离线关键词猜测攻击，即当服务器是攻击者的情况下的攻击，其基本思路是服务器自己猜测一些关键词，然后进行加密，由于服务器能够得到陷门并且通过陷门进行检验，从而得出陷门包含了哪个关键词;文献[14]指出:相似于文献[12]的PEKS方案构造都不能抵制上述攻击,文献[14]还提出了一种在线关键字猜测攻击类型(online keyword guessing attack， OKGA)，这种类型的敌手是一个外部攻击者，敌手可以对所有可能的关键词w都配对一个虚假的明文数据m′，并将它们加密上传至云服务器，并对服务器和目标接收者的通信进行监听.一旦服务器将包含明文数据m′的加密文档发送给接收者，攻击者会知道接收者的陷门包含哪个关键词.

为了抵制内部(即服务器)离线关键词猜测攻击，Shao等人[15]在Fang等人[8]的基础上引入了发送者的身份，通过确定性RSA算法对发送者身份进行签名，当服务器自己产生关键词密文时，却不能进行匹配测试.文献[15]声称其方案能够抵抗内部关键词猜测攻击，但文献[16]指出，该方案中的服务器必须诚实地进行测试，但事实上，服务器可以是恶意的，同时Lu等人[16]指出文献[8]不能抵制外部离线关键词猜测攻击，但服务器必须提供在线服务.文献[16]在文献[8]的基础上提出一个能抵制内部离线关键词猜测攻击的PEKS方案，而且该方案在标准模型下可抵制选择密文攻击.2017年Huang等人[17]在对关键词加密时引入发送者的私钥，实现公钥认证加密功能，从而抵制内部离线关键词猜测攻击，但是这个方案的陷门是固定的，且被指出不满足密文不可区分性[18].Li等人[19]引入了权威机构对用户进行授权认证，并产生对应的身份私钥，随后用户用其私钥对关键词密文进行认证加密，但该方案仍旧是在随机预言模型下进行的安全性证明.Lu等人[20]采用签密的思想来抵制内部离线关键词猜测攻击，即在产生关键词密文的过程中，使用发送者的私钥，由于除了发送者，任何人不知道发送者的私钥，敌手不能产生合法的关键词密文来匹配任何关键词陷门.这种构造方式的局限性是，当接收者产生关键词陷门时，必须要涉及到发送者的公钥或身份，所以相当于接收者事先委派了发送者，这样会影响实际使用效果.使用这种技巧使得方案抵制内部关键词猜测攻击有文献[17-22].文献[23]通过将密文随机化来抵制外部在线和离线关键词猜测攻击.文献[20]指出构造具有任何搜索功能，而不受接收者委派，但是还能够抵制各种关键词猜测攻击的PEKS方案是一个公开问题.

最近文献[24]阐述了基于对称密码学和基于公钥密码学而构造的可搜索加密机制的不同特点，分析了可搜索加密机制在支持单词搜索、连接关键词搜索和复杂逻辑结构搜索语句的研究进展;文献[25]首先介绍了关于可搜索加密的理论研究进展情况，最后指出了关于可搜索加密应用的公开问题和未来发展趋势;文献[26-28]都对可搜索加密进行了综述性的总结，文献[27]提出一种多用户的可搜索方案，用户按照自己的意愿设置访问权限，不需要1个可信的用户搜索中心，弱化了可信第三方的功能.

综上所述，从6个方面对PEKS的安全模型进行总结：

1) 陷门是否通过公开信道传输.通过引入服务器的公私钥对，使得在检验中必须使用服务器的私钥才能检验，从而使得陷门可以在公开信道传输.

2) 是否在标准模型下进行安全性证明.因为随机预言模型下进行的安全性证明只是一种启发式证明，所以在标准模型下可证明方案的安全性是加密方案证明的终极目标.

3) 是否抵制适应性选择关键词攻击.从2方面考虑：敌手为恶意的服务器或恶意的接收者.

4) 是否抵制关键字猜测攻击.从3种情况考虑：外部离线关键词猜测攻击、外部在线关键词猜测攻击、内部离线关键词猜测攻击.

5) 在安全性证明中，敌手的私钥是否必须由挑战者来产生.实际情况是敌手自己产生私钥，但在很多方案中，由于模拟器要利用敌手的私钥，所以敌手的私钥由模拟器来产生，不符合实际情况.

6) 是否抵制适应性选择密文攻击.已有的方案通过引入一次性强不可伪造签名方案抵制适应性选择关键词攻击.这样使得所构造的方案效率较低.通过直接构造来抵制适应性选择关键词攻击成为公开问题.

表1进行了总结，指出目前构造的一些PEKS方案满足哪些安全性要求，其中一些安全性要求缩写为：抵抗选择关键词攻击(resist chosen keyword attack， RCKA)，分2种情况，攻击者为服务器(server)或接收者(receiver)，抵制选择密文攻击(resist chosen ciphertext attack， RCCA)、抵制外部关键词猜测攻击(resist external keyword guessing attack， REKGA)、抵制内部关键词猜测攻击(resist internal keyword guessing attack， RIKGA)、认证功能(authentication Function， AF)、抵制在线关键字猜测攻击(resist online keyword guessing attack，ROKGA).

Table 1 Performance Comparison of Security Model of PEKS表1 PEKS安全模型的性能对比

针对上述问题，本文的主要贡献有3个方面：

1) 提出一种能够抵制内部关键词猜测攻击的带关键搜索的公钥加密方案.目前使用的技巧是通过发送者在加密的同时使用了数字签名，这样使得内部攻击者即服务器不能够产生关键词密文，从而抵制了内部关键词猜测攻击，相当于接收者事先需要指定密文的发送者.但是在很多实际情况下，接收者不知道发送者是谁.本文通过引入发送者和服务器的身份，并将其放在方案中算式的分母上，使得服务器无法自己产生关键词密文，从而抵制内部关键词猜测攻击.

2) 由于关键词密文能够进行公开验证其正确性，本文构造的方案能够抵制适应性选择密文攻击，而且所构造的方案没有使用额外的一次性强不可伪造签名，从而方案的效率很高.

3) 本文的陷门是在公开信道传输，而且能够抵制适应性选择关键词攻击，且方案是在标准模型下可证明安全.

1 基础知识

1.1 双线性对

记G1=g表示由生成元g生成的有限群G1.输入安全参数k，输出双线性映射的参数(p,g,G1,G2,e)，其中G1和G2是阶为素数p的循环群，g是G1的生成元，映射e:G1×G1→G2具有3个性质：

2) 非退化性.对G1的生成元g，有e(g,g)≠1.

3) 可计算性.对于任意的g,h∈G1，存在多项式时间算法计算e(g,h).

1.2 相关的困难问题

1) 商判定双线性Diffie-Hellman(QDBDH)假设.

2) 判定双线性Diffie-Hellman(DBDH)假设.

3) Hash Diffie-Hellman(HDH)假设.

设hLen是一个整数且H:{0,1}*→{0,1}hLen是一个Hash函数.G1中HDH问题定义为：

没有多项式时间算法至少以优势ε在G1中解决HDH问题，我们称HDH假设在G1中成立.

2 SCF-PEKS模型

2.1 SCF-PEKS系统模型

本节我们介绍SCF-PEKS模型，它是一个不需要接收者与服务器建立安全信道的带关键词搜索加密模型，系统中包含4个实体，即系统参数生成中心(system parameter generation center， SPGC)、数据发送者(data sender， DS)、数据接收者(data receiver， DR)、云服务器(cloud server， CS)，系统模型如图1所示：

Fig. 1 System model of PEKS图1 PEKS系统模型

1) 系统参数生成中心

系统参数生成中心是系统中唯一的可信第三方，运行Setup算法产生系统的公开参数，并把公开参数发送给系统中的其他实体.

2) 数据发送者

数据发送者收到公开参数之后，运行PEKS算法，对明文数据和关键词加密并上传至云服务器.

3) 数据接收者

数据接收者运行KeyGenR算法产生自己的公私钥，运行dTrapdoor算法生成关键词对应的陷门，并上传至云服务器.

4) 云服务器

云服务器是一个诚实且好奇的实体，运行KeyGenS算法产生自己的公私钥，运行是dTest算法为接收者提供搜索服务.

5) 云服务器

云服务器最后把搜索的结果返回给数据接收者.

2.2 SCF-PEKS算法定义

我们的算法只关注关键词加密部分，具体为：

1)Setup(1k).该算法由系统参数生成中心执行，输入安全参数1k，输出公开参数params.

2)KeyGenR(params).该算法由数据接收者执行，输入公开参数params，输出他的公私钥对(pkR,skR).

3)KeyGenS(params).该算法由云服务器执行，输入公开参数params，输出他的公私钥对((pkS,skS)).

4)PEKS(params,pkR,pkS,IDsender,w).该算法由数据发送者执行，输入公开参数params、接收者的公钥pkR、服务器的公钥pkS、发送者的身份IDsender、关键词w，输出关键词的密文CT.

5)dTrapdoor(params,pkS,skR,IDserver,w).算法由数据接收者执行，输入公开参数params、接收者的私钥skR、服务器的公钥pkS、服务器的身份IDserver、关键词w，输出关键词的陷门Tw.

6)dTest(params,CT,Tw,skS,pkR,IDsender,IDserver).该算法由云服务器执行，输入关键词的密文CT和陷门Tw、接收者的公钥pkR、服务器的私钥skS、发送者的身份IDsender、服务器的身份IDserver，输出是否匹配成功.

2.3 SCF-PEKS安全模型

3 SCF-PEKS方案

3.1 SCF-PEKS方案的构造

本节提出了一个不仅可以抵抗内部关键词猜测攻击而且能够抵抗适应性选择关键词密文攻击的方案，具体算法为：

4)PEKS(params,pkR,pkS,IDsender,w).输入公开参数params，接收者的公钥pkR，服务器的公钥pkS，发送者的身份IDsender，关键字w，发送者计算关键词的密文为：

③ 输出关键词密文CT=(s′,C1,C2,C3,C4)并发送给服务器.

6)dTest(params,CT,Tw,skS,pkR,IDsender,IDserver).该算法由云服务器执行，输入关键词的密文CT和陷门Tw，接收者的公钥pkR，服务器的私钥skS=xS，发送者的身份IDsender，服务器的身份IDserver.服务器首先计算h′=H2(C1,C2,C3)，判断e(C1,(uh′vs′d))=e(pkR,C4)是否相等.若不相等则匹配失败，终止该算法.

3.2 计算正确性与一致性分析

1) 正确性.正确的关键词密文CT必须与正确关键词陷门Tw匹配，服务器才能测试成功.在dTest算法中，有：

因此:

dTest(params,CT,Tw,skS,pkR,
IDsender,IDserver)=“yes”.

H1[(e(C1,T′xS)C2)]≠C3.

4 SCF-PEKS安全性分析

定理1.假设QDBDH和DBDH问题是困难问题，我们的方案在标准模型下是可证明安全的.

引理1.假设QDBDH问题是困难问题，我们的方案在标准模型下能够抵抗选择关键词和密文攻击(chosen keyword and ciphertext attack， CKCA).

C*1=gx*R=(ga)x*R(1a)=(Ax*R)r*=p，
C2=QxS(wδ×α0×IDsender+β)=

e(pkS,B)(wδ×α0×IDsender+β)a=
e(pkS,Bwδ×α0×IDsenderBβ)=

C*3=H1(QxS(wδ×α0))=H1(e(pkS,g(wδ×α0))ba)=
H1(e(pkS,B(wδ×α0))r*)，
C*4=g(α1h′*+α2s′*+α3)=(Aα1h′*+α2s′*+α3)r*=
(gxuh′*+xvs′*×Aα1h′*×Aα2s′*×Aα3)r*=
((gxu×Aα1)h′*(gxv×Aα2)s′*Aα3)r*=(uh′*vs′*d)r*，

因为Q在G2是独立且均匀分布的，所以挑战密文CT*也独立于δ.

Pr[Abort]至少为因此

证毕.

引理2.假设DBDH问题是困难问题，我们的方案在标准模型下能够抵抗选择关键词攻击(chosen keyword attack， CKA).

证毕.

定理2.假设HDH问题是困难问题，我们的方案在标准模型下能够抵抗离线关键词猜测攻击(off-line keyword guessing attack， KGA).

T*1=B=gr′*,

证毕.

5 SCF-PEKS性能对比

Table 2 Efficiency Comparisons of Different Schemes表2不同方案的效率对比

Fig. 2 Computation cost of PEKS图2 加密关键字的计算代价

Fig. 3 Computation cost of trapdoor图3 陷门产生的计算代价

Fig. 4 Computation cost of test图4 匹配的计算代价

Table 3 Performance Comparison of Security Model Between Ours Scheme and Other Two Schemes表3 本文方案和其他2种方案安全模型的性能对比

6 总结与展望

本文构造了一个高效率的带关键词搜索公钥加密方案，该方案能够抵制内部、外部离线关键词猜测攻击，而且在不使用安全信道的前提下可抵制适应性选择密文攻击.但本文的不足是，在安全性证明中敌手的私钥由模拟器来产生.下一步的工作是构造一个更符合实际应用的带关键词搜索的公钥加密方案.