一种支持联合搜索的多用户动态对称可搜索加密方案

张蓝蓝 曹卫东 王怀超

(中国民航大学计算机科学与技术学院 天津 300300)

随着云计算技术的发展，越来越多的公司和个人会将自己的数据存储到第三方服务器.这样服务器就具有完全访问客户端数据的权限(如数据库查询)，并且会按照客户端的指示将数据的一部分以明文形式显示出来.当客户端的数据包含高度敏感的信息(例如生物医学记录)且服务器不完全可信时，就会暴露出许多隐私问题.

可搜索加密因其能够以密文形式查询数据而一直备受关注.理想情况下，客户端在查询加密数据时可以不向服务器透露任何敏感信息.不过目前只有完全同态加密可能实现这种构想，但由于其性能开销大，不适合实际部署[1-2].对称可搜索加密(symmetric searchable encryption, SSE)[3]是基于对称加密算法设计的一种计算效率高、安全性相对较好的可搜索加密方案，它的目标是在尽可能减少敏感信息泄露的情况下通过查询关键词与文档间的索引来查找加密文档.

与SSE相关的早期研究工作主要集中在对静态数据的安全搜索上.为了支持加密数据的更新，Kamara等人[4]提出了动态对称可搜索加密(dynamic symmetric searchable encryption, DSSE)技术，该技术允许数据拥有者对自己的数据进行加密存储，而且之后可以对加密数据进行搜索和动态更新.然而，更新操作可能会导致严重的额外信息泄露问题.为了解决更新时出现的额外隐私泄露问题，Stefanov等人[5]提出了前向安全和后向安全的概念，Bost等人[6-7]给出了这2个概念的正式定义.前向安全可确保未来的更新不会与以前的搜索相关联，这有助于抵抗强大的文件注入攻击；后向安全保证了后续搜索不会与过去删除的文档相关联.

目前的研究工作中已经存在许多同时满足前向安全和后向安全的DSSE方案，但大部分仅支持单个关键词搜索.因此，尽管它们的效率和安全性很高，但支持的查询在表达能力方面往往受到严重限制，例如查询远程存储的大型电子邮件数据库，单个关键词查询可能会返回大量匹配记录，但数据使用者想要的最终结果只占其中的一小部分，这不仅降低了查询效率，还浪费了许多计算资源[8-9].

为了解决单关键词搜索效率低的问题，Patranabis等人[10]最近提出了一种支持多关键词查询且满足前后向安全的动态可搜索加密方案，即不经意动态交叉索引(oblivious dynamic cross tags, ODXT)，该方案通过引入不经意交叉索引[11]来存储每次更新的状态信息，在查询时将交叉索引返回给客户端作为判断文档是否包含所有关键词的主要依据，从而实现联合查询.不过，通过大量实验结果可以得出，ODXT方案在查询有删除的记录时，在某些情况下存在查询结果不准确的问题.这是由于在查询阶段计算交叉索引时，未考虑更新的操作类型，导致算法无法区分索引是被插入还是被删除；另外，该方案仅支持单个用户查询，这大大限制了数据的使用范围，降低了数据的利用率.例如在医疗系统中，许多部门都需要查询患者的电子病历，如果使用仅支持单个用户查询的动态可搜索加密方案来保护电子病历，则会给患者诊断带来层层阻碍.

针对这些问题，本文提出了一个满足前后向安全且支持多关键词查询和多用户查询的DSSE方案.

本文的主要贡献包括3个方面：

1)通过将ODXT方案中的查询令牌改成插入与删除的查询令牌对，来区分交叉索引对应的更新操作类型，从而使查询结果始终与实际结果一致，且其查询的复杂度仅与更新次数最低的关键词的更新次数有关.

2)提出了一种支持联合搜索的多用户动态可搜索加密方案，即多用户不经意动态交叉索引(multi-client oblivious dynamic cross tags, MC-ODXT)，利用有限域内元素具有乘法逆元的性质，引入了一次性盲因子来生成查询令牌，并用数字信封进行授权验证，实现用户授权与查询.

3)对所提方案进行了安全性分析与性能分析，结果表明本文方案满足前向安全与后向安全，既解决了ODXT方案查询结果不准确的问题，又在搜索类型、适用场景等功能方面更加灵活全面，且计算时间复杂度与ODXT方案相同.

1 相关工作

1.1 动态可搜索加密

可搜索加密能够支持用户远程访问加密数据，在工业界具有广泛的应用前景[9].与公钥可搜索加密方案相比，使用对称密码原语的SSE方案在效率上拥有更突出的优势.

为了使可搜索加密支持更新，Kamara等人[4,10]引入了DSSE方案，不仅可以查询数据，还支持添加和删除数据.不过，这些方案在更新过程中会泄露额外的数据信息，一旦被恶意敌手滥用将导致严重的后果.因此，2013年Stefanov等人[5]提出了前向安全和后向安全的概念；之后Bost等人[6-7]进行了形式化定义，并将后向安全分成3个安全级别，其中BP-I比BP-II更安全，BP-II比BP-III更安全.随后，人们开始对满足前后向安全的动态可搜索加密展开广泛研究.Sun等人[12]使用一种可穿刺加密原语构造动态可搜索加密方案，不过只实现了BP-III后向安全.Ghareh等人[13]和Sun等人[14]通过茫然映射不经意随机访问机(oblivious random access machine, ORAM)技术构造索引，实现了BP-I后向安全，但该技术的计算开销较大.为了平衡安全性与效率，Ghareh等人[13]将文档关键词索引改成关键词的更新索引，设计了满足前向和BP-II后向安全的Mitra方案.Mitra方案通过向数据库增加一条更新条目信息来实现更新操作，并利用本地的更新计数器来生成搜索令牌，降低了计算的复杂度.

1.2 支持联合查询的可搜索加密

在实际应用中，单关键词搜索可能会返回大量无用的结果，降低查询效率.因此，越来越多的人把目光转移到了支持联合查询的前后向安全动态可搜索加密上.Zuo等人[15]给出了2个带有范围查询的前向安全和后向安全DSSE方案，名为SchemeA和SchemeB，其中SchemeA方案满足前向安全，SchemeB满足后向安全.随后一系列支持联合查询且满足前向或后向安全的DSSE方案被相继提出[16].最近，Patranabis等人[10]介绍了2种基于不经意交叉索引(oblivious cross tags, OXT)[11]方案和Mitra方案[13]的联合查询DSSE方案，名为BDXT和ODXT，这2种方案同时实现了前向安全和后向安全.但BDXT方案因查询时需客户端与服务器进行多轮交互，查询效率较低；而ODXT方案由于使用了延迟删除技术，在查询时只能删除部分文档.不过这为我们实现支持联合查询且满足前后向安全的动态可搜索加密方案提供了思路.

1.3 多用户对称可搜索加密

为了使可搜索加密能够支持多用户查询，Curtmola等人[17]引入了多客户端对称可搜索加密(multi-client symmetric searchable encryption, MSSE)的概念.随后，Jarecki等人[18]提出了一个支持布尔查询的MSSE方案，他们的方案利用同态签名和不经意的伪随机函数将OXT方案扩展到多客户端场景，可以抵抗恶意客户端并实现高效检索.在他们工作的基础上，Faber等人[19]提出了一种支持丰富查询类型的MSSE方案.但是，上述2种方案都只适用于静态数据集上.卢冰洁等人[20]引入了一个半诚实的代理服务器实现了DSSE中的多客户端查询，但是该方案不能支持多关键词搜索.Du等人[21]通过改进OXT协议，提出了一个非交互式且支持多用户联合搜索的DSSE方案，然而该方案仅支持授权令牌更新，不支持索引更新.受文献[18,21]的启发，本文通过改进ODXT方案中的OXT协议，将支持联合搜索的动态可搜索加密扩展到多用户场景，在保证安全性的同时，进一步丰富查询功能.

2 预备知识

2.1 伪随机函数

定义1.设Gen(1λ)∈(0,1)λ是一个密钥生成函数，G：(0,1)λ×(0,1)l→(0,1)l′是一个伪随机函数，GK(x)表示G(K,x).如果对于任意概率多项式时间的敌手A都满足：|Pr[K←Gen(1λ);AGK(·)(1λ)=1]-Pr[AR(·)(1λ)=1]|≤v(λ)，则称G是一个安全的伪随机函数，其中R：(0,1)λ→(0,1)l′是一个真随机函数，v(λ)是一个可忽略函数.

2.2 判定性Diffie-Hellman假设

如果对于任意多项式时间的敌手A，都满足：|Pr[A(g,gα,gβ,gα×β)=1]-Pr[A(g,gα,gβ,gγ)=1]|≤v(λ)，则四元组(g,gα,gβ,gα×β)与随机的四元组(g,gα,gβ,gγ)是计算上不可区分的，称为判定性Diffie-Hellman假设，简称DDH假设.

2.3 动态可搜索加密

一个动态可搜索加密方案包括索引建立、文档加密、索引查询、索引更新及文档解密5个过程.不过本文仅考虑索引建立、索引查询与索引更新3个过程，具体过程描述如下.

1)Setup(λ,DB)→(k,st,EDB).索引建立阶段.数据拥有者输入安全参数λ与数据库DB，输出数据拥有者的密钥k、本地状态st及加密数据库EDB.

2)Search(k,w,st;EDB)→DB(w).索引查询阶段.客户端输入密钥k、关键词w及本地状态st，输出查询结果，共有2种结果：当w∈W时，返回包含w的所有文档标识符集合DB(w)；当w∉W时，返回空.

3)Update(k,op,in,st;EDB).索引更新阶段.数据拥有者输入密钥k、操作类型op、待更新条目in=(id,w)及本地状态st，然后在服务器上对in执行插入或删除操作.其中op的值为add或del，id是文档标识符，w是关键词.

动态可搜索加密的安全性由现实模型Real和理想模型Ideal的不可区分性来定义.首先定义泄露函数L=(LSetup,LUpdate,LSearch)来表示敌手A在系统建立阶段、更新阶段及查询阶段获取的泄露信息，并假定敌手A获取的泄露信息只在L表示的范围内.

在现实模型Real中，敌手A运行真实方案中的Setup(λ)来初始化系统，随后A执行更新问询或搜索问询来获取信息.在理想模型Ideal中，模拟器S输入LSetup(λ)，随后敌手A进行更新问询或搜索问询，模拟器S通过相应的泄露函数LUpdate(op,(id,w))或LSearch(w)来回复敌手A.

定义3.若存在一个模拟器S，使得对于任意概率多项式时间敌手A，都有：|Pr[RealA(λ)=1]-Pr[IdealA,S(λ)=1]|≤v(λ)，则称该动态可搜索加密方案是L自适应安全的，其中v(λ)是可忽略函数.

2.4 不经意交叉索引

不经意交叉索引(OXT)协议最初由Cash等人[11]用在可搜索加密方案中，通过设计TSet和XSet索引表实现在加密数据集上的联合搜索.在OXT协议中，客户端通过为每个关键词w定义文档计数器Cnt，来记录包含w的文档数.给定一个查询q=(w1,w2,…,wn)，定义其中文档计数器值最低的关键词为w1，其余关键词为wi(i∈{2,3,…,n})，w1的文档计数器值为Cnt[w1]，则OXT协议包含3个实体和1个过程.其中设KT是从(0,1)λ上选取的随机数，作为对称加密算法Enc的密钥；KX，KY，KZ是从上选取的随机数，作为伪随机函数Fp的密钥.

1)TSet表.TSet是关键词索引表，以addr为索引，存储了包含关键词w的文档标识符信息val和致盲因子α.其计算方式为

val=Enc(KT,id)，

(1)

addr=Enc(KT,w‖Cnt[w])，

(2)

α=Fp(KY,id)(Fp(KZ,w‖Cnt[w]))-1，

(3)

其中，id∈DB(w)

2)XSet表.XSet是交叉索引表，存储了关键词w与文档的交叉索引xtag，xtag标记了w与文档间的包含关系.系统建立时，根据文档标识符id和关键词w，计算出交叉索引值xtag并存到XSet中.xtag的计算方式为

xtag=gFp(KX,w)×Fp(KY,id)，id∈DB(w).

(4)

3)xtoken变量.xtoken是查询令牌，在查询阶段由客户端生成，协助服务器端生成xtag以判断包含w1的文档是否也包含其他关键词wi(i∈{2,3,…,n}).其中，

xtoken=gFp(KZ,s‖Cnt[w1])×Fp(KX，wi).

(5)

3 MC-ODXT方案

3.1 系统模型

如图1所示，本文方案的系统模型包括数据拥有者、客户端、云服务器3个实体，其中可以有多个客户端查询数据，但只有数据拥有者能更新数据.本文的研究内容包括文档索引的建立、更新及查询.以下是各个实体的详细功能介绍.

1)数据拥有者.在系统建立阶段，负责构造文档-关键词索引，初始化系统，并将加密索引及文档上传到云服务器，如图1步骤①所示；在查询阶段，为不同客户端发来的查询生成授权信息及令牌生成因子，如图1步骤④；在更新阶段，负责生成更新数据，发送给云服务器，并在本地更新关键词的更新计数器，如图1步骤②.

2)客户端.在查询阶段，将查询q发送给数据拥有者，如图1步骤③；收到数据拥有者返回的信息后，客户端根据令牌生成因子计算出查询令牌并发给云服务器，如图1步骤⑤.

3)云服务器.提供数据存储服务.在系统建立阶段，负责存储加密文档及文档索引；在更新阶段，根据数据拥有者发来的更新信息，更新加密数据库；在查询阶段，验证授权信息，之后根据查询令牌及授权信息查找加密索引，将满足条件的结果返回给客户端，如图1步骤⑥.

3.2 算法定义

MC-ODXT方案的算法思想与ODXT方案相同，即更新时不直接添加或删除索引，而是将三元组(op,id,w)加密后存储到云服务器；查询时先找到更新次数最低的关键词，然后查询该关键词的所有更新记录，判断每个更新记录对应的文档是否与所有关键词都有更新记录，并将op=del的更新记录对应的文档过滤掉，得到最终查询结果.该方案由系统建立算法、索引更新算法、授权算法、查询令牌生成算法和查询算法5个算法组成，即Σ={Setup,Update,AuthClient,SearchToken,Search}.为方便后续描述，本文假设查询q中更新次数最低的关键词为w1，每个算法的具体描述如下.

1)系统建立算法

Setup(λ)→(sk,st,EDB).数据拥有者运行该算法，给定安全参数λ作为输入，输出数据拥有者的密钥组sk、本地状态st及初始化加密数据库EDB.

2)索引更新算法

Update(sk,st,op,(id,w);EDB)→(st′,EDB′).算法由数据拥有者和云服务器共同执行，将数据拥有者的密钥组sk和本地状态st、更新操作类型op、文档标识符与关键词对(id,w)作为输入，在EDB上更新索引，输出更新后的本地状态st′和加密数据库EDB′.

3)授权算法

AuthClient(sk,st,q)→(env,c,strap,btrlist).授权算法由数据拥有者完成，输入数据拥有者密钥组sk、本地状态st及查询q，输出授权信息env、w1的更新次数c、密钥派生因子strap及查询令牌生成因子列表btrlist.

4)查询令牌生成算法

SearchToken(q,env,c,strap,btrlist)→(env,btklist).客户端运行该算法，输入查询q和授权算法生成的数据，包括授权信息env、w1的更新计数器值c、密钥派生因子strap及查询令牌生成因子列表btrlist，输出授权信息env及查询令牌列表btklist.

5)查询算法

Search(env,btklist,KM,PK;EDB)→(Idlist).该算法由客户端与服务器共同执行.服务器输入客户端发来的授权信息env、查询令牌列表btklist、共享密钥KM及数据拥有者公钥PK，输出查询结果Idlist.

3.3 改进OXT协议

OXT协议中的关键词索引表TSet和交叉索引表XSet在系统建立阶段建立后不再改变，这对于动态可搜索加密方案并不适用.因此，本节在ODXT方案的基础上，对OXT协议中的关键词索引表、交叉索引表、查询令牌的计算方式和查询过程进行了改进，使其同时支持数据库索引更新和多客户端准确联合搜索.以下是改进协议的详细过程描述.

3.3.1 关键词索引表TSet的构建

与OXT协议相同，TSet中存储了加密信息val和致盲因子α，即TSet[addr]=(val,α)，addr是本次记录在TSet中的索引地址.不同的是，式(2)和式(3)中的文档计数器被改为更新计数器UpdtCnt；并将对称加密算法Enc改为效率更高的伪随机函数F；此外，关键词w的更新记录(op,(id,w))被加密存储到val中.其中

addr=F(KT,w‖UpdtCnt[w]‖0)，

(6)

val=(id‖op)⊕F(KT,UpdtCnt[w]‖1)，

(7)

α=Fp(KY,id)×(Fp(KZ,UpdtCnt[w]))-1.

(8)

3.3.2 交叉索引表XSet构建

本文在交叉索引的计算公式(式(4))中增加了更新操作类型op，用于区分本次更新是建立索引还是删除索引，从而为判断文档是否包含所有关键词提供了依据，其中

xtag=gFp(KX,w‖op)×Fp(KY,id).

(9)

3.3.3 查询令牌xtoken的生成

在设计一个支持多客户端联合查询的SSE方案时，需要保证数据拥有者可以对每次查询生成不同的查询令牌，防止客户端越权访问及使用之前的查询令牌访问以后的数据.因此，本文引入了一次性盲因子ρ，每次查询会产生不同的一次性盲因子ρ，用来计算查询令牌，以使每次生成的查询令牌都仅供本次查询使用.另外，本文引入了bxtrap作为查询令牌生成因子，为不同的客户端授权并协助客户端计算查询令牌.

bxtrap=gFp(KX,w‖op)×ρ，

(10)

bxtoken=bxtrapFp(KZ,UpdtCnt[w]).

(11)

为了使服务器可以根据bxtoken和α计算出xtag，之后利用xtag来判断文档是否符合联合查询，本文的xtag应满足关系式

xtag=bxtokenα/ρ.

(12)

3.3.4 联合查询过程

为了详细描述数据拥有者、客户端与云服务器之间的交互过程，本文构建了一个联合查询用例，如图2所示.首先，数据拥有者收到客户端发来的查询请求q=(w1,w2)，找到更新次数最低的关键词(假设是w1)，按照式(6)计算addrw1；接着对每个关键词生成查询令牌生成因子(bxtrapadd,bxtrapdel)和一次性盲因子ρ，分别存储到btrlist和ρlist；然后用对称加密算法加密alist和ρlist，并用云服务器公钥加密对称密钥，形成数字信封；最后将数字信封与btrlist一起发给客户端.客户端根据式(11)计算出bxtoken存储到btklist，并将btklist与存储加密alist和ρlist的数字信封一起发给云服务器.云服务器收到后先验证数字信封并解密alist和ρlist，根据alist中的addr查找TSet表，找到对应的(val,α)；接着根据式(12)，利用α，ρ和bxtoken计算出xtag，然后执行图3所示的判断过程.

由于不知道每个关键词与w1每次更新时涉及的文档之间的包含关系，所以需将每个关键词和这些文档的插入交叉索引xtagadd与删除交叉索引xtagdel都计算出来，根据索引是否在XSet中来判断文档是否包含该关键词，共包括3种判断结果：

1)当xtagadd∉XSet时，文档与w索引不存在，即文档不包含w；

2)当xtagadd∈XSet且xtagdel∉XSet时，文档包含w；

3)当xtagadd∈XSet且xtagdel∈XSet时，文档与w索引已删除，即文档不包含w.

3种判断结果是对单个文档包含单个关键词的判断结果.对于单个文档是否包含联合查询的所有关键词，其判断流程如图3所示：

对于w1的第j个更新记录，若存在关键词的xtagadd∉XSet，说明该关键词从未和该文档建立过索引，即文档不包含所有关键词，故返回空值；当所有关键词的xtagadd∈XSet时，若存在某个关键词的xtagdel∈XSet，则说明该关键词与文档建立索引后又删除了索引，即文档不包含所有关键词，故返回空值；若所有关键词的xtagadd∈XSet且所有的xtagdel∉XSet，则文档包含所有关键词，故返回TSet中的索引值给客户端.

3.4 方案详细描述

本节将改进OXT协议构造为具体的动态可搜索加密方案，主要包括系统建立阶段、更新阶段和查询阶段.

3.4.1 系统建立阶段

系统建立阶段由数据拥有者生成密钥组sk=(KS,KX,KY,KM,PK,SK)，并初始化关键词的更新计数器表UpdtCnt、关键词索引表TSet和交叉索引表XSet，得到加密数据库EDB；最终，数据拥有者将(KM,PK,EDB)发给服务器，然后本地存储密钥组sk和本地状态st=UpdtCnt.具体过程如算法1所示.

算法1.系统建立算法.

输入：安全参数λ；

输出：密钥组sk、本地状态st、数据库EDB.

数据拥有者：

① 用伪随机函数F生成密钥KS；

② 用伪随机函数Fp生成密钥KX，KY和KM；

③ 用密钥生成算法生成公私钥对(PK,SK)；

④ 初始化UpdtCnt，TSet和XSet为空表；

⑤ 令sk=(KS,KX,KY,KM,PK,SK)，st=UpdtCnt，EDB=(TSet,XSet)；

⑥ 发送(KM,PK,EDB)给服务器.

其中，KM是服务器与数据拥有者之间的共享对称密钥；SK和PK被用作数字签名，在查询时实现授权及权限验证.

3.4.2 更新阶段

数据拥有者运行索引更新算法，查找并更新本地状态st中的更新计数器表；接着计算本次更新记录在TSet中的存储地址addr和关键词索引值(val,α)，其中val是(id,op)的加密值，α是致盲因子；然后计算本次更新的交叉索引值xtag，并将(addr,val,α,xtag)存储到服务器上的TSet表和XSet表中.具体的过程如算法2所示.

算法2.索引更新算法.

输入：密钥组sk、本地状态st、操作类型op、关键词与文档标识符对(id,w)、加密数据库EDB；

输出：更新状态st′、更新数据库EDB′.

数据拥有者：

① 令sk=(KS,KX,KY,KM,PK,SK)，st=UpdtCnt；

② ifUpdtCnt[w]==null then

③ 令UpdtCnt[w]=0；

④ end if

⑤UpdtCnt[w]=UpdtCnt[w]+1；

⑥ 令strap=F(KS,w)，KZ=F(strap,1)，KT=F(strap,2);/*strap是密钥派生因子*/

⑦ 令addr=F(KT,w‖UpdtCnt[w]‖0)；

⑧ 令val=(id‖op)⊕F(KT,w‖UpdtCnt[w]‖1)；

⑨ 令α=Fp(KY,id)(Fp(KZ,UpdtCnt[w]))-1；

⑩ 令xtag=gFp(KX,w‖op)×Fp(KY,id)；

服务器端：

3.4.3 查询阶段

在查询阶段，客户端会通过接收者公钥分别与数据拥有者、云服务器端协商一个会话密钥，并用会话密钥加密传输数据，从而保证数据传输过程中的安全性.查询阶段包括授权算法、查询令牌生成算法和查询算法.

数据拥有者收到客户端发送的查询q后，遍历q找到更新次数最低的关键词w1，并为每个关键词生成一次性盲因子ρ和查询令牌生成因子bxtrap，分别存储到ρlist和btrlist；接着用w1生成密钥派生因子strap并派生出子密钥，根据w1的更新计数器值计算每次更新的关键词索引在TSet中的存储地址addr；然后利用数字信封技术和共享密钥KM来加密ρ和addr，最终得到env.最后用会话密钥加密(env,UpdtCnt[w1],strap,btrlist)并发送给客户端.具体过程如算法3所示.

算法3.授权算法.

输入：密钥组sk、本地状态st、查询列表q=(w1,w2,…,wn)；

输出：数字信封env、最低频关键词的更新计数器值UpdtCnt[w1]、密钥派生因子strap、查询令牌生成因子列表btrlist.

数据拥有者：

① 数据拥有者接收客户端发来的查询q；

② 令sk=(KS,KX,KY,KM,PK,SK)，st=UpdtCnt；

③ 找到更新次数最低的关键词w1；

④ fori=1 tolen(q)do

⑤ 令ρi=并存入ρlist；

⑥ 令bxtrapadd/del=gFp(KX,wi‖add/del)ρi；

⑦ 将(bxtrapadd,bxtrapdel)存入btrlist；

⑧ end for

⑨ 令strap=F(KS,w1)，KT=F(strap,2)；

⑩ forj=1 toUpdtCnt[w1]do

/*Enc为对称加密算法*/

/*digest_sign为数字签名算法*/

客户端收到数据拥有者发来的授权信息并用会话密钥解密后，先利用密钥派生因子strap生成子密钥KZ和KT;然后根据查询令牌生成因子bxtrap和子密钥KZ来生成查询令牌bxtoken，并存到列表btklist中;最后用会话密钥将数据拥有者发来的数字信封env和查询令牌列表btklist加密发给服务器.具体过程如算法4所示.

算法4.查询令牌生成算法.

输入：数字信封env、更新次数最低关键词的更新计数器值UpdtCnt[w1]、密钥派生因子strap、查询令牌生成因子列表btrlist；

输出：数字信封env、查询令牌列表btklist.

客户端：

① 生成密钥KZ=F(strap,1)，KT=F(strap,2)；

② fori=1 toUpdtCnt[w1]do

③ forj=1 tolen(btrlist)do

④ 取出bxtrapadd/del的值；

⑥ (bxtokenadd,bxtokendel)存入btk[i]；

⑦ end for

⑧ 将btk[i]存入btklist；

⑨ end for

⑩ 发送(env,btklist)给服务器.

服务器收到客户端发送的数字信封env和查询令牌列表btklist并解密后，首先验证数字信封并解密得到一次性盲因子列表ρlist和最低更新次数的关键词在TSet中的存储地址列表alist；然后遍历alist中的addr，取出对应的关键词索引值(val,α)；接着对于每一个(val,α)，用致盲因子α，ρlist中的ρ和对应的(bxtokenadd,bxtokendel)计算每个关键词的交叉索引对(xtagadd,xtagdel)，判断每个交叉索引值与XSet的关系，从而确定val中存储的文档是否包含每个关键词；最终将符合查询条件的val加入列表EOplist并加密发送给客户端.客户端解密得到EOplist，利用密钥KT解密得到最终的文档标识符列表Idlist.具体过程如算法5所示.

算法5.查询算法.

输入：数字信封env、查询令牌btklist、共享密钥KM、数据拥有者公钥PK、加密数据库EDB；

输出：符合联合查询的文档标识符列表Idlist.

服务器：

① 令EDB=(TSet,XSet)；

② 用PK和KM验证并解密env，得到ρlist和alist；

③ fori=1 tolen(alist)do

④ (val,α)=TSet[alist[i]]；

⑤ 设置b=1;/*标记是否符合联合查询*/

⑥ forj=1 tolen(ρlist)do

⑦ (bxtokenadd,bxtokendel)=btklist[i][j];

⑨ ifxtagadd∉XSetthen

⑩b=0；

客户端：

4 安全性分析与证明

4.1 安全模型

在本文方案的安全模型中，假设数据拥有者与客户端是完全可信的，服务器是诚实且好奇的，它会始终正确执行给定协议，但可能会尝试学习关于存储数据和查询关键词的一些其他信息.为了定义本文方案泄露函数的具体表示形式，本文设Q是一个包含以下信息的列表：

1)(t,w).表示对关键词w执行的搜索问询及对应时间戳t.

2)(t,op,id,w).对(op,(id,w))执行的更新问询及对应时间戳t，其中op∈{add,del}.

对于任意联合查询q=(w1,w2,…,wn)，假设w1是更新次数最低的关键词.本文定义TimeDB(q)返回所有满足q且未被删除的文档标识符及对应的插入时间戳，表示为

TimeDB(q)={({ti}i∈[n],id)|(ti,add,id,wi)∈Q

and ∀t′:(t′,del,id,wi)∉Q}；

(13)

定义Upd(q)返回w1所有更新操作的时间戳，表示为

Upd(q)={t|∃(op,id):(t,op,id,w1)∈Q}.

(14)

根据文献[10]中泄露函数的定义，本文方案的泄露函数L=(LSetup,LUpdate,LSearch)为

LSetup(λ)=⊥，

(15)

LUpdate(op,(id,w))=⊥，

(16)

LSearch(q)=(TimeDB(q),Upd(q)).

(17)

4.2 安全性证明

定理1.给定伪随机函数F和Fp是安全的，以g为生成元的群G满足DDH假设，如果MC-ODXT方案的泄露函数L=(LSetup,LUpdate,LSearch)满足：

LSetup(λ)=⊥，

LUpdate(op,(id,w))=⊥，

LSearch(q)=(TimeDB(q),Upd(q))，

则MC-ODXT方案是L自适应安全的.

本文借鉴文献[10]中的证明方法，通过从Real到Ideal设置一系列游戏来证明定理1，每个游戏都与上个游戏有所不同，但是在敌手A看来2个相邻游戏间是不可区分的，最后使用泄露函数L模拟Ideal，从而得出敌手A无法区分现实模型Real与理想模型Ideal.

游戏G0.与Real相同，运行本文真实方案.

游戏G1.与G0不同的是，在每次更新和查询时，挑战者将伪随机函数F(KS,·)，F(KT,·)，Fp(KX,·)，Fp(KY,·)，Fp(KZ,·)分别替换为GS(·)，GT(·)，GX(·)，GY(·)，GZ(·)，其中GS(·)，GT(·)是(0,1)λ上所有随机函数的集合内均匀随机采样，GX(·)，GY(·)，GZ(·)是上所有随机函数的集合内均匀随机采样.

引理1.如果Fp，F是安全的伪随机函数，则在敌手A看来G0与G1是不可区分的.

证明.假设存在一个多项式时间敌手B，可以区分G0与G1，则该敌手可以设计一个多项式时间算法B′从随机函数中区分出伪随机函数.显然，这与伪随机函数的伪随机性相矛盾.

证毕.

游戏G2.与G1不同的是，挑战者在查询阶段改变了bxtoken的计算方式.对于查询q，挑战者通过浏览敌手A的更新问询历史来获取w1的更新操作集合{(opj,(idj,w1))|j∈{1,2,…,UpdtCnt[w1]}}.然后，对于每个关键词wi，计算它们的αi,j和xtagi,j，并将xtagi,j存到数组A中；接着在上均匀随机采样生成ρi，并存到数组B中.计算bxtokeni,j=xta.对于不可能匹配的bxtoken，挑战者用bxtoken=gFp(KX,wi‖add/del)ρi×Fp(KZ,j)计算，并且将结果存到数组C.从以上步骤可以看出，G2与G1中的bxtoken的分布值是相同，故G2与G1是不可区分的.

游戏G3.与G2不同的是，挑战者改变了α在更新阶段的生成方式，用上的均匀随机采样来代替原来的计算.

引理2.在敌手A看来，G3与G2在统计上是不可区分的.

证明.游戏G2中的α是由GY(·)与GZ(·)的逆来计算的，其中GY(·)与GZ(·)是上所有随机函数的均匀随机采样，而在G2中，α的值也是均匀且独立的随机分布.故G2与G3中的α值在统计上是不可区分的.

证毕.

引理3.若在群G上满足DDH假设，则在敌手A看来G4与G3是不可区分的.

证明.假设存在一个多项式时间敌手B可以从敌手A的视角区分出G4与G3，则存在一个多项式时间算法B′，可以区分出gr和gFp(KX,w‖op)×Fp(KY,id).显然，B′破坏了群G上的DDH假设，故不存在敌手B可以区分G3与G4.

证毕.

游戏G5.与G4不同的是，挑战者改变了addr与val在更新阶段的计算方式.具体地，挑战者将GT(w‖UpdtCnt[w]‖b)(其中b∈{0,1})形式的函数计算改成了GT(t)形式，其中t是每个更新操作执行的时间戳.类似地，挑战者也改变了查询阶段addr的生成方式，将GT(w‖UpdtCnt[w]‖0)改成了GT(t)，其中t是对应的更新操作的时间戳.

引理4.在敌手A看来，G5和G4在计算上是不可区分的.

证明.由于每一个关键词的更新计数器UpdtCnt的值是单调递增的，而GT(·)不会在输入2个不同的时间戳后输出相同的结果.所以在敌手A看来G5和G4在计算上是不可区分的.

证毕.

游戏G6.与G5不同的是，将挑战者换成了模拟器S，并且S在更新阶段和查询阶段只能访问泄露函数L=(LUpdate,LSearch).

引理5.在敌手A看来，G5和G6在计算上是不可区分的.

证明.模拟器S访问泄露函数LUpdate(op,(id,w))=⊥和LSearch(q)=(TimeDB(q),Upd(q))，且模拟器S生成的一系列变量与G5中的挑战者相同.在查询阶段，S可以学习更新次数最低的关键词的更新次数和更新时间戳，用Upd(q)表示.S还可以学习联合查询的最终结果，即一系列文档标识符和相应的时间戳，用TimeDB(q)表示.除此之外，S可以推断出有共同最低更新次数关键词的2个联合查询q1和q2，分别用Upd(q1)和Upd(q2)表示.在敌手A看来，由S做出的回应与G5中挑战者做出的回应是相同的.故G5与G6是不可区分的.综上所述，以上一系列游戏和理论证明都说明了定理1的正确性.

证毕.

由文献[6]中对前向安全的定义可得，动态可搜索加密是自适应前向安全的，当且仅当泄露函数LUpdate可以表示为

LUpdate(op,(id,w))=L′(op,id)，

(18)

其中，L′是无状态函数[22],表示服务器在更新时运行的函数，op和id表示服务器在当前更新阶段接收到的明文信息，即向服务器泄露的信息.由式(16)知本文方案在更新阶段不会泄露关键词w、文档标识符id及更新操作op的任何信息.因此可以得出推论1.

推论1.MC-ODXT的前向安全性.如果F,Fp是安全的伪随机函数，群G满足DDH假设，则本文方案是自适应前向安全的.

由文献[7]中对后向安全的定义可得，一个支持单关键词查询的DSSE方案满足自适应后向安全，

当且仅当更新泄露函数LUpdate和查询泄露函数LSearch可以表示为

LUpdate(op,(id,w))=L″(op,id)，

(19)

LSearch(w)=L‴(TimeDB(w),Upd(w))，

(20)

其中，L″和L‴是无状态函数[22]，分别表示服务器在更新和查询时运行的函数，op和id表示服务器在当前更新阶段获取的明文信息，插入时间戳集合TimeDB(w)和更新时间戳集合Upd(w)表示当前查询阶段获取的明文信息.由式(16)和式(17)可知本文方案的泄露函数满足后向安全的定义，故得出推论2.

推论2.MC-ODXT的后向安全性.如果F,Fp是安全的伪随机函数，群G满足DDH假设，则本文方案是自适应后向安全的.

5 性能分析

5.1 理论分析

1)功能方面

① 索引更新.DMSSE方案不支持索引更新，MitraConj,ODXT及本文方案均支持索引动态更新.

② 多客户端查询.MitraConj方案与ODXT方案仅支持数据拥有者查询，而DMSSE方案与本文方案均支持多客户端查询.

③ 联合查询.DMSSE方案支持静态数据集上的联合查询，MitraConj,ODXT及本文方案均支持动态数据集上的联合查询.不过MitraConj方案的查询效率较低，并且在查询时会向服务器泄露每个关键词的信息；ODXT方案与本文方案在查询时仅泄露更新次数最低的关键词的信息，但ODXT方案在查询有删除记录的关键词时查询结果会与实际结果有偏差.与其他方案相比，本文方案支持的查询功能更为丰富、适用范围更广.

Table 1 Features Comparison of the Conjunctive-keywords Searchable Encryption Schemes

2)效率方面

① 更新时间.DMSSE方案不支持索引更新，故不考虑更新时间.MitraConj,ODXT与本文方案均通过向数据库中添加更新记录来实现更新功能，执行常数级运算，故更新时间复杂度均为O(1).

综上可知，本文方案与ODXT方案在更新时间、生成查询时间及查询时间的复杂度相同，且查询时的时间复杂度仅与更新次数最低的关键词的更新次数有关.

5.2 实验及结果分析

本文实验使用Python语言对算法进行实现，实验环境为Windows 10配置在Intel Core i5-1135G7 2.40 GHz 16 GB内存中，使用Enron电子邮件数据集作为实验数据.本文从Enron的150个用户数据中提取了30 109个邮件数据，并从中提取了121 380个文档与关键词对，参考了文献[21]中的数据预处理方法来处理数据，得到最终实验数据集.

首先，实验固定更新次数最低的关键词的更新次数为10，通过改变单次查询中的关键词数量n，对方案的查询耗时进行了测试，结果如图4所示.

由图4可知，当更新次数最低关键词的更新次数不变时，查询耗时随着关键词的个数增加呈线性增加.这是因为查询时查询令牌的计算次数决定了查询阶段的耗时，而计算次数会随关键词个数的增加线性增加，所以查询耗时也线性增加.

接下来通过改变不同关键词的更新次数，来测试关键词的更新次数与查询耗时之间的关系.实验假设在查询q=(w1,w2)中改变关键词的更新次数时，始终保持w1的更新次数比w2低，UpdtCnt[w]表示关键词w的更新计数器值.结果如图5所示，当固定w1的更新次数为10时，增加w2的更新次数，方案的查询耗时几乎不变；当固定w2的更新次数为2 800时，增加w1的更新次数，查询耗时呈线性增长.这是由于本文方案先查询最低更新次数关键词对应的关键词索引，再从这些索引中筛选包含所有关键词的文档索引，因此查询耗时仅与更新次数最低的关键词的更新次数有关.

最后，为了测试ODXT方案与本文方案的查询结果与实际结果是否一致，从以上实验的匹配结果中随机选取10%的文档并删除了其中一个关键词与这些文档的索引，然后改变另一个关键词从匹配结果中删除文档索引的比例，并统计删除后查询结果占删除前查询结果的百分比.其中，另一个关键词从匹配结果中删除文档的比例分别设为0%、5%且与前一个关键词删除文档完全重复、5%且与前一个关键词删除的文档完全不重复、10%且有一半与前一个关键词删除的文档重复.为了方便分析实验结果，在w1，w2删除了部分索引后，设置w1仍然是最低更新次数的关键词，实验结果如图6、图7所示.

图6展示了从匹配结果中删除10%的文档与w1间的索引后，改变w2删除比例得出的查询结果.由图6可知，ODXT的查询结果始终只比删除前少了10%.此外，当w2删除的文档与w1删除的文档不重复时，相比ODXT方案的结果会发生一定偏差，本文方案仍能保证查询结果始终与实际结果一致.

图7展示了从匹配结果中删除10%文档与w2之间的索引后，改变w1删除比例得出的查询结果.由图7可知，ODXT的查询结果随着w1删除比例的增大而减少，且ODXT的减少比例与w1增加的删除比例一致.而本文方案中的查询结果与实际结果一致，即减少的匹配文档比例是2个关键词删除的文档比例之和.

对比图6、图7可以看出，当w1删除索引而w2不删除索引时，ODXT方案与实际查询结果一致；当w2删除索引而w1不删除索引时，ODXT方案的查询结果与删除前一致；当w1与w2都删除索引时，ODXT方案的查询结果与只删除w1的查询结果是一致的.这是由于ODXT在查询时只能返回更新次数最低的关键词对应的每个更新操作类型，无法返回其他关键词的更新操作类型，故不会过滤掉其他关键词的已删除索引.因此，ODXT方案在查询有删除记录的关键词时，只对更新次数最低的关键词执行删除操作，而未对其他关键词执行删除，所以查询结果与实际结果有一定的偏差.本文方案在查询有删除记录的关键词时，查询结果始终与实际查询结果一致，所以本文方案实现了准确的联合查询.

6 结 论

针对ODXT方案中存在的联合查询结果不准确的问题，本文通过改进不经意交叉索引协议，实现了准确的联合查询，且查询的时间复杂度仅与更新次数最低的关键词的更新次数有关.另外，本文通过引入一次性盲因子和数字信封技术，设计了一个支持联合搜索的多用户动态可搜索加密方案，保证了授权多用户查询时的安全性.通过方案的安全性分析可以得出，本文所提的MC-ODXT方案满足前向安全与后向安全.最后我们对方案性能进行了理论和实验分析，证明了本文方案在保证安全性的同时查询功能更为丰富，且其时间复杂度与ODXT方案的时间复杂度相同.

作者贡献声明：张蓝蓝提出算法思路与实验方案，完成实验并撰写论文；曹卫东提供理论指导、研究思路分析及论文修改意见；王怀超提供理论分析和技术指导,提出论文修改意见.