云计算环境中的数据安全问题越来越多地受到人们关注,为了确保个人数据的隐私性,用户通常先将文档加密,然后再上传到云服务器.然而,数据加密使传统的检索机制失效,随着数据量的增加,如何高效地取回加密存储在云中的数据已成为重要的挑战,密文检索问题已成为近年来信息安全领域重要的研究问题之一.

文献[1]提出了密文顺序检索架构和一种可证明安全的加密方法,即证明了:在只知道密文的情况下,云服务器无法得到任何明文的信息.然而,加密算法和查询算法都需要O(n)的时间复杂度,其中,n表示文档长度.文献[2]形式化地定义了安全索引结构——Z索引,该索引模型通过伪随机函数和布隆过滤器(Bloom filter)实现,可以抵抗适应性选择关键字攻击.然而,Z索引并不提供查询排序机制,若查询词出现在大量文档中,用户需要从大量的结果集中筛选所需文档.通过在倒排表中加入相关度分数,文献[3]实现了支持结果集排序的密文检索方法.在查询阶段,云服务器仅需返回与查询条件匹配的前k个相关文档,而不是所有满足条件的文档,这不但减少了带宽的消耗,还改善了用户体验.然而,上述工作仅能解决单关键词密文检索的问题,即用户在一次查询中仅能提交一个查询检索词.

为了更全面地表达用户的查询意图,多关键字检索技术应运而生.文献[4]提出了一种密文检索框架MRSE,以解决多关键字密文检索问题.在索引建立阶段,每个文档被表示成一个二进制向量,其中,每一位的值代表当前文档是否包含该关键字.查询向量以同样的方式被表示成一个二进制向量.云服务器通过执行矩阵运算和安全k近邻算法获取排序的结果集并返回给用户.然而,MRSE框架的查询响应时间随着文档集的增长而增长,难以适应大数据时代数据迅速增长的需求.

为了加快查询的速度,树形结构普遍应用于索引的构建.比如在数据库领域,文献[5]使用B树加快查询速度,文献[6]通过构造M树加快了对度量空间的索引过程.

本文在MRSE框架上进行改进,提出了一种基于相似查询(similarity search)树的新型高效索引结构(MRSE- SS).该方法在索引建立阶段将聚类算法和相似查询树进行结合,按照领域相关度将文档集合组织起来;采用动态DK-MEDOIDS算法,通过限制中心点到最远成员之间的距离控制聚类的大小,实现聚类的生成过程;使用相似查询树将不同的领域的聚类组织起来,通过控制上级超球体中子节点超球体的数量,动态调整结构以达到新增体积最小的目标,直至生成根节点.在查询阶段,将用户提交的查询向量表示为一个超球体,云服务器通过判断查询向量所代表的超球体与相似查询树中节点所代表的超球体之间的位置关系进行判定,仅当查询向量与某领域构成的超球体有交集时,才将该领域纳入结果集评价范围.递归执行这一步骤直至叶子节点,即可返回叶子节点中k个最相关的文档列表.由于在树形结构中进行了剪枝,减少了相关度计算量,从而获取了更高的效率.实验结果表明:当文档集合呈现指数增长时,使用MRSE-SS索引结构进行检索的查询响应时间仅呈线性增长.

本文的贡献主要体现在以下3个方面:

(1) 提出了一种新型的密文索引结构MRSE-SS,将相似查询树结构引入密文索引框架,用于提升多关键字排序检索的效率,并取得了良好的效果;

(2) 提出了一种动态聚类算法DK-MEDOIDS,聚类过程随文档量增加而动态变化,适用于云计算环境下的密文检索场景;

(3) 通过构建实验,验证了MRSE-SS方法的实际运行效果.

1 定义和背景 1.1 系统模型

在本文中系统涉及3个实体,分别为数据拥有者、数据使用者和云服务器(如图 1所示):

· 数据拥有者负责搜集数据,建立索引,并把数据和索引加密外包到云服务器上.除了关于数据的操作外,数据拥有者还需要给需要查询数据的使用者合理授权;

· 数据使用者需要在得到数据使用者授权的情况下才能访问数据;

· 云服务器提供了密文检索所需的大量存储空间和计算资源,一旦接到数据使用者的合法请求,云服务器需要返回和查询最相关的前k个文档,其中,k值是由用户设定.

系统的设计目标就是:在不向服务器泄露文档信息的前提下,提升密文检索速度并得到更符合用户意图的查询结果.

1.2 安全模型

本文假定数据使用者是可信的,但是云服务器是半可信的.即:云服务器会严格按照指令执行用户的操作请求,但会尽量观察和分析服务器上的数据和索引结构,以期获知用户文档的内容.根据云服务器可以获得的信息,主要有以下的两种安全模型^{[7, 8]}:

· 已知密文模型:云服务器只知道用户外包到云上的数据,即加密后的文档集、相似查询树和加密后的查询超球体;

· 已知背景信息模型:在这个模型中,云服务器不仅知道第1个模型中的所有信息,还可以统计和分析云服务器上的数据.例如:知道文档集的统计信息,进而推测出明文关键字.

1.3 K-MEDOIDS 聚类算法

K-MEDOIDS算法^[9]的目标主要是将n个数据对象划分为k个聚类,选用聚类中最接近所有对象平均值的对象作为聚类中心.K-MEDOIDS算法采用绝对误差标准作为标准测量函数,其定义如下:

$E = \sum\limits_{i = 1}^k {\sum\limits_{p \in {C_i}} {|p - {O_i}|} } $

(1)

其中,p为聚类C_i中的点;O_i为聚类C_i的代表对象,即中心.

K-MEDOIDS算法主要由以下4步组成:

(1) 在数据集中随机选择k个对象,每个对象代表一个聚类的初始均值或中心;

(2) 对剩下的每个对象,根据其与各个聚类中心的绝对误差大小,将它分配到最小绝对误差的聚类中;

(3) 在每个聚类中,顺序选取一个元素,用该元素代替原来的中心,计算得到各个元素和当前中心的绝对误差总和,选取绝对误差和最小的元素作为中心;

(4) 迭代步骤2和步骤3,直至所有的中心点不改变.

1.4 SS- 树

相似查询树^[10]是R树的变形,它采用超球体进行空间的分割,在二维平面上如图 2(a)所示,其用树形结构如图 2(b)所示.相似查询树从下到上构建而成,上层节点为恰好覆盖下层节点的所有元素的超球体,每个节点由一个中心点和半径表示.若该节点为叶子节点,则中心点即为文档向量值;若为中间节点,则表示超球体的球心,其数据结构如图 3所示.

1.5 评价标准 1.5.1 相似度

在相似度计算的时候,本文采用了欧氏距离的方式进行度量.归一化后的向量内积值等价于两个向量之间的余弦值.计算方法见公式(2),其中,x和y分别表示归一化后的两个不同的文档的向量.

$\eqalign{ & D(x,y) = \sqrt {|x{|^2} - 2x \cdot y + |y{|^2}} \cr & {\rm{ }} = \sqrt {|x{|^2} - 2|x| \cdot |y| \cdot \cos (x,y) + |y{|^2}} \cr & {\rm{ }} = \sqrt {2 - 2\cos (x,y)} \cr & {\rm{ }} = \sqrt {2(1 - \cos (x,y))} \cr} $

(2)

1.5.2 检索结果集评价

较好的查询结果应该保持文档与文档之间的相似度.相似度高的文件容易同时被查询,所以文档集中文档与文档之间的相似度可以由下式度量:

${{P}_{l}}=\sum\limits_{{j}'=1}^{{{k}'}}{\sum\limits_{{i}'>=j}^{{{k}'}}{D({{d}_{{{i}'}}},{{d}_{{{j}'}}})}}\text{ /}\sum\limits_{{j}'=1}^{{{k}'}}{\sum\limits_{{i}'>=j}^{{{k}'}}{D({{d}_{{{i}'}}},{{d}_{{{j}'}}})}}$

(3)

其中,k′表示最终密文查询返回的k个文件,k表示明文查询中的top k个文件.

1.5.3 信息泄露评价

本文采用了文献[11]中定义的信息泄露评价方法,即:使云服务器返回前k个文档,同时,尽量少地向云服务器泄漏排序结果的信息.评估排序结果的信息泄露量按以下公式计算:

${{P}_{k}}=\sum{{{P}_{i}}}/k$

(4)

${P_i} = |{C_i} - {C'_i}|$

(5)

其中,C_i表示文档i在排序结果Top k中的位置,${C'_i}$表示文档i在未添加随机值情况下的真实排序位置.从公式中可以看出:当P_k的值越大,说明查询结果隐藏得越好,信息泄露的越少.

1.6 符号定义

为使表达简洁和准确,我们定义了以下符号:

· DC:明文文档向量集,其中有m篇文档,表示为DC={d|d₁,d₂,...,d_m};

· C:密文文档向量集,对应于明文文档集,表示为C={c|c₁,c₂,...,c_m};

· WC:词典,其中有n个关键字,表示为WC={w|w₁,w₂,...,w_n};

· m:SS树中非叶子节点的最少子元素个数,根节点除外;

· M:SS树中非叶子节点的最多子元素个数,根节点除外;

· D(O_i,O_j):表示两超球体球心O_i,O_j之间的距离;

· Qw:表示查询向量;

· T:表示一个聚类中能够容纳的最大文档向量个数;

· r:最小超球面体的半径;

· n:词典中关键字个数;

· u:为了维护文档向量的安全性,添加的维度数目;

· v:从u维度中随机选取的维度数目;

· k:用户指定的返回文档数目.

2 算法和方法框架 2.1 基于相似查询树的索引框架

MRSE-SS索引的框架主要由以下4个算法组成:生成密钥的Keygen(1ⁿ,u)算法、建立密文索引的Build-index(DC,SK)算法、生成陷门算法Trapdoor(w,SK)、查询算法Query(Tw,k,I).

· Keygen(1ⁿ,u)

数据拥有者随机的生成了一个(n+u+1)位的向量作为分割指示向量S,同时生成两个(n+u+1)x(n+u+1)的可逆矩阵(M₁,M₂),组成密钥SK={S,M₁,M₂}.

· Build-index(DC,SK)

数据拥有者为每个文档生成一个n维的文档向量DC[i],其中的每一位DC[i][j](0＜j＜n)记录关键词w_j对应当前文档的权重^[12].调用相似查询树构建算法(将在第2.4节介绍),对文档向量集DC建立相似查询树索引I.其次,将索引中所有节点的中心向量(包括每个超球体的球心向量和所有文档向量)从n维扩展到(n+u+1)维,其中,(n+j)(0＜j＜u+1)为随机值R_j,最后一维(n+u+1)为1.

然后,通过向量S将索引所有节点的中心向量分割为两个子向量DC[i][j]′和DC[i][j]″,若S_i为1,则DC[i][j]′和DC[i][j]″都为随机值,且它们之和为DC[i][j];若S_i为0,则DC[i][j]′=DC[i][j]″=DC[i][j].此时,索引向量I={I′,I″}.最后,通过两个矩阵M₁和M₂对索引I加密,即$I = \{ M_1^TI',M_2^TI''\} $,加密后的索引被上传到云端.

· Trapdoor(w,SK)

用户根据关键字在词典中是否出现设置Qw:如果在词典中出现,则对应位置的Qw[i]值为1;否则为0.随机地从u个关键字中选择v个,在Qw对应位置中设为1,其余位置设为0,最后一维取随机值t.再生成一个随机值q对Qw的前(n+u)维进行整体变化,即Qw=(q×Qw(n+u),t).然后,通过向量S对Qw进行分割:当S_i值为1,Qw[i]′=Qw[i]″=Qw[i];当S_i值为0的时候,Qw[i]′和Qw[i]″取随机值,但它们的和为Qw[i].通过矩阵M₁和M₂对Qw′和Qw″进行加密,陷门可以表示为三元组:$Tw = \{ M_1^{ - 1}Qw',M_2^{ - 1}Qw'',r\} $,其中,r表示最小超球体的半径.

· Query(Tw,k,I)

通过陷门Tw,服务器首先计算查询超球体和根节点各个超球体之间的关系,得到交集最多的某个超球体,然后根据得到的超球体,继续向下一层节点寻找,直到叶子节点.计算叶子节点中的文档向量和查询向量超球体的中心向量之间的距离,得到距离最近的前k个文档向量,并返回这k个文档向量的列表.

2.2 关键词权重计算方法

本文使用了文献[13]定义的关键词的权重计算方法:

${w_i} = {{TF({t_i}) \times IDF({t_i})} \over {\sqrt {\sum\limits_{i = 1}^n {{{(TF({t_i}) \times IDF({t_i}))}^2}} } }} = {{TF({t_i}) \times \log \left( {{N \over {{n_i}}} + 1} \right)} \over {\sqrt {\sum\limits_{i = 1}^n {{{\left( {TF({t_i}) \times \log \left( {{N \over {{n_i}}} + 1} \right)} \right)}^2}} } }}$

(6)

其中,TF是特征项频率,即关键词在文档中出现的次数;IDF是逆文档频率,即与出现该关键词的文档个数成反比;t_i表示关键词;N表示词典中词的个数;n_i表示出现该词的文档个数.

2.3 DK-MEDOIDS 算法

传统K-MEDOIDS算法^[9]的k值需要提前确定,不能在聚类的过程中随着文档数量的变化而动态变化,因此不适用于密文检索场景.本文设计了DK-MEDOIDS算法,其标准测量函数如下:

$E = \sum\limits_{i = 1}^k {\sum\limits_{p \in {C_i}} {D(p,{O_i})} } $

(7)

其中,p为聚类C_i中的点;O_i为聚类C_i的代表对象,表示聚类中心;D(p,O_i)函数用于计算点p和点O_i之间的距离.

算法分为以下几个步骤:

(1) 设置聚类中心和它的成员之间的距离门限值r以及单个聚类中元素的门限值T;

(2) 在DC中随机的选择k个对象,每个对象代表一个簇的初始均值或中心;

(3) 在每个簇中,顺序选取一个元素,用该元素代替原来的聚类中心,计算得到各个元素和当前聚类中心的距离总和,选取距离和最小的元素作为中心;

(4) 检测各个聚类是否存在元素和聚类中心距离大于r的情况:若存在,则k=k+1,即:加入一个新的聚类中心,并将异常点作为此新的聚类中心,重新执行第2步;

(5) 直到所有的聚类中心不再变化;

(6) 检测所有聚类,成员元素是否超过门限值T:若存在,则对该聚类调用DK-MEDOIDS算法,生成子聚类;

(7) 检测所有元素和各个聚类中心之间的距离:若元素和当前聚类中心之间的距离小于r,并且该元素未在当前聚类中出现,则将该元素加入到当前聚类中.

2.4 相似查询树构建算法

本文结合动态DK-MEDOIDS算法和相似查询树构建算法构建新型MRSE-SS树,主要分为以下几个步骤:

(1) 设定每个节点的最少子节点个数m和最大子节点个数M;

(2) 调用动态DK-MEDOIDS算法,建立N₀个最小超球体;

(3) 将距离相近的x(m≤x≤M)个超球体重新组成一个大集合,调用K-MEDOIDS算法,此时k=1,只需求出中心节点,并以中心节点和最远成员之间的距离作为半径;

(4) 重复步骤(3),选取增加“体积”最小的一种组合方案,输出N_i个超球体;

(5) 将N_i个超球体组织成相似查询树中的一层;

(6) 迭代步骤(3)~步骤(5),直到超球体个数N_i小于m个;

(7) 将最后的N_i个超球体构成根节点.

2.5 查询算法

本文所提出查询算法的核心思想是,寻找和查询超球体有最大交集的超球体.查询超球体和相似查询树中的超球体的位置情况可分为包含、相交和不相交.用R_Qw表示查询超球体的半径,R_n表示相似查询树中的超球体半径.

· 相交的判定方法,如图 4(a)和公式(8)所示.

$\left( {{R_{Qw}} + {R_n}} \right) > D\left( {{O_{Qw}},{O_n}} \right) ＞ \left| {{R_{Qw}} - {R_n}} \right|$

(8)

· 包含的判定方法,如图 4(b)和公式(9)所示.

$D\left( {{O_{Qw}},{O_n}} \right) ＜ \left| {{R_{Qw}} - {R_n}} \right|$

(9)

· 不相交的判定方法,如图 5和公式(10)所示.

$D\left( {{O_{Qw}},{O_n}} \right) > \left| {{R_{Qw}} + {R_n}} \right|$

(10)

查询的过程中,针对以上位置关系,通过设置状态标记值来记录相似查询树中节点和查询超球体之间的关系,状态标记值取值范围为:{未标记,不相交,相交但不包含,包含},初始值为未标记.

查询算法的具体步骤如下:

(1) 服务器首先计算查询超球体和根节点各个超球体之间的关系,得到交集最多的某个超球体.该步骤使用的查找算法伪代码见算法1-FindClosestSphere;

(2) 根据得到的超球体,继续向下一层节点寻找交集最多的超球体,在下一层中调用算法1;

(3) 重复步骤2,直到叶子节点,计算叶子节点和查询超球体球心O_Qw之间的距离,选取其中距离最近的前k个文档,并返回给用户.

算法 1. FindClosestSphere/在本层中查找索引树中和查询超球体有最大交集的超球体.

简明起见,定义操作集合A包含以下两个语句:

· candidate_node=current_node;    //当前节点作为候选节点;

· min_dis=D(O_Qw,O_n);       //查询超球体和当前节点的距离作为最小距离.

1. state=unmarked;

2. interate all nodes in this layer {

3.  if (D(O_Qw,O_n)＞=R_Qw+R_n) {     //如果不相交

4.   if (state==intersected||state==contained) {

5.      cut this branch;

6.   } else if (state==disjoint && D(O_Qw,O_n)＜min_dis) {

7.      A;

8.   } else if (state==unmarked) {

9.      A; state=disjoint;

10.   }

11.  } else if (D(O_Qw,O_n)＞abs(R_Qw-R_n)) {  //如果相交

12.   if (state==contained) {

13.      cut this branch;

14.   } else if (state==intersected && D(O_Qw,O_n)＜min_dis) {

15.      A;

16.   }else if (state==unmarked||state==disjoint) {

17.      A; state=intersected;

18.   }

19.  } else {          //如果包含

20.   if (state==unmarked||state==intersected||state==disjoint) {

21.       A; state=contained;

22.   } else if (D(O_Qw,O_n)＜min_dis) {

23.      A;

24.   }

25.  }

26. }

3 效率和安全分析 3.1 查询效率分析

查询过程可以分为陷门生成Trapdoor(w,SK)和查询Query(Tw,k,I)两部分.陷门生成阶段需要的操作见公式(11),其中,n表示词典中的关键字个数,w表示查询的关键字个数:

$O\left( {{\rm{MRSE - SS}}} \right) = 5n + u - v - w + 5$

(11)

当文档向量集DC以指数级增长的时候,陷门的生成时间独立于DC的增长,只与词典有关,其时间复杂度可以表示为O(1).MRSE和MRSE-SS的陷门生成时间复杂度一样.

在MRSE的查询阶段,云服务器需要计算所有的密文文档向量和密文查询向量之间的相关度分数,并排序返回前k个最相关的文档列表.MRSE在查询阶段需要的操作见公式(12),其中,m表示文档向量的个数,n表示词典中关键字个数:

$O\left( {{\rm{MRSE}}} \right) = 2m \times \left( {2n + 2u + 1} \right) + m - 1$

(12)

相比于MRSE,在MRSE-SS的查询阶段,云服务器使用相似查询树索引查询文档,其所需要的操作数见公式(13),其中,B_i表示相似查询树中第i层需要计算的节点的个数;l表示相似查询树的最大层数;m表示文档向量个数;n表示词典中关键字个数;t表示最小超球体中成员的个数,且t＜=T.

$O\left( {{\rm{MRSE}}} \right) = 2m \times \left( {2n + 2u + 1} \right) + m - 1$

(13)

当文档向量集DC呈指数增长时,m可以表示为2^l,那么MRSE的查询时间复杂度就是O(2^l),而MRSE-SS的时间复杂度则为O(l).

总的查询时间复杂度可以通过公式(14)表示:当文档数量以指数级增长的时候,MRSE-SS的查询时间只是线性增长;而传统方法如MRSE,则是以指数级的形式快速增长.

$O\left( {SearchTime} \right) = O\left( {Trapdoor} \right) + O\left( {Query} \right)$

(14)

3.2 安全分析 3.2.1 已知密文模型

在已知密文模型下,敌手可获得相应的密文信息包括加密的文档向量和查询向量等,但是加密密钥是保密的.本方案是基于方案^[14]做出了适应性的改进和安全增强,本方案的加密密钥由两部分组成,分别为(n+u+1)位的分割指示向量S和(n+u+1)x(n+u+1)的可逆矩阵(M₁,M₂).为简单起见,不失一般性,我们假设u=0,即,不添加随机值(添加随机值是为了增加方案的安全性).由于分割指示向量S是未知的,所以文档向量DC[i]′和DC[i]″可被看作是两个随机的(n+1)维的向量.

为解出加密文档数据构建的线性方程组,即${C'_i} = M_1^T \times DC[j]'$和${C''_i} = M_2^T \times DC[j]''$,我们在m篇文档向量中有2mx(n+1)个未知量,在可逆矩阵(M₁,M₂)中有2(n+1)x(n+1)个未知量.因为我们只有2mx(n+1)个等式,小于未知量的个数,所以没有足够的信息来推断出文档向量或者矩阵(M₁,M₂).

同理,查询向量Qw′和Qw″可被看作2个(n+1)维的随机向量,为解出加密查询向量构建的方程组,我们在两个查询向量中有2(n+1)个未知量,在矩阵(M₁,M₂)中有2(n+1)x(n+1)个未知量.因为我们仅有2(n+1)个等式,小于未知量的数量,因此没有足够的信息计算出查询向量或者是矩阵(M₁,M₂).因此,该方案在已知密文场景下是安全的.

3.2.2 已知背景信息模型

在这个模型中,云服务器不仅知道密文索引信息,而且还具备记录查询结果、分析查询过程、推测不同陷门(trapdoor)之间关系、数据库的统计分析知识等能力.下面从查询无联系性和关键字安全两方面进行分析.

· 查询的无联系性:在查询向量的生成过程中,由于加入了随机值,从而使得每次陷门的生成结果都不同,从而使得服务器无法建立查询向量和文档之间的对应关系.在陷门的生成过程中,通过以下3个过程实现了查询向量的随机性:

1. 从添加的u位中随机的选择了v位,并对这些位赋予随机值;

2. 通过生成一个随机值q,对查询向量的前n+u位的值做了一个规约化;

3. 查询向量最后一维的值被置为随机值;

· 关键字安全:用户在进行搜索服务时,倾向于向云服务器隐藏自己的搜索内容.通常使用陷门的方式来保护查询关键字.在已知背景信息模型中,云服务器可利用词频信息(包含关键词的文档个数)来推断关键词.本文的关键字加密方案采用了安全增强的内向量积计算方式^[4],由于该加密方式是满足关键字安全的,所以本文提出的加密方式也是满足关键字安全的.

通过合适设置u的值,用户可以混淆查询和查询结果的关系,增加云服务器运用统计分析猜测关键字的难度.但是,u值的增大也会降低查询的准确性,因此,这是关键字安全和查询准确性的平衡.

4 性能分析

为了测试MRSE-SS模型在真实数据集上的性能,我们建立了实验平台验证检索的准确性和效率.测试平台建立在Intel Core i7 3.40GZ的Linux服务器上,数据集采用《软件学报》最近10年所刊载的论文,共约2 900篇文档,约4 800个关键词.图 6展示了MRSE-SS方案与MRSE方案的效率对比情况.

在图 6(a)中,当文档集合的个数呈指数增加时,MRSE方案的查询响应时间也是呈指数级增加,而MRSE-SS方案的查询响应时间近似线性增加;在图6(b)中,当查询返回的结果文档数目变化时,MRSE和MRSE-SS方案的查询时间都比较稳定;在图 6(c)中,当查询关键词数目变化时,MRSE-SS方案仍然有极大的优势.

图 7展示了MRSE-SS和MRSE方案在查询结果集内的文档间相似度上的对比情况.从图中可以看出: MRSE-SS方案返回的文档集中文档间的相似度更高,文档集中的文档更相关.

图 8展示了MRSE-SS和MRSE方案在排序结果信息泄漏上的对比,可以看出:MRSE-SS方案的排序隐私都数值更高,也就是隐私度更好,安全性更高.

5 总结

本文提出了MRSE-SS密文检索框架、索引结构和相应的算法,并建立了密文检索实验平台验证了本文所提方案的有效性.实验结果表明:MRSE-SS方案支持密文多关键字排序检索,并且在查询效率、排序隐私和查询结果集的相关度上都较传统的MRSE方法有了较大的提升.