为了降低本地资源的计算开销, 越来越多的人选择将个人数据上传到不可信的云存储服务器中, 然而云服务器存在泄露用户隐私的诸多威胁. 权衡云环境既存在安全威胁又具备便利性的特点, 很多人将本地信息加密后在上传到云服务器中从而起到保护数据安全的作用. 随着用户和企业数据存储量逐年增长, 如果将全部数据不加区分地放在一起进行加密和搜索, 不仅增加加密复杂度, 而且影响搜索效率.

可搜索加密(Searchable Encryption, SE)技术^[1]是实现隐私数据加密上传到云端后搜索的重要技术. 对此国内外学者展开研究取得了许多成果. Song等^[2]首先提出了一个数据共享者和一个查询用户模型下的对称可搜索加密方案, 该方案通过对所有密文进行线性扫描的方式完成搜索. 为了提升SE方案的可用性, 2011年Cao等人^[3]首次提出了MRSE方案, 该方案成功解决了多关键字的排序问题, 但该方案的缺点是既不支持相似性搜索查询且效率也较低. 随后Xia等^[4]设计了一种特殊的树状索引结构, 采用贪婪深度搜索算法提高效率, 同时用KNN技术加密文件和索引保证方案的安全性.

上述方案基本解决了SSE方案搜索需求的问题. 但是本地数据的大量产生, 用户急需对云端的文档进行更新从而保证文档的完整性. 这使得支持动态更新的SE方案成为新的研究热点. 然而Zhang等人^[5]在2016年发现文档更新时通过文件注入式攻击会泄露用户的隐私. 为解决这一问题Bost等人^[6]在2017年提出了支持前向安全和后向安全的SSE方案. 但是该方案只支持单关键字的搜索, 为了进一步提升动态可搜索加密的性能和效率国内外学者展开广泛研究并取得丰硕成果.

为应对恶意服务器环境, Wang等人^[7]提出一种可验证的动态可搜索加密方案. 该方案构造了基于时间戳链表和Merkle树结果验证机制, 实现恶意服务器环境下的正确搜索.

为提高搜索效率, 2019年Xu等人^[8]提出了基于R-树动态范围搜索SE方案. 该方案采用R-树索引结构显著提高搜索效率, 并提出一种新的访问控制策略EGRQ实现用户的细化访问.

为提高更新效率, 2020年Huang等人^[9]提出了基于完美二叉树的前向安全SE方案. 作者通过预估更新大小, 构建完美索引树结构, 避免更新时重构节点造成的本地开销. Kermanshahi等人^[10]首次提出了内容隐私的定义. 该方案在更新时, 本地客户端首先构建更新令牌(包含更新的位置和更新内容)并加密上传到云端. 具体的更新过程由服务器完成, 从而降低本地开销. 孙晓玲等人^[11]提出了基于三链表索引结构的高效动态可搜索加密方案. 该方案通过每次搜索操作更新查询链表和删除链表的策略有效的提高了更新的效率.

在多用户场景下, Wang等人^[12]通过引入半可信的第三方服务器用于记录关键词的状态信息, 提出了一种支持多用户访问的前向安全动态可搜索加密方案. 但该方案存在无法抵抗重放攻击和窃听攻击等安全缺陷. 随后卢冰洁等人^[13]对此做出了改进, 通过引入完全可信第三方服务和构建新的索引结构, 提高了方案的安全性和删除效率.

上述方案虽然在性能和效率方面取得巨大提升, 但对索引结构的更新大多采用在已有索引的尾部直接添加的方法, 泄露了新添加关键字和已有文档的信息, 以及新添加关键字在字典中排列的位置. 这造成更新时极大的安全隐患.

为此本文提出了基于语义分组的动态更新可搜索加密方案(Scheme of Dynamic Searchable Encryption based on semantic grouping, SDSE). 首先通过TF-IDF和空间向量模型构建节点向量, 根据计算节点的相关性进行语义分组构建索引树. 然后向节点向量中添加虚拟关键字完成向量扩充, 保证字典排布的安全性. 最后结合分区矩阵思想提出一种更新方法. 实现了在原有关键字字典的基础上能够动态更新云端文件.

1 系统模型

(1) 数据拥有者DO创建关键词字典、加密文档、构建安全索引, 将它们上传到云服务器.

(2) 用户DU生成查询陷门, 并将陷门和想要返回的结果数量K发送到云服务器, 收到云端计算完成的最相关的K个结果文档后对其进行解密.

(3)云服务器收到DU的搜索请求后, CS对加密索引进行搜索, 并计算返回用户最希望的前K个结果文档.系统模型图如图1所示.

2 相关工作 2.1 符号定义

F: 表示明文文件集合F={f₁, f₂, …, f_n}.

C: 表示对应明文F的密文集合C={c₁, c₂, …, c_n}.

W: 表示关键词字典W={w₁, w₂, …, w_m}.

Q: 查询向量.

T: 未加密的索引向量.

I: 加密的索引向量.

T_w: 搜索陷门.

K: 返回结果数.

sk: 对称密钥.

F_up: 更新文档集.

W_up: 更新关键词集.

SK: 安全密钥对{S, M₁, M₂}.

S: m+d阶随机二进制向量.

M₁, M₂: (m+d)×(m+d)阶可逆矩阵.

u.ID: 树节点u的唯一标识.

u.FID: 叶子结点指向的文件的标识. 如果u为非叶子结点, 则u.FID=none.

u.V: 表示结点u所包含的m长的向量, 如果u是叶节点, 则u.V为文件u.FID的加权索引. 如果u是非叶子结点, 则u.V表示为以u为根的子树中所有结点向量对应维度的最大值u.V[t]= max (u₁.V[t], u₂.V[t],…) t∈{1, 2, …, m}.

Left, right:当节点u为非叶子节点时, left为其左孩子节点, right为其右孩子节点.

Tu: 表示树节点u的加权索引向量.

ResultNodeSet:表示一个分组集合.

2.2 安全性定义

本文方案的安全性主要有如下两个概率游戏验证 ${Re} a{l_A}(k),\;Idea{l_{A,S}}(k)$ , 其中, A表示敌手, S表示模拟器. 其中, ${Re} a{l_A}(k)$ 由SDSE执行, $Idea{l_{A,S}}(k)$ 是通过SDSE方案的泄露信息进行模拟. 我们把SDSE方案的泄露信息定义为如下3个泄露函数L₁, L₂,L₃.

定义1. 泄露函数L₁, L₂,L₃

1) ${L_1}(F)$ 以文档作为输入, L₁输出关键词的个数m, 文档数n, 每个文档的标识以及文档 ${f_j}$ 包含关键词的个数, 关键字字典W. 具体形式如下:

${L_1}(F,I) = (n,m,i{d_1}\cdots i{d_m},|{f_1}|\cdots|{f_m}|,W)$

(1)

2) ${L_2}(F,I,w,t)$ 以文档, 索引, 在时间节点t的搜索关键词w作为输入, ${L_2}$ 输出搜索模式和访问模式 $s(I,q,t)$ 和 $a(F,I,w,t)$ , 具体形式如下:

${L_2}(F,I,w,t) = (s(I,q,t),a(F,I,w,t))$

(2)

3) ${L_3}({f_{\rm{up}}})$ 以更新文档作为输入, ${L_{\rm{3}}}$ 输出更新文档标识, 文档 ${f_j}$ 包含的关键词个数, 新的关键字字典. 具体形式如下:

${L_3}(f) = (i{d_i}\cdots i{d_j},|{f_i}|\cdots|{f_j}|,{W_{\rm{up}}})$

(3)

定义2. ${Re} a{l_A}(k),Idea{l_{A,S}}(k)$

${Real_A}(k)$ : 挑战者执行 $srtup({1^l})$ 产生对称密钥sk和安全密钥SK. 然后敌手A选择文档集, 挑战者执行 $Index(F,sk,SK)$ 生成密文文档和索引并发送给敌手A. 敌手在多项式时间内进行普通搜索和更新搜索. 假设查询关键字为w, 挑战者执行 $Trapdoor({q_w},SK)$ 产生搜索陷门. 通过执行 $update({F_{\rm{up}}})$ 得到最新关键字字典. 最后, A返回一个比特b作为实验的输出结果.

$Idea{l_{A,S}}(k)$ : 敌手A进行多次多项式时间内的搜索 $q \in ({w_i},{f_j},{f_{\textit{z}}})$ , 每一次的搜索过程中, 模拟器S都会得到如下的泄露 ${L_1}{L_2}{L_3}$ . 模拟器S根据泄露信息执行SDSE, 并返回相应的密文文档 ${C^*}$ , 索引 ${I^*}$ , 陷门 ${T^*}$ , 更新字典 $W_{\rm{up}}^*$ . 最后敌手A返回一个比特b作为实验的输出结果.

如果方案SDSE对于自适应关键字搜索是安全的, 那么对于任意多项式时间内的敌手, 一定存在模拟器S使得式(4)成立:

$|pr[{Re} a{l_A}(k) = 1] - pr[Idea{l_{A,s}}(k) = 1]| \le neg(k)$

(4)

2.3 TF-IDF和空间向量模型

空间向量模型和TF-IDF规则是解决传统搜索领域的有效手段, 通过建立关键词字典集合与查询文档之间的关系, 实现多关键词的有效排序搜索. TF_fj,wi表示在文档f_j中关键词w_i出现的频率. 令IDF_wi表示含有关键词w_i的文件在文档总集中出现的频率. TF_fj,wi和IDF_wi分别采用式(5)和式(6)计算得到:

$ ID{F_{wi}} = \ln (1 + n/{n_{wi}}) $

(5)

$ T{F_{fj,wi}} = 1 + \ln {N_{fj,wi}} $

(6)

其中, TF_fj,wi为f_j中关键字w_i的个数; n 为 F 中的文件总数;n_wi为包含关键词w_i的文件数. 一般采用归一化的词频TF'_fj,wi和逆文档频率IDF'_wi, 即:

$ TF{'_{fj,wi}} = \frac{{T{F_{fj,wi}}}}{{\sqrt {\displaystyle\sum\limits_{wi \in W} {{{(T{F_{fj,wi}})}^2}} } }} $

(7)

$ IDF{'_{wi}} = \frac{{ID{F_{wi}}}}{{\sqrt {\displaystyle\sum\limits_{wi \in {W_s}} {{{(ID{F_{wi}})}^2}} } }} $

(8)

向量空间模型将文档和查询都看成是关键词的集合, 是关键词的有序排列. 我们可以根据倒排序列构建关键词的字典, 用二进制向量来表示文档和查询. 把查询抽象化为数学形式表示, 用0和1表示查询文档中是否存在词典对应位置的关键词.

2.4 ASPE加密算法

ASPS算法由Wang等人^[14]在2009年Sigmoid上提出, ASPE算法核心功能其实是实现了两个加密向量之间的安全内积计算.

定义3. 非对称保内积加密. 对于加密算法E(), 查询点记为q, 数据D中任意点记为P_i, 如果E()满足下列两个条件, 则称之为非对称的保内积加密算法:

$\left\{ {\begin{array}{l} d(E({p_i}),E(q)) = d({p_i},q) \\ d(E({p_i}),E({q_j})) \ne d({p_i},{q_,})\begin{array}{*{20}{c}}, {}&{{p_i},{p_j} \in D} \end{array} \end{array}} \right. $

(9)

3 基于语义分组的动态可搜索加密方案定义

SDSE方案由如下5个算法组成: (初始化(Setup)、构建索引(Index)、构建陷门(Trapdoor)、查询(Search) , 更新(Update)具体定义如下所示:

(1) ${\textit{Setup}}({1^l}) \to (sk,{\textit{SK}})$ : 初始化阶段, 数据拥有者根据安全参数 $l$ 得到密钥组(sk, SK), 其中, sk是加密文档的对称密钥. SK是用于加密索引和查询向量的密钥.

(2) $Index(F,sk,{\textit{SK}}) \to I$ : 索引构建阶段, 数据所用者根据明文文档F构建关键词字典W. 并以每个文档为叶子节点构建索引向量, 通过计算节点相似性组成明文索引结构. 最后密钥SK加密后上传到云端.

(3) $Trapdoor({\textit{SK}},W) \to {T_w}$ : 陷门生成阶段, 数据用户根据想要查询的关键词w构建搜索向量q_w, 并用密钥SK加密后生成陷门T_w上传到云端.

(4) $Search({T_w},I,K) \to R$ : 搜索阶段, 云服务器收到用户的搜索陷门T_w后与云端存储的索引结构I计算, 返回得分最高的K个结果.

(5) $Update({F_{\rm{up}}},{w_{\rm{up}}})$ 更新阶段, 数据拥有者从更新文档f_up中得出新的关键词w_up, 并为其重构索引结构, 并把新的索引结构和文档加密后上传到原始云端存储中. 得到新的密文文档集和索引结构.

4 基于语义分组的动态可搜索加密方案 4.1 方案构造

(1) ${\textit{Setup}}({1^l}) \to (sk,{\textit{SK}})$

初始化阶段DO根据关键词字典产生用于拆分索引和查询向量的m+d维二进制向量S, 以及两个(m+d)×(m+d)阶可逆矩阵{M₁, M₂}用于加密拆分后的向量. 对称密钥sk用于加密明文文档, 安全密钥SK={S, M₁, M₂}用于加密安全索引和查询向量.

(2) ${\textit{Index}}(F,sk,{\textit{SK}}) \to I$

构建索引分为如下5个步骤.

1) 抽取关键词 : 数据拥有者对文档集F抽取关键词得到关键字字典W={w₁, w₂,…, w_n}.

2) 构建明文形式的二进制索引: 根据空间向量模型数据拥有者为文档f_j, 生成二进制向量T_j. T_j的每个比特表示f_j中相应关键词存在与否.

3) 生成加权索引: 本文中关键词的权重由关键词出现的概率以及它出现的位置决定. TF-IDF的方法来计算关键词和文档之间的相关度. 在根据关键词在文中所处的位置分别赋予不同的权重, 本文把关键词的位置分为如下3类: 标题, 摘要, 正文. 分别使得标题占0.6, 摘要占0.3, 正文占0.1的权重. 假设某文档f中关键词w出现在标题和正文中, 我们用如下公式来表示它的权重: X=0.6×1+0.3×0+0.1×1=0.7, 采用TF-IDF权值计算方法来计算关键词相关度分数:

$ {{Y}} = \frac{1}{{|f|}} \times (1 + \ln t{f_{i,j}}) \times \ln \left( {1 + \frac{N}{{d{f_i}}}} \right)$

(10)

其中, |f|表示文档的长度, tf_{i, j}表示关键词i在文档f_j中出现的概率, df_i表示包含关键词i的文档数量.

4) 构建索引树: 本方案设计了一种新的索引结构-分组平衡二叉树, 构建这种树型索引时, 以自下而上的策略对每一层的树节点进行分组, 使得主题越接近的文档尽可能地分布于索引树的同一分支.

所有叶子结点生成完毕后, 采用自下而上的策略, 基于分组构造索引树. 每一层的非叶子结点都是由分组算法生成, 把加权索引的余弦值较小的两个结点组成一对.

为完成节点分组, 设计了算法1.

算法1. 树节点分组算法

输入: 当前需要处理的节点集PendingNodeSet

输出: 节点分组完的集合ResultNodeSet

1. while PendingNodeSet中的节点大于1do

2. 在PendingNodeSet里边随机选择节点u

3. 寻找一个非u的节点t, 使得cos(Tu, Tt)的值最大

4. 将节点对(u, t)添加到ResultNodeSet集合

5. 将u和t从集合PendingNodeSet中移除

6. end while

7. if PendingNodeSet非空 then

8. 将PendingNodeSet中唯一的节点插入到ResultNodeSet集合的末尾

9. end if

10. return ResultNodeSet

树节点分组完成后, 如果节点总数为2n个, 那么ResultNodeSet中就有n个节点对; 如果节点总数为2n+1个, 那么就有n个节点对和1个单节点. 然后在分组对的基础上构造一个新的节点作为他们的父节点, 这样反复迭代直到最终生成唯一的根节点.

由算法1构成的索引树如图2所示.

5) 加密明文索引树: 索引树构建完成后把节点向量动态扩充为m+d阶, 其中, d为虚拟关键字数, (m+1,…,m+d)的值选择z个置为ε, ε $< {(TF)_{\min }}$ , 其余为0 ( ${\textit{z}} \in Z_q^*$ ). 然后使用安全ASPE加密算法, 给加权索引树中的每个结点加密. 具体的操作是把u.V分割成两个随机向量 $\{u.V{'},u.V''\}$ 拆分思想如下:当S[i]= 0 时, 置 $u.V{'}= $ $ u.V''=u.V$ ; 当 S[i]= 1 时, 使得 $u.V'$ + $u.V''=u.V$ . 再通过{ M₁, M₂ } 对 $\{u.V{'},\;u.V''\}$ 进行加密, 加密成如下形式 $\{{M}_{1}^{\rm{T}}\cdot u.V{'},\;{M}_{2}^{\rm{T}}\cdot u.V''\}$ 待加密完所有的节点把加密索引树上传到云服务器.

(3) ${\textit{Trapdoor}}({\textit{SK}},W) \to {T_w}$

1) 首先根据查询的关键词W_i和关键词字典W生成m阶明文查询Q, 然后对查询向量扩充为m+d阶. 在d个虚拟的关键字中随机选择z个, 使其值置为ε其余的为0. $({\textit{z}} < 1/2d,{\textit{z}} \in Z_q^*,\varepsilon < T{F_{\min }})$ .

2) DO通过ASPE加密算法对向量 Q加密. 根据向量S, 将扩展后的查询向量 $Q$ 拆分为 $\{Q{'},Q''\}$ ,与对u.V的拆分方法不同: 当 $S[i] = 0$ 时, 置 $Q{'}[i]+Q''[i]=Q[i]$ . 当 $S[i] = 1$ 时, 置 $Q{'}[i]=Q''[i]=Q[i]$ . 再通过矩阵{ M₁, M₂ } 对 $\{Q{'},Q''\}$ 进行加密, 加密结果.

(4) ${\textit{Search}}({T_w},I,K) \to R$

收到DU的搜索请求后, CS使用深度贪婪优先算法在上传的加密安全索引树上进行搜索. 具体形式如算法2.

算法2. 深度贪婪优先搜索算法

输入: 索引树t的根节点和查询向量Q

输出: topK的查询结果的文档

1. if u不是叶子结点then

2. if score(Iu, Q)>d(d为前k个临界值) then

3. search (u.rchild)

4. search (u.lchild)

5. end if

6. else

7. if score(Iu, Q)>d then

8. 更新结果列表result和d的值

9. end if

10. end if

在分组平衡二叉树中是如何执行贪婪深度优先搜索的过程如图3所示.

当计算加密索引和安全陷门相关后, 返回得分前K的文档, 用户使用对应密钥解密文档. 搜索完毕.

(5) ${\textit{Update}}({F_{\rm{up}}},{w_{\rm{up}}})$

DO根据本地文档更新需求, 对云端的文档进行更新. 为避免动态更新时泄露关键字和文档相关性信息, 本文采用分区矩阵的思想. 在更新关键字字典时同时添加l−1个虚拟关键字( $l \leftarrow Z_p^*$ ), 增加了关键字字典添加关键字时的随机性. 通过构建两个l×l的可逆矩阵完成关键字字典的更新具体形式如下:

$M_1' = \left( {\begin{array}{*{20}{c}} {{M_1}}&0 \\ 0&{{M_l}} \end{array}} \right)\;,\; M_2' = \left( {\begin{array}{*{20}{c}} {{M_2}}&0 \\ 0&{M_l'} \end{array}} \right)$

(11)

为完成加密生成m+d+l阶分割向量s₁, 其在向量s的基础上得到s₁=(s,l). 然后对新矩阵 $M_1'M_2'$ 进行加密. 具体形式如式(12):

$\left\{ {\begin{array}{l} M_1^{{'}{\rm{T}}} = \left( {\begin{array}{*{20}{c}} {M_1^{\rm{T}}}&0 \\ 0&{M_l^{\rm{T}}} \end{array}} \right)\;,\; M_2^{{'}{\rm{T}}} = \left( {\begin{array}{*{20}{c}} {M_2^{\rm{T}}}&0 \\ 0&{M_2^{{'}{\rm{T}}}} \end{array}} \right)\\ M_1^{{'} - 1} = \left( {\begin{array}{*{20}{c}} {M_1^{ - 1}}&0 \\ 0&{M_l^{ - 1}} \end{array}} \right)\; ,\; M_1^{{'} - 2} = \left( {\begin{array}{*{20}{c}} {M_1^{ - 2}}&0 \\ 0&{M_l^{{'} - 1}} \end{array}} \right) \end{array}} \right. $

(12)

分区矩阵保证了已有的节点向量不变的基础上, 仅对更新文档进行构建加密. 既不会泄露新添加关键字在字典中的分布, 也减少了更新时产生的计算开销.

4.2 方案正确性分析

本节进行证明即使矩阵扩展到m+d+l阶, 仍然可以正常匹配. 并不会影响搜索结果的排序. 其中ε为添加虚拟关键字时产生的平衡参数. 即使搜索相同的关键字得分也存在差异从而保证了在搜索过程中索引和陷门的安全. 但由于ε的取值远小于TF的最小值, 故不影响相关性结果的正常排序. 以下为索引和陷门匹配的过程.

$ \begin{split} I\cdot {T}_{w} & ={I}^{\rm{'}}\cdot {T}_{w}^{\rm{'}}+{I}^{''}\cdot {T}_{w}^{''}\\ &={M}_{1}^{\rm{T}}{D}^{\rm{'}}\cdot {M}_{1}^{-1}{Q}^{\rm{'}}+{M}_{2}^{\rm{T}}{D}^{''}\cdot {M}_{2}^{-1}{Q}^{''}\\ & ={D}^{\rm{'}}{Q}^{\rm{'}}+{D}^{''}{Q}^{''}\\ & =DQ+{\displaystyle \sum \varepsilon }\end{split}$

(13)

4.3 方案安全性分析

根据定义1可知, 本文方案执行搜索和更新时会泄露相关的信息. 在分析SDSE方案的安全性之前, 我们假设加密明文文档的对称加密算法是满足选择明文攻击(CPA)的.

根据定义2可得, 如果本文方案满足对于任意多项式时间内的敌手都能使得式(14)成立:

$|pr[{Re} a{l_A}(k) = 1] - pr[Idea{l_{A,S}}(k) = 1]| \le neg(k)$

(14)

那么我们认为本文方案在自适应不可区分的意义上是安全的. 敌手可以通过分析密钥、索引、密文、陷门的不相关、关键字字典来获得模拟游戏的胜利.

$\begin{split} & pr[Idea{l_{A,S}}(k) = 1] = 1/2 + Adv(A(key) + Adv (A(I)) \\ &\qquad + Adv(A(C)) + Adv(A({T_w})) + Adv(A(W))) \end{split} $

(15)

具体的证明过程如下:

$Adv(A(SK,sk))$ 表示敌手A判断密钥和随机矩阵的优势. $Adv(A(I))$ 表示敌手A判断云端存储索引的优势. $Adv(A(C))$ 表示敌手A区分真实密文中加密文档的优势. $Adv(A({T_w}))$ 表示敌手判断不同陷门之间相关性的优势. $Adv(A(W))$ 表示敌手A判断关键字字典中关键字分布的优势.

本文方案中的安全密钥是由两个(m+d)×(m+d)阶可逆矩阵和分割向量组成SK={S, M₁, M₂}. 可逆矩阵和分割向量S组成的密钥同随机数矩阵和一串随机二进制数组成的密钥在计算上是不可区分的, 概率可以忽略不计. 故式(16)成立.

$\begin{split} Adv(A(key)) =& |pr [setup({1^l}) \to key] - pr [random \to ke{y^*}]| \\ & \le neg{1_1}(k) \\[-10pt] \end{split} $

(16)

本文方案中的索引是由关键字字典加虚拟关键字在ASPE加密算法加密后得到. 通过添加虚拟关键字模糊真实关键字的数量起到隐藏与关键字有关的标识符. 由于ASPE算法加密结果的不确定性使得即使得相同明文加密得出的密文也不同. 故在计算上也是不可区分的. 故式(17)成立:

$\begin{split} Adv(A(I)) =& |pr [buildIndex(F,SK,sk) \to I] - pr [random \\ & \to {I^*}]| \le neg{1_2}(k) \\[-10pt] \end{split} $

(17)

根据前提假设可知本文加密算法是满足CPA安全的, 故式(18)成立:

$\begin{split} Adv(A(C)) =& |pr [Encrypt(F,sk) \to C] - pr [random \to {C^*}]| \\ & \le neg{1_3}(k) \\[-10pt] \end{split} $

(18)

本文方案中陷门是由关键字请求向量加虚拟关键字构成. 即使搜索相同的关键字在不同的时间段产生的请求向量也是不同的. 然后通过ASPE加密算法进行加密更加无法判断. 故式(19)成立:

$\begin{split} Adv(A({T_w})) =& |pr [Trapdoor(w,sk) \to {T_w}] \\ & - pr [random \to T_w^*]| \le neg{1_4}(k) \end{split} $

(19)

本文方案中初始的关键字字典的安全性是由虚拟关键字和ASPE加密保证的. 着重介绍更新时关键字字典的安全性. 对于新产生的关键字通过添加虚拟关键字来模糊其在字典中的位置, 然后通过分区矩阵的思想使其添加到原始字典中. 这使得在判断新添加关键字在字典中的位置以及相关文档的概率可以忽略不计. 故式(20)成立:

$ \begin{split} Adv(A(W)) =& |pr [bulid(F) \to W] - pr [random \to {W^*}] | \\ & \le neg{1_5}(k) \\[-10pt] \end{split} $

(20)

综上所述可得:

$\begin{split} & pr[Idea{l_{A,S}}(k) = 1] = 1/2 + Adv(A(key) + Adv(A(I)) \\ & + Adv(A(C)) + Adv(A({T_w})) + Adv(A(W))) \\ & \le 1/2 + neg{1_1}(k) + neg{1_2}(k) + neg{1_3}(k) \\ & +neg{1_4}(k) + neg{1_5}(k) \end{split} $

(21)

使得式(22)成立:

$ \begin{split} & neg1(k) = neg{1_1}(k) + neg{1_2}(k) + neg{1_3}(k) + neg{1_4}(k) \\ & + neg{1_5}(k)|pr[{Re} a{l_A}(k) = 1] - pr[Idea{l_{A,s}}(k) = 1]| \\ & \le neg(k)\\[-10pt] \end{split} $

(22)

因此本文方案在泄露信息L₁,_{L2, L3的情况下是安全的.}

4.4 方案效率分析

本节从构建加密索引、搜索、更新3个方面进行效率分析, 将本文方案与文献[8-11,13]方案进行对比.

在构建索引上, 本文方案和文献[8-10]所提方案是基于二叉树索引结构. 分析加密索引树效率时分3步; 构建未加密索引树需要经过生成叶子结点、结点分组和构建索引树3个步骤. 生成结点需要O(z),因为关键词字典的大小为m, 所以每个结点生成索引向量耗时O(m). 计算关键词之间相关度时间复杂度为O(m). 由于树节点分组算法的时间复杂度为O(zm²). 所以构建索引树时间复杂度为O(zm²). 二叉树中共有z个节点, 需要加密O(z)个节点, 向量分割时间复杂度为O(m), 语义相似度矩阵的两次乘法时间复杂度为O(m²). 所以加密索引树需要耗时O(zm²).

在关键词搜索方面, 其搜索的时间取决于访问的叶子节点数, 假设实际访问的叶子节点数为L个, 显然L>k与k呈正相关, 文献[9]中方案所构造的搜索的时间复杂度O(Llog₂n). 但本文方案与文献[9]中方案的区别在于, 平衡分组二叉树把相关度高的结点都分到了同一子树下, 所以需要遍历搜索的叶子节点数会大大少于未分组的平衡二叉树, 从而得到更高的查询效率.

在文档更新方面. 本文采用分区矩阵思想进行更新, 保持原有字典不变的基础上通过构建l×l阶矩阵完成更新. L为真实关键字和虚拟关键字的总数. 故时间复杂度为O(l²).

表1给出了本案与已有方案的效率分析对比. 其中, z表示二叉树中节点总数, m表示关键词字典大小, n表示文档总数, L表示二叉树索引中实际访问节点数, R表示范围查询的半径, t表示范围查询坐标位长, p表示更新文档数, l表示更新关键词数.

通过与最新成果对比可得, 本文在搜索和更新方面具备较高效率.

5 结束语

本文提出了一种基于语义分组的动态关键词可搜索加密方案. 提出平衡分组二叉树作为索引结构使得返回的文档更符合用户的请求. 结合分区矩阵思想进行文档更新. 在保证关键字字典安全性的同时, 减少了更新时的计算开销. 与现有的方案相比, 本文方案具备更高的搜索效率和更新效率. 但本文方案只考虑了单用户模型, 为更贴近云服务工作的实际情况. 接下来的工作把本文方案拓展到多用户场景下.