可搜索加密无需解密密文就能实现数据搜索. 其中对称可搜索加密（searchable symmetric encryption，SSE）方案因搜索过程采用对称算法，在数据量较大的云存储环境下往往具有更高的搜索效率，成为近年来的研究热点^[1-2].

2000年，Song等人^[3]首次提出了可搜索加密的概念，并基于对称密码算法，构造了一个对称可搜索加密方案. 文献[4-8]分别构造了正排索引、倒排索引、双向索引和树形索引结构的对称可搜索加密方案，从算法搜索效率、方案安全性等方面就对称可搜索加密方案进行了深入研究.

为提高方案的实用性，文献[9]设计了交叉索引结构，构造了支持连接查询的对称可搜索加密方案OXT（oblivious cross tags）. 该方案将连接查询请求分为$\mathrm{s}\mathrm{t}\mathrm{e}\mathrm{r}\mathrm{m}$和$\mathrm{x}\mathrm{t}\mathrm{e}\mathrm{r}\mathrm{m}$两部分，其中$\mathrm{s}\mathrm{t}\mathrm{e}\mathrm{r}\mathrm{m}$用于实现单关键词查询，$\mathrm{x}\mathrm{t}\mathrm{e}\mathrm{r}\mathrm{m}$用于从单关键词查询结果中去除多余的匹配文档索引. 在此基础上，人们从安全性和性能等方面构造了多种支持连接查询的可搜索加密方案^[10-12]. 文献[13]基于OXT方案实现了一种支持析取操作的布尔关键词查询方案，进一步拓展了方案的场景适应能力.

然而，文献[14]研究指出，OXT结构能够实现任意关键词之间的连接查询，但通常会向服务器泄露更多的结果特征. 理想情况下，连接查询对称可搜索加密仅向服务器泄露与查询关键词相匹配的整体结果特征（whole result pattern，WRP），即与所有查询关键词匹配的文档数量和文档标识. 例如对于$n$个关键词的连接查询${w}_{1}{\wedge … \wedge w}_{n}$（设${w}_{1}$为“$\mathrm{s}\mathrm{t}\mathrm{e}\mathrm{r}\mathrm{m}$”关键词），关键词对结果特征（keyword-pair result pattern, KPRP）向服务器泄露了每个包含${\left({w}_{1},{w}_{i}\right)}_{2\le i\le n}$关键词的文档集合$DB\left({w}_{1}\right)\cap DB\left({w}_{i}\right)$，但实际上仅需返回与所有$n$个查询关键词匹配的文档集合${\bigcup }_{j=1}^{n}DB\left({w}_{j}\right)$. 文献[15]利用OXT结构中泄露的结果特征信息恢复了所有连接查询关键词.

为此，文献[14]采用对称算法和伪随机函数替换复杂的公钥计算，定义了轻量级的对称隐藏向量加密（symmetric hidden vectors encryption，SHVE）原语，增强OXT方案在关联查询时的安全性. 但该方案仍是静态的，不支持密文数据库的动态更新（如添加、删除等）操作.

当前实现前向和后向隐私的动态可搜索加密方案大多仅支持单关键词查询. 文献[16]利用位图索引构建了基于双向索引结构的动态连接关键字查询方案. 文献[17–18]提出一种支持连接查询的对称可搜索加密方案，但方案仅具有前向隐私. 文献[19]基于已有动态对称可搜索加密方案，在OXT方案的基础上设计了不经意动态交叉标签（oblivious dynamic cross tags，ODXT）结构，构造了一种支持动态更新的对称可搜索加密方案，理论分析及实验结果表明，方案同时具有前向/后向隐私，且具有更小的通信开销. 但由于方案是基于OXT方案进行设计的，仍会泄露文献[14]指出的更多结果特征，文献[20]指出方案还存在查询结果不准确的问题.

本文在静态SHVE定义的基础上，给出了支持动态数据更新的动态对称隐藏向量加密（dynamic SHVE, DSHVE）的定义，并结合ODXT方案，构造了一种具有结果特征隐藏的连接查询动态对称可搜索加密方案DSHVE-ODXT，重点在3个方面开展了相关研究：

1）构造了支持动态数据更新的SHVE方案. 结合静态SHVE的定义，给出了支持动态更新操作SHVE的定义. 在此基础上，构造了一种满足可搜索加密应用需求的DSHVE方案.

2）构造了支持动态连接查询的对称可搜索加密方案. 在DSHVE方案的基础上，通过引入ODXT，设计了前/后向隐私的向量存取结构，构造了一种基于DSHVE的连接查询动态对称可搜索加密方案DSHVE-ODXT. 方案保持了对称可搜索加密搜索效率高的特点，同时支持动态更新操作和连接查询，具有更好的实用性.

3）对DSHVE-ODXT方案进行了分析与测试. 结合该方案工作过程，从性能和安全性2个方面对该方案进行了理论分析，并在此基础上对方案的执行性能进行详细测试与分析.

1.   基础知识

为方便描述，有关的通用符号定义如表1所示.

表  1  符号定义

Table  1.  Definition of Notations

符号	含义
$\lambda$	安全参数
$id$	文档标识
$w$	关键词
$EDB$	密文索引数据库
$q$	多关词连接查询语句
$op$	更新操作，$op\in \{\mathrm{a}\mathrm{d}\mathrm{d},\mathrm{d}\mathrm{e}\mathrm{l}\}$
$stoken$	单关键词搜索令牌
$xtoken$	交叉搜索令牌
$xtag$	XSet中交叉标签
$K$	密钥
$negl\left(\lambda \right)$	安全参数$\lambda$上的可忽略函数
$\left[n\right]$	集合$\{1,2,… ,n\}$
$\left|x\right|$	$x$中元素的个数
$\mathit{Pr}\left[A\right]$	事件A发生的概率

下载: 导出CSV 

| 显示表格

1.1   判定性Diffie-Hellman假设

定义1. 判定性Diffie-Hellman假设. 设$\mathcal{G}$是阶为大素数$p$的群，$g$为群$\mathcal{G}$通过均匀采样确定的生成元. 判定性Diffie-Hellman假设定义为对所有多项式时间算法$\mathcal{A}$，有

其中$\alpha ,\beta ,\gamma \stackrel{\$}{\leftarrow }{\mathbb{Z}}_{p}^{*}$，简称DDH假设.

1.2   对称加密算法

定义2. 对称加密算法^[21]. 设明文空间${\mathcalfont\text{M}}$、密钥空间${\mathcal{K}}$和密文空间$\mathcal{C}$，称3个多项式时间算法组成的三元组$(Gen,Enc,Dec)$为对称加密算法，其中：

1）$k\leftarrow Gen\left({1}^{\lambda }\right)$. 输入秘密参数$\lambda$，输出密钥$k\in \mathcal{K}$.

2）$ct\leftarrow Enc(k,mt)$. 输入密钥$k$、明文消息$mt$，输出密文$ct\in \mathcal{C}$.

3）$mt\leftarrow Dec(k,ct)$. 输入密钥$k$、密文$ct$，成功解密输出$ct$对应明文$mt$，否则输出$\perp$.

定义3. 正确性^[21]. 若算法对任意明文$mt\in \mathcalfont\text{M}$，$k\leftarrow Gen\left({1}^{\lambda }\right)$且$c\leftarrow Enc(k,mt)$，满足

则称对称加密算法满足正确性条件.

1.3   动态对称可搜索加密方案

定义4. 动态对称可搜索加密方案. 设数据库由$DB={({id}_{i},{W}_{i})}_{i=1}^{d}$文档地址和关键词集构成，其中${id}_{i}$为第$i$文档，${W}_{i}$为文档$i$包含的关键词集合，$d$为数据库中文档的数量，称三元组概率多项式时间算法$\left(Setup,U pdate,Search\right)$为一个动态对称可搜索加密方案，其中：

1）初始化算法$(K,\sigma ,EDB)\leftarrow Setup\left({1}^{\lambda },DB\right)$. 算法输入安全参数$\lambda$和明文索引数据库$DB$，输出密钥$K$、关键词状态$\sigma$和密文的检索索引数据库EDB. 在动态对称可搜索加密方案中，通常设$EDB=\varnothing$.

2）更新算法$(ED{B}',{\sigma }')\leftarrow U pdate({K}\text{,}\text{}\sigma \text{,}{w,}ind\text{,}op;$ $EDB)$. 输入密钥$K$、关键词状态$\sigma$、更新关键词$w$及对应索引$ind$，更新操作类型$op$，其中$op\in \left\{\mathrm{a}\mathrm{d}\mathrm{d},\mathrm{d}\mathrm{e}\mathrm{l}\right\}$，输出更新后密文索引数据库$EDB'$、关键词状态${\sigma' }$.

3）查询算法$DB\left(w\right)\leftarrow Search\left(K,\mathrm{\sigma },w;EDB\right)$. 输入密钥$K$、关键词状态$\sigma$和检索关键词$w$，输出包含检索关键词$w$的所有文档标识$DB\left(w\right)$. 通常该算法包含客户端生成查询令牌和服务器根据令牌搜索查询结果2部分.

定义5. 正确性^[19]. 对任意数据库$DB$，任意查询$q$，$Search$算法除可忽略概率外，均输出$DB\left(q\right)$，则称动态对称可搜索加密方案满足正确性条件.

2.   动态对称隐藏向量加密（DSHVE）

隐藏向量加密能够实现整体结果特征隐藏，且支持灵活的连接查询和较高的查询效率. 在正式开始对称可搜索加密方案构造前，首先给出支持动态更新隐藏向量加密的形式化定义，进而详细介绍一种动态对称可搜索加密的构造方法.

2.1   形式化定义

设$\varSigma$为属性的有限集，$*$为不包含在集合Σ的通配符，表示“不关心”的值. 设${\varSigma }_{*}=\varSigma \cup \left\{*\right\}$，其中$\varSigma$的典型值为有限域${\mathbb{Z}}_{p}$（p为素数）.

设${\mathcal{P}}^{\mathrm{S}\mathrm{H}\mathrm{V}\mathrm{E}}：{\varSigma }^{m}\to \left\{\mathrm{0,1}\right\}$表示一个谓词族，在所有${{\boldsymbol{v}}}=({v}_{1},{v}_{2},… ,{v}_{m})\in {\varSigma }_{*}^{m}$中存在谓词${P}_{{\boldsymbol v}}^{\mathrm{S}\mathrm{H}\mathrm{V}\mathrm{E}}\in {\mathcal{P}}^{\mathrm{S}\mathrm{H}\mathrm{V}\mathrm{E}}$，满足对属性向量${{\boldsymbol{x}}}=({x}_{1},{x}_{2},… ,{x}_{m})\in {\varSigma }^{m}$，有

即在所有非通配符$*$对应向量${\boldsymbol x}$与${\boldsymbol v}$匹配. 参数$m$代表SHVE的宽度.

定义6. DSHVE. DSHVE定义为4个概率多项式时间（probabilistic polynomial-time，PPT）算法的集合：

1）$msk\leftarrow Setup\left(\lambda \right)$. 输入安全参数$\lambda$，输出主密钥$msk$，并定义消息空间$\mathcalfont\text{M}$，初始化属性向量${{\boldsymbol{x}}}$和密文集合$c$.

2）$c\mathrm{{'}}\leftarrow U pdateEnc(msk,\mu \in \mathcalfont\text{M},c,p,op\in \{\mathrm{a}\mathrm{d}\mathrm{d},\mathrm{d}\mathrm{e}\mathrm{l}\left\}\right)$. 输入主密钥$msk$、消息$\mu$、当前密文集合$c$、更新元素在索引向量${{\boldsymbol{x}}}$中的位置$p$以及更新操作$op$，输出更新后对应密文$c\mathit{{'}}$.

3）${{\boldsymbol{s}}}\leftarrow KeyGen(msk,{{\boldsymbol{v}}}\in {\varSigma }_{*}^{m})$. 输入谓词向量${\boldsymbol v}$，主密钥$msk$，输出解密密钥${{\boldsymbol{s}}}$.

4）$\mu \leftarrow Query({{\boldsymbol{s}}},c)$. 输入属性向量${\boldsymbol x}$对应密文$c$，谓词向量${\boldsymbol v}$对应解密密钥${{\boldsymbol{s}}}$，如果${P}_{{\boldsymbol v}}^{\mathrm{S}\mathrm{H}\mathrm{V}\mathrm{E}}\left({{\boldsymbol{x}}}\right)=1$，输出消息$\mu$.

定义7. 正确性. 设DSHVE表示一个动态对称隐藏向量加密方案，若对所有安全参数$\lambda$，所有$(\mu ,{{\boldsymbol{x}}})\in \mathcalfont\text{M}\times {\varSigma }^{m}$和谓词向量${\boldsymbol v}$，首先执行$DS HVE.\;Setup\left(\lambda \right)$获得$msk$，反复运行$U pdateEnc(msk,\mu \in \mathcalfont\text{M},c,p,op\in \{\mathrm{a}\mathrm{d}\mathrm{d}, \mathrm{d}\mathrm{e}\mathrm{l}\})$后最终获得$c$，$KeyGen(msk,{{\boldsymbol{v}}}\in {\varSigma }_{*}^{m})$获得$\boldsymbol{s}$，如果${P}_{{\boldsymbol v}}^{\mathrm{S}\mathrm{H}\mathrm{V}\mathrm{E}}\left({{\boldsymbol{x}}}\right)=1$，则$Query\left({{\boldsymbol{s}}},c\right)=\mu$，否则

则称DSHVE满足正确性条件.

DSHVE的安全性是通过真实实验和理想实验的不可区分性来定义的. 结合定义5，给出真实实验和理想实验的详细过程.

1）真实实验. 实验包括挑战者和自适应PPT攻击者$\mathcal{A}$，其交互过程为：

① Setup阶段. 挑战者选择安全参数$\lambda$，运行$S etup\left(\lambda \right)$输出$msk$和明文空间${\mathcalfont\text{M}}$. 并将$\mathcalfont\text{M}$发送给攻击者$\mathcal{A}$.

攻击者$\mathcal{A}$自适应选择执行更新阶段或查询阶段1.

②更新阶段. 攻击者$\mathcal{A}$自适应选择位置$p$（$p\in \left[m\right]$）以及更新操作$op$，并将元组$(p,op)$发送给挑战者. 挑战者接收$(p,op)$，执行$U pdateEnc$，返回攻击者$\mathcal{A}$更新后的密文$c\mathrm{{'}}$.

③查询阶段1. 攻击者$\mathcal{A}$自适应选择谓词向量${{{\boldsymbol{v}}}}_{j}$，$j\in \left[{q}_{1}\right]$. 挑战者利用${{{\boldsymbol{v}}}}_{j}$和$msk$运行$KeyGen$，返回相应的解密密钥${{{\boldsymbol{s}}}}_{j}$.

设在这一阶段攻击者$\mathcal{A}$一共执行了$q$次查询操作，接着攻击者$\mathcal{A}$执行挑战阶段和查询阶段2.

④挑战阶段. 攻击者$\mathcal{A}$输出消息$\mu \in \mathcalfont\text{M}$. 挑战者利用$msk$，${{\boldsymbol{x}}}$，$\mu$运行$U pdateEnc$，得到密文$c$并发送给$\mathcal{A}$.

⑤查询阶段2. 攻击者$\mathcal{A}$运行与查询阶段1相同的协议，收到${{{\boldsymbol{s}}}}_{j}$，$q+1\le j{\le q}_{2}$.

设${r}_{\mathcal{A}}$表示$\mathcal{A}$在真实实验中生成的随机比特，使用符号${View}_{\mathcal{A},\mathrm{R}\mathrm{e}\mathrm{a}\mathrm{l}}$表示在上述真实实验中攻击者$\mathcal{A}$所获得的有用信息$(\mathcalfont\text{M},c,{\left\{{{{\boldsymbol{v}}}}_{j}\right\}}_{j\in {q}_{2}},{r}_{\mathcal{A}})$.

2）理想实验. 实验包括PPT模拟器$\mathcal{S}$和自适应PPT攻击者$\mathcal{A}$，模拟器$\mathcal{S}$与攻击者$\mathcal{A}$交互过程为：

① Setup阶段. 挑战者选择安全参数$\lambda$，模拟器$\mathcal{S}$均匀随机选择$msk\stackrel{\$}{\leftarrow }{\left\{\mathrm{0,1}\right\}}^{\lambda }$，定义明文空间$\mathcalfont\text{M}$，并将$\mathcalfont\text{M}$发送给攻击者$\mathcal{A}$.

攻击者$\mathcal{A}$自适应选择执行更新阶段或查询阶段1.

②更新阶段. 攻击者$\mathcal{A}$自适应选择位置$p$（$p\in \left[m\right]$）以及更新操作$op$. 模拟器$\mathcal{S}$接收$(p,op)$，返回攻击者$\mathcal{A}$新的密文$c\mathrm{{'}}$.

③查询阶段1. 攻击者$\mathcal{A}$自适应选择谓词向量${{{\boldsymbol{v}}}}_{j}$，$j\in \left[{q}_{1}\right]$. 模拟器$\mathcal{S}$返回对应的解密密钥${{{\boldsymbol{s}}}}_{j}$.

设在这一阶段攻击者$\mathcal{A}$一共执行了$q$次查询操作，接着攻击者$\mathcal{A}$执行挑战阶段和查询阶段2.

④挑战阶段. 攻击者$\mathcal{A}$输出消息$\mu \in \mathcalfont\text{M}$. 模拟器$\mathcal{S}$返回${{\boldsymbol{x}}}$和$\mu$对应的挑战密文$c$.

⑤查询阶段2. 攻击者$\mathcal{A}$运行与查询阶段1相同的协议，收到${{{\boldsymbol{s}}}}_{j}$，$q+1\le j{\le q}_{2}$.

同样，设${r}_{\mathcal{A}}$表示$\mathcal{A}$在理想实验中生成的随机比特，使用符号${View}_{\mathcal{A},\mathcal{S}}$表示在理想实验中攻击者$\mathcal{A}$所获得的有用信息$(\mathcalfont\text{M},c,{\left\{{{{\boldsymbol{v}}}}_{j}\right\}}_{j\in {q}_{2}},{r}_{\mathcal{A}})$.

定义8. 自适应安全. 设$\mathrm{D}\mathrm{S}\mathrm{H}\mathrm{V}\mathrm{E}$表示一个动态对称隐藏向量加密方案，对任意PPT攻击者$\mathcal{A}$分辨真实实验和理想实验中所取得的攻击优势为${Adv}_{\mathcal{A}}^{\mathrm{D}\mathrm{S}\mathrm{H}\mathrm{V}\mathrm{E}}\left(\lambda \right)=|Pr[{Real}_{\mathcal{A}}\left(\mathrm{\lambda }\right)=1\left]\right|-|Pr[{Idea}_{\mathcal{A},\mathcal{S}}\left(\mathrm{\lambda }\right)=1\left]\right|$，若存在一个模拟器$\mathcal{S}$，对所有PPT攻击者$\mathcal{A}$，函数${Adv}_{\mathcal{D},\mathcal{A}}^{\mathrm{D}\mathrm{S}\mathrm{H}\mathrm{V}\mathrm{E}}\left(\lambda \right)$在安全参数$\lambda$下是可忽略的，则称DSHVE是自适应安全的.

2.2   详细构造

设$\lambda$为安全参数，${F}_{0}： {\left\{\mathrm{0,1}\right\}}^{\lambda }\times {\left\{\mathrm{0,1}\right\}}^{\lambda +\mathrm{lb}\lambda } \to {\left\{\mathrm{0,1}\right\}}^{\lambda +\mathrm{lb}\lambda }$为一个伪随机函数（pseudo random function, PRF），$(S ym. Enc,S ym.Dec)$表示一个IND-CPA安全的对称加密方案，其中密钥空间和明文空间均为${\left\{\mathrm{0,1}\right\}}^{\lambda +\mathrm{lb}\lambda }$. ${{\boldsymbol{x}}}=({x}_{1},{x}_{2},… , {x}_{m})\in {\varSigma }_{*}^{m}$表示一个宽度为$m$的属性向量，$op\in \{\mathrm{a}\mathrm{d}\mathrm{d},\mathrm{d}\mathrm{e}\mathrm{l}\}$表示对属性向量的添加和删除操作. 定义与${{\boldsymbol{x}}}$对应的密文集合$c=\left\{{\left\{{c}_{l}\right\}}_{op,l\in \left[m\right]}\right\}= \{{\left\{{c}_{l}\right\}}_{\mathrm{a}\mathrm{d}\mathrm{d},l\in \left[m\right]}\cup{\left\{{c}_{l}\right\}}_{\mathrm{d}\mathrm{e}\mathrm{l},l\in \left[m\right]}\}$，即集合$c$由添加操作密文集合${\left\{{c}_{l}\right\}}_{\mathrm{a}\mathrm{d}\mathrm{d},l\in \left[m\right]}$和删除更新的密文集合${\left\{{c}_{l}\right\}}_{\mathrm{d}\mathrm{e}\mathrm{l},l\in \left[m\right]}$组成，最多可包含$2m$个元素.

在动态对称可搜索加密的应用场景中，文档索引的更新过程通常是先执行添加操作，然后在之后的某个时间执行删除操作. 因此不妨设向量${\boldsymbol x}$中的元素${x}_{l}$（$l\in \left[m\right]$）满足的删除操作总是在添加操作之后发生. 支持动态更新操作的DSHVE的详细构造过程为：

1）$(msk,\mathcalfont\text{M})\leftarrow Setup({1}^{\lambda },m)$. 输入安全参数$\lambda$，SHVE宽度$m$，通过算法均匀采样得到$msk\stackrel{\$}{\leftarrow }{\left\{\mathrm{0,1}\right\}}^{\lambda }$，并定义明文空间$\mathcalfont\text{M}=\left\{{}^\backprime \mathrm{T}\mathrm{r}\mathrm{u}\mathrm{e}^\prime\right\}$，${{\boldsymbol{x}}}=\left({x}_{1},{x}_{2},… ,{x}_{i},… ,{x}_{m}\right)$，其中${x}_{i\in \left[m\right]}=*$，$c=\left\{{\left\{{c}_{l}=\perp \right\}}_{l\in \left[2m\right]}\right\}$，输出$(msk,\mathcalfont\text{M})$.

2）${c}' \leftarrow U pdateEnc(msk,\,\mu {=}{}^\backprime \mathrm{T}\mathrm{r}\mathrm{u}\mathrm{e}^\prime,\, c=\{{\{{c}_{l}\}}_{op,l\in [2m]}\},$ $p \in [m], op\in \{\mathrm{a}\mathrm{d}\mathrm{d},\mathrm{d}\mathrm{e}\mathrm{l}\})$. 输入主密钥$msk$、消息$\mu$、当前密文$c$和待更新的索引位置$p$、更新操作$op$，计算：

输出更新后的密文${c}'=\left\{{\left\{{c}_{l}\right\}}_{op,l\in \left[m\right]\backslash p}\right\}\cup \left\{{c}_{op,p}\right\}$，即相比输入密文$c$，$c{'}$更新索引位置$p$处的元素为${c}_{op,p}$，其他元素保持不变，且从${c}_{p}$的计算过程可以看出，${c}_{p}$取值与该元素的历史状态无关. 未对索引向量${{\boldsymbol{x}}}\in {\mathrm{\varSigma }}_{*}^{m}$对应位置进行插入操作时，其对应密文元素为$\perp$.

3）${{\boldsymbol{s}}}\leftarrow KeyGen(msk,{{\boldsymbol{v}}}\in {\varSigma }_{*}^{m})$. 输入谓词向量${{\boldsymbol{v}}}=({v}_{1}, … ,{v}_{m})$和主密钥$msk$，若用$S=\{{l}_{j}\in [m\left]\right|{v}_{{l}_{j}}\ne *\}$表示${\boldsymbol v}$中不包含通配符的位置集合，设这些位置中${l}_{1} < {l}_{2} < … < {l}_{\left|S\right|}$，算法均匀样本$K\stackrel{\$}{\leftarrow }{\left\{\mathrm{0,1}\right\}}^{\lambda +\mathrm{lb}\lambda }$，计算

算法最终输出解密密钥：

4）${}^\backprime \mathrm{T}\mathrm{r}\mathrm{u}\mathrm{e}^\prime$或$\perp \leftarrow Query({{\boldsymbol{s}}},c)$. 查询算法输入为密文和解密密钥，并对变量进行编译：

其中$S=\{{l}_{1} < {l}_{2} < … < {l}_{\left|S\right|}\}$. 计算：

然后解密算法计算

若${\mu }'={0}^{\lambda +\mathrm{lb}\lambda }$，算法输出${}^\backprime \mathrm{T}\mathrm{r}\mathrm{u}\mathrm{e}^\prime$，否则输出$\perp$.

从解密计算过程可以看出，$\mu'$与元素在密文集合$c$的位置无关.

正确性证明过程为：

证明. 设与密文$c=\left\{{\left\{{c}_{l}\right\}}_{op,l\in \left[m\right]}\right\}$对应的索引向量${{\boldsymbol{x}}}= ({x}_{1},{x}_{2},… ,{x}_{m})$，且${{\boldsymbol{s}}}=({d}_{0},{d}_{1},S)$为谓词向量${{\boldsymbol{v}}}=({v}_{1},{v}_{2},… , {v}_{m})$对应的解密密钥. 则根据$U pdateEnc$算法工作过程可知：

若${x}_{i}=*$，则${c}_{\mathrm{a}\mathrm{d}\mathrm{d},i}={c}_{\mathrm{d}\mathrm{e}\mathrm{l},i}=\perp$；

若${x}_{i}=1$，则${c}_{\mathrm{d}\mathrm{e}\mathrm{l},i}=\perp$，因此${c}_{\mathrm{a}\mathrm{d}\mathrm{d},i}\oplus {c}_{\mathrm{d}\mathrm{e}\mathrm{l},i}={F}_{0}(msk,1\|i)= {F}_{0}(msk,{x}_{i}\|i)$；

若${x}_{i}=0$，则${c}_{\mathrm{a}\mathrm{d}\mathrm{d},i}\oplus {c}_{\mathrm{d}\mathrm{e}\mathrm{l},i}={F}_{0}(msk,1\|i)\oplus {F}_{0}(msk,1\|i)\oplus {F}_{0}(msk,0\|i) ={F}_{0}(msk,0\|p)={F}_{0}(msk,{x}_{i}\|i) \text{，}$

即${x}_{i}$经过添加和删除操作后对应实际密文元素${c}_{i}$满足

设$S=\{{l}_{1},{l}_{2},… ,{l}_{\left|S\right|}\}$，则：

1）若${P}_{{\boldsymbol v}}^{\mathrm{S}\mathrm{H}\mathrm{V}\mathrm{E}}\left({{\boldsymbol{x}}}\right)=1$，则对所有$j\in \left[\right|S\left|\right]$必须满足${v}_{{l}_{j}}={x}_{{l}_{j}}$，那么

由于${x}_{{l}_{j}}={v}_{{l}_{j}}\ne *$，则对所有$j\in \left[\right|S\left|\right]$均有${c}_{{l}_{j}}={F}_{0}(msk, {x}_{{l}_{j}}\|{l}_{j})={F}_{0}(msk,{v}_{{l}_{j}}\|{l}_{j})$，

即${K}'=\left({\oplus}_{j\in \left[\right|S\left|\right]}{c}_{op,{l}_{j}}\right)\oplus{d}_{0}=\left({\oplus}_{j\in \left[\right|S\left|\right]}{c}_{{l}_{j}}\right)\oplus{d}_{0}=K$.

因此，${\mu }'=S ym.Dec\left({K}',{d}_{1}\right)={0}^{\lambda +\mathrm{log}\lambda }$ 成立.

2）若${P}_{{\boldsymbol v}}^{\mathrm{S}\mathrm{H}\mathrm{V}\mathrm{E}}\left({\boldsymbol x}\right)=0$，则存在$j\in \left[\right|S\left|\right]$，满足${v}_{{l}_{j}}\ne {x}_{{l}_{j}}$，则

若${x}_{{l}_{j}}=*$，则${c}_{{l}_{j}}=\perp \ne {F}_{0}(msk,{v}_{{l}_{j}}\|{l}_{j})$；

若${x}_{{l}_{j}} \ne *$且${x}_{{l}_{j}} \ne {v}_{{l}_{j}}$，则${c}_{{l}_{j}} = {F}_{0}(msk,{x}_{{l}_{j}}\|{l}_{j}) \ne {F}_{0}(msk, {v}_{{l}_{j}}\|{l}_{j})$成立，即存在$j\in \left[\right|S\left|\right]$，使$\left({\oplus}_{j\in \left[\right|S\left|\right]}{c}_{\mathrm{a}\mathrm{d}\mathrm{d},{l}_{j}}\right)\oplus \left({\oplus}_{j\in \left[\right|S\left|\right]}{c}_{\mathrm{d}\mathrm{e}\mathrm{l},{l}_{j}}\right)\ne {F}_{0}(msk,{v}_{{l}_{j}}\|{l}_{j})$成立，进而使得解密时${K}'\ne K$. 因此除非发生可忽略的事件，否则${\mu }'\ne {0}^{\lambda +\mathrm{lb}\lambda }$，解密算法返回失败标志$\perp$.

即DSHVE满足正确性条件. 证毕.

3.   方案构造

结合DSHVE方案的详细构造过程，设计一种支持连接查询的动态对称可搜索加密方案DSHVE-ODXT，本节从该方案总体结构、TSet和XSet结构等方面介绍方案的设计思想，详细描述方案的工作过程.

3.1   方案总体结构

DSHVE-ODXT由一个代表数据拥有者和使用者的客户端和一个服务器组成. 其中客户端能够将用户数据加密成密文，并动态更新至密文服务器. 服务器根据用户请求，执行密文搜索操作，并向客户端返回搜索结果. 假设服务器为“诚实且好奇”的，即服务器能够忠实运行客户的请求，但会尽可能窥探用户的隐私信息.

DSHVE-ODXT以关键词$w$为索引的TSet结构和以文档$id$为索引的XSet结构组成，其中TSet主要用于实现安全的动态单关键词查询，XSet则主要用于实现连接查询. 图1所示为一个连接查询工作过程示意图.

图  1  连接查询过程

Figure  1.  The process of conjunctive queries

下载: 全尺寸图片 幻灯片

客户端一次接受用户输入多个连接查询关键词序列$q=({w}_{1}\wedge {w}_{2}\wedge … \wedge {w}_{n})$，从查询序列中选择更新次数最少的关键词，不失一般性，可设关键词序列$q$中更新次数最少的关键词为${w}_{1}$，则客户端为${w}_{1}$生成TSet查询令牌$stoken$，并为其他关键词$({w}_{2},{w}_{3},… ,{w}_{n})$分别生成XSet添加和删除操作查询令牌$(xtoke{n}_{2}, xtoke{n}_{3},… ,xtoke{n}_{i},… )$，将$stoken$与$(xtoke{n}_{2},xtoke{n}_{3},… , xtoke{n}_{i},… )$合并发送至服务器. 服务器根据相应令牌执行搜索算法，计算满足条件的结果文件集合，并将结果返回客户端.

3.2   不经意动态交叉标签

在构造支持动态连接查询方案前，首先给出一种记录更新状态的数据结构，即动态交叉标签（dynamic cross-tags，DXT）.

定义9. DXT. 设关键词$w$、文档标识$id$通过每个索引关键词对$(id,w)$能够计算得到一个唯一的存储标签${xtag}_{id,w}$，且标签${xtag}_{id,w}$代表的位置存储3种值：

① $(\perp ,\perp )$表示$(id,w)$没有插入和删除操作，

② $({c}_{\mathrm{a}\mathrm{d}\mathrm{d}},\perp )$表示$(id,w)$插入后未删除，

③ $({c}_{\mathrm{a}\mathrm{d}\mathrm{d}},{c}_{\mathrm{d}\mathrm{e}\mathrm{l}})$表示$(id,w)$插入后删除.

其中$\perp$表示对应标签取值为空，${c}_{\mathrm{a}\mathrm{d}\mathrm{d}}$和${c}_{\mathrm{d}\mathrm{e}\mathrm{l}}$分别表示插入和删除操作时写入的操作标志. 这种记录数据操作标签数值对称为DXT.

为了隐藏数据不同操作类型之间的对应关系，即隐藏“删除操作删除了哪个添加操作”信息，为DXT中每类操作标志${c}_{op}\in \{{c}_{\mathrm{a}\mathrm{d}\mathrm{d}},{c}_{\mathrm{d}\mathrm{e}\mathrm{l}}\}$定义一个对应的数据标签${xtag}_{id,w,op}$.

设$g$是素数阶$p$的群$\mathcal{G}$上的生成元，${F}_{p}$是${\mathbb{Z}}_{p}^{\mathrm{*}}$上的PRF，${K}_{X}$和${K}_{Y}$是均匀采样得到的PRF伪随机函数${F}_{p}$的密钥，操作$op\in \{\mathrm{a}\mathrm{d}\mathrm{d},\mathrm{d}\mathrm{e}\mathrm{l}\}$表示数据插入和删除操作，关键词$w$的第$cnt$次更新操作$(op,\left(id,w\right))$对应数据标签${xtag}_{id,w,op}$计算方式为

这里${xtag}_{id,w,op}$的计算过程与$(op,\left(id,w\right))$相关. 文档关键词对$(id,w)$的添加数据标签和删除数据标签分别记为${xtag}_{id,w,\mathrm{a}\mathrm{d}\mathrm{d}}$和${xtag}_{id,w,\mathrm{d}\mathrm{e}\mathrm{l}}$.

在此基础上，引入盲指数（blinded exponentiations），定义交叉搜索令牌$xtoken$和盲因子$\alpha$，设计一种标签盲化的不经意动态交叉标签，进一步减少交叉搜索时的通信次数和需要传递和通信令牌数量. 设计的核心思想是使交叉搜索令牌$xtoken$的计算仅与搜索关键词相关，而与具体的文档无关. 这样通过统一的交叉搜索令牌$xtoken$结合存储在服务器上的盲因子$\alpha$，计算得到所有文档的实际数据标签.

若客户端在插入新元素时记录并更新当前关键词的插入次数$U pdateCnt$，服务器插入关键词信息时，在TSet结构中存储盲元素${\alpha }_{id,w,op}={F}_{p}({K}_{Y},id\|op)\cdot {({F}_{p}({K}_{Z},w\|cnt))}^{-1}$. 若用$q=({w}_{1}\wedge {w}_{2}\wedge … \wedge {w}_{n})$表示连接查询关键词，且${w}_{1}$对应更新次数$cnt$最少，查询时客户端根据查询关键词计算查询令牌

其中$i\in \{\mathrm{2,3},… ,n\}$. 这里${xtoken}_{i,cnt}$计算与具体文档无关.

服务器接收到查询令牌${xtoken}_{i,cnt}$后，计算

恢复动态交叉标签中对应的数据地址${xtag}_{id,w,op}$.

3.3   关键结构

DSHVE-ODXT方案采用2个专门设计的数据存取结构实现单关键词和交叉多关键词查询，即TSet和XSet结构.

1）TSet设计

TSet为一个以关键词为索引组成的“倒排索引”结构，实现前向/后向隐藏的动态单关键词搜索，其核心数据为一个数据集合，记为$tset$. 图2所示为服务器上存储的以关键词${w}_{i}$为索引，更新次数为$cnt$的文档列表，其中$stoken$表示客户端发送的与查询关键词对应的搜索令牌，每个文档节点${id}_{ij}$除存储单关键词搜索相关的信息$val$外，还需要额外存储支持XSet查询的盲因子${\alpha }_{j,op}$.

图  2  TSet数据存储结构

Figure  2.  The storage structure of TSet data

下载: 全尺寸图片 幻灯片

关键词${w}_{i}$的第$j$次更新文档对应盲因子${\alpha }_{j,op}$按如下方式计算：

2） XSet实现

XSet设计为一个存储标签-键值$(xtag,c)$对的存储空间，记为$xset$，其中$xset\left[xtag\right]=c$表示数据$c$写入数据集合$xset$，$c=xset\left[xtag\right]$表示从数据集$xset$中读取标签$xtag$对应数据$c$.

方案中实际存储数据的$xtag$即为ODXT中的DXT. 连接查询时，首先通过在XSet中恢复出ODXT值，然后运用动态对称隐藏向量加密搜索与整体匹配的结果文档集合，并返回匹配的结果集合. 图3所示为服务器利用XSet进行连接查询时的搜索过程.

图  3  服务器利用XSet进行连接查询时的搜索过程

Figure  3.  The search process when the server uses XSet for conjunctive queries

下载: 全尺寸图片 幻灯片

设${xtoken}_{i}$表示连接查询关键词序列$q=({w}_{1}\wedge {w}_{2}\wedge …\wedge {w}_{n})$中第$i$（$i\in \{\mathrm{2,3},… ,n\}$）个关键词${w}_{i}$的交叉查询令牌，${id}_{1j}$表示TSet中关键词${w}_{1}$对应列表的第$j$（$1\le j\le cnt$，$cnt$表示${w}_{1}$的更新次数）个文档节点，${\alpha }_{j,op}$表示XSet中${id}_{1j}$节点上存储的盲因子，则根据ODXT构造过程，可得

其中${xtag}_{i,j,\mathrm{a}\mathrm{d}\mathrm{d}}={\left({xtoken}_{i}\right)}^{{\alpha }_{j,\mathrm{a}\mathrm{d}\mathrm{d}}}$，${xtag}_{i,j,\mathrm{d}\mathrm{e}\mathrm{l}}={\left({xtag}_{i,j,\mathrm{a}\mathrm{d}\mathrm{d}}\right)}^{{\alpha }_{j,\mathrm{d}\mathrm{e}\mathrm{l}}}$.

针对${id}_{1j}$节点上存储的盲因子${\alpha }_{j,op}$计算所有${xtoken}_{i}$（$i\in \{\mathrm{2,3},… ,n\}$），并最终得到与文档索引${id}_{1j}$对应的所有DXT值.

3.4   方案描述

基于上述思想，DSHVE-ODXT由3个PPT算法Setup，Update，Search组成.

算法1. Setup算法：$EDB\leftarrow Setup\left(\lambda \right)$.

输入：安全参数$\mathrm{\lambda }$；

输出：空的密文数据库EDB.

客户端：

① 均匀随机采样得到PRF $F$的密钥${K}_{\mathrm{T}}$；

② 均匀随机采样得到PRF ${F}_{p}$的密钥${K}_{X}$，${K}_{Y}$， ${K}_{Z}$；

③ 均匀随机采样得到DSHVE的密钥${K}_{\mathrm{H}}$；

④ 初始化$st$，$tset$，$xset$为$\varnothing$；

⑤ 客户端保存$sk=\{{K}_{\mathrm{T}},{K}_{X},{K}_{Y},{K}_{Z},{K}_{\mathrm{H}}\}$，$st$；

⑥ 令$EDB=\{tset,xset\}$；

⑦ 发送$EDB$至服务器.

客户端接受输入安全参数$\lambda$，分别通过均匀随机采样，生成方案需要使用的密钥集$sk=\{{K}_{\mathrm{T}},{K}_{X},{K}_{Y}, {K}_{Z},{K}_{\mathrm{H}}\}$，置关键词状态集$st$、密文索引数据库$EDB= (tset,xset)$为$\varnothing$. $sk$，$st$直接存储在客户端，$EDB$发送至服务器保存.

算法2. Update算法：$(s{t}',EDB')\leftarrow U pdate(sk,st,$ $op, \left(id,w\right);EDB)$.

输入：客户端输入为方案密钥$sk$，关键词状态集$st$，更新操作类型$op$，文档关键词对$\left(id,w\right)$，服务器输入为密文索引数据库$EDB$；

输出：更新后的关键词状态集$st\mathrm{{'}}$和密文索引数据库$EDB\mathrm{{'}}$.

客户端：

① 编译得到$sk=\{{K}_{\mathrm{T}},{K}_{X},{K}_{Y},{K}_{Z},{K}_{\mathrm{H}}\}$，$st$；

② 若$st\left[w\right]$=$\varnothing$，则令$st\left[w\right]=(len\left(st\right),0)$；

③ 编译$st\left[w\right]$，得到${w}_{id},{w}_{cnt}$；

④ ${w}_{cnt}={w}_{cnt}+1$；

⑤ $st\left[w\right]=({w}_{id},{w}_{cnt})$；

⑥ $addr=F({K}_{\mathrm{T}},w\|{w}_{cnt}\|0)$；

⑦ $val=(id\|op)\oplus F({K}_{\mathrm{T}},w\|{w}_{cnt}\|1)$；

⑧ $\alpha ={F}_{p}({K}_{Y},id\|op){({F}_{p}({K}_{Z},w\|{w}_{cnt}))}^{-1}$；

⑨ $xtag={g}^{{F}_{p}\left({K}_{X},w\right){F}_{p}({K}_{Y},id\|op)}$；

⑩ if op=add

$c=F({K}_{H},1\|{w}_{id}) \text{；}$

⑪ else if op=del

计算$c=F({K}_{\mathrm{H}},1\|{w}_{id})\oplus F({K}_{\mathrm{H}},0\|{w}_{id})$；

end if

⑫ end if

⑬ 发送$(addr,val,\alpha ,(xtag,c\left)\right)$至服务器.

服务器：

① 编译得到$EDB=\{tset,xset\}$；

② $tset\left[addr\right]=(val,\alpha )$；

③ $xset\left[xtag\right]=c$.

客户端通过编译本地保存的密钥集$sk$和关键词集$st$，恢复方案各参数. 然后通过行⑥~⑧生成TSet中存储数据，即$tset\left[addr\right]=(val,\alpha )$，行⑨~⑫按照ODXT设计思想生成XSet中DXT，即$xset\left[xtag\right]=c$. 服务器接收到客户端发过来的相关参数后，直接更新密文索引数据库$EDB$.

算法3. $S earch$算法：$DB\left(q\right)\leftarrow S earch(sk,st,q;$ $EDB)$.

输入：客户端输入为方案密钥$sk$，关键词状态集$st$，连接查询$q$，服务器输入为密文索引数据库$EDB$；

输出：匹配的文档索引集$DB\left(q\right)$.

Step 1. 查询令牌生成.

客户端：

① 编译得到$sk=\{{K}_{\mathrm{T}},{K}_{X},{K}_{Z},{K}_{\mathrm{H}}\}$，$st$；

② 将谓词向量集合$S$初始化为$\varnothing$；

③ 通过$st$找到更新次数最少的关键词（不失一 般性，设为${w}_{1}$）；

④ 若查询序列$q=\left({w}_{1}\wedge {w}_{2}\wedge … \wedge {w}_{n}\right)$中存在关键 词不在$st$列表中，返回查询结果为$\varnothing$，否则 继续执行；

⑤ 通过编译$st$，得到每一个查询关键词${w}_{i}$的${w}_{i,id}$， 并添加至向量集$S$；

⑥ 将$stokenList$初始化为$\varnothing$；

⑦ 将${xtokenList}_{1},… ,{xtokenList}_{U pdateCnt\left[{w}_{1}\right]}$初始化为 空列表；

⑧ 编译$st\left[{w}_{1}\right]$，得到${w}_{1,id},{w}_{1,cnt}$；

⑨ for j=1 to ${w}_{1,cnt}+1$

${saddr}_{j}=F({K}_{\mathrm{T}},{w}_{1}\|j\|0) \text{；}$

$stokenList=stokenList\cup \left\{{saddr}_{j}\right\} \text{；}$

for $i=1$ to $n$

${xtoken}_{i,j}={g}^{{F}_{p}\left({K}_{X},{w}_{i}\right){F}_{p}({K}_{Z},{w}_{1}\|j)} \text{；}$

${xtokenList}_{j}={xtokenList}_{j}\cup \left\{{xtoken}_{i,j}\right\} \text{；}$

end for

随机选择一个位置插入${xTagList}_{j}$；

⑩ end for

⑪ 均匀随机采样得到对称加密密钥$K$；

⑫ 计算${d}_{0}={\oplus}_{j\in \left[\right|S\left|\right]}\left({F}_{0}(msk,{v}_{{l}_{j}}\|{l}_{j})\right)\oplus K$；

⑬ 计算${d}_{1}=S ym.Enc\left(K,{0}^{\lambda +\mathrm{l}\mathrm{b}\lambda }\right)$；

⑭ 发送到$(stokenList,{xtokenList}_{1},… ,{xtokenList}_{\left[{w}_{1}\right]},$

${d}_{0},{d}_{1})$服务器.

Step 2. 密文搜索.

服务器：

① 编译得到$EDB=\left(tset,xset\right)$和 $stokenList,xtokenLists,\boldsymbol{d}_0,\boldsymbol{d}_1$；

② 初始化$sEOpList$为空列表；

③ for $j=1$ to $stokenList.size$

${cnt}_{j}=1 \text{；}$

$\left({sval}_{j},{\alpha }_{j}\right)=tset\left[stokenList\right[j\left]\right] \text{；}$

初始化集合$S$为$\varnothing$；

for $i=1$ to $n$

${xtoken}_{i,j}={xtoken}_{j}\left[i\right] \text{；}$

计算${xtag}_{i,j}={\left({xtoken}_{i,j}\right)}^{{\alpha }_{j}}$；

$S=S\cup \left\{{xtag}_{i,j}\right\} \text{；}$

end for

计算$K{'}=\left({\oplus}_{j\in \left[\right|S\left|\right]}{c}_{op,{l}_{j}}\right)\oplus{d}_{0}$；

计算$\mu'=S ym.Dec(K',\boldsymbol{d}_1)$；

if ${\mu }'$=${0}^{\lambda +\mathrm{lb}\lambda }$

$sEOpList=sEOpList\cup \{j,{sval}_{j}\} \text{；}$

end if

④ end for

⑤ 发送$sEOpList$到客户端.

Step 3. 最终结果输出.

客户端：

① 初始化$IdList$为空列表；

② for $\mathcal{l}=1$ to $sEOpList.size$

令$\left(j,{sval}_{j}\right)=sEOpList\left[\mathcal{l}\right]$；

恢复$\left({id}_{j}\|{op}_{j}\right)={sval}_{j}\oplus F({K}_{T},{w}_{1}\|j\| 1)$；

$IdList=IdList\cup \left\{{id}_{j}\right\} \text{；}$

③ end for

④ 输出$IdList$.

多关键词的连接查询过程仅需进行1轮交叉就可实现，主要包括客户端生成查询令牌、服务器执行密文搜索和客户端输出最终结果3个步骤.

1）查询令牌生成（Step 1）. 客户端接受用户输入连接查询关键词$q$，利用本地保存的关键词状态集$st$，找出更新次数最少的关键词（不妨设为${w}_{1}$）. 若发现某个查询关键词${w}_{i}$不更新列表，即${w}_{i}\notin st$，则说明${w}_{i}$之前未执行过更新操作，因此直接返回查询结果为空（行④）.

通过$st$恢复连接查询$q$中对应的每个关键词${w}_{i}$的惟一标识，记为${w}_{i,id}$，存入谓词向量集合$S$中（行⑤），并在行⑪~⑬生成DSHVE解密密钥向量$({d}_{0},{d}_{1})$，与行⑨⑩生成的查询令牌一起，发送至服务器.

2）密文搜索（Step 2）. 服务器接收查询令牌和解密密钥向量后，按照ODXT设计思想，分别从XSet对应位置取出存储索引密文${sval}_{j}$和盲因子${\alpha }_{j}$，并与对应交叉令牌${xtoken}_{i,j}$恢复需要读取的TSet数据存储标签$xtag$，加入谓词向量集合$S$，并通过行③，执行DSHVE查询操作，返回符合查询条件的文档在TSet中的位置和密文数据.

3）最终结果输出（Step 3）. 客户端利用服务器返回的信息恢复出真实文档索引集合，并计算最终结果$IdList$，即$DB\left(q\right)$.

4.   方案分析

结合方案详细构造，从性能与安全性2个方面对其进行分析，其中性能分析包括服务器及客户端存储开销、通信开销和计算开销等，而安全性着重围绕方案更新泄露和搜索泄露的信息展开.

4.1   性能分析

存储开销、通信开销和计算开销是影响方案性能的重要因素，下面从这3个方面对方案的性能进行分析.

1）存储开销

方案的存储开销包括服务器和客户端2部分.

服务器在方案初始化阶段，实际存储的数据集$tset$和$xset$为$\varnothing$. 随后每执行一个更新操作，服务器需要在集合$xset$中存储$(addr,\left(val,\alpha \right))$，在集合$tset$中存储$(xtag,c)$，占用空间大小为方案执行更新操作次数的整数倍，即服务器存储开销约为$O\left({N}_{U pdate}\right)$，${N}_{U pdate}$为方案执行更新操作的次数.

客户端仅需要存储相关密钥集$sk$和关键词更新状态集$st$，其中$st$在方案初始化时为$\varnothing$，每新增一个索引关键词，需要为其分配一定存储空间. 因此客户端存储空间实际随密文索引关键词个数线性增加，即客户端存储空间开销约为$O\left({N}_{w}\right)$，其中${N}_{w}$为关键词个数.

2）通信开销

方案仅需经过1轮通信就可以完成支持连接查询的密文搜索，通信开销与连接查询中更新次数最少关键词${w}_{1}$的更新次数和查询关键词个数相关，即通信开销可表示为$O\left(n\right|U pdate\left({w}_{1}\right)\left|\right)$，其中$n$表示查询关键词个数，$\left|U pdate\right({w}_{1}\left)\right|$表示更新次数最少关键词${w}_{1}$的更新次数.

真实应用场景中，使用频率最低的关键词与更新次数最少关键词通常是一致的，因此在数据量较大时，通过选择更精确的查询关键词有望大大提高大数据集上的查询效率.

DSHVE构造过程中，服务器执行$DS HVE.Search$的查询算法，可以直接得到匹配查询的文档索引密文，不需要返回所有信息，这极大提高了返回时的通信量. 实际上在多关键词查询应用场景下，返回的文档索引数最大值为更新次数最少关键词${w}_{1}$的匹配文档数，即服务返回查询结果的通信开销上限可表示为$O\left(\right|U pdate\left({w}_{1}\right)\left|\right)$.

3）计算开销

由于在DSHVE中查询谓词向量${{\boldsymbol{v}}}$中非通配符位置相对索引向量${{\boldsymbol{x}}}$是稀疏排列的，即在大多数应用场景下，连接查询关键词的个数远小于当前数据库中关键词的个数. 因此DXT数据盲化处理和标签恢复时，指数运算次数仅为当前连接查询关键词数量的2倍（添加和删除操作），计算开销通常不大，具有较高的查询效率.

4.2   安全性

下面分别对DSHVE和DSHVE-ODXT的安全性进行分析.

4.2.1   DSHVE方案安全性

定理1. 设${F}_{0}$是安全的伪随机函数，对称加密方案$(S ym.Enc,S ym.Dec)$为一个理想的加解密算法，且属性向量删除更新操作总是在添加操作之后发生，则在随机预言机模型下DSHVE是自适应安全的.

证明. 通过一系列模拟实验，运用构造法证明DSHVE的安全性.

1）实验0. 该实验与真实实验完全相同，即挑战者分别执行$DS HVE.U pdateEnc$，$DS HVE.KeyGen$，$DS HVE. Query$算法实现更新、解密密钥生成和查询操作.

由于执行过程与真实方案完全相同，所以对PPT的分辨器$\mathcal{D}$有

2）实验1. 在实验0的基础上，每次执行更新操作时，挑战者将$DS HVE.U pdateEnc$中的${F}_{0}$用均匀采样的随机数代替. 设攻击者$\mathcal{A}$对位置为$p$的属性${x}_{p}$（$p\in \left[m\right]$）执行操作$op$（$op\in \{\mathrm{a}\mathrm{d}\mathrm{d},\mathrm{d}\mathrm{e}\mathrm{l}\}$），记为$(op,p)$.

若$op=\mathrm{a}\mathrm{d}\mathrm{d}$，挑战者直接通过均匀采样生成随机数${s}_{\rm add}\stackrel{\$}{\leftarrow }{\left\{\mathrm{0,1}\right\}}^{\lambda }$，并置${c}_{\mathrm{a}\mathrm{d}\mathrm{d},p}={s}_{\rm add}$；

若$op=\mathrm{d}\mathrm{e}\mathrm{l}$，挑战者首先查找${c}_{\mathrm{a}\mathrm{d}\mathrm{d}}$，得到${s}_{\rm add}={c}_{\mathrm{a}\mathrm{d}\mathrm{d},p}$，由于属性向量删除更新操作总是在添加操作之后，因此${s}_{\rm add}\ne \perp$，同时，挑战者均匀采样生成随机数${s}_{\rm del}\stackrel{\$}{\leftarrow }{\left\{\mathrm{0,1}\right\}}^{\lambda }$，计算${c}_{\mathrm{d}\mathrm{e}\mathrm{l},p}={s}_{\rm add}\oplus{s}_{\rm del}$. 即

其中${s}_{\rm add}$，${s}_{\rm del}$挑战者通过均匀采样生成2个随机数${s}_{\rm add}\stackrel{\$}{\leftarrow }{\left\{\mathrm{0,1}\right\}}^{\lambda }$，${s}_{\rm del}\stackrel{\$}{\leftarrow }{\left\{\mathrm{0,1}\right\}}^{\lambda }$. 最后挑战者计算密文集合${c}'=\{{\{{c}_{l}\}}_{op,l\in \left[m\right]\backslash p}\}\cup \{{c}_{op,p}\}$，并将${c}'$发送至攻击者$\mathcal{A}$.

设实验1中将PRF ${F}_{0}$输出用均匀采样的随机数代替，攻击者$\mathcal{A}$通过模拟器$\mathcal{B}1$所取得的优势记为${Adv}_{\mathcal{B}1,\mathcal{A}}^{\mathrm{P}\mathrm{R}\mathrm{F}}\left(\lambda \right)$，即在实验1中，攻击者所取得的攻击优势可表示为

3）实验2. 在实验1的基础上，解密密钥生成算法$SHVE.KeyGen$和$DS HVE.Query$算法中的挑战者将对称加密方案$(S ym.Enc,S ym.Dec)$用一个快速查询列表代替. 设攻击者$\mathcal{A}$自适应地选择谓词${P}_{{{\boldsymbol v}}_{j}}^{\mathrm{S}\mathrm{H}\mathrm{V}\mathrm{E}}$，$j\in \left[{q}_{2}\right]$，生成解密密钥时，挑战者随机采样$K\stackrel{\$}{\leftarrow }{\left\{\mathrm{0,1}\right\}}^{\lambda +\mathrm{l}\mathrm{b}\lambda }$. 然后，对$i\in \left[\right|{S}_{j}\left|\right]$，计算

最后挑战者向攻击者$\mathcal{A}$返回解密密钥

由于对称加密方案$(S ym.Enc,S ym.Dec)$为一个理想的加解密算法，算法的加解密输出与均匀采样随机数在计算上是不可区分的. 设对称加密方案输入用均匀采样随机数替换，攻击者$\mathcal{A}$通过模拟器$\mathcal{B}2$所取得的优势为${Adv}_{\mathcal{B}2,\mathcal{A}}^{Sym}\left(\lambda \right)$，则在实验2中

4）实验3. 按实验2方式构造模拟器$\mathcal{S}$并执行理想实验，可以看出攻击者在实验3中所取得的攻击优势与理想实验中相同，即

综合模拟器$\mathcal{B}1$，$\mathcal{B}2$可以构造出高效的模拟器$\mathcal{S}$，使得对于PPT的分辨器$\mathcal{D}$下，满足

即高效模拟器在安全参数$\lambda$下使攻击者$\mathcal{A}$在真实实验和理想实验中所取得的优势是可忽略的. 根据定义8可知，在随机预言机模型下DSHVE是自适应安全的.证毕.

4.2.2   DSHVE-ODXT方案安全性

方案初始化时，服务器存储信息为$\varnothing$，不会泄露任何信息，即${\mathcal{L}}^{S etup}=\perp$，泄露主要发生在数据动态更新和连接查询阶段，即方案的泄露函数$\mathcal{L}$可表示为

下面分别对2个阶段的信息泄露给出定性分析.

1）更新泄露${\mathcal{L}}^{U pdate}$

执行更新算法DSHVE-ODXT$.U pdate$实现对服务器上密文索引数据库EDB的$xset$和$tset$更新. 方案采用标签数据对的方式存储$xset$与$tset$中的数据，数据存储标签均采用PRF生成，既能够节省存储开销，也可以实现更新操作，与$xset$和$tset$的历史状态无关. 因此方案是前向隐私安全的.

设相关文档索引不会出现相同的更新操作，则利用PRF生成的数据标签也不会重复. 同时对于不同的更新操作，服务器均采用相同的处理过程，服务器无法通过操作过程和存储的数据差异分辨更新操作的类型.

2）搜索泄露${\mathcal{L}}^{S earch}$

从方案的搜索算法执行过程可以看出，通过设计DSHVE方案，使得连接查询结果中仅包含与连接查询相匹配的所有文档集合，有效避免了更多的KPRP信息泄露，有效提高了连接查询时方案的安全性. 同时，相比单关键词搜索方案，连接查询泄露${\mathcal{L}}^{S earch}$还包括：

①TSet访问泄露. 泄露更新次数最少关键词${w}_{1}$的更新操作次数及发生时间，且服务器通过跟踪TSet查询时访问的数据地址标签，可以发现2次查询中是否包含相同的关键词${w}_{1}$.

②XSet访问泄露. 泄露与当前查询相关的所有更新操作的次数及发生时间，以及通过监控XSet访问标签，发现2次不同查询结果是否包含相同的文档信息.

③输出泄露. 泄露与当前查询匹配的文档索引集合.

其中①③对单关键词查询方案也同样存在.

引理1. ODXT的安全性^[19]. 假设$F$和${F}_{p}$为安全的伪随机函数，且群$\mathcal{G}$上满足DDH假设，则ODXT是对于泄露函数${\mathcal{L}}_{\mathrm{O}\mathrm{D}\mathrm{X}\mathrm{T}}$自适应安全的. 其中泄露函数${\mathcal{L}}_{\mathrm{O}\mathrm{D}\mathrm{X}\mathrm{T}}$定义为

其中：

推论1. DSHVE-ODXT安全性. 假设$F$和${F}_{p}$为安全$\mathrm{P}\mathrm{R}\mathrm{F}\mathrm{s}$且群$\mathcal{G}$上满足DDH假设，${F}_{0}$是安全的伪随机函数，且在随机预言机模型下DSHVE和ODXT分别是自适应安全的，则DSHVE-ODXT对泄露函数${\mathcal{L}}_{\mathrm{D}\mathrm{S}\mathrm{H}\mathrm{V}\mathrm{E}-\mathrm{O}\mathrm{D}\mathrm{X}\mathrm{T}}$是自适应安全的.

从DSHVE-ODXT中连接查询的工作过程可以看出，方案可以分别构造2个模拟器${\mathcal{B}}_{\mathrm{D}\mathrm{S}\mathrm{H}\mathrm{V}\mathrm{E}}$和${\mathcal{B}}_{\mathrm{O}\mathrm{D}\mathrm{X}\mathrm{T}}$，并将算法中其他PRF用均匀采样的随机数代替，进而构造出方案的高效模拟器$\mathcal{S}$，使推论得以证明，详细证明过程在此不再赘述.

若用$q$表示包含$\left|q\right|$个关键词的连接关键查询语句，$\left|q\right|$表示$q$中包含关键词的个数，不妨设${w}_{1}$表示$q$中更新次数最少的关键词.${N}_{w}$表示关键词的个数，${N}_{U pdate}^{w}$表示关键词$w$的更新次数，${N}_{U pdate}$表示执行更新操作的总次数，${n}_{\mathrm{h}}$为Bloom过滤器中Hash函数的个数，DSHVE-ODXT与同类方案在性能和安全性方面的对比结果如表2所示.

表  2  方案对比

Table  2.  Comparison of Schemes

方案	动态更新	存储		通信轮数	计算	KPRP隐藏	查询结果
		客户端	服务器
OXT[9]	√		$\ {O}\left({N}_{U pdate}\right)$	2	$O\left(|q|{\times N}_{U pdate}^{{w}_{1}}\right)$	×	准确
BDXT[19]	√		${O}\left({N}_{U pdate}\right)$	2	$O\left(|q|\times {2N}_{U pdate}^{{w}_{1}}\right)$	×	准确
ODXT[19]	√		$O \left({N}_{U pdate}\right)$	1	$O\left(|q|\times {2N}_{U pdate}^{{w}_{1}}\right)$	×	不准确[15]
SHVE[14]	×		$\le O\left({n}_{\mathrm{hash}}{N}_{U pdate}\right)$	2	$O\left(|q|{\times N}_{U pdate}^{{w}_{1}}\right)$	√	准确
DSHVE-ODXT（本文）	√	$\ {O}\left({N}_{w}\right)$	$O\left({N}_{U pdate}\right)$	1	$O\left(|q|\times {2N}_{U pdate}^{{w}_{1}}\right)$	√	准确

下载: 导出CSV 

| 显示表格

5.   实验及结果分析

DSHVE-ODXT测试通过在物理机上安装的虚拟机实现，其中物理机处理器为Intel^® Core^TM i7-8550U，内存为8 GB，虚拟机硬件配置4核处理器、4 GB内存，操作系统为Ubuntu 18.08、编程语言为Python3.9.基于以上环境，从存储空间开销和搜索性能2个方面对方案进行测试. 其中涉及密码学算法均采用pycryptodome 3.14工具包实现，服务器密文索引数据库TSet和XSet采用支持标签访问的数据字典.

5.1   存储空间开销

Setup算法执行完毕后，反复执行Update算法，向服务器中添加密文索引，以字节形式将客户端数据和服务器密文索引数据库以字节形式保存，记录保存的文件大小，得到方案存储空间开销随更新操作次数的变化关系如图4所示.

图  4  存储空间开销的影响因素

Figure  4.  Influencing factors of storage space overhead

下载: 全尺寸图片 幻灯片

从图4可以看出，服务器存储空间开销与更新次数呈线性关系，相比于ODXT方案，DSHVE-ODXT方案存储空间开销略大，但仍在可承受范围内. DSHVE-ODXT客户端所需的存储空间开销较低，且与相同关键词的更新次数无关，而与索引中维护的关键词个数呈线性关系.

5.2   性能测试

DSHVE-ODXT方案单关键词、多关键词连接查询以及删除时的搜索性能测试结果如图5~7所示.

图  5  单关键词查询性能

Figure  5.  Performance of single keyword queries

下载: 全尺寸图片 幻灯片

图  6  连接查询性能

Figure  6.  Performance of conjunctive queries

下载: 全尺寸图片 幻灯片

图  7  删除操作对搜索时间的影响

Figure  7.  Effect of deletion operation on search time

下载: 全尺寸图片 幻灯片

1）单关键词查询

方案初始化完成后，按照先后顺序，通过更新算法向服务器分别添加关键词${w}_{1}$，${w}_{2}$，${w}_{3}$，使得${\left|U pdate\right({w}_{i}\left)\right|}_{i\in \{\mathrm{1,2},3\}}={10}^{5}$，$\left|U pdate\right({w}_{i}\left)\right|$表示${w}_{i}$的更新次数. 在更新过程中，对添加的关键词反复执行10次查询操作，记录结果返回时间，并计算查询平均时间$\overline{t}=\dfrac{\overline {ts}}{N}=\dfrac{ts/\left|{r}_{{w}_{i}}\right|}{N}$，其中$N=10$，$\left|{r}_{{w}_{i}}\right|$表示匹配文档索引集合中的元素个数，$ts$表示每次查询结果的总时间.

从图5可以看出，单关键词的查询响应总时间与该关键词的更新次数呈线性关系，与服务器中密文索引规模大小$\left|EDB\right|$无关.

2）多个关键词连接查询

方案初始化完成后，按照先后顺序，通过更新算法向服务器分别添加关键词${w}_{1}$，${w}_{2}$，${w}_{3}$，${w}_{4}$，使得${\left|U pdate\right({w}_{i}\left)\right|}_{i\in \{\mathrm{1,2},\mathrm{3,4}\}}={10}^{5}$，$\left|U pdate\right({w}_{i}\left)\right|$表示${w}_{i}$的更新次数. 在更新过程中，分别执行连接查询操作，反复执行10次记录查询结果返回时间，并按1）的方式计算平均查询时间，得到测试结果如图6所示.

可以看出，多关键词连接查询的平均查询时间随连接关键词个数的增加而增大，但连接查询结果文档包含${10}^{5}$个文档索引时的4个关键词的连接查询，其平均时间依然在3 ms左右，略大于ODXT方案，能够满足大部分应用场景对搜索性能的要求. 另外，由于方案的查询时间与服务器中密文索引规模大小$\left|EDB\right|$无关，从图6（c）（d）可以看出，连接查询时，最终方案的总查询时间与文档更新操作最少的关键词的更新次数有关. 在真实应用场景下，若能在连接查询中给出更精确的关键词，可以进一步提高最终查询结果的响应时间，提升方案的应用效果.

3）删除操作对操作性能影响

向密文数据库中加入3个密文索引${w}_{1}$，${w}_{2}$，${w}_{3}$，其中$\left|U pdate\right({w}_{1}\left)\right| = {10}^{5}$，$\left|U pdate\right({w}_{2}\left)\right| = 7\;000$，$\left|U pdate\right({w}_{3}\left)\right| = 5\;000$，然后执行方案的删除操作，并在删除后反复执行10次连接查询$q=({w}_{1}\wedge {w}_{2}\wedge {w}_{3})$，记录查询时间并取其平均值，得到测试结果如图7所示，其中关键词${w}_{3}$删除40%的文档索引后总查询时间基本保持不变，因为继续删除TSet中${w}_{3}$对应列表文档索引后，$\left|U pdate\left({w}_{3}\right)\right| > \left|U pdate\right({w}_{2}\left)\right|$，查询时间不再受${w}_{3}$更新次数影响.

6.   结　　语

针对当前大部分连接查询方案仅支持静态密文数据库的问题，结合对称隐藏向量加密思想，设计了支持动态数据更新的动态对称隐藏向量加密（SHVE）方案，并在此基础上，通过设计动态连接查询的TSet和XSet结构，构造了支持连接查询的动态对称可搜索加密方案. 方案具有3个特点：

1）支持动态更新. 相对当前大多数静态连接查询方案，该方案支持密文数据库添加和删除操作，进一步提高了方案在真实应用场景下的可用性.

2）查询时仅需单轮交互. 方案引入基于盲指数计算的ODXT，实现了单轮交互的连接查询. 相比其他2轮以上的交互方案，减少通信轮数可以有效降低真实网络环境下网络延时对搜索性能的影响，且更易于多客户端场景下的扩展.

3）安全性高. 通过构造SHVE，结合ODXT，使方案在单次查询中，仅泄露文档索引与查询条件的完全匹配结果，减少交叉查询信息泄露，进一步提高了安全性.

方案中的连接查询语句灵活性以及多客户端场景下方案适用性问题仍值得进一步深入研究.

作者贡献声明：黄一才提出了算法思路和实验方案，并撰写了论文；郁滨参与了实验方案制定并提出论文修改意见.