一种基于SRE 的对称可搜索加密方案

黄一才 郁 滨 李森森

（信息工程大学 郑州 450001）（huangyicai3698@163.com）

可搜索加密无需解密就能实现数据搜索.依据搜索时所采用的加密算法加密方案可分为公钥可搜索加密（public key encryption with keyword search, PEKS）和对称可搜索加密（searchable symmetric encryption,SSE）这2 类.其中SSE 方案因采用对称算法，在数据量较大的云存储环境下往往具有更高的搜索效率.

1 相关工作

2000 年，Song 等人[1]提出了可搜索加密的基本概念，并基于对称密码算法，构造对称可搜索加密方案.文献[2-6]分别构造了正排索引、倒排索引、双向索引和树形索引结构的对称可搜索加密方案，提高了方案的搜索效率.

相比静态方案，支持密文数据更新，如添加、删除等操作的动态方案具有更好的实用性.文献[6]利用OMAP 结构隐藏服务器密文字典的访问地址，实现了一种安全且支持动态更新的对称可搜索加密方案，但OMAP 结构较高的通信开销降低了方案的实用性[7].文献[8-10]分别采用并行计算和优化I/O 效率的方式进一步提高了方案的搜索效率.文献[11]设计2 级索引链结构，实现了固定大小的客户端存储空间开销.

安全性一直是动态方案构造中研究的热点问题.为方便对动态方案的安全性进行分析，Curtmola 等人[4]通过泄露函数给出了自适应安全对称可搜索加密方案的定义.文献[12]给出了方案动态更新时前向及后向隐私的正式定义.文献[13]构造了一种前向隐私的可搜索加密方案，但方案需要进行大量的指数运算，搜索效率不高.文献[14-16]提出了执行效率更高的前向隐私方案.文献[17-18]提出了同时满足前向和后向隐私的对称可搜索加密方案，文献[19]提出了利用SGX 技术实现的后向隐私，但方案的安全性需要基于特殊软件平台，一定程度上降低了方案的通用性.

方案的构造过程通常需要结合应用场景在搜索效率、存储和通信开销、安全性、功能性等方面进行多种妥协.其中利用可穿刺加密技术构造的前向/后向隐私方案，具有交互少、安全性高的特点，近年来越来越受到人们的重视.文献[20]基于可穿刺加密技术，在Janus 方案[12]基础上，采用可穿刺伪随机函数[21]代替公钥算法，设计了对称可穿刺可搜索加密方案Janus++，提高了方案在增加和删除密文索引时的效率，且方案在实现后向隐私的同时，具有更小的通信开销.

Sun 等人[22]指出Janus++方案中使用的对称可穿刺加密（symmetric puncturable encryption，SPE）无法抵抗共谋攻击，为此定义了基于可穿刺伪随机函数的对称可撤消加密（symmetric revokable encryption，SRE）密码学原语，并利用对称可撤消加密构造一种单轮交互的后向安全对称可搜索加密方案Aura.Aura 方案使用GGM 树实现可穿刺伪随机函数，并在此基础上引入Bloom Filter 记录删除索引，实现了TypeII 级后向隐私.实验证明，该方案能够进一步提高搜索响应速度.然而该方案存在2 个方面的不足：1）由于Bloom Filter 存在假阳性[23]，会导致索引误删除.2）服务器在每次搜索前需要生成所有密钥序列，增加了服务器计算开销，降低了搜索效率，且使非可信服务器提前掌握了所有密钥信息，存在一定的安全隐患.

本文基于Aura 方案[22]提出了一种改进的可穿刺对称可搜索加密方案，具有3 个方面的优势：

1） 搜索效率高.通过在客户端增加存储节点使用标志，解密时仅传输已使用节点密钥，减少服务器端计算开销，提高搜索效率，且节点平均搜索时间不受节点规模影响.

2） 避免误删除.结合Bloom Filter 设计思想，计算可穿刺密钥节点位置选择算法，在提高节点利用率的同时，防止因哈希碰撞而误删索引.

3） 服务器密文存储规模小.Aura 方案中密文规模与Bloom Filter 中哈希函数个数相关，通过设计插入位置选择算法为每个索引选择唯一的节点位置，避免密文规模扩大，减少服务器密文存储开销.

2 预备知识

首先简要介绍方案设计中用到的相关密码学基础知识，包括多点可穿刺伪随机函数、对称加密算法及前向与后向隐私等.

2.1 多点可穿刺伪随机函数

定义1.多点可穿刺伪随机函数[21-22].设t(·)表示一个确定的多项式，密钥空间为 K的伪随机函数MF：K×X →Y ， 若集合S满 足 |S|≤t，存在另外一个密钥空间Kp以及3个多项式时间算法 （Setup,Punc,Eval）：

1）k←Setup(1λ).输入安全参数λ，输出伪随机函数密钥k∈K.

2）kS←Punc(k,S).输 入 密 钥k∈K ， 集 合S⊂X s.t.|S|≤t(λ)， 输出可穿刺密钥kS∈Kp.

3）y←Eval(kS,x).输入可穿刺密钥kS∈Kp，x∈X，输出y∈Y 或 ⊥.

则称MF为多点可穿刺伪随机函数t-Punc-PRF（tpuncturable pseudorandom function）.

定义2.MF正确性[22].对所有S⊂Xs.t.|S|≤t(λ)，x∈XS，k←Setup(1λ)，kS←Punc(k,S)， 对 所 有k∈K使

成立，其中 ν (λ)为 可忽略函数，则称函数MF满足正确性条件.

2.2 对称加密算法

定义3.对称加密算法[22].设明文空间 M、密钥空间 K 和密文空间 C，则对称加密（symmetric encryption，SE）算法可用3 个多项式时间算法的三元组表示，记为S E=(Gen,Enc,Dec)，其中：

1）k←Gen(1λ).输入秘密参数 λ ，输出密钥k∈K.

2）ct←Enc(k,m).输入密钥k、明文消息m，输出密文ct∈C.

3）m←Dec(k,ct).输入密钥k、密文ct，成功解密输出ct对应明文m， 否则输出 ⊥.

定义4.SE正确性[22].若算法对任意明文m∈M，k←Gen(1λ)且ct←Enc(k,m)，满足

则称算法SE满足正确性条件.

2.3 前向隐私与后向隐私

可搜索加密方案前向隐私是指更新查询不会泄露正在更新的关键字或文档对中所涉及的关键字信息，主要针对文档添加操作，确保新添加文档不会包含在以前查询令牌的检索结果中.文献[24]指出针对不具备前向隐私的方案可有效实施文件注入攻击，快速恢复用户检索信息.

后向隐私要求搜索和更新操作仅泄露数据库中的当前文档（不包括已删除的文档），主要针对文档删除操作，确保当前查询不会包含过去已删除的文档索引.文献[4]根据泄露信息不同，将安全强度由高到低分为TypeⅠ，TypeⅡ，TypeⅢ.TypeⅠ后向隐私允许泄露当前关键词所匹配的文档索引、插入时间及更新关键词的更新总数；TypeⅡ在TypeⅠ基础上，增加了泄露关键词的操作类型和时间；TypeⅢ相对于TypeⅡ，增加了泄露删除操作对应的那个添加操作.

3 搜索模型

本文方案中各主要符号定义如表1 所示.为简化方案构造，假定：

Table 1 Symbol Definition表1 符号定义

1）服务器为“诚实且好奇（honest but curious）”的.即服务器能忠实运行用户发出的请求，但也会尽可能地窥探用户个人隐私.

2）只有数据拥有者（data owner，DO）是完全可信的，且能够访问系统中所有的明文信息；各实体之间以及云存储服务器内部各通信信道均不可信，且存在各种可能的网络攻击行为.

3）数据拥有者能够对文档进行解密，但在访问服务器前并不确定云服务器中存有哪些文件，以及是否包含其想要的文件.

4）不考虑多客户端应用场景.仅对方案搜索效率优化与避免误删除进行设计，对多客户端场景下的特殊性不做专门研究.

3.1 场景描述

对称可搜索加密应用场景由安全存储服务器和数据拥有者2 部分组成，其中安全存储服务器包括1个存储用户密文文件的存储服务器和1 个实现数据密文搜索的密文索引搜索服务器.DO 既能够向安全存储服务器中添加新的密文文件，又可以实现对数据密文查询.应用场景如图1 所示.

Fig.1 Application scenario of dynamic searchable symmetric encryption图1 动态对称可搜索加密应用场景

方案的工作过程包括数据动态更新和数据查询2 个阶段，其中数据动态更新通常包括数据添加、删除和更新3 种操作，为简化描述过程，这里以数据添加为例，具体描述方案的工作过程.

1）数据添加.用于向密文索引数据库中加入新的数据文件索引.DO 先将数据文件加密后存储在文件存储服务器，并返回访问入口信息；然后DO 通过对明文数据进行处理，生成文件访问入口信息与关键词对应关系，并按照一定索引结构生成密文索引，将密文索引存储于密文索引服务器.

2）数据查询.要求密文服务器不用解密具体密文文件，便能从所有密文文件中返回符合用户查询需求的文件信息，这也是可搜索加密方案的核心.此过程一般是DO 通过关键词生成查询令牌，然后通过密文索引服务器获取密文文件的入口地址信息，最终从密文文件服务器获取密文文件.

3.2 方案形式化描述

动态对称可搜索加密（dynamic searchable symmetric encryption, DSSE）的形式化定义通常由一组多项式时间算法组成.

定义5.DSSE 方案.设数据库由DB=文档地址或关键词集构成，其中idi为第i文 档，Wi为文档i包含的关键词集合，d为数据库中文档的数量，则动态对称可搜索加密方案可用一个三元组多项式时间算法(Setup,Search,Update)表示，其中：

1）初始化算法：(K,σ,EDB)←S etup(1λ,DB).算法输入安全参数 λ和明文索引数据库DB， 输出密钥K、关键词状态 σ和密文索引数据库EDB.在DSSE 方案中，通常设EDB=∅.

2）查 询 算 法：(DB(w),σ′,EDB′)←S earch(K, σ,w;EDB).输入密钥K、关键词状态 σ和检索关键词w，输出包含检索关键词w的所有文档标识DB(w)，以及搜索操作后关键词状态 σ′和密文索引数据库EDB′.通常算法包含客户端生成查询令牌和服务器根据令牌搜索查询结果2 部分.

3）更新算法：(σ′,EDB′)←Update(K,σ,w,ind,op;EDB).输入密钥K、关键词状态 σ、更新关键词w及对应索引ind，更新操作类 型op，其中op∈{add,del}，输出更新后的密文索引数据库EDB′、 关键词状态 σ′.

定义6.DSSE 正确性[25].对于所有的DB和W，若任意的w∈W，满足

则称DSSE 方案满足正确性条件.

3.3 SRE 语法定义

定义7.SRE 算法定义[21].设 MSK表示密钥空间，T表示标签空间，则一个SRE 算法可用4 个多项式时间算法表示，记为SRE=(KGen,Enc,KRev,Dec)，其中：

1）msk←KGen(1λ).输入安全参数 λ，输出系统密钥msk∈MSK.

2）ct←Enc(msk,m,T).输入系统密钥msk，消息m∈M 及 标签列表T⊆T ，输出消息m标 签T下的密文ct.

3）skR←KRev(msk,R).输入系统密钥msk及撤消列表R⊆T ，输出撤消后的密钥skR，仅能解密不属于标签R对应的密文.

4）m←Dec(skR,ct,T).输入撤消后的密钥skR、密文ct及对应标签T，输出消息m（ 解密失败输出 ⊥）.

定义8.SRE正确性.对所有安全参数 λ ∈N+，消息m∈M 及 对应标签T⊆T 、撤消列表R⊆Ts.t.R∩T=∅，算法SRE正确解密的概率Pr[SRE.Dec(skR,ctm,t)=m]=即对于未撤消加密节点均可正确解密，则称算法S RE满足正确性条件.

相比文献[21]给出的正确性定义中，解密发生错误的概率以一个不可忽略函数 ν (λ)为上界，定义8要求能够对t∈T 且t∉R的 所有密文ctm及对应标签T，均可正确解密.

定义9.撤消操作.对所有安全参数 λ ∈N+， 消息m对应标签t∈Ts.t.T⊆T 和撤销列表R⊆T ，消息m∈M，撤消加密操作定义为R=R∪{t}.

性质1.撤消操作的有效性.对所有安全参数λ ∈N+， 消 息m对 应 标 签t∈Ts.t.T⊆T 和撤 销 列 表R⊆T ，消 息m∈M 撤 消 加 密，则Pr[S RE.Dec(skR,ctm,t)=m]=0 ， 即撤消加密后无法通过撤消后的密钥skR、密文ctm和对应标签t完成解密.

证明.令消息m撤消前的撤消列表为R′，根据定义9，撤消后撤消列表R=R′∪{t}， 则有t∈T 且t∈R.

根据正确性定义，Pr[S RE.Dec(skR,ctm,t)=m]=0.

证毕.

性质2.撤消操作的正确性.对所有安全参数λ ∈N+， 已 插 入 消 息 M={m1,m2,···,mn}，对 应 标 签T={t1,t2,···,tn} 和 撤销列表R⊆T ，其中n为已插入消息 数.∀mi,mj∈M ， 对 应 标 签 分 别 为ti,tj∈Ts.t.i≠j,ti≠tj.当ti∈R,tj∉R，则

Pr[SRE.Dec(skR,ctmi,ti)=mi]=0且Pr[SRE.Dec(skR,ctmj,tj)=mj]=1，即撤消解密后不会破坏其他已加密密文解密的正确性.

证明.因为ti∈R，由性质1 可知，Pr[S RE.Dec(skR,ctmi,ti)=mi]=0成立.

因为tj∈T且tj∉R， 则由定义8 可知，Pr[S RE.Dec(skR,ctmj,tj)=mj]=1成立.证毕.

撤消消息m∈M 对 应密文ctm的 解密操作，将ctm对应标签tm加入撤消列表，即进行消息删除操作.

定理1.误删除条件.若方案满足正确性条件，发生误删除的充要条件是 ∃j≠i,且ti=tj.

证 明.设 ∀mi,mj∈M ，对 应 标 签 分 别 为ti,tj∈Ts.t.i≠j，mi撤 消前撤消列表为R*.

1） 充分性

设消息mi撤 消后，mj也 被撤消，其中j≠i,ti≠tj.撤消前，ti,tj∈T 且ti,tj∉R*.当mi撤消后，依据性质2，撤消列表R=R*∪{ti}.

因 为j≠i且ti≠tj，tj∉R*，所 以tj∉R*∪{ti}=R, 则Pr[SRE.Dec(skR,ctmj,tj)=mj]=1.

因为mi撤 消时，mj也被撤消，所以依据性质1，有Pr[SRE.Dec(skR,ctmj,tj)=mj]=0.

矛盾，即假设不成立.

2） 必要性

由定义9 得到，删除mi后 ，撤消列表R=R*∪{ti}，即ti∈R.因为ti=tj， 所以tj∈R.

根据正确性定义，可得

则由定义9 可知，消息mj也已删除.证毕.

可以看出，防止选择相同标签加密是避免误删除的有效手段.

4 方案构造

插入位置选择算法为每个插入文件索引寻找唯一的节点位置.在此基础上，构造基于SRE 的对称可搜索加密方案.

4.1 插入位置选择算法

插入位置选择算法用于在给定范围内，为消息m随机选择一个未使用的节点位置pm.

设hp(x)，hf p(x)分 别表示2 个 哈希函数，Lb表示长度为b的状态列表，Lb[i]=(fi,f pi).其中，fi为占用标志，宽度为1 b，用于记录列表Lb中位置i的占用情况，占用时标志置为 t rue， 否则置为false；f pi为 位置i上存储的消息指纹，一般为消息m的哈希值低n比特（n为预设指纹宽度）.图2 所示为消息m选择插入位置过程示意图.

Fig.2 Design idea of insertion position selection algorithm图2 插入位置选择算法设计思想

算法记为InsPos（b,dmax,n）， 其中b表示列表规模，dmax表示最大搜索深度，n表示消息指纹宽度，且b,dmax,n∈N+，dmax＜b，则 算 法 可 以 用 一 个 三 元 组InsPos=(S etup,Insert,Test)表示.

1）初始化：Lb←S etup(b,n,Lbinit).输入列表规模b、初始状态Lbinit， 输出状态列表Lb.工作过程为：

① 分配位长为b+nb的 比特状态列表Lb.

②若Lbinit=⊥， 令Lb[i]=(false,⊥)， 否则Lb[i]=Lbinit[i]，其中0 ≤i≤b-1.

③ 返回比特列表Lb.

2）插入点位置选择：(Rst,pm,Lb′)←Insert(m,dmax,Lb).输入待插入消息m、 最大搜索深度dmax、状态列表Lb；输出为插入结果Rst、 插入位置pm、插入后状态列表Lb′.工作过程为：

① 计算消息m的插入位置pm=hp(m)modb，f pm=hf p(m).

②令Rst=false ，若fpm=false， 则Rst=true，运 行③，否则 ∃ ≤i≤dmax，使fpm=false 成 立（其中pm=(pm+i)modb） ，则pm=(pm+i)modb，Rst=true.

③ 若Rst=true ，则 修 改Lb列 表fpm=true，f ppm=f pm.

④ 返回插入结果Rst、 插入位置pm、最新状态列表Lb′=Lb， 即 (Rst,pm,Lb′).

当Rst=true时表示在列表中找到唯一的节点位置pm， 否则表示在搜索深度d=dmax下未能找到空闲节点，返回pm为第1 哈希的节点位置.此时若选择此节点位置伪随机数作为加密密钥，将导致密钥重用，并在删除该节点时因同时删除多个文件加密密钥而造成误删除.

3）插入位置测试：(rstPos,f pm)←Test(m,dmax,Lb).通过对消息指纹对比获取消息m在 列表Lb中的位置.输入为消息m、最大搜索深度dmax、 状态列表Lb；输出为消息m插入位置rstPos，消息指纹f pm.工作过程为：

① 计算消息m的插入位置pm=hp(m)modb和消息指纹f pm=hfp(m).

②令rstPos=-1， 若 ∃0≤i≤dmax，Lb[(pm+i)modb]=(rstPos,f pm)， 则rstPos=(pm+i)modb.

③ 返回 (rstPos,f pm).当rstPos≥0时，表示找到消息m的插入位置.

在可搜索加密方案构造中，Test算法主要用于从列表删除索引时查找索引准确位置.搜索时服务器通过存储密文对应标签，直接获取节点在列表中的位置，因此不需要重新通过Test算法计算.Test算法的性能仅影响节点删除时的执行速度，不影响添加和搜索效率.

插入指纹生成时使用的哈希函数、位置选择以及位置深度搜索时使用的哈希函数可以设为相同也可以设为不同，列表占用标志fi可以通过判断指纹位置是否为0 判断该位置是否已被占用.然而指纹生成时采用哈希函数的质量将直接影响方案指纹大小设定，选择优秀的哈希函数作为消息指纹生成算法能有效降低指纹占用空间的大小.同时方案中，由于fi仅需1 b，占用空间较小，且能够方便对指定位置占用情况进行判断，提高算法执行效率.

4.2 SRE的一般构造

设S E=(Gen,Enc,Dec)为标准对称加密算法，其密钥空间为 Y，MF：K×X →Y为多点穿刺伪随机函数，记 为MF=（S etup,Punc,Eval）[20-21]，InsPos（b,dmax,n）=(S etup,Insert,Test)表示插入位置选择算法，则对称可撤消加密算法S RE=(KGen,Enc,KRev,Dec)的具体描述为4 个步骤.

1）msk←KGen(1λ,b,n,Lbinit)： 输入安全参数 λ和整 数b,n∈N+，Lbinit[i]=(false,⊥)， 其中0 ≤i≤b-1，系统主密钥msk的生成过程有2 步：

①生成Lb←InsPos.Setup(b,n,Lbinit).

②生 成sk←MF.Setup(1λ)， 输 出msk=(sk,Lb).

2） (ctm,t)←Enc(dmax,msk,m,t).输入msk=(sk,Lb)和消息m∈M对 应标签t∈T，通过2 个步骤生成密文ctm：

① (Rst,t)←InsPos.Insert(m,dmax,Lb)和skt=MF(sk,t).

② 生 成ctm=S E.Enc(skt,m)， 返 回 密 文ctm和 对 应标签t.

3）skR←KRev(msk,R).输入msk=(sk,Lb)和撤消标 签 列 表R={t1,t2,…,tτ}， 满 足 τ ≤NL，NL为Lb中 已使用节点数.通过2 个步骤生成R下撤消的密钥skR：

① 计算Lb所 有置1 的索引节点位置集合IR={t:t∈[b]且t∉R}.

② 计算集合skIR←MF.Punc(sk,IR)， 返回skR=(skIR,IR).

4）m←Dec(skR,ctm,t).输入密文ctm、 对应标签t，以及R下撤消后的密钥skR，按2 个步骤恢复消息：

① 若t∉IR，解密失败，运行②.

② 若t∈IR， 计 算skt=MF.Eval(skI,t) ， 计 算m=S E.Dec(skt,ctm).

4.3 方案描述

设Σadd=(S etup,S earch,Update)为一个前向安全的对称可搜索加密方案，用于动态增加密文索引，并保证前向数据隐私，SRE=(KGen,Enc,KRev,Dec)为对称可撤消加密算法（构造方法详见4.2 节）.算法1详细描述 基于SRE和 Σadd的可搜索 加密方 案Σadd=(S etup,S earch,Update)的工作过程.

算法1.初始化Σ.Setup(1λ).

输入：安全参数 λ；

输出：密钥集K，关键词状态 σ，密文索引数据库EDB.

客户端：

①(EDBadd,Kadd,σadd)←Σadd.S etup(1λ)；

③return((Kadd,Ks,Kt),(σadd,MS K,C,A,D),(EDBadd,EDBcache)).

初始化完成后，客户端存储密钥K=(Kadd,Ks,Kt)、关键词状态 σ =(σadd,MS K,C,A,D)，服务器存储密文索引数据库EDB=(EDBadd,EDBcache).

算法2.查询 Σ.S earch(K,w,σ;EDB).

输入：客户端输入密钥集K，关键词状态 σ，查询关键词w，服务器输入密文索引数据库EDB；

输出：匹配结果集DB(w)及 更新后关键词状态 σ′.

Step 1.生成查询令牌 Σ.S earch(K,w,σ;EDB).

客户端：

①c←C[w],mskw←MS K[w],D←D[w],

A←A[w]；

② ifc=⊥ then

③ return ∅；

④ end if

⑤ 计算skR=(skA,A)←S RE.KRev((mskw,A),D)；

/*A来自A[w]，D来自D[w]*/

⑥发送skR和tkn=h(Ks,w)至服务器；

⑦←S RE.KGen(1λ,A)；

/*搜索后更新w对应的msk*/

⑧MS K[w]←，C[w]←c+1.

Step 2.Σ.S earch(K,w,σ;EDB)结果搜索.

客户端 & 服务器：

① 运行 Σadd.S earch(Kadd,w||i,σadd;EDBadd)，服务器得到关于密文和标签对的列表((ct1,t1),(ct2,t2),···,(ctℓ,tℓ)).

服务器：

② 服务器使用skR按如下步骤解密所有密文{(cti,ti)}；

③ fori∈[1,ℓ] do

④indi=S RE.Dec(skR,cti,ti)；

⑤ ifindi≠⊥ then

⑥NewInd←NewInd∪{indi,ti}；

⑦ else

⑧DelInd←DelInd∪{ti}；

⑨ end if

⑩ end for

⑪OldInd←EDBcache[tkn]；

⑫OldInd←OldInd{(ind,t):

∃ti∈DelInds.t.t=ti}；

⑬Res←NewInd∪OldInd,

EDBcache[tkn]←Res；

⑭ returnRes.

查询算法用于实现对关键词w的搜索操作，主要包括客户端生成查询令牌和结果搜索2 个步骤，即生成查询令牌和结果搜索.

1） 查询令牌生成.查询令牌生成算法在客户端运行，输入 (K,w,σ)， 通过查询本地MS K,C,A,D的值，生成查询令牌tkn和 穿刺密钥skR，并发送到服务器.

Step1 中，客户端执行行①～⑥，根据待查询的关键词w，从MS K获取密钥mskw， 使用S RE算法生成撤消加密密钥skR，使用伪随机函数F生成查询令牌tkn，将(tkn,skR)发送至密文索引服务器.执行行⑦⑧，更新本地存储状态 σ，隐藏查询特征.同时由于行⑦⑧与Step2 在时间上可并行执行，并不会对查询效率造成明显影响.

2） 结果搜索.服务器接收到查询请求，解析查询令牌tkn和 穿刺密钥skR，运行 Σadd搜索算法查询密文索引数据库EDB， 获取关键词w未穿刺节点所有密文索引，将搜索结果返回客户端.

Step2 中，通 过 调 用 Σadd方 案 的 Σadd.S earch和S RE算法，计算查询关键词w相关的索引，去除已删除索引，更新服务器端结果缓存EDBcache，并向客户端返回查询结果.

算法3.更新 Σ.Update(K,σ,op,w,ind;EDB).

输入：客户端输入密钥集K、关键词状态 σ、操作类型op、更新关键词w及对应文档索引ind，服务器输入为密文索引数据库EDB；

输出：更新后的关键词状态 σ′，密文索引数据EDB′.

客户端：

①mskw←MS K[w]，i←C[w]，D←D[w]，A←A[w]；

②ifmskw←⊥then

③ (mskw,A)←S RE.KGen(1λ) ；

④MS K[w]←mskw，D[w]←D；

⑤i←0，C[w]←i；

⑥ end if

⑦ ifop=add then

⑧ 计算 (rst,t,A′)←FKt(w,ind)，InsPos.Insert(w,dmax,A)；

⑨ct←S RE.Enc(dmax,(mskw,A),ind,t)；

⑩A←A′； /*更新添加列表*/

⑪ 运行Σadd.Update(Kadd,add,w||i,(ct,t),σadd;EDBadd)； /*客户端&服务器运行*/

⑫ else(i.e.,op=del)

⑬D←D[w]；

⑭ ifposw≥0 then

⑮D′=InsPos.Insert(w,dmax,D)；

⑯D[w]←D′； /*更新删除列表*/

⑰ end if

⑱ end if

数据更新包括插入和删除2 类，即op=add和op=del.

插入文档索引时，客户端查找主密钥列表，找出w对应密钥信息，利用节点位置选择算法查找插入点位置，并利用SRE.Enc算法对索引进行加密，修改本地密钥位置使用标志.将密文和标签对 (ct,A)发送至服务器，服务器运行 Σadd.Update算法更新密文索引数据库EDB.

删除文档索引时，通过InsPos.Test查找需要删除的节点位置，并在删除列表记录删除标记，在下次生成搜索密钥时对应位置密钥进行穿刺，服务器因无法恢复对应节点密钥信息而无法解密，从而实现后向隐私.

5 方案分析

下面从插入位置选择算法和搜索方案分析2 个方面对方案进行理论分析.

5.1 插入位置选择算法分析

需要记录每个位置使用情况，至少需要1 b，对于一个节点规模为b列表，算法工作时需要分配b比特存储空间.插入时的时间复杂度为多项式时间O(n).为了进一步对算法的性能进行评价，现给出节点利用率定义.

定义10.节点利用率.当InsPos.Insert(x,dmax,Lb)首次输出Rst=false 时，节点利用率 ρ=N/b，其中N为Lb中元素为1 的个数.

由定义10 可以看出，因为0 ＜N≤b， 所以0 ＜ρ ≤1.随着搜索深度dmax的增大，插入点生成时间增大，空间利用率逐步升高.当dmax=b时，搜索插入点位置时间最长，节点利用率 ρ=1.在实际方案构造过程中，提高节点利用率可有效减小节点规模、减少搜索时的通信开销.

由定理1 可知，插入消息mi后导致发生误删除的概率与消息mi在 插入位置选择算法中Rst=false的概率相等.当最大搜索深度为dmax时 ，第i（i∈[b]）次选择插入位置时InsPos.Insert算法输出发生Rst=false的概率等于Lb在pm后 连续dmax+1个节点为1 的概率.

设位置选择时每次均是从空余节点中随机选择一个位置，则设指纹长度足够的情况下，节点规模为b、搜索深度为dmax的 列表在第N+1(N≥dmax)次插入失败的概率为

5.2 搜索方案分析

结合本文方案的实现过程，从搜索效率、存储开销、通信开销和安全性等方面进行分析.

1）搜索效率

搜索时服务器仅需要计算使用的密钥节点，相比每次均需要计算GGM 树所有节点密钥的Aura 方案，平均搜索时间更低.实际上GGM 树节点计算随着节点规模的扩大而迅速增加，在节点规模较大、但使用节点较少的场景中，每个索引平均搜索时间将迅速增加.本文方案平均搜索时间受节点规模影响较小，在节点规模较大但使用节点较少时具有明显的优势.

2）存储开销

客户端需要为每个节点存储指纹、使用标志、删除标志，通常使用标志和删除标志仅需1 b 存储空间，则客户端需要预先为每个节点分配n+2比特存储空间，其中n为每个节点指纹宽度.

服务器中需要存储索引密文和节点位置信息，相比Aura 中密文大小为索引密文大小的整数倍，不会导致密文规模扩张，存储空间占用更低，如表2 所示.

Table 2 Scheme Comparison表2 方案对比

3）通信开销

本文方案采用文献[22]的节点压缩算法对传输节点进行压缩，但与Aura 删除前仅需传输单个节点信息不同，由于每次选择节点位置是随机的，在插入文档索引较少时，节点压缩率也较低，随着使用节点数量增多，传输节点数量将逐步降低.

在删除索引时，Aura 由于中间使用的索引位置被删除，通常需要发送更多的节点.

4）安全性

本文方案通过在服务器端增加EDBcache保存上次查询结果，并在每次查询后更新查询密钥，以保护数据访问特征.下面通过真实游戏Real和理想游戏Idea对方案安全性进行证明.

RealΣA(k).攻 击 者 A选 择 数 据 库DB，DO 运 行S etup(DB)算法生成检索索引EDB并发送给攻击者.A按一定规则选择一系列查询q， DO 运行Trapdoor(q)算法生成的 Tq并发送给 A.服务器运行Search(EDB,将运行的所有结果发送给A.最后， A输出一个比特b.

IdeaΣA,S.模拟器初始化查询数组q.A 选择数据库DB，DO 运行 S(L(DB))算法生成检索索引并发送给A.接着， A 按一定规则的选择查询q.模拟器记录下查询q[i]， 运行S(L(q,DB)).最后， A 输出一个比特b.

定理2.方案 Σ后向隐私自适应安全.设sp(w)为关键词w的搜索特征，TimeDB(w) 表 示关键词w有关索引（去除删除索引），DelTime(w) 表示关键词w上的删除操作的时间戳，方案 Σ的泄露函数 LBS定义为

其中：

若 Σadd为前向自适应隐私的对称可搜索加密方案，SRE 满足IND-sREV-CPA 安全，则方案 Σ为随机预言机模型下对所有多项式时间攻击者 A是TypeⅡ后向隐私自适应安全的.

证明.设多项式时间攻击者 A在模拟器S中所取得的最大优势记为AdvA,S(λ)，Gi表 示Gamei，Pr[E]表示事件E发生的概率.证明定理2的关键是针对自适应A构造一个高效的模拟器S，使得Pr[=1]-(λ)成 立，其中(λ)是可忽略的.

利用构造法，从真实游戏构造一个满足要求的高效模拟器S，进而证明定理2.

Game 0.G0为 完全按照方案 Σ运行的真实游戏，则有

Game 1.在G0基 础上，将伪随机函数F使用随机数代替，并将生成的随机数存入数组中，在下次调用时重新找出生成的随机数.在攻击者视野下，相同的输入均会获得相同的随机数.

由于伪随机函数计算上具有不可区分性，不防设使用真随机数代替函数F，对所有多项式时间攻击者B1获 得 的最 大 优 势 为(λ) ，其 中(λ)是可忽略函数.

方案 Σ中每次新加入的关键词和生成密文标签均采用随机数代替，则攻击者B1能够获得2 倍的优势，即

Game 2.在G1基 础上，将前向安全SSE 方案Σadd使用模拟器代替，同时在服务器端维护一个更新操作列表Ladd，在攻击者发出查询操作时再执行更新操作.由于 Σadd满足前向隐私，更新操作不会泄露关键词和索引的有关信息.

Ladd包 含了方案 Σ 搜索时泄露的信息，即搜索特征sp(w) 、 索引密文及对应标签、更新时间u.Ladd反映了关键词w通过方案 Σadd执行添加操作更新的历史记录，并作为方案 Σadd的模拟器的输入.针对方案 Σadd的多项式时间的攻击者Badd，存在一个模拟器，满足

其中(λ)是可忽略的.

Game 3.在G2基础上，在执行可穿刺加密操作前将已删除文档索引置为0.由于SRE 是IND-sREVCPA 安全的[22]，因此对攻击者B3存在一个高效的模拟器SSRE，满足

其中(λ)是可忽略的.

Game 4.使用更新列表获得泄露信息TimeDB和DelHist，重建索引添加列表Ladd、 使用标志A和删除标志D，并作为模拟器的输入.若假设每个文档索引只会被添1 次和删除1 次，则标签不会被重复使用，也就不必为了保证一致性而为每个密文索引存储对应的密文标签.

在G4中，仅对模拟器的工作方式进行了修改，即

为构造理想游戏的模拟器，不能直接调用关键词w，而改用查询特征sp[w] 来生成令牌信息.同时，不再保持维护更新记录的列表，而是利用搜索查询中的泄露信息TimeDB(w)，DelTime(w)重建添加列表Ladd和 节点使用标志A、 删除标志D.这样利用 LBS有关信息，构造了一个高效的模拟器S，使得

将以上多项式时间攻击者B1，Badd，B3对 方案 Σ攻击所获得的优势相加，可得

其中(λ)是可忽略的，即定理2 成立.证毕.

6 方案测试

方案性能测试所采用的软/硬件环境配置如表3所示.

Table 3 Environment Configuration of Software/Hardware for Testing表3 测试软/硬环境配置

6.1 插入点位置选择算法测试

插入点位置选择算法中，消息位置、消息指纹所使用的哈希函数均采用SpookyHash V2 算法，随机生成消息m，发生第1 次插入失败（即未找到可用节点或发生指纹冲突）时，每个搜索深度下随机生成500组索引，节点利用率 ρ的平均值随指纹宽度n和搜索深度dmax的变化关系如图3 所示.

Fig.3 The curve of node utilization rate图3 节点利用率曲线

可以看出，在n=32，dmax=100时能够保证较高的节点利用率.

6.2 搜索方案性能测试

对称加密算法采用AES，哈希算法选用计算速度较快的SpookyHash V2，伪随机数发生器采用GGM 算法实现，采用支持分布式部署的非关系数据库rocksDB 作为密文索引数据库.测试中，随机生成文档索引，利用 Σ.Update算法添加至密文索引数据库.

如表4 所示，从存储空间开销可以看出，Aura 在服务器中因需要同时存储多个密文备份，服务器占用空间开销更大.相比Aura 方案，本文方案每个密文索引不存在密文扩展，实际平均每条索引占用存储空间开销更小.在客户端，密文删除操作需要为每个节点存储一个指纹，存储客户端存储空间开销为O(b).节点实际占用空间包含了rocksDB 内部存储结构数据，方案实际占用的空间相比测试值要更小.另外，采用质量更好的指纹哈希算法，降低每个节点的指纹长度，也可进一步快速降低客户端中存储空间的大小.

Table 4 Actual Storage Overhead of Schemes表4 方案实际存储开销

由于GGM 树随着节点规模的扩大，其计算时间迅速增加，如图4 所示，本文方案通过增加节点使用列表，避免每次搜索时服务器需要生成全部穿刺密钥，大大减少在匹配节点较少时搜索的响应时间，随着匹配节点数的增多，方案平均搜索时间趋于一致.

Fig.4 The comparison of actual search time（N = 100 000）图4 实际搜索时间对比（N = 100 000）

如图5 所示，在节点规模b=60 000时，客户端运行查询算法时向服务器发送的节点个数随节点利用率 ρ的变化情况.在插入文档索引较少时，发送数据随文档索引增加而增加，当 ρ ＞0.3时，发送的节点数逐渐提高.

图6 为删除索引后查询到的匹配节点个数变化情况，可以看出本文方案不会发生误删除.图7 为删除索引时方案通信开销变化情况.从图7 可以看出，在频繁发生索引删除的DSSE 应用场景下，本文方案通信开销也随着删除节点增多而逐渐降低.

Fig.6 Search results after index deletion（b = 60 000, N =30 000）图6 删除索引后搜索结果（b = 60 000, N = 30 000）

Fig.7 Scheme communication overhead comparison after index deletion（b = 60 000, N = 30 000）图7 删除索引后方案通信开销对比（b = 60 000, N =30 000）

7 总 结

本文结合可搜索加密方案的应用场景，给出了动态对称可搜索方案的形式化描述.同时给出了SRE 更严格的正确性定义，并通过理论分析证明了避免误删除发生的条件.在设计插入点位置选择算法的基础上，构造了基于SRE 的对称可搜索加密方案.

大多数情况下，关键词的使用密钥节点数远小于未使用节点数，通过为每个关键词添加节点插入标志，记录每个关键词实际使用的节点位置信息，查询时只发送已使用节点，可以大大降低服务器恢复密钥时的时间开销.理论分析和实现结果表明，本文方案进一步优化了Aura 方案搜索效率，有效避免了节点误删除问题.然而方案需要在客户端存储更多节点信息，增加了客户端数据存储开销，同时在删除索引较少的场景下，本文方案具有更大的通信开销.下一步将在减少客户端存储开销、方案通信开销以及多客户端场景下的扩展等问题上展开进一步研究.

作者贡献声明：黄一才提出了算法思路和实验方案，并撰写了论文；郁滨提出指导意见并修改论文；李森森参与了实验方案制定及部分数据分析与整理.