支持联合搜索的动态前向安全可搜索加密方案

汤永利 李静然 闫玺玺 赵 强

(河南理工大学计算机科学与技术学院 河南焦作 454003)

可搜索加密(searchable encryption, SE)是保护云存储数据安全性的重要加密技术，用户将需要存储的数据加密后外包到云，防止云端数据泄露，同时支持云端搜索密文[1-6].然而，在实际应用中，新的安全问题日益凸显.例如向数据库添加文件时，可能会泄露之前搜索的关键词有哪些包含在更新文件中.为了避免这种信息泄露问题，提出前向安全可搜索加密方案，并应用于现实生活中的各种场景[7-13].Stefanov等人[14]于2014年首次系统地定义了前向安全可搜索加密(forward secure searchable encryption, FSSE)的概念，并给出一个具体的FSSE方案，但该方案更新开销巨大.2016年Bost[15]提出基于陷门置换的公钥加密FSSE方案∑oφoζ，该方案具有良好的更新能力和搜索复杂度.但因该方案由非对称原语构造，所以在索引、更新和令牌生成过程中都具有较大的消耗.2019年Wei等人[16]对∑oφoζ进行改进，基于对称原语的密钥块链技术提出一种前向安全的可搜索加密方案.2019年Hu等人[17]提出支持联合关键词搜索的前向安全可搜索加密方案，其基础方案在用户端加入布隆过滤器，服务器将联合问询关键词中某一个关键词的单关键词搜索结果发送给用户端，然后用户端使用布隆过滤器对所得文档进行二次筛选，得到搜索结果.该方案增加用户端的额外存储量，通信开销较差，且因使用布隆过滤器，更新能力和文件存储量受限，只能用于数量一定的小型文件数据库.其增强方案，为查询的每个关键词添加1个向量，导致效率不佳.2020年卢冰洁等人[18]提出一种增强的多用户前向安全可搜索加密方案，在保持前向安全性的同时将性能扩展到多用户，并且该方案可以抵抗窃听攻击和重放攻击.

本文提出一种支持联合搜索的方法，在支持单关键词搜索FSSE方案的基础上，将搜索能力扩展成联合搜索.所提方法在服务器端添加1个简化的布谷鸟过滤器，同时使用密文等值测试技术加密索引信息，并将加密后的索引存储于布谷鸟过滤器中.搜索协议将查询关键词分为2种：1)最低频的关键词(与该关键词相关的文件最少)；2)其他关键词.对最低频的关键词执行基础FSSE方案得到查询结果，随后使用布谷鸟过滤器存储的信息筛选查询结果，最终得到满足联合问询的结果.本文基于文献[16]的FSSE-ε方案(其他支持单关键词搜索的方案同样有效)，构造支持联合搜索的前向安全可搜索加密方案FSSE-CT.主要贡献有4个方面.

1) 构造一种支持联合搜索的方法，在任意单关键词FSSE方案[16]的基础上，于服务器端新增1个扩展结构，以存储加密后的关键词信息.该结构用于对联合问询的关键词进行二次筛选，且支持更灵活的文件-关键词对更新.

2) 在服务器端采用布谷鸟过滤器，增强方案的搜索能力和搜索效率.基于布谷鸟过滤器自身添加/删除和快速查询的功能，本方案支持4种更新方式：文件-关键词集合添加、删除，单个文件-关键词对添加、删除工作，并在一定程度上提升方案效率.

3) 采用密文等值测试技术，对需要存于布谷鸟过滤器相应桶中的关键词使用密文等值测试技术构造加密信息，实现搜索阶段对联合关键词进行有效筛选的同时，完成对关键词信息的隐藏.

4) 给出所提方案的安全性证明和性能对比.结果表明，该方案满足自适应模型下不可区分性安全.与其他方案性能对比分析表明，该方案在搜索方式、更新类型等功能方面更加全面且灵活.并且将联合搜索方案的更新时间降至对称加密操作耗时O(ts)，同时在用户端存储代价不变的基础上，将服务器端存储代价降至.对每人关键词-文件对存储ind长度和2个群G中元素长度O(N)×(λ+2|G|).

1 相关工作

1.1 前向安全可搜索加密方案

前向安全可搜索加密希望达成的目标是：恶意服务器在文件更新阶段不泄露任何数据库中已有数据的信息.2005年Chang等人[19]的方案已支持前向安全，该文指出文件更新时，新增文件可能与之前已查询过的关键词相关，从而泄露某些信息.2014年前向安全可搜索加密的概念由Stefanov等人[14]系统提出，同时还提出后向安全的概念.随后学者们相继提出各种的方案[20-23]，但这些方案普遍具有开销过大或者无法在现实世界中实现的问题.2016年Bost[15]提出了第1个具有良好的通信开销和计算复杂度的FSSE方案——∑oφoζ，该方案在建立索引的过程中通过陷门置换隐藏文件标签和关键词之间的关系，在新的文件注入时，不泄露之前已查询文件的信息.2019年Wei等人[16]提出基于对称原语的密钥块链技术，该技术不依赖独立索引生成规则，可以与任意形式的索引结构联用，扩展了前向安全可搜索加密的灵活性，且在快速搜索和令牌生成方面具有较高的效率.

1.2 支持多关键词的前向安全可搜索加密方案

2018年Zuo等人[24]提出2种支持范围查询的前向安全可搜索加密方案：1)将∑oφoζ与树状结构结合以支持范围搜索；2)将替换为Paillier加密的字符串，同时支持前向/向后安全.随后Hu等人[17]提出支持联合搜索的前向安全可搜索加密方案.给出2种解决方法，基础方案在用户端引入布隆过滤器筛选文件，加强方案使用内积加密(inner-product encryption, IPE)方法代替布隆过滤器.Wu等人[25]构建了1个基于虚拟二叉树的结构(virtual binary tree, VBTree)，有效地实现前向安全的联合关键词搜索.当从叶到根的所有节点都包含所有查询的关键词时，服务器可以自上而下执行联合关键词搜索并返回叶节点作为搜索结果.但该方案中服务器可通过对每个查询的关键词执行搜索来直接获取大量泄露.Wang等人[26]构造2种有效的联合关键词FSSE方案，且不会产生明显的泄露.其基础方案因引入XSet表格，存储开销增加；增强方案因在基础方案上添加RC表格，在计算过程中需要对XSet表格中的信息剥除一次外壳，计算开销和存储开销都有所增加.

2 预备知识

2.1 布谷鸟过滤器

布谷鸟过滤器是一种基于Hash函数的新形式概率数据结构，用于测试集合中的元素资格，它包含1个由桶组成的数组.插入到布谷鸟过滤器中的每个元素a有2个候选桶，分别由Hash函数h1(a)和h2(a)确定.查找a时，对由Hash函数计算出的2个桶进行查找，看其中一个是否包含此项.图1左部分显示了将新元素a插入到包含8个桶的简易布隆过滤器的示例，其中a可以放在桶2或桶6中.如果a的2个桶中的任何一个为空，则算法将a插入到该空闲桶中，插入完成.如果2个存储桶都不为空，如本例中的情况，则项目选择1个候选存储桶(如桶6)，踢出现有项目(如a)，并将此项目重新插入到其自己的备用位置.该过程可能会重复，直到如图1右部分所示找到空桶，或直到达到最大位移数.如果未找到空桶，则认为此Hash表已满，无法插入.

Fig. 1 Illustration of cuckoo Hash图1 布谷鸟Hash图解

本文引用文献[27]中提出的布谷鸟过滤器.具体细节为：

(1)

其中,j∈R[b],∈R表示从集合中随机选择1个元素.重置i,j索引的k，tij=∅⟺tij=k(i=i⊕h(k)，j∈[b]).若不存在这样的tij，则重复上述过程，从式(1)中得k.

测试集合成员a∈S：首先检测是否存在i,j，使i∈{h(a),h(a)⊕h(fp(a))}，j∈[b]且tij=fp(a).若条件成立则称大概率a∈S(a∉S的概率忽略不计)；若条件不成立则称a∉S.错误率与存储在布谷鸟过滤器中的指纹大小相关，指纹越长错误率越低.从S中删除a时，仅需检测是否存在i,j满足tij=fp(a)，i∈{h(a),h(a)⊕h(fp(a))}，j∈[b].若存在，将tij置为空.

2.2 密文等值测试

简单地讲，密文等值测试就是检查2个密文是否由同一明文加密[28].本文对文献[29]中的密文等值技术进行简化.使用双线性映射技术，对不同公钥生成的2个密文进行等值测试.

简化的密文等值测试方案PKEET′：

2)PKEET′.T(C1,C2).给定密文C1=(U1,V1)和C2=(U2,V2).若e(U1,V2)=e(U2,V1)，则返回True，否则返回False.

3 算法定义和安全模型

3.1 算法定义

基于文献[16]的FSSE-ε方案、文献[27]的布谷鸟过滤器和文献[29]的密文等值测试技术，构造一种支持联合搜索的前向安全可搜索加密方案FSSE-CT.该方案由1个算法和2个协议组成：Π=(Setup,Update,Search).

1) 系统初始化算法.Setup(1λ)→(uk,W,T,CF).该算法输入安全参数λ；输出密钥uk、空映射W、空树T、空布谷鸟过滤器CF.

2) 更新协议.Update()=(Update(),UpKW(),AddInd(),DelInd()).该协议根据不同的操作要求由4个算法组成.

① 更新树算法UpdateTree(op,(w,ind),σ)→(T).用户端、服务器端合作完成.输入更新操作op∈{add,del}(添加或删除)、文件-关键词对(w,ind)、用户状态σ={w,W[w].cnt}；服务器输出更新后的树T.

② 文件-关键词对更新算法UpKW(op,w,ind,σ)→(T,CF).用户端、服务器端合作完成.用户端输入操作op∈{add,del}、该文件包含的关键词集合w={w1,w2,…,wn}、待添加文件ind、用户状态σ；服务器端输出更新后的数据库树T和布谷鸟过滤器CF.

③ 文件添加算法AddInd(op=add,w={w1,w2,…,wn},ind,σ)→(T,CF).用户端、服务器端合作完成.用户端输入操作op=add、该文件包含的关键词集合w={w1,w2,…,wn}、待添加文件ind、用户状态σ；服务器端输出更新后的数据库树T和布谷鸟过滤器CF.

④ 文件删除算法DelInd(op=del,w={w1,w2,…,wm},ind,σ)→(T,CF).用户端、服务器端合作完成.用户端输入删除操作op=del、该文件包含的关键词集合w={w1,w2,…,wm}、待添加文件ind、用户状态σ；服务器端输出更新后的数据库树T和布谷鸟过滤器CF.

3) 搜索协议.Search(w1∧w2∧…∧wd,σ)→(T,Q).用户端、服务器端合作完成.用户端输入待问询联合关键词(w1∧w2∧…∧wd)、用户状态σ，服务器端输出更新后的数据库树T和问询结果文件En(ind)集合Q.

3.2 安全模型

FSSE-CT的安全模型由现实世界SSEReal和理想世界SSEIdeal的游戏定义.SSEReal等同于FSSE-CT方案中的操作，SSEIdeal由模拟器S构造.定义泄露函数L=(LSetup,LUpdate,LSearch)，表示敌手A可以从Setup()，Update()，Search()算法中获取的泄露信息，且敌手能获取信息的范围不会超出泄露函数L.

在现实世界游戏SSEReal中，敌手A运行Setup()并获得EDB.随后A执行搜索问询或更新问询以获取信息.在理想世界游戏SSEIdeal中，模拟器S输入LSetup(λ,DB).随后敌手A进行搜索或更新问询，模拟器S相应地通过泄露函数LSearch(q)或LUpdate(op,in)回复问询，给A提供信息.最终，A输出b∈{0,1}表示对SSEReal和SSEIdeal的区分.

定义1.L-自适应安全(L-adaptively-secure).如果存在1个模拟器S，使得对于任意概率多项式时间PPT敌手，都有：

|P[SSERealA(λ)=1]-
P[SSEIdealA,S(λ)=1]|≤negl(λ),

则该对称可搜索加密方案是L-自适应安全的.

3.3 前向安全

前向隐私是防止动态对称可搜索加密方案(dynamic searchable symmetric sncryption, DSSE)泄露的强大属性.简单地讲，这意味着更新不会泄露已更新关键词的任何信息.本文引用文献[16]中前向隐私技术的定义.

1) 泄露.泄露函数L=(LSetup,Search,LUpdate)表示FSSE协议泄露给敌手的信息量.泄露函数L将问询列表LQ(到目前为止所有问询的列表)看作状态.将每次对关键词w的问询表示为(i,w)，或将输入值为IN的更新问询OP表示为(i,OP,IN).其中整数i表示初始值为0的时间戳，随问询次数的增加而增加.

sp(x)表示搜索模式：

sp(x)={j:(j,x)∈LQ}(仅匹配搜索问询).

qp(x)表示问询模式：

qp(x)={j:(j,x)∈LQor (j,op,in)∈LQ
且x出现在IN中}.

2) 前向安全.引用文献[15]中的定义.

定义2.若更新泄露函数LUpdate可以表示为式(2)，则L-自适应安全的方案∑是前向安全的.

LUpdate(OP,IN)=L′(OP,{(indi,ui)}),

(2)

其中,{(indi,ui)}表示修改后的文档集合，ui表示被更新文件indi的修改数量.

4 方案构造

本节具体描述支持联合搜索的动态前向安全可搜索加密方案FSSE-CT.原理上该方案可以将任何支持单关键词搜索的FSSE扩展成支持联合关键词搜索的方案，且不会造成重大的泄露.即，构造一种联合搜索的方法：在服务器端添加1个简化的布谷鸟过滤器，将经密文等值测试技术构造后的加密关键词存于该过滤器中，以筛选联合关键词，得到所需结果.本文以与FSSE-ε方案[16]结合为例完成完整的方案.

4.1 存储结构

4.1.1 倒排索引构造SE

4.1.2 构造二叉索引树

构造二叉索引树T，存储加密后的文件信息.

3) 生成1个块链.执行CInit()初始化链C.对每个待存入链C的块b执CAddHead().链接这些块，将1个块的ptr和key设置为下一个块的数据标识符和加密密钥(尾部块中为⊥)；加密块的标识符和加密密钥并存储在先前的块中(将头块中的ptr和key存储于用户端)以隐藏关系.

4.1.3 用户状态

使用对称加密原语构造单向置换函数P:{0,1}λ→{0,1}λ，Pkρ(x)为由密钥kρ控制的置换函数.选取由密钥控制的伪随机函数FFSSE，输入输出值长度相同.定义伪随机函数PRF G: W→{0,1}λ，W表示关键词或关键词的唯一标识符iw≤W.选取由密钥控制的Hash函数HRG，输出值为μbit的字符串.

重新生成算法ReGen(w,c)：

1) 若W[w].cnt==-1，分别设置id，key为⊥.

4.1.4 布谷鸟过滤器

在服务器端构造简化的布谷鸟过滤器，存储快速筛选文件ind的信息.具体地，随机选取2个Hash函数fingerprint:{0,1}*→{0,1}m，Hc:{0,1}*→{0,1}l，构建布谷鸟过滤器的布谷鸟Hash表，基础单元为entry.Hash表由多个存储桶bucket数组组成.每个存储桶bucket可以存储多个entry.每个桶的首个entry用于存放索引该桶的指纹f=fingerprint(tag)，其余的entry用于存放加密后的关键词.在本方案中每个桶代表1个文件，由文件标签tag索引，桶中存放该文件包含的所有关键词(经加密的).

服务器端为所有的tag分配桶.具体操作为：

1) 插入算法CFInsert(tag).输入文件标签tag，无输出.将指纹f=fingerprint(tag)插入布谷鸟过滤器相应的桶中.计算2个候选桶bucket[i1]和bucket[i2]：

(3)

若存在bucket[i2]或bucket[i1]为空，则将指纹f添加到该桶的第1个块中.若都不为空，则i←R{i1,i2}.取出桶bucket[i]中存放的指纹f；计算i=i⊕Hc(f)；若bucket[i]为空，则添加f到bucket[i].循环这个步骤，找到合适的位置，插入指纹.循环次数需小于最大踢出量MaxNumKicks，若达到MaxNumKicks则插入失败.

2) 查询算法CFLookup(tag).输入文件标签tag，判断若tag存在则返回True，否则返回False.即，生成f=fingerprint(tag)，执行式(3)，得到相应的桶bucket[i1]，bucket[i2].若桶中含有f则返回True，否则返回False.

3) 删除算法CFDelete(tag).输入文件标签tag，删除相应桶中的指纹f，成功返回True，否则返回False.即生成f=fingerprint(tag)，执行式(3)，得到相应的桶bucket[i1]，bucket[i2].若桶中含有f则移除并返回True，否则返回False.

4.2 方案结构

本节对FSSE-CT方案进行详细说明.

4.2.1 系统初始化阶段

Setup(1λ).输入：安全参数λ，μ，ν，ο.输出：密钥uk←R{0,1}λ，uk*←R{0,1}λ、用户状态σ、空树T、空简化布谷鸟过滤器CF.

1) 定义G1，G2是q上的2个乘法循环群，阶为素数q，g为群G的生成元，定义双线性映射e:G1×G1→G2.

2) 选取由密钥控制的Hash函数HFSSE:{0,1}*→{0,1}2μ+ν+1+log N.随机选取2个Hash函数Htag:{0,1}*→{0,1}ν，HRG:{0,1}*→{0,1}μ.

3) 生成密钥uk←R{0,1}λ，uk*←R{0,1}λ.

4) 为单向置换函数P选择密钥kP.

5) 选取由密钥uk控制的伪随机函数FFSSE，输入输出字符串长度相等.

4.2.2 更新阶段

本方案支持3种更新操作：文件添加、文件删除、关键词更新.每个操作分为2步：1)更新树T；2)更新布谷鸟过滤器中的桶.

1) 更新树T阶段UpdateTree(op,(w,ind),σ;EDB).用户端、服务器端合作完成.输入：更新操作op←{add/del}、(w,ind)对、用户状态σ={w,W[w].cnt}，W[w]表示关键词w的映射.输出：加密后的数据库树T.即通过在服务器端插入由用户端构建的块b，实现(w,ind)对的更新.

用户端：

① 生成新数据块b.输入σ，调用ReGen()得到关键词w的信息(id,key).根据op，对W[w].cnt执行相应操作(W[w].cnt++/--).再次调用ReGen()得到块b的标识符id*和加密密钥key*.b.value=tag‖En(ind)‖op，b.key=key，b.ptr=id.生成mask←HFSSE(key*,id*)，用于加密b.value，b.key，b.ptr.

② 为文件ind生成标签tag←Htag(ind).

③ 将构建好的块b发送到服务器端.

服务器端：

④ 将从用户端接收到的块b插入树T.

2) 单个关键词更新阶段UpKW(op,w′,ind,σ;T，CF).用户端、服务器端合作完成.输入：更新操作op、待更新关键词w′、文件ind、用户状态σ.输出：更新后的树T和布谷鸟过滤器CF.

用户端：

① 修改用户状态σ中关键词w′索引的文件个数(根据op，W[w].cnt++/--)，调用UpdateTree()生成b.

③ 生成文件ind的标签tag←Htag(ind).

④ 将{b,(C′,op),tag}发送给服务器端.

服务器端：

⑤ 服务器端接收到{b,(C″,op),tag}后，将块b插入到树T中.

⑥ 执行Lookup(tag)找到布谷鸟过滤器中对应的桶.若op==add直接将C′添加到桶中，若op==del从桶中的第2个元素开始执行PKEET′.T(C′,Cb)找到返回为True的Cb并删除.

3) 文件添加阶段AddInd(op=add,{w1,w2,…,wn},ind,σ;EDB,CF).用户端、服务器端合作完成.用户端输入添加操作op=add、待添加文件ind、关键词集合{w1,w2,…,wn}、用户状态σ；服务器端输出更新后的树T和布谷鸟过滤器CF.

用户端：

① 生成2个空集合B←{}，C←{}.

② 修改文件ind中每个wi(i∈{1,2,…,n})相关文件个数W[w].cnt++，然后调用UpdateTree()生成n个块{b1,b2,…,bn}，并将这n个块存入集合B中.

③ 执行PKEET′.E(wi)为加密wi.即，随机选择ri←R计算Ui=gri，Vi=，得到待测试内容为Ci=(Ui,Vi)，将Ci存于集合C中.

④ 生成文件ind的标签tag←Htag(ind).

⑤ 最后将{B,C,tag}发送给服务器端.

服务器端：

⑥ 服务器端接收到{B,C,tag}后，先将B中的块b逐个插入到树T中.

⑦ 执行CFInsert(tag)找到布谷鸟过滤器中对应的桶，并将C中内容逐个插入该桶.

4) 文件删除阶段DelInd(op=del,w={w1,w2,…,wm},ind,σ;T，CF).用户端、服务器端合作完成.用户端输入操作op=del、关键词集合w={w1,w2,…,wm}、文件ind、用户状态σ；服务器端输出更新后的树T和布谷鸟过滤器CF.

用户端：

① 生成1个空集合B←{}.

② 对文件ind的每个(wtag,ind)，t∈{1,2,…,m}，修改wt相关文件的个数W[w].cnt--，然后调UpdateTree()共生成n个块{b1,b2,…,bn}，并将这n个块存入集合B中.

③ 生成文件ind的标签tag←Htag(ind).

④ 将{B,tag}发送给服务器端.

服务器端：

⑤服务器端接收到{B,tag}后，先将B中的块b逐个插入到树T中.

⑥执行CFDelete(tag)，删除布谷鸟过滤器相应桶中的所有元素.

4.2.3 搜索阶段

Search((w1∧w2∧…∧wd),σ;EDB,R).用户端、服务器端合作完成.用户端输入问询联合关键词集合(w1∧w2∧…∧wd)，用户状态σ；服务器端输出更新的树T和问询结果文件En(ind)集合R.

用户端：

1) 生成空集合Q←{}.

2) 查询σ得到{w1,w2,…,wd}中W[w].cnt最小的关键词w(设为w1).调用ReGen(w1,W[w1].cnt)得到W[w1].id，W[w1].key.

3) 对除w1外的其他关键词ws(s∈{2,3,…,m})执行PKEET′.E(ws)，选取rs←R(值可以相同或不同)，计算Us=grs，Vs=得到测试内容为Qs=(Us,Vs)，将Qs存于集合Q中.

4) 生成令牌t←{W[w1].id,W[w1].key,Q}.

服务器端：

5) 生成3个空集合S←{}，C←{}，R←{}.

7) 对所有b.value∈S，先执行CFLookup(tag)找到布谷鸟过滤器中相应的桶，将桶中除首个entry(f)外的所有元素添加到集合C中.对所有的Qs∈Q与C′∈C进行PKEET′.T(Qs,C′)操作.若所有的对比结果都为False，则说明该b.value对应的文件ind不满足联合问询；若每个Qs都查出存在C中的元素与其对比结果为True，则说明该b.value对应的文件ind满足联合问询，将其中的En(ind)存入集合R.

8) 最终将联合搜索的结果R返回给用户端.

5 方案分析

5.1 安全性

在随机预言机模型下证明本方案满足自适应性安全.

方案中LSetup=⊥，即初始化不泄露任何信息.在搜索协议中，用户端将关键词w1的搜索令牌，和其他关键词经密文等值测试构造的加密信息一起发送到服务器.在这一过程中仅会泄露问询关键词的个数，由于每个关键词都经过加密，且用于加密的r都是随机产生的，所以不会泄露除w1的部分信息外的信息.在更新过程中，所有的函数都是输入更新操作、关键词、文件标识符、用户状态，后经用户端计算，输出加密后的集合B，C和相关文档标识符，并将得到的结果发送给服务器.服务器端仅需将B和C中的元素插入到相应的位置，因此服务器无法得知更新后的文档与先前查询的关键词之间的匹配关系LUpdate=⊥.

此外，定义Hist(w)表示关键词w的历史.它列出了一段时间内对DB(w)做的所有修改.FFSSE表示由密钥控制的伪随机函数，输入λbit随机字符串和密钥uk，输出λbit字符串.HFSSE，Htag，HRG均是建模于随机预言机模型的安全Hash函数.

证明.设安全参数λ，μ，v.这里使用从真实世界衍生出的难以区分的游戏帮助证明该定理.

① tag←{0,1}ν;② if Htag(ind)≠⊥ then③ Bad←True,tag←Htag(ind);④ end if⑤ tag[ind]←tag;⑥ Htag(ind);⑦ u←Htag(ind);⑧ if u=⊥ then⑨ u←R{0,1}ν;⑩ if ∃ind,s.t. tagind∈tag[] then Bad←True,u←tag[ind]; end if Htag(ind)←u;end if return u.

结论：根据以上游戏和模拟器S.由于HFSSE，Htag，HRG都是Hash函数，可得：

证毕.

5.2 性能分析

将本方案与相关方案从搜索能力、更新类型等功能方面和搜索时间、更新时间等效率方面，以及用户端、服务器端存储代价3方面进行对比.具体的对比结果如表1所示:

Table 1 Scheme Comparison表1 方案对比

1) 功能方面.

① 搜索能力.文献[15]∑οφοζ方案和文献[16]FSSE-ε方案仅支持单关键词搜索，其余方案连同本文FSSE-CT方案均可实现联合关键词搜索.

② 更新类型.Hu等人[17]的Scheme-E方案仅支持对整个文件的更新操作.其余方案均仅支持文件-关键词对的更新操作.而本文方案，不仅支持单个文件-关键词对的更新操作，也支持对整体文件信息的更新操作，相对于其他方案有较灵活的更新能力.

2) 效率方面.

3) 存储代价.

① 用户端存储代价，除Scheme-B方案外，其余方案都是对每个关键词包含的文件个数进行存储(其余的信息通过后期计算得到)，具有相同的空间复杂度O(W′logD)，Scheme-B方案在此基础上额外存储了1个布隆过滤器.

② 服务器端存储代价，∑οφοζ方案、FSSE-ε方案因仅支持单关键词查询空间复杂度为O(N)×λ.Scheme-B方案将布隆过滤器放置在用户端，服务器端空间复杂度也为O(N)×λ.Scheme-E方案额外为每个元件存储用于IPE计算的向量，空间复杂度为O(N)×λ×W′.OXT-E方案额外存储3个表格用于筛选联合搜索的关键词空间复杂度为O(N)×(λ+2|本文方案仅额外增加1个布谷鸟过滤器，空间复杂度减少至O(N)×(λ+2|G|).显然本文具有一定的存储优势.

综上所述，本文支持联合搜索，并且具有相对灵活的更新操作，即本文可以对单个文件-关键词对进行更新操作，也可以对整个文件集合进行操作,且更新效率较佳.同时，在支持联合搜索的方案中，本文方案无论是用户端存储还是服务器端存储都具有优势.

6 实验结果

本节对FSSE-CT方案进行实验性能分析，分别从基于大数据集的实验和与Scheme-B[17]对比实验2个方面，对本文方案进行实验评估.因FSSE-CT方案基于FSSE-ε，所以仅对扩展联合搜索性能的部分进行评估，并用将扩展开销与FSSE-ε开销相加的方式来计算方案的总体性能.

6.1 基于大数据集的FSSE-CT方案实验

本实验以Enron电子邮件数据集为测试数据集，从布谷鸟过滤器操作时间、整体更新时间、整体搜索时间3个方面进行仿真测试.

Enron电子邮件数据集含有51.7万个文档，从中提取出167.20万个关键词、0.86亿个关键词-文件对，其中超过100万个关键词仅匹配1个文档，且大多数文档的匹配关键词数少于10个(本方案以关键词数量为10为例设置参数)，将整个数据集插入到1个空的rocksdb数据库中.

本实验的硬件环境为Intel Core i5-3337 CPU和8 GB DDR3 RAM的个人计算机.使用FSSE-ε给出的开源代码进行基础FSSE方案构造.对称密钥长度λ=256 b，关键词-文件对的最大数量Nmax=232，标识符ind长度μ=64 b.块长度为480 b(值416 b，块标识符64 b).扩展部分为在服务器端添加1个经加密的布谷鸟过滤器，在其中存储每个关键词用于密文等值测试的加密原语.使用文献[27]提出的ssCF布谷鸟过滤器，大小为2.7 MB，包含9种Hash函数每项12 b，Hash表具有m=217个存储桶，每个存储桶由4个12 b条目和32 b的地址组成.该过滤器约可存1.3亿个元件，其假阳性率为0.09%，构建效率为3.13×106个元件/s.为每个关键词存储的用于进行密文等值测试的加密原语为32 b，总存储大小为6.4 MB.FSSE-CT方案中对布谷鸟过滤器的占用率最多达到约50%，所以执行布谷鸟过滤器中文件更新和查找操作所消耗的时间可忽略不计.实验结果如图3～5所示.

Fig. 3 Time of setting/checking cuckoo filter图3 布谷鸟过滤器执行设置/查找操作所消耗的时间

Fig. 4 Average time spent on update operations图4 更新操作平均消耗的时间

Fig. 5 Average time spent by search operations图5 搜索操作平均消耗的时间

图3展示在不同规模的大数据集中(Enron电子邮件数据集的倍数)，布谷鸟过滤器执行设置/查找操作所消耗的时间.横坐标分别取Enron电子邮件数据集的20～24倍，分别约0.86亿、1.73亿、3.46亿、6.92亿和13.84亿个关键词-文件对.对Enron电子邮件数据集本身(约0.86亿个关键词-文件对)执行布谷鸟过滤器设置/查找操作所消耗的时间约为0.17 s.21倍时(约1.73亿个关键词-文件对)，耗时约为0.32 s；22倍时(约3.46亿个关键词-文件对)，耗时约为0.63 s；23倍时(约6.92亿个关键词-文件对)，耗时约为1.25 s；24倍时(约13.84亿个关键词-文件对)，耗时约为2.42 s.由图3可见时间消耗的增加几乎与数据集的大小成线性关系.

图4展示在不同规模的大数据集(Enron电子邮件数据集的倍数)中，FSSE-CT方案对单个文件-关键词对执行更新操作所消耗的时间.即，执行FSSE-ε更新操作所消耗的时间，加上对关键词进行密文等值测试加密并将其插入至布谷鸟过滤器所消耗的时间.数据集大小为Enron电子邮件数据集本身时(约0.86亿个关键词-文件对)，执行更新操作消耗的时间为0.124 ms；数据集大小为1.73亿个关键词-文件对时，耗时约为0.147 ms;数据集大小为3.46亿个关键词-文件对时，耗时约为0.160 ms；数据集大小为6.92亿个关键词-文件对时，耗时约为0.190 ms；数据集大小为13.84亿个关键词-文件对时，耗时约为0.236 ms.图3显示出随数据集的扩大，更新操作所消耗的时间呈线性增长.

图5展示了在不同规模的大数据集(Enron电子邮件数据集的倍数)中，FSSE-CT方案执行搜索操作所消耗的时间.随着单次联合搜索中关键词数量的增多，搜索所消耗的时间会有所增多.本实验以对2个关键词进行联合搜索为例.数据集大小为Enron电子邮件数据集本身时(约0.86亿个关键词-文件对)，执行搜索操作消耗的时间约为14.290 9 ms；数据集大小为1.73亿个关键词-文件对时，耗时约为14.299 3 ms;数据集大小为3.46亿个关键词-文件对时，耗时约为14.293 3 ms；数据集大小为6.92亿个关键词-文件对时，耗时约为14.304 9 ms；数据集大小为13.84亿个关键词-文件对时，耗时约为14.347 7 ms.搜索效率主要受单个文件包含的关键词数量的影响.

综上所述，本方案实际性能测试和理论性能分析一致，且无论是布谷鸟过滤器执行操作消耗的时间还是更新、搜索操作消耗的时间，都是毫秒级别，在实际应用过程中具有较高的可操作性.

6.2 FSSE-CT方案与Scheme-B方案对比实验

本实验的硬件环境和FSSE-CT方案的参数设置与7.1节相同.将FSSE-CT方案与Scheme-B方案进行具体的实验对比分析，实验结果如图6～7所示.

Fig. 6 Time consuming comparison between Bloomfilter and cuckoo filter图6 布隆过滤器和布谷鸟过滤器的耗时对比

Fig. 7 Time consuming comparison of search operation图7 搜索操作的耗时对比

1) 布隆过滤器与布谷鸟过滤器实验对比.图6显示了Scheme -B方案中使用的布隆过滤器和FSSE-CT方案中使用的布谷鸟过滤器的耗时对比.如图6所示，横坐标分别为包含100～1 000个索引的数据集，间隔为100.当索引数为100时FSSE-CT方案和Scheme-B方案的耗时分别为0.319 ms和12.723 ms，Scheme-B方案的耗时高于FSSE-CT方案.2个方案的耗时均随着索引数的增加而增加.由图6可见，Scheme-B方案的耗时增长速度大于FSSE-CT方案.综上，FSSE-CT方案使用布谷鸟过滤器，不论是在时间消耗量还是在增长趋势方面都具有一定的优势.

2) 搜索操作实验对比.图7显示了Scheme-B方案和FSSE-CT方案的搜索算法的耗时比较.横坐标分别为包含100～1 000个索引的数据集，间隔为100.当索引数为100时，FSSE-CT方案和Scheme-B方案的耗时分别为10.730 ms和25.058 ms，Scheme-B方案的耗时高于FSSE-CT方案.Scheme-B方案搜索操作耗时随索引数的增加而增加，而FSSE-CT方案的搜索耗时在8～15 ms之间浮动.FSSE-CT方案在时间消耗和增长趋势上都优于Scheme-B方案.

结果表明，FSSE-CT方案具有良好的计算效率.且Hu等人.Scheme -B方案中布隆过滤器存储在用户端，增加了用户端的存储负担和计算开销.FSSE-CT方案使用的布谷鸟过滤器存储在服务器端，在不给客户端增加存储和计算负担的同时，提高计算效率.

7 结束语

本文方案在支持单关键词搜索的前向安全可搜索加密方案的基础上，采用布谷鸟过滤器技术和密文等值测试技术，构造一种支持联合搜索的动态前向安全可搜索加密方案，实现前向安全基础下，对关键词进行联合搜索，并且支持更加灵活的更新操作，即支持对整个文件信息的添加/删除和对单个文件-关键词对的添加/删除工作.此外本文方案满足自适应模型下不可区分的安全性.采用密文等值测试技术加密保证在对关键词进行二次筛选时，不泄露关键词的相关信息.同时由于使用布谷鸟过滤器进行存储，降低了服务器端的存储开销.理论性能分析和实际性能分析表明，本文方案与相关方案相比，在更新类型的灵活性、更新时间、用户端/服务器端存储方面有一定的性能提升.下一步将考虑如何进行轻量级优化，提升搜索能力并在实际应用场景中实现.