随着大数据时代的到来，数据的飞速增长使得维护、管理和利用数据逐渐变得困难.因此，越来越多的企业和个人都倾向于将数据外包到云上以节省本地存储和维护数据的开销.为了保护敏感数据，数据拥有者往往会选择将数据加密后再上传至云服务器，然而这会导致检索数据变得困难.因此，如何在加密的数据库上实现安全且高效的关键字搜索成为一个亟待解决的问题.
对称可搜索加密技术(symmetric searchable encryption, SSE) [1]是一种允许第三方对用户上传的加密数据进行检索，同时不会泄露除搜索模式和搜索结果外任何信息的一种密文技术.早期的对称可搜索加密往往仅适用于静态环境，即加密数据一旦上传至云服务器就不再进行修改与更新.但在实际应用中，用户往往希望能够实现数据库的更新，例如文件的插入、删除等，为此提出了动态对称可搜索加密的概念[2].然而在动态SSE环境下，数据的添加和删除将会比搜索泄露更多的隐私信息.最近，Zhang等人[3]提出了一种针对动态可搜索加密方案的攻击，敌手可以通过向服务器注入少量文件来破坏用户的查询隐私.为了抵抗这种攻击，前向安全[4-5]的定义和方案相继被提出.这种方案可以防止旧的搜索令牌对新添加的密文文档进行搜索，因此大大降低了暴露令牌和数据集隐私的可能性.
目前大部分的动态对称可搜索加密方案仅支持单用户，不适用于多用户环境.这是由于这些方案往往要求客户端在本地维护关键字的状态信息以生成最新的限门.在这种设计下，其他用户只能向数据拥有者询问最新的关键字状态信息才能够生成限门，这就要求数据拥有者始终保持在线状态.为了解决这个问题，最近，Wang等人[6]提出了一种支持多用户且前向安全的动态可搜索加密方案MFS，该方案通过引入代理服务器来存储关键字信息和用户的访问控制权限，解决了前向安全的多用户加密数据搜索问题.然而，MFS方案中仅给出了简单的安全性分析，缺乏形式化的安全性定义和证明；并且，我们注意到MFS方案中并未考虑数据拥有者和用户在与代理服务器通信时产生的信息泄露，主要包括2点：
1) 敏感信息泄露.为了使代理服务器得到最新的关键字信息，数据拥有者需要在每次文件更新发生时向服务器发送一些辅助信息，但是这些信息会泄露更新文件中包含的关键字与旧的搜索令牌之间的关联，使方案无法保持前向安全性.
2) 搜索令牌可关联.一个用户对于同一个关键字生成的搜索令牌始终是固定值.
针对上述存在的问题，我们提出了一个增强的多用户前向安全动态可搜索加密方案.本文的主要贡献包括3个方面:
1) 指出了MFS方案中存在敏感信息泄露和搜索令牌可关联的安全问题，并基于这2个安全问题提出了攻击的方法.
2) 提出了增强的多用户前向安全动态可搜索加密方案EMFS，通过增加用户与代理服务器之间的通信密钥，保证了搜索令牌的不可关联性.并且，我们还将关键字状态信息生成全权授权给代理服务器，避免了状态信息在传递中造成的泄露.此外，我们的方案还采用了一种新的索引结构，能够大大提升删除的效率.
3) 给出了EMFS方案的安全性证明和性能对比，实验结果表明尽管我们的方案在查找复杂度上有略微增加，但删除复杂度从O(nw)降低到O(1)，因此在实际应用中具有更高的效率.
1 相关工作
可搜索对称加密是一种非常有效的加密工具，能在实现隐私保护的同时保证可搜索性[7].具体来说，一个SSE方案允许数据所有者对自己的数据进行加密，并将加密的数据库外包给云服务器，之后云服务器在接收到有效的查询请求时可以对密文进行搜索操作.首个对称可搜索方案由Song等人[8]提出，通过顺序扫描技术来实现搜索操作.此后，诸多SSE方案被不断提出[9-15]，大大丰富SSE的查询表达性，提升了方案安全性和性能.
随后，为了满足数据动态性的要求，文献[2]提出了首个动态可搜索加密方案，实现了搜索和更新操作.但是，动态可搜索加密在数据添加和数据删除过程中会泄露额外的信息.例如敌手可以分析新添加或删除的文档是否包含先前搜索的关键字.Cash等人[16]对动态SSE方案的泄露进行了研究，表明即使是最小的泄露也能够被攻击者利用来揭示用户查询的内容，导致泄露滥用攻击.最近Zhang等人[3]提出的一种恶意攻击称为文件注入攻击，通过向数据库中注入少量文件来破坏用户的查询隐私.为了抵抗上述攻击，Stefanov等人[4]首先提出了2个安全性概念，即前向安全和后向安全，并提出了一个类ORAM构造的前向安全的动态可搜索加密方案.随后，Bost[5]在2016年提出了一个基于陷门原语支持增添前向安全动态可搜索加密方案,并正式给出了前向安全的定义.2017 年Bost等人[17]给出了后向安全由强到弱3种正式定义，并给出了一个支持单关键字搜索且满足前向和后向安全的动态可搜索加密方案.
在前向安全方面，文献[18]提出了可验证的前向安全动态可搜索加密方案，使方案适用于恶意服务器环境.文献[19]通过树状结构实现了一种支持范围搜索的前向安全动态可搜索加密方案.文献[20-21]提出了一种支持多关键字搜索的前向安全动态可搜索加密方案.
在后向安全方面，文献[22]提出了一种实现了第3类后向安全的对称可搜索加密方案，作者构造了一种新的密码学原语称为对称可穿刺加密，大大降低了通过穿刺实现后向加密所需的计算开销.文献[23]采用了一次一密的方式构造了一种后向安全的对称可搜索加密方案，该方案不仅高效，还能实现比第1类后向安全更高的安全性，缺陷是无法支持大量数据.文献[24]从第2类、第3类后向安全入手，分别提出了2种满足后向安全的对称可搜索加密方案，表明了实现后向安全的成本大大低于实现前向安全的成本.
尽管多用户在动态对称可搜索加密方案中并不少见，如文献[25]实现了一个支持多用户的动态对称可搜索加密方案，通过密钥分发和重新加密技术避免了密钥共享带来的一系列问题.文献[26]将客户端的授权信息合并到搜索令牌和索引中提出了一个支持布尔型查询的动态多用户可搜索方案.但是，前向安全和后向安全方案在目前大多仅支持单用户模型.为了支持多用户环境，Wang等人[6]首次从单用户模型进行扩展，提出了一种支持多用户的前向安全动态可搜索加密方案MFS，这为现有的单用户前向安全可搜索方案扩展提供了一种新的思路.然而，MFS方案中仍然存在无法抵抗窃听攻击或重放攻击等安全缺陷，且搜索与删除效率也有待进一步提高.我们认为这是单用户扩展至多用户前向安全动态对称可搜索加密方案时必须解决的关键问题之一，为此我们提供了一种解决思路并给出了一个新的方案.
2 预备知识
2.1 双线性映射
设G1,G2均为阶为素数p的乘法循环群，其中g是G1的生成元. 双线性映射e：G1×G1→G2具有3条性质：
1) 双线性.对于任意u,v∈G1，a,b∈Zp，有e(ua,vb)=e(u,v)ab .
2) 非退化性.e(g,g)≠1.
3) 可计算性.对于任意u,v∈G1，e(u,v)的计算应该是高效的.
2.2 伪随机函数
定义函数F：{0,1}λ×{0,1}m→{0,1}n，我们称其为伪随机函数，如果对于所有概率性多项式时间的区分器D有：|Pr[DF(k,.)=1|k←{0,1}λ]-Pr[Dg=1|g←{Func[m,n]}]|≤negl(λ)，其中negl(λ)是一个可忽略函数.
2.3 伪随机置换
给定密钥空间
定义域
和值域
一个伪随机置换包含2个函数
以及
其中，函数F和F-1满足4种性质：
2) F-1(k,y)=⊥当且仅当
3) F和F-1可以通过确定性多项式算法高效地计算.
4) F(k,.)和F-1(k,.)是到
到的单射函数.
为了便于后续方案中的使用，我们额外定义了一个算法GenIPRF(1λ)，给定安全参数λ，输出为从密钥空间
中随机均匀选取的值k.
我们称伪随机置换是安全的，如果对于所有概率性多项式时间的区分器D有：|Pr[DF(k,.),F-1(k,.)=1|
其中negl(λ)是一个可忽略函数.
3 系统模型
方案中涉及4类实体：数据拥有者(data owner, DO)、数据使用者(data user, DU)、云服务器(cloud server, CS)和代理服务器(proxy server, PS)，具体系统模型如图1所示.
1) 数据拥有者负责为需要上传的文档选取对应关键字，加密并上传文档，并为文档生成辅助信息.其中，密文发送到云服务器，辅助信息发送到代理服务器.最后，数据拥有者还会为授权用户生成私钥，并通过安全信道将私钥分发给授权用户.
2) 云服务器是“诚实且具有好奇心的”，用于存储加密文件、对应的索引以及用户信息，同时对代理服务器提交的查询请求进行响应，并将查询结果返回给对应用户.
3) 代理服务器是“诚实的”，负责为关键字生成状态信息，存储每个关键字对应的最新状态值和用户验证信息，负责验证数据使用者的身份，并为数据使用者生成搜索令牌提交给云服务器.
4) 数据使用者是“诚实的”，可以为需要搜索的关键字生成验证令牌，并将令牌提交给代理服务器，最终得到云服务器返回的搜索结果.
Fig. 1 System model
图1 系统模型
4 动态可搜索加密
4.1 形式化定义
在本文的构造中，数据拥有者能够与多个用户共享文件，但是，只有数据所有者可以对数据集进行添加和删除.下面，我们给出了动态对称可搜索加密方案的定义：
定义1. 动态对称可搜索加密(dynamic symmetric searchable encryption, DSSE)方案由多项式时间算法构成：
Setup(1λ,DB)→(SKo,stq,EDB).数据拥有者选择安全参数1λ和数据库DB作为输入，输出为数据拥有者的私钥SKo、关键字状态值stq和加密数据库EDB.其中，关键字状态值由代理服务器管理.
Register(u,Ucqt,Udqt)→(SKu,Ucqt′,Udqt′).用户注册算法，密钥由数据拥有者和用户共同生成，最终用户保留密钥SKu，代理服务器更新用户搜索表Ucqt，云服务器更新用户解密表Udqt.
数据拥有者运行该算法将文件f添加到数据集中，代理服务器中的状态值和云服务器中的索引及密文会相应更新.
Delete(SKo,id(f),stq,EDB)→(EDB′).数据拥有者运行此算法从数据集中删除文件f，存储在云服务器上的索引和密文会相应地更新.
Search(w,SKu,stq,EDB)→(rstw).用户运行此算法搜索包含关键字w的文件，搜索令牌由代理服务器生成提交到云服务器，云服务器将结果集返回给用户.
Decrypt(rst,SKu)→F.用户收到云服务器返回的数据集rst后，可以用私钥进行解密，得到满足查询结果的文件集F.
4.2 泄露函数
本节给出DSSE方案泄露函数的一般定义：
1) sp(w)={t:(t,w)∈Q}.搜索模式存储了查询和关键字之间的映射，该映射用于判断查询是否针对同一个关键字，其中t代表时间戳.
2) rp(w)=rstt.访问模式被定义为每个搜索查询的结果，其中rstt表示当前匹配关键字w的所有文件.
3) UpHist(w).以(t,op,ind)的形式记录了关键字w上的所有更新操作，其中t为时间戳，op为操作符，ind为文件索引.
4.3 安全性定义
DSSE方案的安全性主要通过
和
这2个游戏来制定.其中由DSSE执行，通过DSSE的泄露来模拟.我们将DSSE方案的泄露函数定义为
它描述了敌手
在方案运行期间能获得的信息.如果敌手不能区别这2个游戏，那么我们认为泄露的信息仅仅局限于泄露函数
下面给出2个游戏的具体定义：
输入敌手选定数据库DB，通过运行Setup(λ,DB)算法输出EDB并发送给敌手
敌手可以重复执行3种查询：搜索查询w、添加查询f1以及删除查询id(f2).其中DB中至少存在一个文件f包含关键字w，f1∉DB，f2∈DB.游戏分别运行搜索和更新算法生成搜索令牌τw、添加令牌τα以及删除令牌τd返回给敌手最终，输出一个字符.
敌手选定数据库DB，使用模拟器
将EDB返回给敌手敌手可以重复执行3种查询：搜索查询w、添加查询f1以及删除查询id(f2).其中DB中至少存在一个文件f含有包含关键字w，f1∉DB，f2∈DB.根据敌手提交的查询，模拟器
使用泄露函数
和
模拟生成令牌返回给敌手最终，输出一个字符.
定义2. 我们称方案Σ是
自适应安全的，如果对于所有多项式时间的敌手，存在一个高效的模拟器
使得：
4.4 前向安全
DSSE方案的前向安全性要求旧的搜索令牌无法匹配到新的更新，换而言之，数据的更新操作不能泄露有关关键字的任何信息.我们定义前向安全SSE如下：
定义3. 称一个
自适应安全的DSSE方案是前向安全的，如果方案中关于更新操作的泄露函数可以分别描述为
其中,|f| 代表文件f的大小，op代表操作符(在
中op=add, 在
中op=del)，μf表示文件f包含的关键字个数.
5 MFS方案分析
为了更好地阐述我们的观点，本节首先介绍Wang等人[6]提出的多用户前向安全动态可搜索加密方案MFS，并对方案中存在的安全性问题进行了分析，最后介绍了攻击的方法.
5.1 MFS方案
5.1.1 初始化算法Setup(1λ)
给定安全参数λ，从
中选取随机数(wk,ek)作为数据拥有者的搜索和加密密钥，随机选取sk1,sk2,ks∈{0,1}λ.给定双线性映射ê：G1×G1→G2，g1,g2为分别为G1,G2的生成元，Hash函数h1,h2,h3,H1,H2.服务器端初始化索引T，代理服务器初始化索引W.数据拥有者保存私钥SK=(wk,ek,sk1,sk2,ks)，公布公共参数pp=(p,g1,g2,G1,G2,h1,h2,h3,H1,H2).
5.1.2 文件添加算法Add(SK，f,W,EDB)
1) DataOwner(SK,f)：给定一个文件f，文件标识符indf，文档中包含的所有关键字W(f)，从G1中随机选取rf，计算文件加密密钥ekf=h3(ê(rf,g2)ek)，密文Cf=AES.Encrypt(ekf,f)，将(Cf,rf)发送给云服务器.此外，对于每个关键字w∈W(f)，执行操作：
① addr(w,indf)=H1(sk1,w‖indf);
② k(w,indf)=H2(sk2,w‖indf);
③ tw=F(ks,w);
④ Tr(w)=h2(ê(h1(w),g2)wk);
⑤ e2=indf⊕F(k(w,indf),tw);
⑥ AddTuple←(Tr(w),addr(w,indf),
k(w,indf),tw,e2);
⑦ 将AddTuple发送给代理服务器.
2) ProxyServer(AddTuple,W)：代理服务器收到AddTuple=(Tr(w),addr(w,indf),k(w,indf),tw,e2)后，执行操作：
① if W[Tr(w)]=null then
② s←{0,1}λ;
③ e1=〈0μ‖s〉⊕〈Tr(w)‖F(k(w,indf),
addr(w,indf))〉;
④ else
⑤ (addr(w,indc),k(w,indc),tw)←
W[Tr(w)];
⑥ e1=〈addr(w,indc)‖k(w,indc)〉⊕
〈Tr(w)‖F(k(w,indf),addr(w,
indf))〉;
⑦ end if
⑧ W[Tr(w)]←(addr(w,indf),k(w,
indf),tw);
⑨ AddTuple← (addr(w,indf),e1,e2);
⑩ 将AddTuple发送给云服务器.
3) CloudServer(AddTr,EDB)：云服务器更新T，使得T[addr(w,indc)]←(e1,e2).
5.1.3 用户注册算法Register(u)
给定用户u的身份uid∈{0,1}λ，从中选取随机数(qku,dku)作为用户的搜索及文件加密密钥，计算
其中，(uid,qkc)发送给代理服务器，(uid,dkc)发送给云服务器，(uid,qku,dku)发送给注册用户u.
5.1.4 搜索算法Search((w,qku),(qkc,stq),(dkc,EDB))
1) DataUser(w,qku)：计算Tru(w)=h1(w)qku，将(uid, Tru(w))发送给代理服务器.
2) ProxyServer(Tru(w),uid,qkc,W):给定搜索用户的uid以及查询令牌Tru(w)，执行操作：
① if Ucqt[uid]≠⊥ then
② qkc←Ucqt[uid];
③ else
④ 非授权用户，程序结束;
⑤ end if
⑥ Tr(w)=h2(ê(Tru(w),qkc));
⑦ if W[Tr(w)]≠⊥ then
⑧ (addr(w,indf),k(w,indf),tw)←
W[Tr(w)];
⑨ SearchTrapdoor←(Tru(w),addr(w,
indf),tw,k(w,indf));
⑩ 将SearchTrapdoor和uid发送给云服务器;
else
返回“none”给用户u;
end if
3) CloudServer(SearchTrapdoor,uid,qkc,EDB)：初始化2个集合ResultSet和rst用于存放查询结果及数据，并执行操作：
① while addr(w,indc)≠0μdo
② ind=T[addr(w,indc)].e2⊕F(k(w,
indc),iw);
③ 〈addr(w,indc)‖k(w,indc)〉←
T[addr(w,indc)].e ⊕〈Tr(w)‖
F(k(w,indf),addr(w,indf))〉;
④ ResultSet←ResultSet∪ind;
⑤ end while
⑥ dkc=U[uid];
⑦ for each ind∈ResultSet do
⑧ cdsind=ê(rind,dkc);
⑨ rst←rst∪(cdsind,Cind);
⑩ end for
将数据集 rst 返回给用户.
5.1.5 解密算法Decrypt(rst,dku)
用户收到数据集rst后执行操作：
① F=null;
② for each (cdsind,Cind)∈rst
③
④ f=AES.Decrypt(dkind,Cind);
⑤ F=F∪f;
⑥ end for
最终得到所有符合查询的结果.
5.2 安全性问题
MFS方案是首个在单用户模型下扩展至多用户模型的前向安全动态可搜索加密方案，为了解决前向安全和多用户合并的问题，作者引入了第三方代理服务器来存储关键字信息和用户的访问控制权限.然而由于作者将代理服务器设置为半可信，使得数据拥有者不得不泄露某些信息以达到托管关键字信息的目的.由于代理是半可信的，本质上这是把部分泄露转移到了代理服务器上，违背前向安全的性质.因此尽管MFS方案中考虑了诸多安全因素，其中依然存在2项严重的安全性问题，最终致使MFS方案无法保证前向安全性.
1) 敏感信息泄露.在文件添加算法Add中，我们注意到用户将AddTuple直接发送给代理服务器，其中包含了关键字标识符tw，这是极度不安全的，因为旧的搜索令牌中同样包含了tw，而前向安全要求隐藏更新文件与旧的搜索令牌之间的关系.
2) 搜索令牌可关联.对于某一用户，他搜索同一关键字时向代理服务器提交的令牌始终是一个固定值，这使敌手可以轻易伪装成任何用户.
5.3 攻击方法
根据5.2节分析的安全性问题，我们给出2种攻击方法：
1) 窃听攻击.敌手通过监听数据拥有者向代理服务器发送的信息来维护一个关键字
文件表，每当数据拥有者向代理服务器发送更新令牌AddTuple时，敌手将AddTuple中的关键字标识符tw和文件ind 存放到表中(ind可以通过AddTuple中的其他值计算).对于窃听敌手来说，尽管他并不知道tw对应的关键字，但是他能轻而易举地将搜索令牌与更新文件进行关联(搜索令牌中同样包含tw)，这对保证方案的前向安全性是十分不利的.
2) 重放攻击.敌手维护一个用户令牌表，存放用户向代理服务发送的令牌，一旦发现数据拥有者更新了一个新的文件，敌手就将他存储的所有令牌发送给代理服务器.在这种情况下，云服务器不断获得用户搜索过的所有关键字对应的最新搜索令牌.如果令牌包含了最新的更新索引，那么云服务器就掌握了更新文件所包含的关键字.注意此时没有任何用户提交有关该文件的搜索请求，云服务器应对该文件中包含的关键字保持未知.
6 EMFS方案
6.1 数据结构
我们的方案采用了状态链构造，如图2所示，每个关键字对应一条状态链，所有匹配关键字w的文件标识符都存放在链中，当客户端想要搜索关键字w时，他向服务器发送最后一个状态stc+1，服务器可以从stc+1开始反向遍历状态链获得所有先前状态stc,stc-1,…,st1，最终获得所有查询结果.需要注意的是，服务器无法从当前状态stc+1获取下一个状态stc+2，这也确保了方案的前向安全性.为了进一步提高搜索和更新的效率，我们采用随机生成的方式来生成状态值.
Fig. 2 Update and search in our scheme
图2 更新和查找图示
为了使方案适应多用户环境，我们选择引入一个诚实的代理服务器来维护关键字的状态值，并将状态值的生成全权及交给代理服务器，避免用户生成状态值传递给服务器导致的信息泄露.需要注意的是，为了保证方案的非交互性，代理服务器除了记录关键字最新的状态信息外，还会额外保存各关键字对应的文件数和用户的搜索次数用于用户验证(令牌的生成与这些信息相关).虽然敌手可能会获知这些信息，例如某用户的查询次数，但我们认为在未持有密钥的情况下，敌手伪造令牌的概率仅为一个可忽略值.
6.2 具体构造
6.2.1 初始化算法Setup(1λ)
给定安全参数λ，从
中选取随机数ek，随机选取ks∈{0,1}λ.给定双线性映射ê：G1×G1→G2，g1,g2分别为G1,G2的生成元，伪随机置换R1,R2，Hash函数H1,H2,H3，运行算法GenIPRF(1λ)生成伪随机置换R1的密钥KG.数据拥有者初始化更新集合Files,服务器端初始化索引集合T，代理服务器初始化映射集合W. 数据拥有者保存私钥SKo=(ek,ks,KG)，代理服务器秘密保存KG，公布公共参数
6.2.2 文件添加算法Add(SKo,f,W,EDB)
1) DataOwner(SKo,f)：给定一个文件f，文件标识符indf，文档中包含的所有关键字W(f)，从G1中随机选取rf，计算文件加密密钥ekf=H3(ê(rf,g2)ek)，密文Cf=AES.Encrypt(ekf,f)，将(Cf,rf)发送给云服务器. 此外，初始化一个集合τupd，对于每个关键字w∈W(f)，执行操作：
① Files[w]=Files[w]+1 ;
② tw=F(ks,w);
③ updw=R1(KG,tw‖add‖ind‖Files[w]);
*op=add代表文件插入*
④ τupd=τupd∪updw.
然后，将τupd发送给代理服务器.
2) ProxyServer(KG,W,τupd)：代理服务器收到τupd后，初始化一个集合τtd，并执行操作：
① for each updw∈τupd do
② 
updw); *根据op的不同分别代表文
件插入和删除*
③ (stc,c)←W[tw];
④ if Files[w]≠c+1 then
⑤ return “无效令牌”;
⑥ else if c=0 then
⑦ stc+1←{0,1}λ;
⑧ e=H2(tw‖stc+1)⊕(⊥‖op‖ind);
⑨ else
⑩ stc+1←{0,1}λ;
e=H2(tw‖stc+1)⊕(stc‖op‖ind);
end if
c=c+1;
u=H1(tw,stc+1);
W[tw]←(stc+1,c);
τtd=τtd∪(u,e);
end for
将τtd发送给云服务器.
3) CloudServer(τtd,EDB)：云服务器根据收到的τtd执行操作：
① for each (u,e)∈τtd do
② T[u]=e;
③ end for
6.2.3 用户注册算法Register(u)
给定用户u的身份uid∈{0,1}λ，数据拥有者从中选取随机数dku作为用户的文件解密密钥，计算
用户运行算法GenIPRF(1λ)生成伪随机置换R2的密钥qku，计数器s=0.其中，代理服务器保存(uid,qku,s)，云服务器保存(uid,dkc)，用户保存SKu=(uid,qku,ks,dku,s).
6.2.4 搜索算法Search((w,SKu),(qku,W),(dkc,EDB))
1) DataUser(w,SKu)：给定搜索的关键字w，执行操作：
① (uid,qku,ks,dku,s)←SKu;
② tw=F(ks,w);
③ s=s+1;
④ τu=R2(qku,tw‖s);
⑤ SKu←(uid,qku,ks,dku,s).
将(uid,τu)发送给代理服务器.
2) ProxyServer(uid,W,Ucqt,τu):给定搜索用户的uid以及令牌τu，执行操作：
① (qku,sc)←Ucqt[uid];
②
③ if s≠sc+1 then
④ return “无效令牌”;
⑤ end if
⑥ (stc,c)←W[tw];
⑦ τw←(tw,stc);
⑧ if stc=⊥ then
⑨ 返回消息“none”给用户u;
⑩ else
将(uid,τw)发送给云服务器;
end if
sc=sc+1;
U[uid]←(qku,sc).
3) CloudServer(uid,Udqt,τw)：给定搜索用户的uid以及搜索令牌τw=(tw,stc)，云服务器初始化3个集合Δ，R和rst并执行操作：
① head=H1(tw‖stc);
② flag=false;
③ while stc≠⊥ do
④ u=H1(tw‖stc);
⑤ e=T[u];
⑥ (stc‖op‖ind)=e⊕H2(tw‖stc);
⑦ if op=del then
⑧ Δ=Δ∪ind;
⑨ if u≠head then
⑩ 删除当前块;
else
flag=true;
end if
else if op=add then
if ind∈Δ && flag=false then
Δ=Δ\ind;
删除当前块;
else if ind∈Δ && flag=true then
Δ=Δ\ind;
else
ResultSet←ResultSet∪ind;
end if
end if
end while
dkc←Udqt[uid];
for each ind∈ResultSet do
cdsind=ê(rind,dkc);
rst←rst∪(cdsind,Cind);
end for
将数据集rst返回给用户.
6.2.5 删除算法Delete(id(f),W(f),SKo,P)
1) DataUser(id(f),W(f),SKo)：对于每个关键字w∈W(f)，执行操作：：
① Files[w]=Files[w]+1;
② tw=F(ks,w);
③ updw=R1(KG,tw‖del‖ind‖Files[w]);
*op=del代表文件删除*
④ τupd=τupd∪updw.
然后，将τupd发送给代理服务器.
2) ProxyServer(KG,W,τupd)：代理服务器执行算法见6.2.2节.
3) CloudServer(τtd,EDB)：云服务器执行算法见6.2.2节.
6.2.6 解密算法Decrypt(rst,dku)
用户收到数据集rst后执行操作：
① F=null;
② for each (cdsind,Cind)∈rst do
③ dkind=H3(cdsinddku);
④ f=AES.Decrypt(dkind,Cind);
⑤ F=F∪f;
⑥ end for
最终得到所有符合查询的结果.
7 安全性分析和证明
7.1 安全性分析
在给出EMFS方案的安全性证明前，我们首先从文件和索引的安全性、验证令牌的不可伪造性、搜索令牌的保密性来分析方案的安全性.
1) 文件安全性.文件由数据拥有者在本地加密后上传到云服务器，在本文中，我们选择用主流的对称加密算法AES来加密文件.AES 算法的安全性保证了在密钥不外泄的情况下，敌手无法区别一串0的加密与文件的加密，保证了文件的安全性.
2) 身份验证令牌的不可伪造性.方案中采用了可逆伪随机函数来生成身份验证令牌，所需的密钥由代理服务器和用户持有，并且生成的验证令牌仅仅能够使用一次.在密钥不外泄的情况下，可逆伪随机函数的安全性保证了敌手无法区分随机值和一个验证数据的加密，故我们认为敌手仅有可忽略的概率可以伪造验证令牌.
3) 搜索令牌的保密性.存储在云服务器端的索引中保存的并非是真正的关键字，而是关键字的标识符.在未持有密钥的情况下，我们认为云服务器无法根据标识符推测出其中的关键字的相关信息.
7.2 安全性证明
定理1. 给定CPA安全的对称密钥加密方案AES，伪随机函数F，可逆伪随机函数R，Hash函数H1,H2,H3，双线性映射e.如果EMFS方案的泄露函数
满足定义：
则EMFS方案构造是
自适应安全的.
证明. 构建一个模拟器来模拟真实的算法，并且任何多项式时间的敌手都无法对真实算法和模拟算法进行区分.为了证明构造方案的安全性，我们使用了混合参数，模拟器将通过泄露函数
和
模拟算法.
混淆0：规定所有算法都按照协议运行.
混淆1：模拟器通过泄露函数
而非Setup(1λ)来模拟算法.
算法1. 系统初始化模拟算法.
① k←AES.KeyGen(1λ);
② 初始化字典Dict存放模拟索引;
③ 初始化字典KeyStore存放模拟关键字标识符;
④ 初始化字典ST存放模拟状态值;
混淆2：和混淆1类似，模拟器通过泄露函数
模拟添加令牌.
算法2. 添加令牌模拟算法.
①
② for i=1 to μfdo
③ 随机生成(u,e)对;
④ 将(id(f),(u,e))添加到字典Dict;
⑤
⑥ end for
⑦ c=ASE.Enc(k,0|f|);
⑧
添加模拟算法允许模拟器在初始化算法执行后用敌手提供的文件保持字典的更新.在模拟算法中，我们采用能满足随机预言机模型的随机字符串来代替Hash函数H的输出.这个随机值会被存储在字典Dict中，当下一次需要生成Hash值时，这个随机值就会被重用.模拟字典的大小与真实字典完全相同，因此敌手无法进行区分.并且，我们使模拟器模拟的令牌与真正的令牌同样保持完全相同的格式和大小，证明了仅知道
就可以模拟添加令牌，即证明了我们的方案保持了前向安全性.
混淆3：和混淆1类似，模拟器通过泄露函数
模拟搜索令牌.
算法3. 搜索令牌模拟算法.
①
② rst←rp(w);
③ if KeyStore[w]=null then
④ 随机生成KeyStore[w];
⑤ end if
⑥ tw=KeyStore[w];
⑦ if ST[w]=null then
⑧ 随机生成stc;
⑨ ST[w]←(rst,stc);
⑩ else if rst⊄ST[w].allrst then
*搜索需要最新状态值*
随机生成stc;
ST[w]←(allrst∪rst,stc);
end if
(allrst,stc)←ST[w];
τw=(tw,stc).
在令牌模拟算法中，模拟器通过sp(w)来判断查询是否针对同一个关键字，通过rp(w)来维护字典allrst，allrst中存储了每次查询发生时匹配关键字w的文件ind.一旦rp(w)中包含了新的ind，模拟器就会随机生成一个新的令牌，否则返回旧的令牌.同样地，对于以前从未出现在查询中的关键字，我们用一个随机值来替换伪随机函数F的输出.这个随机的值会被存储在一个字典KeyStore中，当下一次再对此关键字做查询时，这个随机的值会被重用.需要注意的是，模拟的搜索令牌和真实的搜索令牌在大小和格式上是完全一样的，因此任何多项式时间的敌手都无法进行区分.
混淆4：和混淆2类似，模拟器通过泄露函数
模拟删除令牌.
算法4. 删除令牌模拟算法.
①
② 从Dict中随机选取一个包含μf个关键字的文件id(f);
③ for i=1 to μfdo
④ 从Dict中取出(id(f),(u,,e))对;
⑤ 随机生成新的(udel,edel)对;
⑥
⑦ 将字典Dict的(id(f),(u,,e))替换为
(id(f),(u,v,udel,edel));
⑧ end for
⑨
在删除令牌模拟算法中，模拟器用字典Dict来回答删除请求，同样地，模拟的删除令牌与实际的删除令牌具有相同的格式和大小.
通过以上混淆，我们构建了一个模拟器模拟真实协议，任何多项式时间的敌手都无法区分真实协议和理想协议，证明了方案的安全性.
证毕.
8 性能分析
本节给出EMFS方案与MFS方案的性能对比.
为了更好地展现实验结果，我们首先给出方案的计算通信开销复杂度对比，如表1所示.其中nw表示当搜索发生时匹配关键字w的文件个数，aw表示关键字w上更新次数之和.相比于MFS方案，我们方案的删除操作不需要遍历数据链，复杂度仅为O(1)，但由于数据链中包含部分需要删除的块，因此搜索复杂度略微升高.
表2中给出了2个方案的性能对比，为了更简明地进行对比，我们主要考虑限门生成以及服务器查询链表所需的开销.其中，tBE表示执行双线性配对(bilinear pairing)和指数运算(exponential operation)合计所需要的时间，tma表示执行异或运算(modular addition)所需要的时间，λ表示安全参数，n代表插入或删除文件中包含的关键字个数.可以观察到我们的方案较MFS方案在计算和通信方面的开销都有所降低，这是由于我们通过伪随机置换来生成令牌，而MFS方案中生成令牌需要进行双线性和指数操作.此外，我们的方案为了减少信息的泄露，去除了部分不必要的数据传输，因此通信开销也优于MFS方案.
Table 1 Comparison of Search and Update Complexity Between MFS and EMFS
表1 MFS方案与EMFS方案的复杂度比较
SchemeComputationCommunicationSearchAddDeleteSearchAdd∕DeleteMFS[6]O(nw)O(1)O(nw)O(nw)O(1)Our SchemeO(aw)O(1)O(1)O(nw)O(1)
Table 2 Performance Comparison Between MFS and IMFS
表2 MFS方案与EMFS方案的性能比较
SchemeComputationCommunicationSearchAddDeleteSearchAddDeleteMFS[6]O(nw)×tma+tBEO(1)×tBE×nO(nw)×tBE×n5λ8nλ5nλOur SchemeO(aw)×tmaO(1)×tma×nO(1)×tma×n3λ3nλ3nλ
我们在Windows 7操作系统上(单核的Intel Core i5 4590 K 3.30 GHz CPU，内存4 GB)进行了仿真实验，采用Java编程语言，并通过jsCrypto库实例化方案的加密操作.其中，伪随机函数的实现采用了128 b HMAC-MD5，Hash函数的实现用的是160 b HMAC-SHA1，加密文档使用的是256 b密钥的对称加密算法AES，关键词状态表则通过Hash表实现，以写入文件的方式进行存储，需要使用时再从文件中读取，加密索引的存储则采用了持久化的Key-Value数据库Redis以加快存取速度.
Fig. 3 Performance evaluation of search on client side
图3 客户端搜索效率对比
为了评估2个方案中用户端搜索关键字的效率，我们选取了一系列出现频率不同的关键词，将匹配数据集的大小从10增加到105分别进行搜索，并计算出检索匹配项所需的平均时间.如图3所示，当匹配文档数量增加时，平均搜索时间会随之降低，这是由于方案在搜索时需要执行一些一次性操作，譬如读取文件中存放的最新状态值和生成搜索令牌等等，这些操作耗费的时间会平均地分配到每个匹配结果项中.我们方案的搜索效率是优于MFS的，这是由于在MFS方案中生成搜索令牌需要通过双线性配对，耗时较大.而在我们的方案中搜索令牌则通过一个伪随机置换生成，搜索效率更高.
Fig. 4 Performance evaluation of search on data owner side
图4 数据拥有者端搜索效率对比
数据拥有者端在搜索关键字的效率如图4所示，需要注意的是，此时云服务器并不需要计算匹配项的文件密钥，开销相比于客户端大幅度降低.同样，我们的方案在用户端的搜索效率也是优于MFS方案的.
如图5所示，我们给出方案在云服务器端的删除效率对比.我们将删除的数据集的大小从104增加到4×104，可以观察到随着文件数的增加，MFS方案的响应时间以一种线性方式增加，这是因为MFS在每次删除时都需要遍历数次链表(遍历次数与当前文件包含的关键字数有关)，而在EMFS方案中(我们考虑实际链表中块的删除，即删除操作与搜索绑定)，我们认为删除最多需要遍历N条链表，其中N代表删除数据集中包含的关键字总数.
Fig. 5 Performance evaluation of delete on cloud server side
图5 云服务器端删除算法效率对比
9 总 结
本文发现了Wang等人[6]提出的MFS方案存在的安全性问题，并针对这些存在问题提出了一个改进的方案EMFS.通过避免关键字信息在数据拥有者和代理服务器之间的传递和增加用户验证机制，我们保证了在引入第三方代理服务器时，方案仍能保持前向安全性.此外，我们还给出了方案的安全分析和证明，表明我们的方案具有良好的安全性.最后，通过性能评估，证明我们的方案比EMF方案拥有更高的删除效率，在实际应用中效果更佳.
[1]Curtmola R, Garay J, Kamara S, et al. Searchable symmetric encryption: Improved definitions and efficient constructions[J]. Journal of Computer Security, 2011, 19(5): 895-934
[2]Chang Yancheng, Mitzenmacher M. Privacy preserving keyword searches on remote encrypted data[C] //Proc of Int Conf on Applied Cryptography and Network Security. Berlin: Springer, 2005: 442-455
[3]Zhang Yupeng, Katz J, Papamanthou C. All your queries are belong to us: The power of file-injection attacks on searchable encryption[C] //Proc of the 25th USENIX Security Symp (Security 16). Berkeley, CA: USENIX, 2016: 707-720
[4]Stefanov E, Papamanthou C, Shi E. Practical dynamic searchable encryption with small leakage[C] //Proc of NDSS. Reston, VA: Internet Society, 2014: 72-75
[5]Bost R. ∑ oφo
: Forward secure searchable encryption[C] //Proc of the 2016 ACM SIGSAC Conf on Computer and Communications Security. New York: ACM, 2016: 1143-1154
[6]Wang Qiao, Guo Yu, Huang Hejiao, et al. Multi-user forward secure dynamic searchable symmetric encryption[C] //Proc of Int Conf on Network and System Security. Berlin: Springer, 2018: 125-140
[7]Dong Xiaolei, Zhou Jun, Cao Zhenfu. Research advances on secure searchable encryption[J]. Journal of Computer Research and Development, 2017, 54(10): 2107-2120 (in Chinese)(董晓蕾, 周俊, 曹珍富. 可搜索加密研究进展[J]. 计算机研究与发展, 2017, 54(10): 2107-2120)
[8]Song D X, Wagner D,Perrig A. Practical techniques for searches on encrypted data[C] //Proc of 2000 IEEE Symp on Security and Privacy (S&P 2000). Piscataway, NJ: IEEE, 2000: 44-55
[9]Cash D, Jarecki S, Jutla C, et al. Highly-scalable searchable symmetric encryption with support for Boolean queries[C] //Proc of Annual Cryptology Conf. Berlin: Springer, 2013: 353-373
[10]Miao Meixia, Wang Jianfeng, Wen Sheng, et al. Publicly verifiable database scheme with efficient keyword search[J]. Information Sciences, 2019, 475: 18-28
[11]Lai S, Patranabis S, Sakzad A, et al. Result pattern hiding searchable encryption for conjunctive queries[C] //Proc of the 2018 ACM SIGSAC Conf on Computer and Communica-tions Security. New York: ACM, 2018: 745-762
[12]Ogata W, Kurosawa K. Efficient no-dictionary verifiable searchable symmetric encryption[C] //Proc of Int Conf on Financial Cryptography and Data Security. Berlin: Springer, 2017: 498-516
[13]Loh R, Zuo Cong, Liu J K, et al. A multi-client DSSE scheme supporting range queries[C] //Proc of Int Conf on Information Security and Cryptology. Berlin: Springer, 2018: 289-307
[14]Soleimanian A, Khazaei S. Publicly verifiable searchable symmetric encryption based on efficient cryptographic components[J]. Designs, Codes and Cryptography, 2019, 87(1): 123-147
[15]Sun Shifeng, Liu J K, Sakzad A, et al. An efficient non-interactive multi-client searchable encryption with support for Boolean queries[C] //Proc of European Symp on Research in Computer Security. Berlin: Springer, 2016: 154-172
[16]Cash D, Tessaro S. The locality of searchable symmetric encryption[C] //Proc of Annual Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2014: 351-368
[17]Bost R, Minaud B, Ohrimenko O. Forward and backward private searchable encryption from constrained cryptographic primitives[C] //Proc of the 2017 ACM SIGSAC Conf on Computer and Communications Security. New York: ACM, 2017: 1465-1482
[18]Zhang Zhongjun, Wang Jianfeng, Wang Yunling, et al. Towards efficient verifiable forward secure searchable symmetric encryption[C] //Proc of European Symp on Research in Computer Security. Berlin: Springer, 2019: 304-321
[19]Zuo Cong, Sun Shifeng, Liu J K, et al. Dynamic searchable symmetric encryption schemes supporting range queries with forward (and backward) security[C] //Proc of European Symp on Research in Computer Security. Berlin: Springer, 2018: 228-246
[20]Hu Chengyu, Song Xiangfu, Liu Pengtao, et al. Forward secure conjunctive-keyword searchable encryption[J]. IEEE Access, 2019, 7(7): 35035-35048
[21]Wang Yunlin, Wang Jianfeng, Sun Shifeng, et al. Toward forward secure SSE supporting conjunctive keyword search[J]. IEEE Access, 2019, 7(7): 142762-142772
[22]Sun Shifeng, Yuan Xingliang, Liu J K, et al. Practical backward-secure searchable encryption from symmetric puncturable encryption[C] //Proc of the 2018 ACM SIGSAC Conf on Computer and Communications Security. New York: ACM, 2018: 763-780
[23]Zuo Cong, Sun Shifeng, Liu J K, et al. Dynamic searchable symmetric encryption with forward and stronger backward privacy[C] //Proc of European Symp on Research in Computer Security. Berlin: Springer, 2019: 283-303
[24]Chatterjee S, ParshuramPuria S K, Shah A. Efficient backward private searchable encryption[J]. Journal of Computer Security, 2020, 28(2): 229-267
[25]Guo Chen, Fu Xingbing, Mao Yaojun, et al. Multi-user searchable symmetric encryption with dynamic updates for cloud computing[J]. Information, 2018, 9(10): No.242
[26]Du Leilei, Li Kenli, Liu Qin, et al. Dynamic multi-client searchable symmetric encryption with support for Boolean queries[J]. Information Sciences, 2020, 506: 234-257
