云计算下支持语义的可搜索加密方法研究

杨清琳，黄治国，钱文标，杨晓雷

(1.广西财经学院 现代教育技术部，广西 南宁 530003；2.河南工程学院 计算机学院，河南 郑州 451191)

0 引 言

随着云计算技术的日趋成熟和快速发展，把数据存储在云端，只需较小的代价就能享受高效快捷的文件存储和处理服务已经成为当下数据存储的一种重要选择。然而，数据安全和隐私保护如何有效地得到保障仍然是很多用户所担心的问题。常见的解决方法是将用户数据先进行加密，再将加密后的密文数据上传到云端，当用户需要使用某个数据时，再从用户密文中检索出需要的文档。如何对加密数据执行检索等操作，是近年来可搜索加密(searchable encryption，SE)技术[1-2]研究的内容。

针对国内外学者可搜索加密技术的相关研究，大致可以分为单关键词可搜索加密、多关键词可搜索加密和模糊加密搜索。单关键词可搜索加密[3-5]是基于对称密码学的精确的单关键字搜索机制，用户只能在一次搜索过程中发送1个单词，很难实现用户的个性化需求，无法满足用户多关键词查询需求，因此支持多关键词的可搜索加密被提出。Cao等[6]提出了MRSE(multi-keyword ranked search over encrypted cloud data)算法，该算法基于安全KNN(k-nearest neighbor)查询技术创建文档向量，增强了隐私数据保护，并利用可逆矩阵与文档向量间“内积相似度”来实现多关键字的排序查询。文献[7]提出的多关键字的排序搜索方案利用树构建索引结构，减少了搜索时间。文献[8]基于同义词查询技术，提出了一种多关键字排序搜索算法，实现了在加密云数据上进行多关键词排序搜索的功能。文献[9]提出一种安全且高效的多关键词密文排序检索方案，同时支持动态更新和并行检索。以上方法只有查询关键词跟预置的关键字完全匹配时，才能有检索结果返回。为解决实际应用中用户输入的搜索请求会出现拼写错误或格式不匹配的问题，模糊搜索方案被提出，实现了当用户输入的查询关键字与预置的关键字不能精确匹配时，也能找到相关文档。文献[8，10]提出了一种将LSH(locality sensitive hashing)和安全KNN方法结合的新型多关键词模糊搜索方案。文献[11]基于布隆过滤器使用对偶编码函数和位置敏感Hash函数来构建文件索引,并使用距离可恢复加密算法加密索引,实现了对多关键字的密文模糊搜索。文献[12]将计数型布隆过滤器与MinHash算法结合，实现了一种可以减少索引构建和查询陷门生成时间的模糊多关键词检索方案。然而，现有的模糊搜索方法中，针对的只是字符串上的模糊，而没有实现关键词语义上的搜索。例如，当用户输入关键词“搜索”时，基于字符串匹配的方案只能返回那些包含有关键词“搜索”的文档，而实际应用中，包含了“检索”或者“查询”关键词的文档也有可能是用户需要的结果。

针对现有的可搜索加密方案没有对查询关键词进行语义扩展，导致用户查询意图与返回结果存在语义偏差，无法满足人们对智能搜索的要求，文中提出了一种支持语义的可搜索加密方法。利用本体知识库对用户查询进行语义拓展，并引入了语义相似度和关键词不同域加权评分，实现了对拓展后的关键词进行权重计算并根据用户需求设定阈值，防止因拓展词过多而语义相似度较大时，影响检索的精确度。并基于向量空间模型，利用文档向量、查询向量分块技术构造出对应的标记向量，以过滤大量的无关文档，并将语义相似度、关键词不同位置加权评分及关键词-文档相关度等影响因子引入到查询-文档的相似度计算得分中，实现了检索结果的有效排序。

1 支持语义的可搜索加密方法系统模型

1.1 系统框架模型

文中设定的系统框架模型如图1所示。其中密钥管理中心负责密钥的生成和发放。数据用户一方面将明文文档及文档索引加密成密文文档及安全索引，并发送至公有云服务器，另一方面从明文文档构造出文档标记向量，发送至私有云。授权用户根据自身需要输入查询关键词，通过本体知识库对关键词进行语义扩展，再将扩展后的查询生成查询标记向量上传给私有云，并使用密钥对扩展后的查询构造出陷门上传给公有云服务器。私有云服务器的主要责任是存储文档标记向量，并根据授权用户提交的查询标记向量生成可能满足授权用户查询请求的候选索引标识符， 提交给公有云，由公有云执行进一步的检索操作。公有云服务器的主要责任是存储密文文档及安全索引，并根据授权用户的查询请求执行检索服务。公有云通过私有云提交的候选索引标识符找出与之相应的安全索引，并用找出的安全索引与授权用户提交的陷门来计算查询-文档相关度得分，返回得分最高的前Top-k篇文档给授权用户。

图1 云计算下支持语义的可搜索加密系统模型

1.2 系统威胁分析

从图1的系统模型中可以看出，用户数据通过网络上传到云服务器中储存，存在网络攻击者截取窃听用户数据的可能，但由于用户数据上传前是经过加密的，即使攻击者盗取用户数据，如果没有获取解密密钥，也不能破解加密文件，因此该类攻击对系统的威胁较弱。

另外公有云服务器具有“诚实而好奇”的特征[13-14]，它会正确地执行授权用户提交的陷门完成查询请求，并会根据私有云上传的候选索引标识符找出与之相对的安全索引，完成检索服务后会如实返回检索结果，但是无法保证公有云不会采取一些措施去分析用户数据、索引及查询请求以获取额外的用户隐私信息。

文中探讨的为已知密文模型，假设公有云在知道数据用户上传的加密文档、加密索引和授权用户发送的查询陷门的前提下，无法利用查询陷门构造出一个新的查询陷门，并且私有云不会对外泄露标记向量信息，会如实地完成授权用户提交的查询请求并提交给公有云。并假定数据用户和授权用户是完全可信的，对存储在公有云上的加密文档有权限共享，不会通过其已了解的部分数据、索引、陷门、密钥等信息来试图攻击其他用户隐私信息，且密钥已经安全分发，即数据用户与授权用户之间的密钥授权已经完成。

2 云计算下支持语义的可搜索加密方法

2.1 关键词-位置加权评分

(1)

2.2 基于领域本体的语义相似度计算

本体是以树状层次结构对概念进行描述和组织，从而构建出概念的语义空间，并使得概念树中任意两个概念节点之间的语义距离具有可计算性。

定义1：文中使用两个节点间的语义距离来计算其语义相似度，对于已知的有向边A→B，节点A的深度Deep(A)代表有向边A→B的深度，则该A→B的语义距离定义为：

(2)

定义2：两个概念节点Vi,Vj之间的语义距离定义为：

Dist(Vi,Vj)=Dist(Vi,Can(Vi,Vj))+

Dist(Vj,Can(Vi,Vj))

(3)

(4)

其中，MaxDeep为本体层次结构的最大深度。

2.3 计算关键词-文档相关度得分

文中使用关键词词频*逆文档率来计算关键词与文档的相关度，计算公式为：

tf-idf=tf(f,t)*idf(t)

(5)

其中，tf(f,t)为关键词t在文档f中出现的频率，idf的计算公式为:

(6)

其中，N表示整个文档集D中包含的所有文档个数，n表示整个文档集D中包含有关键词t的文档个数。

不难发现上述公式存在如下问题：一般情况下，文档集中会包含长短不一的各类文档，而长文档(即大文档)所包含的词条个数通常会大于短文档(小文档)中所包含的词条个数，如果同一个关键词在长文档(10 000个分词)和短文档(100个分词)中的词频都为10次，显然上述公式的计算方法不利于短文档中关键词对文档的相关度得分计算。为公平起见，将对词频做归一化处理，以保证词频计算权重公式更加合理。

(7)

gf_idf=gf(f,t)*idf(t)

(8)

2.4 算法描述

文中基于向量空间模型实现文档检索，每个文档构造一个文档向量，其维度为文档集抽取的关键词集合的个数，从文档中抽取的每个关键词对应向量的每一维，每一维的值设置为相应关键词的权重。用户的查询也被构造成一个查询向量，维度与文档向量一致。用查询向量与文档向量进行内积来计算查询-文档的相关度得分并用该相关度分数对文档进行排序。文中支持语义的可搜索加密算法描述如下：

Step1：数据用户从整个文档集D=(d1,d2,…,di,…,dm)中使用分词工具提取出关键词集合T=(t1,t2,…,tj,…,tn)。

Step2：KMS生成对称密钥K，生成的密钥用三元组形式表示：{S,M1,M2}，其中S为n维随机比特指示向量，M1、M2为n维可逆矩阵，并将密钥K安全分发到数据用户和授权用户手中。

Step3：数据用户用式(1)计算关键词的位置加权评分L，用式(8)计算出关键词在文档中的相关度得分gf_idf。

Step4：数据用户为每个文档di构造出相应的文档向量DVi，若tj∈di，则DVi[j]=1，否则为0。

Step5：数据用户将文档向量DVi平均分成u块，u满足条件u|n，生成文档标记向量DMVi=(DMVi1,DMVi2,…,DMVij,…,DMViu)，方法是如果某块全为0，则DMVij=0，否则为1。并生成对应索引标识符IMi=(DMVi,idi)，后将文档标记向量DMVi及其对应的索引标识符IMi上传到私有云。

Step7：数据用户使用加密密钥K对文档集合进行D=(d1,d2,…,di,…,dm)加密，生成密文文档集合C=(c1,c2,…,ci,…,cm)，然后提交至公有云上存储。

Step8：授权用户输入初始查询关键字Q=(q1,q2,…,qi,…,qn)，再使用本体知识库进行语义扩展，并使用语义相似度公式(4)计算初始关键字与扩展词的语义相似度，选择相似度排前的s个扩展词(c1,c2,…,cs)加入到初始查询来构成最终的查询关键字集合Q'=(q1,q2,…,qi,…,qn,c1,c2,…,cs)，其对应的语义相似度为SC=(sc1,sc2,…,scn,scn+1,…,scn+s)。

Step9：根据语义扩展后的查询关键字集合Q'构造查询向量QV，方法是若ti∈Q'，则QV[i]=1，否则为0。将查询向量QV平均分成u块，u满足条件u|n，生成查询标记向量QMV=(QMV1,QMV2,…,QMVi,…,QMVu)，方法是如果某块全为0，则QMVi=0，否则为1。将查询标记向量上传至私有云。

Step11：私有云对查询标记向量QMV中的每一位1的值与文档标记向量DMVi进行匹配，相同位置上都为1，则说明该文档对应的块包含有查询关键词，则将文档标记向量DMVi对应的索引标识符上的idi记录下来，最终得到所有可能包含查询关键词的候选索引标识集合ID'={…,idi,…,idj}，并将其提交至公有云。公有云根据ID'找到对应的安全索引Ii，将对应的SVi与陷门T进行内积来计算查询与文档的相似度得分。

Step12:对查询-文档的相似度得分进行排序，将前Top_k篇文档返回给授权用户。

Step13:授权用户使用密钥K对返回的文档进行解密，得到原始的明文文档。

3 实验结果分析

文中实验环境为：Windows 7，CPU：i7四核3.4 GHz，内存：8 GB，硬盘空间：1 TB，仿真实验编程语言：Java。建立了一个计算机领域本体知识库，并从Web上抓取计算机领域网页3 000 个作为测试数据集，使用ICTCLAS分词系统抽取出文档关键词。实验的目的是验证在用户初始查询中加入了本体语义推理的扩展词及在查询-文档的相关度分数中引入了语义相似度、关键词不同位置加权评分及关键词-文档相关度得分影响因子后，密文检索效率(用F_measure来衡量)是否被提高。

(9)

当参数α取值为1时，就是常用的F1调和平均考虑了precision和recall的结果，F1值较高则证明文中方法的有效性。

图2给出了文中方法与MRSE方法创建索引所花费时间的变化趋势，可以看出随着文档关键词数量的增加，两种方法创建索引的时间都与之成正比，但由于文中方法需要对文档向量进行分块标记，因此创建索引的时间略有增加。但是对数据用户来说创建索引是外源到云端前的操作，因此对时间上的要求不是很高。

图2 索引创建时间对比分析

由于文中方法基于文档向量和查询向量的分块技术，因此所分块的数量u的取值直接决定了标记向量的维度，u的取值与检索时间成反比。因为u值越大，那么文档向量所分的块数越多，每块的维度“u|n”越小，块全为0的概率越大，私有云对查询标记向量与文档标记向量匹配时，能过滤掉更多的无关文档，从而会节省花费在计算不相关文档相关度分数和文档排序上的时间。但是查询标记向量与文档标记向量是明文保存在私有云上的，u值越大，每块的维度“u|n”越小，越会暴露查询向量与文档向量的信息，因此，需要在考虑检索时间和保护隐私两者间权衡u的取值。

图3 检索时间对比分析

图3给出了文中方法与MRSE方法检索时间的变化趋势，可以看出随着文档关键词数量的增加，两种方法的查询时间都与之成正比，但是文中方法比MRSE方法大大降低了检索时间。因为文中方法基于标记向量，提前过滤了不相关文档，从而节省了花费在计算不相关文档相关度分数和文档排序上的时间。

图4给出了文中方法与MRSE方法的F1比较，其中相关性的判断采用专家评判的方法。可以看出文中方法取得了显著结果，获得了更高的F1值，也即相关度得分更高。因为MRSE采用的是关键词精确匹配，没有上升到语义层面的检索，必然不会检索出与关键词语义上相似的文档。

图4 F-measure(F1)对比分析

4 结束语

针对传统的可搜索加密算法基于关键词精确匹配，查全查准率低，对检索结果没有进行合理的相关度排序，无法满足用户对智能搜索的要求，提出了一种支持语义的可搜索加密方法。该方法利用本体知识库对用户查询进行了语义拓展，通过语义相似度来控制扩展词的规模，防止因拓展词过多产生“查询漂移”。结合向量空间模型实现文档检索，通过文档向量、查询向量分块技术构造出对应的标记向量，过滤无关文档，提高了检索效率，并通过引入语义相似度、关键词不同位置加权评分及关键词-文档相关度得分来构造索引，在查询-文档的相似度得分函数中也引入这三个影响因子，进一步改善了排序效果，从而满足了授权用户对检索结果排序的需求。