基于差分隐私的多模式隐藏动态对称可搜索加密方案

云计算的流行使得外包数据存储技术得到了广泛的关注和应用，越来越多的用户将数据存储在远程云服务器中.这种方式降低了用户的存储和计算成本，但也带来了一系列隐私问题.将隐私信息明文保存在云数据库中，会让云存储提供商轻而易举获得用户信息；将数据加密后存入服务器中，虽然对内容进行了保护，但用户无法直接对远程数据进行检索；同时，即使数据进行了加密，云服务提供商也可以通过对查询进行分析，得知用户最近的搜索偏好，构建人物模型；或者得知公司最近的营业方向、业务的增长趋势，判断公司的发展情况.毫无疑问，对大数据毫无防护的存储会使隐私泄露，从而极大地影响到人身安全.

对称可搜索加密技术(symmetric searchable encryption, SSE)正是解决这一隐私问题的极好方法.它允许客户端将加密文档存储在不受信任的服务器上，使用对关键字加密编码得到的令牌(token)检索包含某个关键字的所有文档.自Song等人[1]提出首个SSE方案以来，SSE已经在许多领域得到了广泛的应用[2].初期方案基于静态设置下，即用户只能对关键字进行检索；Kamara等人[3]提出了首个动态方案，允许用户更新关键字信息，但仍只能提供抵御被动敌手攻击的安全性.Zhang等人[4]提出的文件注入攻击使人们开始重视对动态可搜索加密方案及其应满足的安全特性的研究.

动态对称可搜索加密(DSSE)不仅可以在数据保密的情况下进行搜索，而且还能够对数据提供更新(添加和删除)后对增量进行查询，并且能够破除添加操作的关联性(前向安全)，甚至删除操作的关联性(后向安全).

然而仍然存在大量泄漏使得敌手能够利用它来获取用户的私人信息，例如搜索模式(标识序列中哪些查询对应同一个关键字)、访问模式(与查询匹配的文档的标识符)、更新模式(更新历史记录)、容量模式(响应查询返回的文档个数)等.

近年来，动态对称可搜索加密方案在提高效率，功能和安全性方面取得了许多进展[5-7].然而，他们专注于搜索和访问模式，而忽略了容量这一严重的威胁，该威胁会泄漏关键字查询结果的个数，被敌手利用执行特定攻击，获取用户隐私，针对这一泄露的最有效防御方法是设计一个容量隐藏方案.

对于动态对称可搜索加密，另一个研究目标是利用泄露设计攻击，还原查询的原始信息，或者是数据存储的原始内容，就近年来已经提出了很多攻击方案[8-10]，给可搜索加密研究的安全性提出了严峻的挑战.这些攻击方案使用可搜索加密中的固有泄露，包括搜索模式、访问模式、更新模式以及容量模式，但在目前所设计的方案中，都是专注于一种访问模式进行保护，因此难以抵抗使用其他泄露构造的攻击，因此，设计一个能够隐藏多种泄露模式的安全方案是目前的难点，也是研究正在追求的方向.

针对这些问题，我们设计了一个基于差分隐私[11]的高效存储填充方案，并研究如何将其应用到多服务器框架下的动态对称可搜索加密方案中.具体来说，我们希望在实现动态更新的同时减少搜索模式、访问模式、更新模式和容量模式，实现多模式隐藏的动态可搜索加密方案.

总而言之，本文的贡献有3个方面：

1) 引入差分隐私这一安全概念，提出了新的填充方式-差分隐私填充(differential privacy padding, DPP)，并且给出了它在方案中的动态使用机制.它可以根据隐私保护要求程度对噪音量进行调节，不仅可以提供存储量更少的安全填充方案，还可以通过其隐私保护属性来保护关键字的容量信息.

2) 提出了一个基于多服务器框架的动态对称可搜索加密方案MDSSE(multi dynamic searchable symmetric encryption)，使用第三方服务器存储更新，并且使用DPP进行填充，定义了新的安全泄露DP-Update，证明了我们的方案的容量泄露在查询和更新过程中满足差分隐私安全，并且方案同时满足前向安全和后向安全性.

3) 对方案进行了攻击实验，证明方案可以抵抗容量泄露攻击，并且拥有良好的表现.

4) 对目前提出的容量泄露的保护方法进行了研究梳理，并将算法与其进行比较.结果证明我们的填充算法拥有更低的填充率.

1 相关工作

1.1 可搜索加密

可搜索加密能够使用户远程对加密数据进行检索，得到了来自学术界和工业界的广泛关注[12-15].数据所有者可以将私有数据外包给不受信任的服务器，同时有选择地检索与查询匹配的数据元素，而无需向服务器透露数据内容或搜索关键字.相比于使用公钥原语的非对称可搜索加密方案，能够提供更高效率的对称可搜索加密方案成为了我们的研究目标.

对称可搜索加密最基本的构造是对文件生成索引，将加密文件和索引外包给服务器.在查询时客户端生成关键字令牌上传给服务器，服务器通过令牌使用密码工具生成索引位置，通过索引找到与查询匹配的文件列表.在此之上，开展了一系列对于安全性、功能性以及性能方面的优化[16-17].

Kamara等人[3]提出了首个动态可搜索加密方案，除了常规的查询操作，DSSE允许在数据集中进行添加和删除.之后人们尝试使用红黑树[7]、茫然存储[18]、陷门置换[19]等进行实现.DSSE的出现丰富了SSE的研究，但是也引入了新的泄露，敌手通过利用泄露进行攻击破坏数据隐私性.为了准确刻画方案中出现的泄露以及方案能够达到的安全性，对前向安全与后向安全的形式化定义进行了深入研究.

1.2 前向与后向安全

前向安全与后向安全的概念，首先由Stefanov等人[20]提出，之后由Bost等人[21]将概念形式化.自此，人们开始对具有这2种性质的方案展开了广泛的研究[22-27].

前向安全(forward privacy, FP)能够保证服务器不会得知新添加进数据库的文档是否包含之前查询过的关键字.Mohammad等人[6]使用ORAM将查询索引进行外包；Bost等人[19]使用单向陷门置换生成搜索令牌链使得没有私钥的服务器无法正向计算出新的搜索令牌.Song等人[27]将其方案中冗余的公钥原语替换成伪随机置换，使用对称密码原语实现了更优的计算和通信效率.

后向安全(backward privacy, BP)是指更新和接下来的查询都无法泄露关于删除文档的信息.后向安全根据安全强度分为3类:1)后向安全(BP-Ⅰ)泄露最近匹配关键字的文档、插入文档的时间以及关键字的更新个数；2)BP-Ⅱ在前面的基础上泄露关于关键字更新的时间和类型；3)BP-Ⅲ又泄露对于每一个删除操作对应的插入操作.Bost等人[21]首先提出了一系列构造：基于Sophos的BP-Ⅱ安全方案Fides,使用TWORAM的BP-Ⅰ方案Moneta；以及基于可穿刺加密的BP-Ⅲ方案Janus.Demertzis等人[28]提出了3个客户端存储的方案SDa和SDd以及QOS，将茫然映射作为数据结构的同时减少客户端存储.

1.3 泄露与攻击

即使在可搜索加密协议中数据库和检索请求都是保密的，服务器仍然能得到某些泄露信息.首先，如果对于相同关键字每次生成的令牌是确定性的，那么服务器会发现多次搜索可能对应同一个关键字.这就是所谓的搜索模式(search pattern, SP)[29]泄漏.有些方案会在查询时泄露关键字所匹配的文档列表，这就是所谓的访问模式(access pattern, AP)泄漏.更新时间、长度甚至是更新内容的泄露对应的就是更新模式(update pattern, UP)泄露.对于泄露的研究表明可以利用这些泄露函数对查询和文件信息进行攻击.

计数攻击(count attack)[30]的提出使容量泄露(volume pattern, VP)成为研究关注的焦点，关键字容量是指关键字搜索返回的结果数量，计数攻击可以通过每次查询返回的文档数量推测是否请求了相同的关键字.对于他的防御方式，最朴素的想法就是通过使用填充.将所有关键字都填充到最大的容量，这样无疑是最安全的做法，但是消耗了大量的存储和通信.Demertzis等人[31]提出了一种特殊的群填充方案，将每个关键字的长度都填充到与当前容量最近的x的指数次方.Kamara等人[32]首先使用伪随机置换为关键字生成新长度，这减少了存储负载但是产生了截断；之后使用稠密子图置换重新排列关键字进行填充，这个方案消灭了截断，但需要额外存储映射表和字典以保证搜索的正确性.Patel等人[33]中使用差分隐私生成拉普拉斯噪音对容量进行填充，但是仅应用于静态设置下.方案受此启发，设计了能够适应动态设置下的查询与更新操作的填充方法DPP，能够在保证安全效果的前提下提供更好的存储效率.

2 预备知识

2.1 动态可搜索加密技术

动态可搜索加密方案由3个协议构成：

1) (K,σ,ED)←Setup(λ,D).初始化阶段用于生成密钥、构造加密数据集.用户输入安全参数λ和数据集D，输出密钥K，关键字状态σ、以及加密数据集ED，将ED发送到服务器端存储.

2) (σ′,D(w),ED′)←Search(K,σ,w,ED).查询阶段用于搜索关键字对应的数据集，这里我们的查询是单关键字查询.用户输入密钥K、查询的关键字w及其状态σ，服务器输入加密数据集ED，输出关键字对应的数据集D(w).在查询过后关键字的状态和加密数据集有可能会发生改变，用σ′和ED′表示.

3) (σ′,ED′)←Update(K,σ,ind,w,op,ED).更新阶段用于对数据集进行插入/删除操作.用户输入密钥K，关键字状态σ、关键字w、加密数据集ED及其对应的文档标识符(w,ind)，以及进行的操作op=添加/删除.更新后关键字状态和数据集会发生改变，用σ′和ED′表示.

2.2 差分隐私

定义1. 差分隐私.给定相邻数据集D和D′，两者至多相差一条记录，即

给定一个隐私算法M:Xn→Y，Y的任意子集T，若算法M在数据集D和D′上输出的结果满足不等式：

则称算法M满足ε-差分隐私.其中ε是隐私预算，表示算法隐私保护的程度，参数越小，隐私保护的程度越高.

方案使用拉普拉斯机制实现算法的差分隐私保护.在介绍拉普拉斯机制之前，首先介绍函数敏感度概念以及拉普拉斯分布的密度函数：

定义2. 全局敏感度.设函数f:D→R，那么f的L1敏感度为：

其中D和D′为相邻数据集，R为查询结果.

对于位置与规模参数分别为μ与q的拉普拉斯分布，定义其密度函数：

基于定义2，给出拉普拉斯机制的定义：

定义3. 拉普拉斯机制.设函数f:Nn→Rk则拉普拉斯机制满足M(X)=f(X)+(Y1,Y2,…,Yk)，其中Yi是满足拉普拉斯分布为Laplace(Δ/ε)的随机变量.

2.3 泄露函数与前后向安全

针对方案所涉及的泄露函数，我们给出其形式化定义4：

定义4. 泄露模式安全定义.泄露函数为查询列表保持查询时的状态，定义了用户在进行关键字查询时可以被服务器获取的信息，包括搜索模式、更新模式、容量模式，分别表示为sp(w),up(w),vp(w)，定义为：

sp(w)={i:(i,w)∈Q}, up(w)={i:(i,op,in)∈Q and w appears in inw}, vp(w)={|i|:(i,w)∈Q},

其中,i为时间戳，初始时设置为0，在每次查询时自增，Q为查询集合，op为更新操作、in为更新时的输入.

定义5. 前向安全.称一个

自适应安全的DSSE方案是前向安全的，如果更新泄露可被定义为

其中ind为文档标识符，μ为文档中所更改的关键字个数.

我们提出的DSSE方案满足BP-Ⅱ后向安全，在BP-Ⅱ后向安全方案中，搜索和更新操作中的泄露可被定义为：

其中,TimeDB(w)表示目前所有匹配关键字w的文档标识符集合以及它们被插入的时间点，不包含被删除的标识符；Updates(w)是关于关键字w的一系列更新时间戳.

2.4 可搜索加密安全定义

方案使用理想/真实世界模拟定义可搜索加密方案的安全性.Real实验中敌手攻击的是真实方案，Ideal实验中敌手攻击的是模拟器通过泄露模拟的环境，如果敌手无法区别真实世界与模拟世界，那么说明无法获得除了定义以外的其他泄露.我们将DSSE方案中的泄露函数定义为Lsetup,Lsearch以及Lupdate，分别表示方案在初始化、查询及更新时产生的泄露，敌手输出1表示判断自己与真实世界交互.具体游戏的定义为：

Real.敌手产生数据集D，将其发送给挑战者.挑战者执行初始化操作后生成加密数据集ED返回给敌手.敌手可以自适应的选择多项式个请求对挑战者进行挑战.如果是查询请求，挑战者调用产生返回结果；如果是更新请求，挑战者调用产生返回结果.最后敌手输出字符b∈{0,1}.

Ideal.敌手产生数据集D，将其发送给模拟器.模拟器根据Lsetup生成加密数据集ED返回给敌手.敌手可以自适应的选择多项式个请求对模拟器进行挑战.如果是查询请求，模拟器根据Lsearch生成查询结果，如果是更新请求，模拟器根据Lupdate进行更新.最后敌手输出字符b∈{0,1}.

定义

自适应安全.如果对于所有多项式时间的敌手

存在一个高效的模拟器S，使得:

那么称方案Σ满足

自适应安全.

2.5 差分隐私的容量泄露

本文使用文献[32]中基于游戏的定义，来定义泄露函数的容量隐藏性，便于后面理解，我们将游戏所需概念和定义进行介绍：

首先将2个相邻数据库D0，D1抽象成(关键字，关键字容量)对，作为2个数据库的标识Sign：

其中,l0(key)表示关键字key在D0中的容量，l1(key)表示关键字key在D1中的容量.

对于所有key∉{key0,key1}，l0(key)=l1(key)，

相邻数据库仅有一个关键字不同，D0中独有的关键字为key0，D1中独有的关键字为key1,他们在查询时的容量相差为d.

接下来定义游戏DPGAME0和DPGAME1，其中η∈{0,1}.

定义7. DPGAME(η)：

1) 敌手按照定义，生成2个数据库标识Sign0和Sign1，发送给挑战者.

2) 挑战者接收到2个标识，选取其中一个Signη进行差分隐私处理，将处理过后的标识记作San(η)

3) 挑战者根据San(η)为关键字生成对应数量的文档标识符，然后将初始化时产生的泄露发送给敌手.

4) 敌手适应性选择关键字进行询问，对于每个关键字，挑战者将对应的查询泄露发送给敌手.

5) 敌手输出b，判断查询来自哪个数据库.

将敌手在游戏中猜测成功的概率记为Pr，由此可以得到安全性定义8：

定义8. ε-差分隐私容量隐藏.令

是方案中由于容量差异产生的泄露，则

满足ε-差分隐私容量隐藏性，如果所有的敌手

在对于2个相邻标识进行输出时的概率满足条件为

3 本文提出的方案表示

3.1 参数表示与安全定义

令数据集表示为

其中n为关键字个数，{ind}i表示包含关键字Wi的文档标识符集合.关键字Wi与文档标识ind使用倒排索引(inverted index)形式进行存储，即每个关键字对应一系列文档标识符，这些标识符所对应的文档中都包含Wi.关键字Wi的状态σ保存在客户端本地存储的映射表

中，它存放了与令牌生成相关的关键字状态信息，包括数据所存放的服务器位置b∈{0,1}，关键字目前的搜索次数sw，初始化填充后的长度dlw以及更新填充长度dpw.

为了便于描述算法，我们在表1中给出所使用符号的整体说明.

3.2 方案框架

本文方案的系统框架由2种实体组成，分别是可信的客户端以及不可信的服务器端，服务器端包括用于初始化存储的存储服务器S0,S1以及用于隔离更新的更新服务器Sup，目的是将存储和更新隔离放置，阻断针对同一个关键字搜索和更新请求的关联关系，同时在2个服务器之间挪移数据隐藏搜索模式.

客户端首先在本地将数据集分割成2部分，分别放置到S0和S1上，并将关键字的存储位置b∈{0,1}保存在本地关键字的状态集σ中.当客户端对数据进行更新时，先在本地将更新进行差分隐私填充，之后上传到更新服务器Sup.进行查询时，客户端在本地生成关键字陷门，同时向存储服务器Sb和更新服务器Sup发送查询陷门和文档个数，服务器端根据接收参数生成索引位置，返回索引处存放的数据.

客户端接收到查询返回的数据后，在本地进行解密，丢弃填充的虚拟标识符后将有效标识符进行聚合.将聚合后的数据进行差分隐私填充后放置到存储服务器Sb⊕1上.

我们使用2种方式用于切断不同请求之间的关联关系，首先是使用DPP填充关键字容量，每次搜索请求返回时都使用随机生成的噪音填充.由于噪音的生成与关键字容量独立，提供的随机性能够隐藏关键字的真实容量，敌手无法通过返回的关键字数量对查询进行匹配，保护了关键字的容量模式.其次是在令牌生成时，我们为关键字维护一个搜索次数状态sw，每次搜索完成后数量加以保存，使用新的sw为关键字生成新的搜索令牌.这样做可以保证每次搜索时关键字对应的令牌不同，切断了令牌链接性，减少了搜索模式产生的泄露.

3.3 Differential Privacy Padding(DPP)算法

在处理生成加密数据库之前，客户端将首先对原始数据执行差分隐私填充算法，为原始容量生成服从拉普拉斯分布的噪音，具体DPP算法如下：

输入：隐私预算ε1、均值μ、敏感度d、关键字集合W;

输出：填充后的数据集DPDB.

① ε=ε1,Δf=d,q=Δf/ε;

② for each keyword w in W in parallel:

③ noise(w)=Lap(q);

④ dlw=lw+Ceiling(noise(w));

首先，客户选择隐私预算ε，为每个关键字添加符合拉普拉斯分布的噪音，然后使用Ceiling函数返回一个整数噪音值，填充到原始数据中.这里的填充是对关键字返回的文档个数添加噪音，举例来说，关键字w1所对应的文档个数为10，添加数值型噪音后长度变为12，w1相对应需要各自增加2个虚拟标识符和无效文档.为了区分虚拟标识符与有效标识符，使得客户端在获取搜索结果时过滤虚拟标识符，我们将所有文档标识符的第1位设置为标志位，无效文档内容为全0.

3.4 方案详细描述

方案的主要思想是利用三台服务器与差分隐私填充方案相结合，以提供可调节的SSE泄漏.在将可搜索索引外包给服务器之前，客户端将在数据库DB上应用DPP算法以获取其填充版本DPDB.然后，客户端像普通的SSE方案一样对填充的索引进行加密，并外包给服务器.

在以下伪代码中，我们使用伪随机函数F，带密钥的哈希函数H生成协议期间所需的令牌，哈希函数h和MDSSE.Enc和MDSSE.Dec表示语义安全对称加密方案的加密和解密算法.

首先初始化需要远程存储的数据集，之后描述服务器上执行的查询与更新操作.为了简化操作，我们将文档使用文档标识符进行代替，即加密数据集存储文档标识符.

算法2. MDSSE.Setup().

输入：安全参数λ，数据集DB;

输出：密钥K、关键字状态σ、加密数据集DPDB.

① ks,ku←{0,1}λ,Σ,EDB0,EDB1初始化为空的映射表;

② DPDBb←DPP(ε1,μ,d,DB);

④ dlw,sw,dpw←0,b←{0,1};

⑤ tw←F(ks,h(w)‖sw‖b);

⑥ for ind∈DPDBb(w) do

⑧ v←MDSSE.Enc(ku,ind);

⑨ dlw←dlw+1,DPDBb[e]←v;

将状态(b,sw,dlw,dpw)存入映射表中;

初始化算法的具体描述为：

首先客户端产生2个密钥ks,ku.ks从PRF的密钥空间中选择，ku用于加密文档标识符.选取隐私预算ε，使用DPP算法对原始数据进行填充，得到填充数据库DPDB.对于每个关键字w，随机选取存放的服务器位置b，查询次数sw初始置为0.我们将ks与h(w)‖sw作为伪随机函数F的输入，生成关键字w的令牌tw，使用令牌为关键字w的每一个标识符生成索引e，指示标识符的存放位置，然后加密文档标识符，存放入存储服务器Sb中.

算法3. MDSSE.Update().

输入：关键字w、更新列表UDB(w)；

输出：填充后的加密数据集DPDBup(w).

① DPDBup(w)←DPP(ε2,μ,d,UDB(w))

/*随机选择隐私预算*/

② for w in DPDBup do

③ 从映射表中取出w的状态信息(sw,dpw);

④ tp←F(ks,h(w)‖sw‖2);

⑥ v←MDSSE.Enc(ku,op‖ind);

更新算法的具体描述为：

当需要对关键字进行更新时，随机选择隐私预算生成噪音添加到原始数据中.接下来为填充后的标识符生成索引位置e.从关键字的状态表中取出状态信息sw,dpw，其中dpw表示关键字2次搜索间的更新个数，每更新1次加1，在每次查询后置0.使用状态信息为关键字产生更新令牌tp，为更新标识符生成索引、进行加密.加密关键字的同时需要绑定对关键字进行的操作(增加或者删除).最后将关键字的更新DPDBup(w)存入更新服务器.

需要注意的是，在生成更新令牌时使用sw而不是dpw，因为dpw在每次查询后都会被置零，所以每次对于同一个关键字的更新会被放到相同位置上，泄露关键字的更新次数.在生成索引时使用的是dpw，因为在关键字的2次搜索之间，sw并没有改变从而会产生位置冲突.因此在2次搜索间的所有更新，我们都可以使用相同的更新令牌进行查询，2次查询之间的更新个数由dpw维持.

算法4. MDSSE.Search().

输入：查询令牌kw、kp，关键字长度dlw、dpw，查询列表SDB(w);

输出：查询结果EM.

步骤1)客户端发送查询令牌

① 从映射表中取出w的状态(b,sw,dlw,dpw)

② for w in SDB(w) do

③ tw←F(ks,h(w)‖sw‖b)；

④ tp←F(ks,h(w)‖sw‖2)；

⑥ 将(tw,dlw)发送到Sb，(tp,dpw)发送到Sup

步骤2)服务器进行检索

① for i←0 to dlwdo

③ R←R∪{EDBb[e]}； /*R为存储服务器端存放查询结果的集合*/

⑤ 将R发送回客户端，从服务器端删掉R

① for i←0 to dpwdo

③ P←P∪{EDBup[e]}；

⑤ 将P发送回客户端，从服务器端删掉P

步骤3)客户端筛选并重新加密数据

① D,EM←{} /*存放下载的关键字文档*/

② for C∈R∪P do：

③ (op,ind)←MDSSE.Dec(ku,c)；

④ if op=“add” ∧ ind is valid then

⑤ D←D∪{ind}；

⑥ else D←D-{ind}；

⑨ DPDBb⊕1←DPP(ε1,μ,d,D)；

⑩ for ind∈DPDBb⊕1 do

e←H(ks,h(w)‖sw+1‖b⊕1)；

v←MDSSE.Enc(ku,“add”‖ind)；

将(b⊕1,sw+1,|DPDBb⊕1|)存入映射表中.

搜索算法描述为：

给定一个关键字w,去关键字状态表中拿出参数b,sw,dlw，使用sw级联与h(w)作为输入，嵌入带密钥的PRF中生成查询令牌kw，将生成的查询令牌tw和差分长度dlw一起送往Sb.更新服务器同理.

2个服务器各自根据传递过来的参数生成查询的索引e，去对应的位置取出密文放入P/R，其中P/R分别为存储/更新服务器存放文档标识符的集合，之后将集合返回，将存储在服务器端的密文删除.

客户端接收加密数据集后开始解密，根据解密后操作符op对应的是增加还是删除判断是否将其放入新的数据集EM中还是删除，同时丢弃填充的虚拟标识符.将解密后的数据进行汇总再次使用DPP算法进行填充得到新的DPDBb⊕1(w)，将其存入Sb+1中.

4 本文提出的方案分析

4.1 复杂度分析

在我们的方案中，客户端需要存储关键字的状态信息，因此其客户端存储开销为O(|w|)，其中|w|表示关键字的数量.

服务器存储开销为O(n×l+nw×μ)，其中n表示关键字的个数，l表示所有关键字对应的平均文档个数，nw表示关键字的数量，μ表示噪音的期望值.

在搜索和更新过程中，计算复杂度分别为O(dpnw)和O(1)，其中O(dpnw)是差分隐私保护了匹配关键字w之后搜索结果集的大小.通信复杂度分别为O(dpnw)和O(1).

4.2 容量泄露分析

首先证明方案的查询更新操作同时满足了差分隐私容量隐藏安全(下文简称差分隐藏).

关于查询，假设第k个查询开始查询到2个数据库中不一样的关键字.

关于更新，我们也可以证明它是差分隐藏的.服务器上的更新，可以看作每个关键字、每次更新的累计和.对于每次更新，根据更新数量的不同选用不同的ε，一个关键字在2次查询期间所产生的噪音，由差分隐私的组合定理可以得到Mup(X)=Lap(ε1)+Lap(ε2)+…+Lap(εn)，那么Mup(X)满足

DP.对于整个更新服务器，由差分隐私的平行定理可以得到Mup(S2)=max(Mup(X1),Mup(X2),…,Mup(Xn))，其中n为更新服务器上所存在的关键字数量，即ε-DP.

关于搜索模式，方案也进行了差分隐藏.搜索模式一般用于对2次查询进行匹配，在令牌层面，随着查询次数与服务器位置的变化，关键字查询令牌也随之改变，切断了令牌之间的关联性，此时唯一可能泄露搜索模式的信息来自查询结果长度.由于关键字的长度使用DPP算法进行填充，并且在每次搜索后为关键字赋予一个新噪声，这使得服务器也无法通过2次查询返回的长度判断是否是同一个关键字，实现了差分隐私的容量隐藏.因此本方案搜索模式的泄露也是差分隐私的，并且只额外泄露了关键字存放的服务器位置b.

4.3 安全性分析

MDSSE不仅提供了动态可搜索加密方案满足的前向安全与后向安全性，而且消除了更新泄露，提供了差分隐私安全的容量泄露，实现了搜索泄露的差分隐私隐藏，具有更加强大的安全特性.

在对方案的安全性进行证明之前，需要对之前的更新历史定义进行改造，使其适应提出的方案.基于此，我们引入了一个新的安全定义，称为差分隐私部分更新(Differential Privacy Partial Update, DP-Update).假设现在产生了一系列更新：(add,w1,ind1),(del,w1,ind1),(add,w1,ind3),(search,w1),(add,w1,ind4),(add,w1,dummy),search(w1)，其中dummy为差分隐私后对文档标识符进行的补充.在时刻4和时刻7之间的差分更新历史泄露为DP-Update(w1)={5，6}，并且更新长度是经过差分之后的，并不代表准确的更新次数.

定理1证明了MDSSE的自适应安全性.

定理1. 给定伪随机函数F，哈希函数实例化随机语言机H，CPA安全的对称加密方案Enc，如果泄露函数

满足定义：

其中，|indi|表示与关键字相关标识符的个数，则可以证明MDSSE是一个只泄露

并且满足前向安全和后向安全的方案.

G0.我们将G0定义为真实世界中的实验Real.

G1.G1中不再使用伪随机函数F生成令牌，而是使用随机数代替，并将生成的随机数与关键字存放在定义为Token的数组中.由于伪随机函数和真随机函数的不可区分性，可知2个实验是不可区分的.

G2.G2中使用随机字符串而不是调用哈希函数为关键字生成标识符，并将其存在映射表H中.

G3.G3中将原先使用语义安全对称密钥加密方案生成的密文替换为相同长度的随机字符串.由于加密方案的语义安全性，我们无法区分G2和G3.

G4.G4中不再保存关键字的状态，而是将其输入随机预言机得到输出，而是在搜索时随机生成；在更新时使用数组U保存上次查询之后的更新请求.由于更新时真随机串与伪随机串的不可区分性，无法区分G3和G4.

Simulator.在理想世界中，模拟器需要通过泄露函数来生成敌手所需要的视图.初始化时，模拟器根据泄露长度随机生成DPNDb对随机字符串上传到服务器Sb.在搜索时，由于涉及2个服务器，需要各自为他们分配模拟器Simb以及Simb⊕1，用来模拟的各自视图，由于2个服务器是非共谋的，他们可以独立完成模拟而不进行协同.

Simb⊕1生成|DPDB(w)|个随机对上传至服务器.对于Simb，客户端使用泄露函数获取关键字长度，随机生成kw后一起发送给服务器端.在进行返回时，模拟器从泄露中取出DP-Update(w)，如果内容为空，说明之前从未被搜索过，那么随机选择|DPDB(w)|个随机对；如果之前搜索过，根据泄露中的时间戳确定返回结果，对随机语言机进行编程，使未来的搜索结果相匹配.

算法5. 模拟算法.

步骤1)初始化模拟算法：

① 初始化映射表EDB将其置为空;

③ for i←0 to DPNDb-1 do

④ e←{0,1}l,v←{0,1}|v|;

步骤2)查询模拟算法：

② kw←{0,1}l,uw←|DPDB(w)|;

③ 将kw，uw发送到服务器端

① (sp(w),TimeDB(w),DP-Update(w))

② e←{0,1}l,v←{0,1}|v|;

④ if DP-Update(w) is null then

⑤ 从EDBb中随机选取|DPDB(w)|项，将其放入数组E中;

⑥ else从数组E中取出DP-Update(w)时产生的更新;

⑧ for i←0 to H(kw,i)←E[i] do

⑨ 使用编程RO：H(kw,i)←E[i] ;

服务器Sb⊕1端：

接受从客户端发来的EDB并保存.其中EDB是|DPDB(w)|对随机字符串.

步骤3)更新模拟算法：

② for i←0 to {ind}i| do

③ e←{0,1}l,v←{0,1}|v|;

5 实验分析

本节首先列举出目前常用的3种填充方案，之后在相同的攻击效果下将3种填充方式所需要的额外存储进行对比，实验证明我们的填充方式能够在相同的安全效果下使用更少的存储.之后将我们的方案与其他使用差分隐私但实现方法不同的方案进行性能上的比较.最后我们从采取另一种方法的方案中选择了在各方面表现效果良好的CLRZ[34]方案进行对比.

我们选用的3种填充方式分别为普通填充(将每个关键字长度都填充到最大长度)、可调节填充(每个关键字长度都填充到离他最近的指数的幂)以及差分隐私填充(为关键字生成服从拉普拉斯分布的噪音).在可调节填充中我们将所有关键字填充到2的幂次，差分隐私填充中选择的隐私预算和均值分别为1与3.实验结果如表2所示：

我们将这3种填充方式在不同数据规模下的全部数据与真实数据之比进行计算.比率越大，说明填充方法所需要的虚拟标识越多.表格显示，普通的填充虽然最安全，但是所需要的存储与数据规模呈线性增长.可调节填充与差分隐私填充各有优势，可调节填充根据底数的选取将关键字分组，保护组内关键字的安全性，因此保护效果更好，所需要的填充也更多.差分隐私保护关键字查询敏感度内相邻的关键字，因此填充的数量更少.可以注意到DPP也可以通过对参数进行修改达到可调节的目的.

截至目前，使用差分隐私实现容量隐藏的方案可分为2种：1)使用拉普拉斯机制为关键字生成噪音补充道原始的容量中，文献[32]和本方案使用了这一方法.2)将访问模式表示成关于查询与文档标识的矩阵，元素为1表示文档与查询相匹配.通过对矩阵中元素的随机反转生成混淆的访问模式进行保护，文献[34-35]均使用这一方法.我们将这4种方案的性能与安全性方面进行对比，结果如表3所示，我们的方案能够在动态更新的同时提供更高的安全保障.

下面将方案与CLRZ进行比较：首先从功能性上进行分析.CLRZ基于静态设置，使用比特翻转制造混淆访问模式，但他在使用的过程中引入了p(将包含关键字的文档判断为不包含的比率)与r(将不包含关键字的文档判断为包含的比率)，而p将会导致本应该返回的文档标识符被过滤，降低了搜索的完整性与准确性.我们为原始长度添加噪音，增加了不包含关键字但仍然能被返回的几率，并且我们的方案支持动态的更新操作.

接下来对性能进行分析.我们使用Python语言对算法进行实现，运行环境为Ubuntu18.04配置在Intel® CoreTM i7-10700 CPU@2.90 GHz,16 GB内存中.使用Enron email dataset作为数据集，使用文献[35]中的技巧对关键字进行提取处理.每个实验结果均为实验重复100次后取平均值得到.

我们将本方案(MDSSE)与CLRZ同时进行计数攻击，测试方案在攻击下的防御程度.测试结果如图1所示，实验表明在引入噪音后，MDSSE对攻击的防御性能有了明显的提升，这里的噪音量是对整个数据库添加，原始数据长度为1 378 473.由于CLRZ使用r添加噪音，因此我们将r换算成噪音量绘制了此图.实验证明在添加的噪音增大时，我们的方案攻击准确率下降显著.

在对不同容量的关键字进行搜索时间统计后，结果如图2所示.为了简化实验操作，减少实际文件检索带来的干扰，我们使用文件标识符来代替文件进行搜索.随着搜索数量的增加，初始化生成索引的时间被平摊到后面每一个搜索结果中，因此，搜索结果数量越多，单个文档的平均搜索时间越少，有利于搜索效率的提升.

6 总结与未来展望

本文针对可搜索加密中一个重要的泄露模式-容量泄露进行了讨论，并提出了改进的填充模式，在节约内存的情况下保证了安全性，之后将其部署在动态环境中，提出了一个新的DSSE方案MDSSE.我们的方案在提供更新的同时保证了前向安全和后向安全.最后我们给出了方案的安全性证明，并对其进行了性能评估，证明我们的方案能够在保证安全性的情况下具有更好的存储和效率.

需要注意的是，MDSSE支持单用户的对称加密搜索与更新操作，下一步我们打算将其推广到多用户搜索模式下，并且压缩由此产生的额外的查询泄露，应用到更加广泛的场景之中的同时保证安全性.

[1]Song D X, Wagner D, Perrig A. Practical techniques for searches on encrypted data[C] //Proc of 2000 IEEE Symp on Security and Privacy. Piscataway, NJ: IEEE, 2000: 44-55

[2]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

[3]Kamara S, Papamanthou C, Roeder T. Dynamic searchable symmetric encryption[C] //Proc of the 2012 ACM Conf on Computer and Communications Security. New York: ACM, 2012: 965-976

[4]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 Association, 2016: 707-720

[5]Cash D, Jaeger J, Jarecki S, et al. Dynamic searchable encryption in very-large databases: Data structures and implementation[C] //Proc of Annual Network and Distributed System Security Symp. San Diego: The Internet Society, 2014, 14: 23-26

[6]Etemad M, Küpçü A, Papamanthou C, et al. Efficient dynamic searchable encryption with forward privacy[J]. Proceedings on Privacy Enhancing Technologies, 2018, 1(2018): 5-20

[7]Kamara S, Papamanthou C. Parallel and dynamic searchable symmetric encryption[C] //Proc of Int Conf on Financial Cryptography and Data Security. Berlin: Springer, 2013: 258-274

[8]Blackstone L, Kamara S, Moataz T. Revisiting leakage abuse attacks[C] //Proc of Annual Network and Distributed System Security Symp. San Diego: The Internet Society, 2020: 1- 20

[9]Islam M S, Kuzu M, Kantarcioglu M. Access pattern disclosure on searchable encryption: Ramification, attack and mitigation[C] //Proc of Annual Network and Distributed System Security Symp. San Diego: The Internet Society, 2012: 12-20

[10]Pouliot D, Wright C V. The shadow nemesis: Inference attacks on efficiently deployable, efficiently searchable encryption[C] //Proc of the 2016 ACM SIGSAC Conf on Computer and Communications Security. New York: ACM, 2016: 1341-1352

[11]Dwork C. Differential privacy: A survey of results[C] //Proc of Int Conf on Theory and Applications of Models of Computation. Berlin: Springer, 2008: 1-19

[12]Song Xiangfu, Yin Dong, Jiang Han, et al. Searchable symmetric encryption with tunable leakage using multiple servers[C] //Proc of Int Conf on Database Systems for Advanced Applications. Berlin: Springer, 2020: 157-177

[13]Chang Y, 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

[14]Chase M, Kamara S. Structured encryption and controlled disclosure[C] //Proc of Int Conf on the Theory and Application of Cryptology and Information Security. Berlin: Springer, 2010: 577-594

[15]Bost R, Fouque P A. Security-efficiency tradeoffs in searchable encryption[J]. Proceedings on Privacy Enhancing Technologies, 2019, 2019(4): 132-151

[16]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)

[17]Li Zhen, Jiang Han, Zhao Minghao. A discretionary searchable encryption scheme in multi-user settings[J]. Journal of Computer Research and Development, 2015, 52(10): 2313-2322 (in Chinese)(李真, 蒋瀚, 赵明昊. 一个自主授权的多用户可搜索加密方案[J]. 计算机研究与发展, 2015, 52(10): 2313-2322)

[18]Naveed M, Prabhakaran M, Gunter C A. Dynamic searchable encryption via blind storage[C] //Proc of 2014 IEEE Symp on Security and Privacy. Piscataway, NJ: IEEE, 2014: 639-654

[19]Bost R. ∑ oφo width=5,height=8,dpi=110

: Forward secure searchable encryption[C] //Proc of the 2016 ACM SIGSAC Conf on Computer and Communications Security. New York: ACM, 2016: 1143-1154

[20]Stefanov E, Papamanthou C, Shi E. Practical dynamic searchable encryption with small leakage[C] //Proc of Annual Network and Distributed System Security Symp. San Diego: The Internet Society, 2014: 72-75

[21]Bost R, Minaud B, Ohrimenko O. Forward and backward private searchable encryption from constrained cryptographic primitives[C] //Proc of the 2017 ACM SIGSAC Confon Computer and Communications Security. New York: ACM, 2017: 1465-1482

[22]Li Jin, Huang Yanyu, Wei Yu, et al. Searchable symmetric encryption with forward search privacy[J]. IEEE Transactions on Dependable and Secure Computing, 2019, 18(1): 460-474

[23]Li Hongwei, Yang Yi, Dai Yuanshun, et al. Achieving secure and efficient dynamic searchable symmetric encryption over medical cloud data[J]. IEEE Transactions on Cloud Computing, 2017, 8(2): 484-494

[24]Ghareh Chamani J, Papadopoulos D, Papamanthou C, et al. New constructions for forward and backward private symmetric searchable encryption[C] //Proc of the 2018 ACM SIGSAC Conf on Computer and Communications Security. New York: ACM, 2018: 1038-1055

[25]Cui Shujie, Song Xiangfu, Asghar M R, et al. Privacy-preserving searchable databases with controllable leakage[J]. arXiv preprint arXiv:1909.11624, 2019

[26]Zuo Cong, Sun Shi Feng, 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

[27]Song Xiangfu, Dong Changyu, Yuan Dandan, et al. Forward private searchable symmetric encryption with optimized I/O efficiency[J]. IEEE Transactions on Dependable and Secure Computing, 2018, 17(5): 912-927

[28]Demertzis I, Chamani J G, Papadopoulos D, et al. Dynamic searchable encryption with small client storage[C] //Proc of Annual Network and Distributed System Security Symp. San Diego: The Internet Society, 2020: 1-20

[29]Oya S, Kerschbaum F. Hiding the access pattern is not enough: Exploiting search pattern leakage in searchable encryption[C] //Proc of the 30th USENIX Security Symp(Security 21). Berkeley, CA: USENIX Association, 2021: 1-16

[30]Cash D, Grubbs P, Perry J, et al. Leakage-abuse attacks against searchable encryption[C] //Proc of the 22nd ACM SIGSAC Conf on Computer and Communications Security. New York: ACM, 2015: 668-679

[31]Demertzis I, Papadopoulos D, Papamanthou C, et al. {SEAL}: Attack mitigation for encrypted databases via adjustable leakage[C] //Proc of the 29th USENIX Security Symp(Security 20). Berkeley, CA: USENIX Association, 2020: 2433-2450

[32]Kamara S, Moataz T. Computationally volume-hiding structured encryption[C] //Proc of Annual Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2019: 183-213

[33]Patel S, Persiano G, Yeo K, et al. Mitigating leakage in secure cloud-hosted data structures: Volume-hiding for multi-maps via hashing[C] //Proc of the 2019 ACM SIGSAC Conf on Computer and Communications Security. New York: ACM, 2019: 79-93

[34]Chen Guoxing, Lai T H, Reiter M K, et al. Differentially private access patterns for searchable symmetric encryption[C] //Proc of IEEE Conf on Computer Communications. Piscataway, NJ: IEEE, 2018: 810-818

[35]Shang Zhiwei, Oya S, Peter A, et al. Obfuscated access and search patterns in searchable encryption[J]. arXiv preprint arXiv:2102.09651, 2021