布隆过滤器(Bloom filter)^[15]是初始化为0的x位向量.若存在集合P={p₁, p₂, …, p_l},利用y个相互独立的哈希函数H={h:{0, 1}^*→{1, x}}将集合中每个元素p_i∈P, 1≤i≤l的哈希值作为布隆过滤器的下标,对应位置为1.判断一个元素x是否属于集合P, 将元素p_i作用于y个独立的哈希函数.若输出结果对应布隆过滤器的相应位置有1位为0,则元素p_i不属于集合P; 若y个相应位置都为1,那么元素p_i属于P或者不属于P, 不属于P的现象称为假阳性(false positive).1个x位的布隆过滤器出现假阳性的概率大约为(1-e^(ly)/x)^l. 其中, x为布隆过滤器的长度; y为哈希函数的个数; l为将要插入布隆过滤器中关键词的个数.

局部敏感哈希函数(locality-sensitive hashing, LSH)^[16]是将2个距离相近的向量映射为同一值.向量的相近程度可以用欧几里得距离进行度量.局部敏感哈希函数H的定义为:

对于任意2个向量m、 n及h∈H, 若满足当d(m, n)≤r₁:p[h(m)=h(n)]≥p₁,当d(m, n)≥r₂:p[h(m)=h(n)]≤p₂, 则称哈希函数族是(r₁, r₂, p₁, p₂)-sensitive. 其中, d(m, n)为向量m和 n的距离. 当d(m, n)≥r₂, 但哈希函数值相等时,这种情况称为假阳性; 当d(m, n)≤r₁, 但哈希函数值不相等时,这种情况称为假阴性.本研究采用p-stable LSH函数族^[17].

为实现关键词模糊检索功能,在构建文件索引时需将关键词转化为向量.将关键词任意相邻的两个字母作为一组,如将keyword转化为{ke, ey, yw, wo, or, rd}.在26²种排列组合中选择一种生成长为26²位的向量作为参考,将关键词的二元组对应位置为1,生成与关键词对应的向量.

1)词频信息.通常方案检索结果只依赖于文件索引与查询向量的内积结果,实际应用环境中还有其他因素能够影响检索结果准确性.用户关注的关键词与其在一篇文章中出现的频率呈正相关; 与其在数据库文件集中出现的频率呈负相关.

为使检索结果更加准确,使用词频(term frequency,TF)×逆文件频率(inverse document frequency,IDF)作为词频信息度量依据,将数据内嵌到检索过程中,使检索结果更符合用户的检索要求.在一份给定的文件里,TF指特定词语在该文件中出现的频率.IDF是一个词语普遍重要性的度量.某一特定词语的IDF,可由文件总数除以包含该词语文件的数目,再取对数得到.这样,某一特定文件内的高词语频率与词语在整个文件集合中的低文件频率,可以产生高权重的TF×IDF.现在关于TF×IDF计算的权重方案有多种变体,但尚未出现性能特别突出的计算方案^[18].本研究选择在文献中广泛使用的相关计算方案

Score(F_i)=1/(|F_i|)∑_Wj∈w^～[(1+lnf_i,j)ln(1+e/(f_j))](1)

其中,f_i,j为关键词W_j在文件F_i中的词频信息; f_j为文件集中包含关键词W_j的文件数量; e为文件集包含的总文件数; |F_i|为文件F_i的欧几里德长度, |F_i|=(∑ⁿ_j=1(1+lnf_i,j)²)^1/2.

2)用户喜好.目前多数方案在检索时,关键词的作用是相同的,没有体现出侧重点.在实际检索过程中,用户喜好也是值得考虑的因素.用户在检索关键词时,根据实际情况为关键词赋予不同的权重,体现不同关键词的重要性.

在建立系统模型前,先定义变量符号: F_C为文件集合,F_C={F₁, F₂, …}; W_C为关键词集合,W_C={(W₁, t₁),(W₂, t₂), …}. 其中W_i为关键词; t_i为关键词W_i对应的词频信息. w_C为关键词对应的二元组集合,表示为w_C={(w₁, t₁),(w₂, t₂), …}, w_i∈{0, 1}; b为文件索引; q为查询向量索引; W^～为查询关键词集合,表示为W^～={(W^～₁, d₁),(W^～₂, d₂),…}. 其中, d_i为用户赋值给关键词W^～_i的权重(用户喜好程度). w^～为W^～对应的二元组集合,表示为w^～={(w^～₁, d₁),(w^～₂, d₂),…}, w^～_i∈{0, 1}²⁶². 其中, w^～_i为关键词W^～_i对应的二元组向量. H为局部敏感哈希函数族,表示为H={h:{0, 1}²⁶²→{0, 1}^m}.

如图1,基于云储存的可搜索加密体系涉及云服务器、数据拥有者以及用户3方.为保证外包数据的安全,数据拥有者对文件加密后将密文上传到云服务器.为提高数据利用率,数据拥有者需通过特定机制,为数据集中的每一份文件构建唯一对应的文件索引,将加密索引文件与密文文件一起上传到服务器.用户通过安全渠道获得数据使用权后,利用关键词构建查询向量,加密后发送给服务器.服务器在接收到查询信息后,通过特定的搜索机制返回相关密文文件.有关访问控制参见文献[19].

图1 基于云计算的可搜索加密系统模型
Fig.1 System architecture of search over encrypted data in cloud computing

方案采用“honest-but-curious”模型,即云服务器是半可信的,也就是说服务器会根据方案设计协议执行所有过程并提供相应的服务,但是有可能会出于某种原因收集用户查询信息进行分析.安全模型是为保证云存储数据安全而必须考虑的.基于服务器获取数据的能力,本研究考虑已知密文的威胁模型.在该模型中,云服务器仅能获取数据拥有者上传的密文文件、密文索引、密文查询向量及检索结果,其余的信息云服务器是无法获知的.

为有效利用加密数据,方案应具备如下性能:

1)支持词频和用户喜好的密文模糊搜索. 方案检索结果由关键词词频信息和用户喜好综合决定.

2)隐私保护.方案能够保护用户的隐私,使云服务器在相应安全模型下,无法获取密文文件、密文索引、查询向量及检索结果以外更多信息.

3)效率.方案在引入关键词词频信息和用户喜好的同时,尽可能保证高效可行.

为提高加密数据的使用效率及检索结果的准确性,本研究采用向量内积方式量化评估查询向量与文件索引的相关程度.利用局部敏感哈希函数及布隆过滤器,构建支持多关键词的密文模糊检索方案. 同时将关键词的词频信息内嵌到文件索引中,将用户喜好引入到查询向量中,以提高查询结果的准确性.在方案构建过程中,为保证文件索引及查询向量的安全性,借鉴kNN方案^[20]中的向量分割和加密思想,对文件索引和查询向量进行加密.

本方案由以下4部分组成:

GenKey(m). 对于给定的参数m, 算法输出密钥SK=(M₁, M₂, S). 其中, M₁, M₂∈R^m×m为可逆矩阵; S∈{0, 1}^m, 是一个二进制向量.

GenIndex_enc={F_C, SK}. 数据拥有者对数据集F_C中的每一个文件F, 构造一个m位的布隆过滤器b作为相应的文件索引向量,并初始化为零向量.在文件F中抽取关键词并统计关键词词频信息,形成关键词集W_C. 将关键词集进行预处理生成二元组w_C. 从LSH族H中选择n个相互独立的哈希函数,将w_i作为哈希函数h_j∈H, 1≤j≤n的输入,输出结果作为文件索引b的下标,对应的值为t_i. 对文件索引b进行加密,以S为向量分裂指示器,将b分裂为2个向量{b₁, b₂}. 若S第j位s_j=1,则i_j'=i_j″=i_j; 否则,i_j'=i_j/2+r, i_j″=i_j/2-r. 其中, s_j∈S、 i_j∈b、 i_j'∈b₁; i_j″∈b₂; r为随机数.然后,用矩阵{M₁, M₂}对{b₁, b₂}加密, 输出加密后的文件索引GenIndex_enc={MT₁b₁, MT₂b₂}.

GenQuery_enc(W^～, SK).用户选择关键词并赋值给不同关键词相应权重生成关键词集W^～, 将关键词集预处理生成二元组集合w^～. 构造m位的布隆过滤器 q作为查询向量,并初始化为零向量.利用与构建文件索引相同的n个局部敏感哈希函数,以w^～_i为输入,输出作为向量q的下标,下标对应的值为d_i. 对q进行加密,以S为向量分裂指示器,将q分裂为2个向量{q₁, q₂}. 若向量S第j位s_j=0, 则置i_j'=i_j″=i_j; 否则,i_j'=i_j/2+r', i_j″=i_j/2-r″.其中, s_j∈S; i_j∈q; i_j'∈q₁; i_j″∈q₂; r'为随机数.用矩阵{M₁, M₂}对{q₁, q₂}加密,得到{M^-1₁q₁, M^-1₂q₂},输出加密后的查询向量GenQuery_enc={M^-1₁q₁, M^-1₂q₂}.

Search(GenQuery_enc, GenIndex_enc). 服务器将查询向量GenQuery_enc与每个文件索引GenIndex_enc作内积计算,输出GenQuery_enc·GenIndex_enc.

出于安全考虑,方案构建过程中参数选择遵循以下原则:① 为了能够抵抗暴力攻击,参数m应该足够长; ② 分裂向量S中0和1的数量应尽可能接近,使向量分裂实现最大限度的随机性; ③ 随机数r∈R的选择应均匀分布.

该方案返回的是根据关键词词频信息和用户喜好程度综合量化后的检索结果,并不仅仅依赖于用户喜好程度.稍微修改方案,就能使该方案的检索结果完全依赖于用户喜好或者关键词词频信息.若要使检索结果仅依赖于用户喜好,在构建文件索引向量时,将方案中所有关键词对应的词频信息替换为“1”,此时无需统计关键词词频信息.若要使检索结果仅依赖于关键词词频信息,在构建查询向量时,将用户输入关键词的权重默认置为“1”即可.

方案中采用kNN^[18]加密算法对向量进行加密,文件索引向量b加密输出值为GenIndex_enc,查询向量q加密输出值为GenQuery_enc.方案检索返回的文件以GenIndex_enc和GenQuery_enc的内积值为依据.内积计算过程为

GenQuery_enc·GenIndex_enc=

{M^T₁·b₁, M^T₂·b₂}·{M^-1₁·q₁, M^-1₂·q₂}=

{M^T₁b₁}^T·M^-1₁q₁+{M^T₂b₂}^T·M^-1₂q₂=

b^T₁·q₁+b^T₂·q₂=bT·q(2)

计算结果表明,方案中向量加密过程的正确性,能确保方案可依据查询关键词返回准确的检索结果.

用户检索过程中,云服务器能根据用户的访问记录与搜索结果获知访问模式.在已知密文模型下,服务器能够获得的信息包括文件密文数据、密文索引数据、密文查询向量数据、查询结果及访问模式. 下面从2.3节设计目标中的3方面进行分析.

1)支持词频和用户喜好的密文模糊搜索.方案在构建文件索引向量时将关键词词频信息引入,在构建查询向量时嵌入查询关键词权重(用户喜好),将文件索引和查询向量的内积结果作为衡量查询关键词与文件相关性的依据,实现云存储中支持词频和用户喜好的多关键词搜索,词频信息的引入体现出关键词的类别区分能力.为确保文件索引和查询向量数据安全,方案采用kNN^[18]算法加密数据项.

2)隐私保护.文件加密采用传统的对称加密技术可保证数据的隐私.限于篇幅,本研究在此不作讨论.方案中文件索引或查询向量的加密过程中算法的复杂度为O(m²), 检索过程中内积计算复杂度为O(m). 在已知密文模型的条件下,分裂向量S是未知量,因此向量 b分裂后的 b₁和 b₂是2个m位的随机向量.假定有n个加密的文件索引,将能够列出2mn个线性方程,其中有2mn个未知量且矩阵M₁和M₂中有2m²个未知量,由于未知量多于已知量,所以无法对方程求解,也无法获得明文的任何信息.对于查询向量如此,查询向量 q分裂为 q₁和 q₂也是2个m位随机向量,能够列出2m个方程,其中,有2m个未知量和2m²个未知量.由于未知量多于已知量,所以无法对方程进行求解.在已知密文模型条件下,无法根据密文恢复出明文的任何信息,因此方案在该模型下是安全的.

3)效率.包括时间的效率和搜索结果准确性方面.

① 时间效率.该方案基于文献[14]进行了改进.假定两个方案初始化参数相同,比较该方案和文献[14]方案的时间效率,结果如表1.其中, I(t)和Q(t)分别为文件索引和查询向量生成时间; I_enc(t)和Q_enc(t)分别为文件索引和查询向量加密时间; S(t)为搜索时间, t_I、 t_Q、 t_qEnc、 t_QEnc和t_S分别为方案中各模块工作的耗时数值.分析表明,该方案在时间效率方面,只有文件索引向量生成用时增加,增量Δ为计算关键词词频信息所用时间.其余性能指标维持不变:查询向量生成时间与关键词的数量呈正相关增长; 文件索引向量和查询向量加密时间随文件数量的正常呈线性增长; 搜索时间与文件集的大小呈线性增长; 查询向量中关键词的数量对搜索时间几乎没有影响.

表1 时间代价比较
Table 1 Time cost comparison

② 搜索结果准确性.方案构造过程使用的工具直接影响检索结果的准确性.构造文件索引以及查询向量过程中,用到的局部敏感哈希函数与布隆过滤器有假阳性或假阴性的情况发生. m位布隆过滤器发生的假阳性率为(1-1/m)^kn. 其中, k为关键词的数量; m为布隆过滤器的长度; n为局部敏感哈希函数的数量. p-stable局部敏感哈希函数假阳性率为Pⁿ₂, 方案假阳性率为[1-(1-p₂)^k(1-(1/m)^k(n-1))]ⁿ. 方案中假阴性率只有哈希函数会引入,方案的假阴性率为1-[1-(1-p₁)(1-p₂)^k-1(1-(1/m)^k(n-1))]ⁿ. 若参数初始化值完相同,则本方案和文献[14]方案将获得基本相同的检索性能.本方案中引入了关键词的词频信息,在文件中出现频率高,而在文件集中出现频率低的关键词将获得较高的加权值,使检索结果获得更多的信息,同时能够体现出关键词具有的类别区分能力.