基于双向索引的高效连接关键字查询动态可搜索加密方案

杜瑞忠，张玉晴，李明月

（1.河北大学网络空间安全与计算机学院，河北 保定 071000；2.河北省高可信信息系统重点实验室，河北 保定 071000；3.南开大学计算机学院，天津 300071）

0 引言

云计算的出现允许个人和组织将大量数据的存储和处理外包给第三方服务器。然而，这导致了隐私问题，用户通常不相信服务提供者会尊重其数据的机密性[1]。这种信任的缺乏往往会受到来自内部恶意用户和外部攻击者的威胁。为了解决这个问题，Song 等[2]首次提出了可搜索加密（SE,searchable encryption）技术。可搜索加密分为对称可搜索加密（SSE,searchable symmetric encryption）[3]和公钥可搜索加密（PEKS,public-key encryption with keyword search）[4]，SSE 算法简单并且更加高效，所以得到更广泛的应用。然而，早期的SSE 方案都是静态的。

动态对称可搜索加密（DSSE,dynamic searchable symmetric encryption）技术[5]的提出扩展了SSE的应用，其不仅支持数据检索，还支持数据动态更新。然而，DSSE 方案在动态更新的过程中，服务器可能会学习到一些信息，即导致信息泄露，泄露的信息包括数据库大小、查询模式和访问模式。为提出更安全的方案，前向安全和后向安全[6]的概念被提出。前向安全是指无法确认新添加的文件是否包含已搜索的关键字。后向安全是指如果一个关键字/文件对(w,f )被添加到数据库中，然后被删除，则对w的后续搜索查询不会显示文件f。Bost 等[7]根据泄露程度的不同定义了3 种后向安全：对于关键字w，Type-I 泄露了当前匹配关键字w的文件和文件的插入时间，以及w更新的总次数；Type-II额外泄露了更新发生的时间；Type-III 额外泄露了已删除文件被添加的时间，以及被哪次更新删除。

大多数前向安全和后向安全的DSSE 方案都是利用茫然随机访问机（ORAM,oblivious random access machine）避免访问模式的泄露。然而，ORAM结构检索和更新效率低，通信开销和计算开销大，并且不支持包含大量文件的数据库，所以需要采用新的索引结构去提升检索和更新效率，并且保证方案的前向安全和后向安全。同时，现有的同时满足前向安全和后向安全的DSSE 方案只支持单关键字查询，表达能力受到严重限制且不满足实际应用的需求。因此，任何SSE 方案要真正实用，至少应该支持连接关键字查询，即给定一组关键字(w1,...,wn)，该方案能够找到并返回包含所有这些关键字的文档集。

为了解决上述问题，本文主要研究工作如下。

1) 采用正排索引和倒排索引结合的思想，利用位图索引设计双向索引结构，添加和删除操作仅需要一个模加法运算，不仅简化了更新过程的操作，而且防止了访问模式的泄露。

2) 利用双向索引设计了连接关键字查询方案BPC-DSSE。该方案使用内积匹配算法计算连接关键字查询结果，查询过程只需要两轮交互，提高了查询效率，同时实现了Type-I-后向安全。

3) 理论分析和仿真实验结果表明，BPC-DSSE方案与使用ORAM 结构和其他结构实现前向安全和后向安全的连接关键字方案相比，具有更好的查询与更新性能，并且保证了更新过程的安全性。

1 相关工作

SSE 首先由Song 等[2]提出，对于长度为n的文件，该方案加密和搜索算法需要流密码和分组密码，操作时间复杂度为O(n)。为了支持动态更新，DSSE[5]被提出。早期的DSSE 方案很容易受到潜在攻击的威胁[8]，如文件注入攻击[9]。为了减轻这种攻击造成的威胁，前向安全和后向安全的概念被提出[6]。2016 年，Bost[10]给出了前向安全的正式定义，并给出了一种前向安全的DSSE 方案Σoφoς，该方案使用简单的密码工具（只有伪随机函数和陷门原语），不依赖ORAM 结构，效率和安全性都有一定的提升。2017 年，Bost 等[7]根据泄露的不同程度从高到低定义了3 种后向安全类型，并给出了4 种前向安全和后向安全的方案。第一种方案Fides 实现了Type-II的后向安全。第二种方案Diana非常高效，但只实现了Type-III 的后向安全，Diana 被修改成只需要2 种往返的后向安全方案Dianadel。第三种方案Janus 是具有单次往返的后向安全方案，但该方案也只实现了Type-III 的后向安全。第四种方案Moneta 实现了Type-I 的后向安全，但此方案是基于TWORAM（ORAM in two rounds）结构的，因此计算开销和通信开销都非常大。自此，一系列前向安全和后向安全的方案被提出[11-17]。

Cash 等[18]提出基于茫然交叉标签（OXT,oblivious cross tag）协议设计有效的SSE 协议，支持单作者阅读框架中的连接关键字查询。虽然OXT 协议通过许多专门的数据结构来提供高性能，但它向服务器泄露“部分”数据库信息。同时，该方案需要三轮交互，增加了通信开销。2018 年，Lai 等[19]提出了一种新的SSE 协议，称为隐藏交叉标签（HXT,hidden cross tag），它消除了连接关键字查询的关键字对结果模式（KPRP,keyword pair result pattern）泄露。2019 年，Wu 等[20]提出以自上而下的方式存储索引元素到虚拟二叉树（VBTree,virtual binary tree）结构中，而不存储任何树枝和树节点，该树只存在于逻辑视图中，并且所有的元素实际上都存储在一个哈希表中，但是该方案只实现了前向安全。2020 年，Zuo 等[21]提出了一个扩展位图索引结构，比VBTree 更高效地实现了连接关键字查询，并且实现了前向安全和后向安全。2021 年，Patranabis等[22]提出了茫然动态交叉标签（ODXT,oblivious dynamic cross tag），ODXT 通过有效地支持在大型数据库上的快速更新和连接关键字查询，在性能和安全性之间提供了现实的折中，同时根据现有的前后隐私概念，只对服务器造成适度的访问模式泄露。

2 DSSE 定义及其安全模型

本节给出了必要的背景知识，包括符号定义、DSSE 方案的定义及其安全模型、前向安全和后向安全。

2.1 符号定义

本文中使用的主要参数如表1 所示。

表1 主要参数

2.2 DSSE 方案的定义

数据库DB 为关键字/文件标识符对的列表；fi为文档标识符；wi为fi中包含的所有关键字集合，wi⊆{0,1}*；n 为数据库DB 中所有文件的数量。那么数据库DB 可以表示为|DB|为关键字/文件标识符对的总数量。W 为数据库DB 中所有关键字的集合

DSSE 方案包括算法Setup 以及运行在客户端和服务器的协议Search 和Update，即DSSE=(Setup,Search,Update)，具体描述如下。

(EDB,σ)←Setup(1λ,DB)。输入安全参数λ、数据库DB，输出当前的状态σ以及加密数据库EDB，其中，σ存储在客户端，EDB 上传到云服务器。

(Γ,⊥)←Search(s,σ;EDB)。对于状态σ，客户端发出搜索请求s，与拥有加密数据库的服务器进行交互。执行协议结束后，客户端输出一个匹配搜索请求s的文件标识符的集合Γ，服务器不输出任何内容。

(σ′,EDB′)←Update(σ,op,in;EDB)。对于状态σ，操作op∈{add,del}，集合in=(f,w)是文件/关键字对，客户端向拥有加密数据库的服务器发出添加或删除in 中文件/关键字对的请求。协议结束后，返回给客户端新的状态σ′，并更新服务器的加密数据库为EDB′。

2.3 DSSE 方案安全模型

给定一个2.2 节定义的DSSE 方案，本文将定义现实博弈REAL 和理想博弈IDEAL 并给出其安全模型，REAL 反映了原始的DSSE 方案的行为，IDEAL反映了模拟器S的行为，该模拟器将原始的DSSE的泄露作为输入。对于敌手A，泄露函数定义为L=(Lstup,Lsrch,Lupdt)，Lstup是在执行Setup 算法时A可以学到的信息，Lsrch是在执行Search 协议时A可以学到的信息，Lupdt是在执行Update 协议时A可以学到的信息。概率博弈REAL 和IDEAL 定义如下。首先运行Setup(λ,DB)，得到加密数据库EDB，A发起一系列搜索查询q或者是更新查询(op,in)，最后，A返回实验结果b,b∈{0,1}。模拟器S首先执行泄露函数Lstup(λ,DB)，针对A发起一系列搜索查询或更新查询的不同(op,in)，模拟器S分别输入Lsrch和Lupdt，并将输出结果返回给A。最后，A返回实验结果b,b∈{0,1}。

定义1机密性。给定一个动态可搜索加密方案DSSE 和以上规则，如果对于任意概率多项式的敌手A，存在高效的模拟器 S 和输入 L 满足则这种DSSE 方案是L-适应性安全的。

2.4 前向安全

前向安全由Stefanov 等[6]提出。前向安全保证了DSSE 方案在更新期间不会泄露新插入的文件与之前的搜索查询匹配的信息，前向安全的正式定义[7]如下。

定义2前向安全。如果一种L-适应安全的DSSE方案是前向安全的，那么存在一个无状态的函数L′，其更新的泄露函数Lupdt为

其中，{(fi, µi)}是与更新文件fi的修改关键字数量µi配对的修改文件集。

本文中，泄露函数为Lupdt(op,{(W,bsw),(f,bsf)})=L′(op, bsw,bsf), 其中，W和f是更新操作关键字和文件集合，bsw和bsf是对应的更新索引。

2.5 后向安全

后向安全由Stefanov 等[6]提出。对同一关键字的两次查询期间，后向安全保证不会泄露之前插入且之后删除的文件的信息。Bost[10]定义了3 种不同泄露程度的后向安全：Type-I、Type-II 和Type-III。Zuo 等[16]定义了Type-I-级别的后向安全。后向安全泄露信息对比如表2 所示，其中，√表示泄露相应信息，—表示不泄露相应信息。

表2 后向安全泄露信息对比

例如，发生以下一组操作序列，顺序为{1,search,w},{2,add,(w,f1)},{3,add,(w,f2)},{4,add,(w,f3)},{5,delete,(w,f1)},{6,search,w}，Type-I 后向安全会泄露当前匹配关键字w的文档有f2和f3，分别在时间3 和时间4 插入，以及发生在w上的更新一共有4 次；Type-II 额外泄露w的更新发生在时间2～时间5；Type-III 额外泄露w在时间2 的插入在时间5 被删除。而Type-I-后向安全仅泄露一共有4 次更新，分别发生在时间2～时间5。

本文中基于动态填充算法的BPC-DSSE方案采用基于位图索引的技术，添加和删除使用同一个模块，所以不会泄露文件插入时间；并且查询结果返回位串，隐藏了访问模式。综上，BPC-DSSE 方案仅泄露更新次数以及更新时间，实现了Type-I-后向安全。

为了正式定义Type-I-，对于搜索查询列表Q，本文定义了搜索模式sp(w)={t:(t,w)∈Q}，其中t为时间戳。该搜索模式会泄露对关键字w的搜索查询重复的次数。本文还定义了新的泄露函数TimePDB，对于一个关键字w，TimePDB(w)存储了关键字w所有更新时间t的列表。对于更新查询Q＇，有

定义3后向安全。对于一个L-适应性安全的DSSE 方案，如果存在2 个无状态的函数L′和L′′，使搜索和更新的泄露函数可以写为

则称这种DSSE 方案是Type-I-后向安全的。

3 BPC-DSSE 方案

本节给出了BPC-DSSE 的方案设计。首先介绍了方案的设计理念，然后给出了方案涉及的详细步骤。

3.1 设计理念

BPC-DSSE 方案是具有前向安全和Type-I-后向安全的连接关键字DSSE 方案，主要思想是基于位图索引[16]构建双向索引结构，利用基于同态加法的对称加密[17]对索引进行加密，并通过基于内积的匹配算法[23]实现连接关键字查询。

更新操作。构建索引采用位图索引，索引结构及其运算规则如图1 所示。假设数据库文件数量最大为n，关键字空间W的每个关键字都维持一个n位的比特串，用来表示文件是否包含此关键字，如果包含则将相应位置设置为1，否则设置为0。对倒排索引以相同的方式进行处理，为每个文件维持一个|W|大小的比特串。如图1(a)所示，数据库的文件最大数量为6，关键字空间大小为4，即n=6，|W|=4，对应的比特串(000100)2以及(0010)2表示(w1,f2)存在。下面以关键字索引演示位图索引的计算规则，文件索引计算规则相同。如图1(b)所示，如果添加文件f3，需要生成比特串(001000)2，并将其加到初始比特串(000100)2上，得到结果(001100)2。如图1(c)所示，如果删除文件f2，需要生成比特串-(000100)2=(111100)2mod26并加到初始比特串(000100)2上，得到结果(000000)2。

图1 索引结构及其运算规则

连接关键字查询实现。其主要思想是采用正排索引和倒排索引结合，利用位图索引实现高效的连接关键字查询。首先，搜索频率最低的关键字w1得到相应倒排索引的位串，将其解密后得到与w1匹配的文件标识符。然后，根据文件标识符获取相应的正排索引对应的位串。最后，利用基于内积的匹配思想将位串解密并计算与查询位串的内积，通过内积结果过滤得到最终的结果集合。

方案主要步骤如图2 所示，以明文形式进行说明。此时的索引结构如左上角位图索引所示，关键字空间大小为6，文件数量为8。查询关键字w0、w1和w5，即q=(100011)2。首先，访问倒排索引得到频率最低的关键字w0对应的位串为(10101010)2，解密后得到包含关键字w0的文件标识符集合为f={f1,f3,f5,f7}，访问正排索引获取f中文件对应的位串分别为(100111)2、(111010)2、(100111)2、(101011)2，将其分别与查询位串q内积，并将内积结果与查询关键字的个数（此例为3）进行比较，将比较结果相同的文件标识符加入结果集合，得到最终结果集合result={f1,f5,f7}。

3.2 方案涉及的详细步骤

在详细介绍算法之前，首先给出具有加法同态性质的对称加密算法[14]，主要由以下4 种算法组成。

初始化Setup(1λ)。其输入为安全参数λ，输出为公共参数消息空间N。如果一种方案可以支持的最大文件数量为n，那么消息空间N=2n。

加密算法Enc(m,sk,N)。其输入为明文消息m、随机的安全密钥sk 以及公共参数N，输出为加密后的密文c。其中，0≤m＜N，0≤sk＜N，密文c=sk+m (mod N)。

解密算法Dec(c,sk,N)。其输入为密文c、随机的安全密钥sk 以及公共参数N，输出为解密后的明文m。其中，明文m=c-sk (mod N)。

同态加法Add(c1,c2,N)。其输入为2 个密文c1和c2以及公共参数N，输出为2 个密文c1和c2之和c。对于密文c1=Enc(m1,sk1,N)，c2=Enc(m2,sk2,N)，c=c1+c2=Enc(m1+m2,sk1+ sk2,N)。

BPC-DSSE 方案由一种算法 Setup 和2 个协议Update 和Search 组成。

Setup 算法如算法1 所示。客户端首先初始化2 个空映射Mw和Mf，分别存储关键字w对应的bsw和文件f对应的bsf，然后初始化2 个空的映射CTw用来存储当前搜索令牌STcw以及每个关键字更新次数cw，CTf用来存储当前搜索令牌STcf以及每个关键字更新次数cf。最后计算EDB←{Mw,Mf}，将EDB 以及状态σ发送给服务器。

算法1BPC-DSSE Setup(1λ,DB)

输入安全参数λ，数据库DB

输出EDB，状态σ=(nw,nf, K, CTw, CTf)

图2 方案主要步骤

Update 算法如算法2 所示。客户端根据更新的(w,id)生成对应的位串bsw和bsf，将其加密后得到加密位串Ew 和Ef。首先访问CTw得到关键字w对应的搜索令牌STcw和更新次数cw，并访问CTf得到文件f对应的搜索令牌STcf和更新次数cf，接下来生成密钥。如果数据库为空，则初始化搜索令牌STcw、STcf和更新次数cw、cf。用哈希函数H1生成更新令牌UW 和UF 来更新服务器端的EDB，并用H2混淆之前的搜索令牌，用哈希函数H3生成一次密钥skcw和skcf。将UW、UF、Ew、Ef 和混淆后的搜索令牌C发送给服务器，并且更新CT 得到新的状态σ′。服务器更新映射对应的位串，并加到原始位串上。

算法2BPC-DSSE Update(w,f,bsw,bsf,σ;EDB)

输入关键字w和文件f，对应的更新位串bsw和bsf，状态σ

输出更新后的加密数据库EDB′

客户端

Search 算法如算法3 所示。客户端首先根据频率最低的w1生成搜索令牌并发送给服务器。服务器访问Mw得到加密位串bsw，并返回客户端。客户端解密得到对应文件id，并发送给服务器。服务器访问Mf得到对应的位串，将其逐一与查询位串内积，并将内积结果和查询关键字的个数相同的文件id加入结果集合。

算法3BPC-DSSE Search(q,σ;EDB)

输入查询连接关键字q=w1∧w2∧…∧wk，状态σ

输出结果集合result

客户端

4 安全性分析

本节给出BPC-DSSE 的安全分析。

4.1 前向安全

BPC-DSSE 是前向安全的。在更新期间，使用3 个哈希函数，H1通过随机选取的密钥来生成更新令牌UW 和UF，由于加上计数c，每个更新令牌都是不相同的；H2通过新生成的搜索令牌和密钥将之前的搜索令牌进行更新，如果拥有之前的搜索令牌，就可以通过哈希函数计算得到之后的搜索令牌，而拥有最新的搜索令牌却无法得知之前的搜索令牌，保证了前向安全性；H3用来生成一次性密钥。综上所述，BPC-DSSE 是前向安全的。

4.2 后向安全

BPC-DSSE 是Type-I-后向安全的。由于使用位图索引，并且添加和删除操作只需要一个模加法运算，因此不会泄露插入时间以及文件被插入后删除对应的插入和删除时间；同时由于F的伪随机性，每次更新时都包含了不同的输入，对于两次查询期间添加随后又删除的文件，服务器是无法学习到其相关信息的。综上所述，BPC-DSSE 是Type-I-后向安全的。

定理1BPC-DSSE 的前向安全和Type-I-后向安全。F 是安全的伪随机函数，RO1、RO2和RO3是随机预言机。定义泄露函数LBPC-DSSE=(Lsrch,Lupdt)，如果泄露函数Lsrch(w)=(sp(w),rp(w),Time(w))，Lupdt(op,(w,bsw),(f,bsf))=⊥，那么BPC-DSSE 是LBPC-DSSE-适应前向安全和Type-I-后向安全的。

证明与Chamani 等[12]类似，从现实博弈REAL和理想博弈IDEAL 之间构造了一系列博弈Game，连续2 个Game 之间存在细微的不同，但不可区分，从而得到REAL 与IDEAL 不可区分的结论。最后，用定理1 中定义的泄露函数模拟了IDEAL。

GameG0。G0和现实博弈完全一样。

GameG1。G1与G0相同，除了不使用F生成关键字w的密钥，而是以相同的概率随机选择密钥，并将密钥存储在表Key 中。如果从来没有搜索过w，则生成w的密钥并存储在表中；如果搜索过w，则返回表中关键字w的密钥。由于伪随机函数的安全性，G1与G0是不可区分的。

GameG2。G2与G1相同，除了在更新过程中，使用随机预言机RO1代替H1进行运算。对于更新协议，更新令牌是随机生成的并被存储在表UT 中。当搜索协议被调用时，通过计算RO1(K,ST)生成更新令牌并存储在表R1中，若(K,ST)已经在R1中，则可以直接搜索R1得到结果。对于同样的哈希函数H2和H3，也同样使用随机预言机逐个替换，由于搜索令牌是随机选取的，并且每次输入的令牌都是不同的，G2与G1是不可区分的。

GameG3。G3与G2相同，除了使用长度为n的全0 的位串代替bs。由于具有加法同态性质对称加密的安全性，G3与G2是不可区分的。

模拟器。模拟器与G3相同，只是用搜索模式sp(w)代替搜索关键字w来模拟理想博弈。对于更新，在G3中为每次更新选择了新的随机字符串。对于搜索，模拟器从当前搜索标记STc开始，并为之前的搜索标记选择一个随机字符串。对于关键字w，模拟器使用新的时间戳t′←minsp(w)，然后通过RO2将其嵌入密文C中。此外，模拟器通过RO3将bs 嵌入STc并将所有0 嵌入剩余的搜索标记中。因此，G3和模拟器是不可区分的。另外，模拟器中描述的本质上是2.3 节定义的理想博弈因此是不可区分的。综上与G0是不可区分的，即是不可区分的。

5 仿真分析

本节主要对BPC-DSSE 方案的查询、更新复杂度和存储开销进行分析，并给出仿真结果。BPC-DSSE 方案与已有前向安全和后向安全的动态可搜索加密方案（包含单关键字查询以及连接关键字查询）的性能对比如表3 所示，其中，N为关键字/文件标识符对数，nw为包含关键字w的文档数量，dw为关键字w被删除的条目数，aw为关键字w的更新次数，|w|为关键字的总数，|D|为文件总数，Õ 符号隐藏了多对数因子。连接关键字中，n为连接关键字查询的关键字个数，w1为其中频率最小的关键字，|Upd(w1)|为包含w1的文件的数量更新操作，HT 为树的高度。经对比分析可以发现，实现连接关键字的方案中，VBTree[20]没有实现后向安全性，FBDSSE-CQ[21]实现了Type-C 的后向安全性，ODXT[22]只实现了Type-II 的后向安全性，因此，BPC-DSSE 方案实现了更强的后向安全性。

5.1 计算开销

在查询阶段，第一次交互服务器需要计算关键字w1对应的位串并返回，时间复杂度为O(|Upt(w1)|)，客户端需要计算出文件对应的更新令牌，复杂度相同；接下来服务器通过文件更新令牌返回文件对应的加密位串，时间复杂度为O(|Upt(w1)|)，客户端解密出文件的位串，并与查询位串进行内积，时间复杂度为O(|Upt(w1)|)，综上，查询过程时间复杂度为O(|Upt(w1)|)。在更新阶段，客户端服务器只需要固定地进行搜索令牌更新以及更新令牌生成操作，时间复杂度为O(1)。

5.2 存储开销

在客户端，存放状态σ，由于需要找到最小频率的关键字，因此造成的客户端的存储开销为O(1)。在服务器端，由于需要存储双向映射Mw和Mf，因此服务器端存储开销为O(max(|w|,|D|))，其中max(|w|,|D|)为文件数量和关键字数量中的最大值。

5.3 性能对比

本节给出BPC-DSSE方案经过一系列测试后的性能评估。本文方案采用拥有AMD Ryzen 7 4800U with Radeon Graphics 1.8 GHz 的处理器配置了Windows 10(64 位)系统的机器，支持16 GB RAM，使用Java 语言编程实现。实验采用的是安然电子邮件（Enron）数据集，包括50 万个不同的文件，将其解析为本文设计的双向索引结构，在索引中提取190 万个不同的关键字。对于本文方案，将文件的最大数量设置为50 万。在实验过程中，多次调整文件更新次数以及查询连接关键字的个数进行实验，以此模拟不同的情境下本文方案的性能。

首先，测试更新性能。选用实现连接关键字的方案中效率较高的VBTree 方案[20]以及同样使用位图索引实现连接关键字的FBDSSE-CQ 方案[21]来进行对比。通过变换更新次数来测试更新时间受更新次数的影响，根据现有论文对比实验的设计，将更新次数设置为10～50 次，测试结果如图3 所示。由于位图索引简化了更新操作并且方案基于双向索引结构，因此BPC-DSSE 的更新时间比VBTree 以及FBDSSE-CQ更短。由此可见，BPC-DSSE 实现了更好的更新性能。

表3 不同方案的性能对比

图3 更新时间受更新次数的影响

接下来，测试查询性能。查询性能主要从两方面来考察：一方面是关键字频率最低的w1的更新次数对查询时间的影响；另一方面是查询关键字个数对查询时间的影响。

图4 查询时间受w1 的更新次数的影响

对于第二方面，对比方案 VBTree[20]和FBDSSE-CQ[21]分别测试了3 个和5 个关键字的实验结果，由于5 个关键字已满足实际应用的需求，因此本文将查询的连接关键字个数设置为1～5，测试结果如图5 所示。当查询关键字个数为1 时，与FBDSSE-CQ 相比，BPC-DSSE 的搜索时间大约是相比，BPC-DSSE的查询时间大约是通过表3 的查询时间复杂度分析可以看出，FBDSSE-CQ 和VBTree 的查询时间复杂度与查询关键字个数呈线性相关，而BPC-DSSE 的查询时间不受查询关键字个数的影响。所以随着查询关键字个数从1 增加到5，FBDSSE-CQ 的查询时间增长了5 倍，VBTree的查询时间增加了2 倍，而BPC-DSSE 的查询时间几乎不受影响。由此可见，BPC-DSSE 实现了更好的查询性能。

图5 查询时间受查询关键字个数的影响

6 结束语

本文构造了一种前向安全和后向安全的连接关键字查询方案。基于位图索引设计了双向索引，简化了更新过程，同时防止了访问模式的泄露，提高了方案的安全性。此外，利用基于内积的匹配思想计算连接关键字的查询结果，具有更好的查询性能。安全分析表明，本文方案具有前向安全以及Type-I-的后向安全。仿真结果表明，本文方案具有更好的更新性能以及查询性能。