一种可抵抗关键词猜测攻击的动态非对称可搜索加密方案

李智译，汪学明，王泽贤

(贵州大学计算机科学与技术学院，贵州 贵阳 550025)

0 引 言

由于计算机技术的发展和现代社会数据量的不断膨胀，使得公司的数据存储成本越来越高，于是云服务和云存储技术应运而生，没有自己服务器的公司往往选择将数据交给云服务器提供商进行管理和储存，但大多数公司的数据都以明文的形式放在服务器上，这可能会带来数据隐私被窥探的风险。密文搜索研究最先开始于文献[1],Song指出将数据存在不可信的云服务器时，为保证数据安全性，只有把原始的明文数据进行加密，再上传到服务器，并首次提出第一个实际的可搜索加密方案。此后，许多相关人员陆续开展了可搜索加密的研究。根据可搜索加解密过程使用密钥性质的不同，可搜索加密方案可分为对称和非对称2种[2]。2003年，Goh[3]创建了一种安全索引——布隆过滤器，通过多个hash函数为每个文件的所有关键词建立映射数组，待查询关键词通过与数组进行匹配查询。不同于文献[3]，Curtmola等人[4]构建索引的思路为关键词-文档，以关键词陷门为索引的键值，将包含某个关键词的所有文件进行聚集，搜索时，不用每次都要扫描所有文件，大大提高了搜索的效率。2012年，Kamara等人[5]使用一种inverted index的索引结构实现了完全支持动态操作的对称可搜索加密方案。2014年，文献[6]使用文件索引表和查询索引表构造了能快速进行查找、添加的动态可搜索加密方案。2018年，许盛伟等人[7]通过引入ABE加密思想，实现了一对多用户的文件动态更新的基于属性的可搜索加密方案。在2019年，孙晓玲等人[8]针对文献[7]中对文件删除效率过低的缺点，增加了一个删除索引表，比较原方案，删除效率有了很大的提高。相对于对称可搜索加密，2004年Boneh等人[9]在密文搜索中使用了非对称密钥，基于双线性Diffie-Hellman假设和陷门排列各设计了一个公钥可搜索加密(PEKS)方案，用公钥对关键词和密文进行处理，使用私钥和待查询的关键词生成陷门。后来，Abdalla等人[10]发现基于身份的加密方案(IBE)与PEKS的共性，描述了将IBE转化为PEKS的一般变换算法，并给出了一种满足统计一致性的PEKS方案。金海以及倪绿林等人[11-12]基于双线性Diffie-Hellman困难问题各设计了一种方案，在构造中利用文件的身份ID来进行删除操作，当需要删除某个文件时，只需将其ID发送给服务器即可完成删除。文献[13-16]则针对现有的大多数PEKS方案无法抵抗关键词猜测攻击而进行了研究。因为双线性运算的复杂性，一些学者也提出了一些不依赖双线性对的方案[17-18]。上述方案都是针对特定用户的，文献[19-20]分别提出了一种支持动态增加删除用户的方案，文献[21]则在考虑了多用户场景的基础上，将可搜索密文放在了多个服务器上，郎晓丽等人[22]针对文献[21]不能应用在公开信道中作出了改进。

通过研究发现，现有使用公钥密码体制的密文搜索方案极少涉及密文文件的动态更新，为此参考对称可搜索加密方案索引的构造思想，本文提出一种安全的动态公钥可搜索加密方案(简称DNBP-PEKS)，使得用户能对云端的秘密文件安全高效地搜索、删除和添加。

1 系统模型

系统的参与者主要有三方：数据拥有者、数据使用者和服务器，具体如图1所示。

一个DNBP-PEKS方案主要包括以下几个部分：

1)Keygen(k)。输入安全参数k,得到公私钥对K=(sk,pk)，一般地k是指所使用的大素数p二进制位的长度。

2)Enc(K,f)。输入K和明文文件集f,数据拥有者对明文文件进行分词得到关键词集合W，使用服务器和用户公钥将明文文件和关键词加密后上传到服务器。

3)Trapdoor(K,W,ID,f)。用户使用掌握的密钥和待查询的关键词，待增加的文件或者待删除的文件ID生成相应的安全陷门。

4)Test(Tw,Tid,c)。服务器输入陷门，密文集合c，根据目的不同，返回给用户相应的结果。

5)Dec(K,cf)。如果第4步成功，用户使用私钥解密返回的文件。

图1 系统结构

2 基础知识

2.1 判定性Diffie-Hellman假设(简称DDH假设)

2.2 HDH困难问题假设

Pr[A(g,ga,gb,H(gab))=1]|≤negl(k)

2.3 区别引理

设E、S1、S2是3个不同的事件，S1|E发生当且仅当S2|E，则有|Pr[S1]-Pr[S2]|≤Pr[E]。

2.4 安全性定义

传统的方案一般只具备适应性选择关键词攻击下的关键词密文不可区分安全性，如果敌手通过某种渠道获得某个关键词的陷门时，由于敌手可以产生任意的自己猜测的明文关键词的密文，从而利用掌握的关键词陷门进行攻击,最终可能会暴露相关关键词的信息。敌手之所以能够进行关键词猜测攻击，根本原因在于其能够使用公钥产生任意自己想要的密文，但如果在密文中插入只有数据拥有者和使用者共享的秘密值，便会使得密文具有不可伪造性。

根据文献[23]，一个具备抵抗关键词猜测攻击的DNBP-PEKS方案应具有适应性选择关键词攻击下的密文不可区分安全性(CIND-CKA)和适应性选择关键词攻击下的陷门不可区分安全性(TIND-CKA)。其中，CIND-CKA由以下游戏来刻画：

1)挑战者运行Keygen(k)算法生成公私钥对pk和sk，把公钥pk交给敌手A。

2)挑战者生成敌手A选择的关键词w的陷门Tw，并将其发送给A。

3)挑战者生成敌手A选择的关键词w的密文cw，并将其发送给A。

4)敌手给挑战者发送2个关键词w0、w1，但要求敌手之前没有查询过这2个关键词的陷门。挑战者收到挑战关键词后，随机地选择一个数b∈{0,1}，将密文cwb交给敌手A。

5)除关键词w0、w1的陷门外敌手可以继续请求任何关键词w的陷门以及密文。

6)敌手A输出对关键词密文的猜测b′∈{0,1}，假如b=b′，就说明A赢得了游戏。

定义A赢得游戏的优势为：

TIND-CKA由以下游戏来刻画：

1)挑战者运行Keygen(k)算法生成公私钥对pk和sk，把公钥pk交给敌手A。

2)敌手A可以进行CIND-CKA游戏中步骤2和步骤3的询问。

3)敌手给挑战者发送2个关键词w0、w1，但要求敌手之前没有查询过这2个关键词的密文。挑战者收到挑战关键词后，随机地选择一个数b∈{0,1}，将陷门Twb发送给敌手A。

4)除了关键词w0、w1的密文外敌手可以继续请求任何关键词w的陷门以及密文，。

5)敌手A输出对关键词陷门的猜测b′∈{0,1}，假如b=b′，就说明A赢得了游戏。

定义A赢得游戏的优势为：

定义1 如果不存在多项式时间敌手以不可忽略的优势赢得以上2个游戏，DNBP-PEKS能够抵抗关键词猜测攻击。

由于DNBP-PEKS使用了动态的索引，在用户搜索、添加以及文件加密的过程中会造成一定的信息泄漏，文中使用泄漏函数将其指出，即Lsearch、Ladd、Lencrypt，考虑下面2个实验，实验中有攻击者A和模拟器S。

2.5 符号说明

为方便读者理解方案，本节将对方案所用到的一些符号作出说明，具体如表1所示。

表1 符号说明

3 方案设计

本章将详细介绍DNBP-PEKS方案的具体实现。

3)BuildIndex(c)。创建3个空链表I1、I2、I3作为索引，在链表I1[IDf]处放入cw、cIDf、I2、I3暂时为空，将索引I=(I1,I2,I3)和密文文件上传至服务器，链表I1如图2所示。

图2 索引I1

4)SearchTrapdoor(w,X,y,D)。对于要查询的关键词w用私钥生成其搜索陷门，即Tw=(DH(w‖H1(Xy)))y。

5)Search(Tw,I,d)。服务器端维持一个集合α记录搜索历史。收到陷门后，首先查询索引I2，如存在I2[Tw]项，则输出该项的值。否则，服务器查询索引I1，使用自己的私钥计算是否存在Tw=(cw(gr)-d)d，如果存在，则将相应的ID插入临时集合t中，最后更新索引，在索引I2中添加I2[Tw]=t，在索引I3中添加I3[t]=Tw，置α=α∪Tw，输出集合t，I2和I3如图3所示。

图3 索引I2、I3

6)AddTrapdoor(fa,Y,X,x,D)。假设要添加的文件为fa，运行步骤2对其加密得到cfa以及cIDfa，并对其唯一关键词集合加密得到cwa，并对文件的每一个关键词计算δwi=YH(wi‖H1(Yx))，并将其插入到集合β中，将添加陷门Ta=(cfa,cIDfa,cwa,β,IDfa)上传至服务器。

8)DeleteTrapdoor(IDfb,X,y,D)。对于要删除的文件fb，用户对其IDfb生成删除陷门，即TIDfb=(DH(IDfb‖Xy))y。

10)Dec(y，cf)。用户接收到服务器返回的密文文件(c′1,c2),使用私钥解密得到明文文件，F(f)=c2(c′1)-y。

4 方案分析

本章将对所提出DNBP-PEKS方案的运算过程的正确性和安全性进行分析验证。

4.1 正确性分析

当服务器收到用户的搜索陷门时，会对陷门进行如下的运算：

=Tw=(DH(w‖H1(Xy)))y=gdyH(w‖H1(gxy))

通过上式可以发现，对于不同的关键词w，服务器在接收到正确的陷门后，通过逐一匹配，能正确地返回包含此关键词的密文。同理，服务器在接收到密文的删除陷门后会先查询是否有相同的IDf，再对其进行验证，过程如下：

=(DH(IDf‖H1(Xy)))y=gdyH(IDf‖H1(gxy))

不难发现，只有掌握了私钥和文件正确的标识码的用户，才能删除相应的密文文件。最后的解密阶段，用户使用私钥得到明文：

c2(c′1)-y=F(f)Yu(Dud-1)-y=F(f)gyu(gdud-1)-y=F(f)

综上，方案的正确性得以验证。

4.2 安全性分析

定理1 假设DDH、HDH问题是困难问题，并且所使用哈希函数是随机预言机，则DNBP-PEKS可抵抗关键词猜测攻击。

引理1 假设DDH问题是困难问题，并且哈希函数是随机预言机，则DNBP-PEKS满足CIND-CKA安全。

证明针对CIND-CKA的证明将由以下3个游戏组成，A为针对CIND-CKA安全的敌手，设在游戏Gamei中A攻击CIND-CKA安全猜测正确的事件定义为Si(即b′=b)。

Game1。即为最初的游戏，敌手的优势为：

Adv(A)=|Pr[S1]-1/2|

Game2。与Game1相同，不同之处在于当下列事件发生时终止挑战：H(w‖l)=H(wb‖l)，且w≠wb。不难发现，若要终止挑战，必定存在敌手B1能以一定优势ε1攻破哈希函数H。因此，根据差别引理，敌手A在Game1和Game2中猜测正确的概率有以下关系:

|Pr[S1]-Pr[S2]|≤ε1

Game3。与Game2的不同之处在于挑战密文的回答方式，挑战者以随机数z1代替Dr的形式产生敌手的挑战密文YH(wb‖H1(Yx))z1，z1∈RG。则Game2与Game3应是一致的，除非存在敌手B2能以不可忽略的优势ε2区别z1和Dr(即解决DDH问题)，有:|Pr[S2]-Pr[S3]|≤ε2。因为z1是群中的随机元素，Game3中敌手猜测正确的优势为：Pr[S3]=1/2。

结束游戏，联合上列游戏得到：

Adv(A)=|Pr[S1]-1/2|≤|Pr[S1]-Pr[S2]|+

|Pr[S2]-Pr[S3]|≤ε1+ε2

因为哈希函数H是随机语言机，群上的DDH问题是困难的，从而ε1、ε2是可忽略的，所以Adv(A)可忽略，得证。

引理2 假设HDH问题是困难问题，并且哈希函数是随机预言机，则DNBP-PEKS满足TIND-CKA安全。

证明同上，针对TIND-CKA的证明将由以下几个游戏来完成，敌手A在游戏Gamei中猜测正确的事件定义为Si(即b′=b)。

Game1。最初的游戏，敌手A的优势定义为：

Adv(A)=|Pr[S1]-1/2|

Game2。同引理1证明中的Game2，此时有:

|Pr[S1]-Pr[S2]|≤ε1

Game3。将Game2转换为Game3，以H(w‖z2)代替H(w‖H1(gxy))的形式产生敌手的挑战陷门，z2∈R{0,1}l，则Game2和Game3是一致的，敌手A不能区别Game2和Game3，除非存在敌手B3以不可忽略的优势ε3区分H1(gxy)和z2，有：|Pr[S2]-Pr[S3]|≤ε3。因为此时z2是{0,1}l中的随机数，所以Pr[S3]=1/2。

同理联立游戏1、游戏2和游戏3得到：

Adv(A)=|Pr[S1]-1/2|≤|Pr[S1]-Pr[S2]|+

|Pr[S2]-Pr[S3]|≤ε1+ε3

因为哈希函数H是随机预言机，群上的HDH问题是困难的，从而ε1、ε3是可忽略的，所以Adv(A)可忽略，得证。

引理3 方案使用的明文文件加密算法满足IND-CPA安全，添加陷门满足IND-CKA安全。

因为方案中使用的明文文件加密算法的构造方式与文章的关键词加密相近，证明方法与上述证明类似，这里不再赘述。

综合引理1和引理2,定理1成立。

定理2 在随机预言模型下，假如引理1、引理2和引理3成立，DNBP-PEKS具有适应性动态选择关键词攻击下的安全性。

证明将前面提到过的泄漏函数定义如下。

Lsearch(f,w)=(ACCPT(w),ID(w))

Lencrypt(f)=len(f)

1)初始化运行环境。

2)通过泄漏函数Lsearch(f,w)=(ACCPT(w),ID(w))模拟搜索索引，模拟器检查ID(w)是否在U中，也就是说检查相应关键词的陷门之前是否被搜索过。

①假如ID(w)在U中，则直接输出U[ID(w)]。

5 方案对比

本章给出了DNBP-PEKS与其他基于非对称密钥体制实现的可搜索加密方案的对比，如表2和表3所示。表2从功能和安全性方面进行了对比，表3从密文生成、陷门生成(由于某些方案并不具备删除功能，其中陷门生成对比主要对比搜索陷门的生成效率，陷门的验证对比同理)，以及服务器搜索验证方面对各个方案进行了性能对比，其中p代表双线性运算，e代表模指运算，h代表哈希运算。

表2 方案功能对比(KGA指关键词猜测攻击)

表3 方案性能对比

综合来看，系统建立初期DNBP-PEKS方案的性能与文献[17]的方案相当，高于文献[18]，但随着系统索引的不断建立，DNBP-PEKS方案的查询效率将逐渐提升，当系统中所有关键词都被查询过时，服务器收到查询陷门后将不需要做任何群上的指数以及哈希运算，仅需要简单地匹配索引I2中的值便能输出用户所需要的结果，这使得DNBP-PEKS方案的查询效率将远远高于文献[17]的方案。为了直观的对比，假设系统中有m个密文文件，q个唯一关键词，为方便计算，设每个文件包含n个关键词，每次搜索，文献[17]需要进行2mn次指数运算和匹配运算，而当检索被搜索过的关键词时，DNBP-PEKS方案的搜索效率仅与索引I2的匹配效率有关，平均仅需(1+q)/2次匹配运算便能得出结果，通过Java编程运行结果显示，模指运算耗时是匹配运算的37倍左右。根据文献[17]的实验结果，一次指数运算需要0.01 ms，一次哈希运算需要0.19 ms，而一次双线性运算大约为1.5 ms，因此DNBP-PEKS方案的性能也高于使用双线性对的文献[9]、文献[12]和文献[16]方案。综上，DNBP-PEKS方案在性能、功能性以及安全性方面有着一定优势。

6 结束语

在研究了当前存在的PEKS方案的基础上，发现其不支持动态更新且查询的效率较为低下，于是本文基于Elgamal加密算法提出了一种可抵抗关键词猜测攻击的动态公钥可搜索加密方案，本文方案的索引构造参考了对称可搜索加密，并在随机预言模型下证明了方案的安全性。下一步的工作将致力于研究支持多关键词搜索的动态公钥可搜索加密方案，并考虑一对多用户的模式以及将密文放在多个服务器上的情况。