基于语义扩展的多关键词可搜索加密算法

徐光伟 史春红 王文涛 潘 乔 李 锋

(东华大学计算机科学与技术学院 上海 201620)

摘 要 云存储中为保护数据所有者的数据安全性和隐私性,采用数据加密后再提供按需数据服务的方式,可搜索加密技术是解决加密数据接入的关键方法.但搜索时的多关键词不加区别和忽视索引之间的关联性会造成搜索时间长和准确率低等问题,提出一种基于语义扩展的多关键词可搜索加密算法.首先,基于依存句法区分多关键词的重要性进行语义扩展,并生成多关键词陷门;其次,基于凝聚层次聚类和关键词平衡二叉树,构建索引关联性的索引树结构;最后,引入剪枝参数和相关性得分阈值对索引树进行剪枝,在索引树中过滤掉索引无关的子树.基于真实数据集的理论和实验分析表明:所提算法能够抵抗规模分析攻击,并能提高搜索时间效率和搜索准确率.

关键词 云存储;可搜索加密;语义扩展;依存句法;凝聚层次聚类

现今,云存储给数据用户(个人和企业)提供了一个第三方服务平台.为了节省本地存储成本和管理成本,用户可以将自己的数据外包到云服务器[1].但是,将数据(特别是敏感数据)直接上传到云服务器中,使得数据拥有者将数据的管理权限完全给予云服务提供商,数据安全性不能得到保证[2].为了保证上传数据的隐私性,目前最常用的方法是数据拥有者将数据加密后再上传到云服务器,这带来了新的问题:传统的检索技术不再适用[3].为了能够使用户有效地获取加密数据,研究人员提出了可搜索加密技术(searchable encryption, SE)[4].首先,数据拥有者在上传数据文件之前,根据数据文件来抽取关键词,并建立索引.然后,将索引和数据文件加密并上传到云服务器.当数据使用者想要获取加密文件时,数据使用者输入相关关键词并使用相应的加密算法进行加密生成安全陷门,然后将安全陷门发送给云服务器,云服务器接收安全陷门并和索引进行匹配,最后返回相关加密文件给用户,用户在本地进行解密,获得所需文件.

最近,许多研究者提出了一系列的可搜索加密算法.Song等人[4]提出了一种实现密文搜索的可搜索加密算法,但是他的算法只支持单关键词搜索;Li等人[5]确定了有效模糊关键词搜索加密数据的问题,利用编辑距离和通配符的方法构建模糊关键词集;随后,Cao等人[6]提出了一种安全的多关键词可搜索加密算法(multi-keyword ranked search over encrypted cloud data, MRSE),利用空间向量模型和向量内积实现高效检索;Wang等人[7]将局部敏感Hash(locally sensitive Hash, LSH)和布隆过滤器结合解决了基于多关键词的模糊搜索问题;沿着这个方向,文献[8-9]研究者提出了验证返回结果正确性的算法.这些算法提出了不同的搜索功能,例如单关键词搜索、多关键词搜索和模糊搜索等;除了在功能上多样化之外,还有一些研究者[10-11]从提高检索密文文件的效率和准确性出发提出了基于TF-IDF算法的可搜索加密算法,并为了节省传输成本只返回top-k个文档.

虽然上述算法有效解决了可搜索加密问题,但它们也存在一定的局限性.1)现有工作中大多将搜索关键词视为同等重要,忽略了关键词的差异性,导致关键词扩展后返回的结果不能满足用户的搜索意图;2)现有工作没有考虑索引之间的关联性,关键词搜索必须遍历所有索引,使得搜索效率较低.

因此,为了解决上述问题,我们研究了关键词之间的关系,提出一种基于语义扩展的多关键词可搜索加密算法(multi-keyword searchable encryption algorithm based on semantic extension, SEMSE),以搜索出满足用户意图的数据文档.此外,在搜索阶段,利用凝聚层次聚类和关键词平衡二叉树的思想将相似度高的索引聚类在同一个子树下,从而构建了一个新的索引树结构,并通过引入剪枝参数和相关性得分阈值对索引树进行剪枝来过滤掉大量不相关的子树,从而大大减少了搜索时间.最后,所提算法可抵御2种不同的安全威胁.本文的主要贡献有3个方面:

1) 考虑不同搜索关键词之间的关系,提出一种关键词权重算法,以区分不同搜索关键词之间的重要性,利用关键词权重来选出需要扩展的关键词,而不是查询中的所有关键词来进行多关键词排序搜索;

2) 利用凝聚层次聚类和关键词平衡二叉树思想将相似索引聚类在同一个子树下,从而构建一种新的索引结构.然后设置剪枝参数和相关性得分阈值对索引树进行剪枝来过滤掉大量不相关的子树,从而大大减少搜索时间;

3) 应用真实数据集的实验表明,与现有算法相比,我们所提的算法在保证隐私的前提下,提高了搜索效率和准确性.

1 相关工作

近些年,可搜索加密算法获得了长足的发展,许多算法都在基于文档的可搜索加密中提供了丰富的搜索功能.此外,可搜索加密算法分为2类:1)非对称可搜索加密(asymmetric searchable encryption, ASE);2)可搜索对称加密(searchable symmetric encryption, SSE).这里,我们只关注后者.

Song等人[4]第1次提出了对称可搜索加密算法,该算法使用顺序扫描密文文档,这是首次定义了对称可搜索加密问题并给出了解决算法,对后续研究起到极大的推动作用.但是,该算法只接收固定长度的关键词且存储复杂度比较高.Goh[12]定义了一种安全索引结构,并为自适应选择攻击的语义安全性建立了一种安全模型;Curtmola等人[13]针对对称可搜索加密算法给出了安全性定义,并基于倒排索引结构提出了一种新的与文档相关联的索引结构;Cash等人[14]提出了一种新的支持大型数据库的动态SSE算法;Stefanov等人[15]首次针对动态搜索加密问题提出了一种在次线性时间进行更新和搜索的解决算法,虽然该算法搜索时间是非线性的,但是随着索引数量的增加,实际搜索时间还是非常大;通过陷门置换的方式,Bost[16]首次实现了支持前向隐私的可搜索加密算法,并推广到任意基于索引的SSE算法中;Kim等人[17]提出了一种称为双字典的数据结构,该字典是一种包含前向和倒置索引的链接字典.为了实现前向安全性,该算法采用与前向搜索令牌无关的新密钥来加密新添加的数据文件;文献[17-18]提出了一些支持前向和后向安全的SSE算法,然而这些算法都支持单关键词搜索.

Fig. 1 Keyword balanced binary tree
图1 关键词平衡二叉树

另一方面,为了丰富搜索表达,大量研究工作集中在设计多关键词可搜索加密算法.文献[19-21]中提出的解决算法着重于如何在提供隐私保护的同时对加密数据进行多关键词联合搜索,这些算法的时间开销和文件集的大小成线性关系.Cash等人[22]提出了一种具有可扩展性的对称搜索加密算法,该算法将计算开销减少到子线性,并将搜索模式扩展到布尔查询.Cao等人[6]基于文献[23]提出的安全kNN技术解决了支持搜索结果排序的多关键词搜索问题,提出了基于向量空间模型和向量内积计算的可搜索加密算法,该算法支持2种安全威胁.为了解决多关键词搜索和搜索结果排序问题,Sun等人[24]提出了一种基于词频的索引和余弦相似度建立的向量空间模型,以提高搜索的准确性.为了消除预定义字典的存储开销,Wang等人[25]通过在Bloom Filter中使用局部敏感Hash构建文件索引,并实现了文件更新,Fu等人[26]提出了支持并行计算的加密云数据的多关键词排序搜索算法.Xia等人[27]在文献[6]的基础上提出了一种支持多关键词排序搜索和动态更新的加密搜索算法,该算法利用向量空间模型和TF-IDF来实现多关键词排序搜索并构建了基于树的特殊索引结构来降低搜索的时间复杂度.

在算法中,未考虑搜索关键词之间的关系和索引之间的关联性,导致搜索结果不能满足用户需求,搜索的效率还有待改善.

2 预备知识

2.1 安全kNN

为了安全高效地获得索引向量和搜索陷门之间的相关性得分,在2009年Wong等人[23]提出了一种迄今为止使用最广泛的安全kNN算法.安全kNN的目标是将数据集中的k个最近点进行安全地识别、匹配给定的点,而不需要使用服务器来获取数据集的内容.该算法通过计算2个向量之间的向量内积来获得它们之间的相关性得分.文献[6]提出了基于安全kNN算法的多关键词排序搜索加密算法,并给出了安全性证明.在安全kNN算法中,首先,需要设置一个用来加密向量的安全密钥(S,M1,M2).其中Sm位的二进制向量,由{0,1}组成,用于将向量分割成2部分,M1M2是2个用于加密向量的可逆矩阵.

2.2 关键词平衡二叉树

2015年Xia等人[27]设计了一种基于关键词平衡二叉树索引结构(keyword balanced binary tree, KBB-Tree)的多关键词排序搜索算法,并设计了一种贪婪深度优先遍历算法,其算法的时间复杂度基本上保持为对数级,能够实现高效的多关键词排序搜索.关键词平衡二叉树的索引结构采用TF-IDF表示文档关键词的权重值,并采用向量空间模型构造一个索引向量,最后通过安全kNN算法进行加密计算相关性得分,从而返回top-k个排序结果.

如图1所示为基于关键词平衡二叉树的索引结构.KBB-Tree的节点标识为u=(ID,I,Pl,Pr,FID).其中,ID表示节点的唯一编码;I表示文档向量;PlPr分别表示节点u指向左孩子的节点和指向右孩子的节点;对于FID来说,如果节点是叶子节点,则FID表示文档编号,如果节点是中间节点,则FID为空.在构建关键词平衡二叉树时,从叶子节点进行构建生成中间节点,比较2个叶子节点中的文档向量I,将向量中取值较大的值作为中间节点中I对应向量的取值.根据这一原则逐步构建中间节点,直到生成根节点为止.

其中,N表示索引树的中间节点,F表示文档所在的叶子节点,中间节点的向量值为其左右孩子节点对应位向量的最大值.在搜索过程中,通过基于KBB-Tree的索引结构和贪婪深度优先遍历算法能够极大地节省搜索的时间开销,提高搜索效率.但是当输入关键词字典中不存在关键词时,该索引结构会线性地执行遍历操作,致使搜索效率大大降低.

2.3 依存句法

依存句法(dependency grammar)的主要用途是分析句子的句法结构,从而更好地理解句子的含义[28].依存句法具有一个一般性的假设,即句法结构本质上包含词和词的关系,这种关系被称为依存关系(dependency relations)[29].在依存句法中,能够准确识别出关键词的词性以及句子中关键词之间的支配和从属的关系,其中属于支配地位的关键词称为支配词(head),处于被支配地位的关键词称为从属词(dependency)[28].句子中各关键词之间的关系是单向的,并通过语义弧链接它们之间的依赖关系.对于句子中关键词的依存关系,需符合4条公理.

1) 句子中有且仅有一个关键词是独立的;

2) 其他关键词必须依存于另一个关键词;

3) 任何关键词不能同时与2个关键词之间存在依存关系;

4) 如果2个关键词AB之间存在依存关系,而这2个关键词之间还有其他关键词C,则该关键词C只能依存于关键词AB,或者依存于AB之间的其他关键词.

与短语结构句法不同,依存句法中不存在短语节点,只考虑句子各成分之间的依赖关系,如图2所示为以“Information security is very important”为例的依存句法结构依赖关系图.

Fig. 2 Dependency grammar structure
图2 依存句法结构

其中,root表示根节点关系,compound表示补语关系,nsubj表示名词主语关系,cop表示系动词关系,advmod表示状语关系.

3 模型与问题描述

3.1 系统模型

如图3所示,本系统模型主要分为3个不同实体:数据拥有者、数据使用者和云服务器.

1) 数据拥有者.在数据文档F={F1,F2,…,Fn}外包给云服务器之前,首先对数据文件提取关键词W={w1,w2,…,wm} 并采用安全密钥SK加密关键词构建安全索引I={I1,I2,…,Im}.然后,采用对称加密算法加密数据文档生成加密数据集C={c1,c2,…,cn}.最后,将加密数据集C和安全索引I一同上传至云服务器并将对称密钥sk和安全密钥SK发送给数据使用者.

2) 数据使用者.首先,接收从数据拥有者发送的对称密钥和安全密钥;然后,在本地输入一定的关键词进行搜索,使用安全密钥生成安全陷门T并将安全陷门T发送给云服务器;最后,获取云服务器返回的加密数据文件,并利用对称密钥进行解密.

3) 云服务器.云服务器存储数据拥有者发送的加密数据集和安全索引,并为数据使用者提供数据搜索服务等.当数据使用者发送安全陷门给云服务器时,云服务器利用指定算法将安全陷门和安全索引进行匹配,并返回top-k个密文给数据使用者.

Fig. 3 System model
图3 系统模型

为了便于描述多关键词可搜索加密算法,表1给出本文使用到的符号定义.

Table 1 Symbol Definition
表1 符号定义

SymbolsDescriptionFDocuments uploaded by the data userWExtracted keywords from documentsCEncrypted documentsSKKey generated by the data ownerskSymmetric keyIIndex vector constructed by document keyword WqSearch keywords input by the data userQSearch vectors constructed by keyword featuresISecurity index generated by encrypted index vectorQSecurity trapdoor generated by encrypted search vectornNumber of documentsmNumber of keywords extracted from documents

系统模型包括5个多项式时间算法SSE={KeyGen,BuildIndex,TrapdoorGen,Search,Decrypt},具体过程为:

1) 初始化KenGen(1λ)→(SK,sk).是一个由数据拥有者执行的概率密钥生成算法,该算法将安全参数λ作为输入,然后输出密钥SK={S,M1,M2}和对称密钥sk.

2) 索引构建BuildIndex(sk,SK,F)→(I,C).是一个概率算法,将密钥SK和外包文档集F作为输入,对文档集进行关键词提取,生成关键词字典W,并构建关键词索引,然后使用密钥SK加密索引向量和使用对称密钥sk加密文档集F.算法输出安全索引I和密文集C.

3) 陷门生成TrapdoorGen(Wq,SK)→T.是一个概率算法,该算法将密钥SK和搜索关键词Wq作为输入,利用密钥SK对搜索关键词进行加密生成安全陷门T,算法返回安全陷门T.

4) 搜索Search(I,T,k)→Ck.是一个由云服务器执行的确定性算法,该算法将安全索引I、安全陷门T和需要返回文档的个数k作为输入,计算安全陷门和安全索引的向量内积作为相关性得分,并对相关性得分进行排序.云服务器返回包含top-k个密文的文档集Ck给数据使用者.

5) 解密Decrypt(Ck,sk)→Fk.是一个确定性算法,该算法将密文文档Ck和密钥sk作为输入,数据使用者通过对称密钥sk对加密文档集Ck进行解密,算法返回明文数据集Fk.

3.2 安全威胁

采用文献[6,25,27]中提出的安全威胁,假设数据拥有者和数据使用者是可靠的,而云服务器是“诚实且好奇的”,即它会“诚实地”根据算法的指定协议存储数据拥有者的数据文档,但对存储的数据“感到好奇”,即云服务器想通过推断或分析加密数据和安全陷门信息来获取数据所有者的数据信息.

1) 已知密文模型.在已知密文模型中,假设云服务器仅能获取数据拥有者上传的加密文档集C、加密的索引向量安全陷门T和云服务器掌握的部分明文索引向量Ip及其加密形式且各索引向量之间线性无关而不能获取其他任何信息,即安全威胁表示为

2) 已知背景模型.在已知背景模型中,云服务器能够获取比已知密文模型更多的数据信息,比如与安全陷门相关的信息或者数据集之间的统计信息等.因此,云服务器具有更强的攻击能力.云服务器可以根据已知的陷门信息,并借助一些统计信息来推断,分析上传的安全陷门、安全索引和搜索结果等来确定搜索中的某些关键词的明文信息.

3.3 问题描述

1) 现有的算法都是将搜索关键词彼此之间视为同等重要,忽略了关键词的重要性的不同,导致关键词扩展后搜索准确率较低.

2) 现有多关键词可搜索加密算法在构建索引的过程中没有考虑索引之间的关联性,关键词搜索必须遍历所有索引,使得搜索效率较低.

4 基于语义扩展的多关键词可搜索加密

本文提出一种多关键词陷门生成方法,以区分不同关键词权重,然后详细描述了多关键词排序搜索过程,最后给出了SEMRS算法的具体实现.

4.1 多关键词陷门生成

1) 关键词权重计算

用户进行搜索时,输入的关键词存在一定的句法关系,即关键词之间存在修饰和被修饰的关系.因此,关键词之间的句法关系一定程度上反映出关键词的重要性.此外,如果一个关键词和不止一个关键词之间具有句法关系,则该关键词具有更大的重要性.

因此,将搜索关键词之间的句法关系视为关键词重要性的表现形式.对搜索关键词之间的句法关系进行分析,如果存在句法关系,则增加关键词权重.

定义1. 关键词关系.对于每个关键词来说,设初始关键词关系为1,如果该关键词和其他关键词之间具有句法关系,则其权重变为1+R,其中R表示2个关键词之间的句法关系.

以2个关键词之间的句法关系关联关键词,并使用短语结构树中的距离来量化它们的关系,其中树中的叶子节点为输入的关键词,中间节点为短语结构成分.如果2个关键词之间的距离越近,则说明它们之间的关系越紧密.由于2个关键词之间共享句法关系的特点,其权重应该分为2部分,这里采用关键词到公共祖先节点的距离来衡量关键词权重的分配比例.对于2个搜索关键词q1q2,句法关系表示为R(q1,q2).如果q1q2之间存在句法关系,则q1 的关系增加了 的关系增加了其中d1d2 表示关键词与其公共祖先节点之间的距离,d表示关键词之间的距离,即d=d1+d2.

对于任意的搜索Q={q1,q2,…,qz},z是搜索关键词的个数,对于关键词q,其权重值为p×z,其中p是搜索关键词q的权重比率,即因此,搜索关键词q的权重KW表示为

(1)

Fig. 4 Keyword phrase structure tree
图4 关键词短语结构树

然后将结构树转换为依存句法结构,获取关键词之间的句法关系,如图5所示:

Fig. 5 Keyword dependence relations
图5 关键词句法关系

其中,“root”表示依存句法结构的根节点关系,“amod”表示形容词修饰语,“compound”表示名词复合修饰语,“dep”表示依赖关系,“NP”表示名词短语,“NN”表示常用名词单数形式,“JJ”表示形容词、数字和序号等.我们采用关键词之间的句法关系和短语结构树中关键词之间的距离来衡量关键词的权重,例如“encryption”和“multiple”的距离为5,则它们之间的句法关系为R(a mod)=1ln 5.根据上述规则,可以得出总的关键词关系为4+1ln 4+1ln 4+1ln 4+1ln 5=6.785,而“multiple”的关系为1+1ln 4+35ln 5=2.094,然后利用关键词权重式(1)可知,“multiple”的关键词权重为KW(multiple)=1.23.同理,其他关键词的权重分别为KW(search)=0.81,KW(keyword)=1.01,KW(encryption)=0.95.

2) 多关键词的语义扩展

对关键词进行扩展,不是对所有关键词进行扩展,而是通过关键词权重计算方法选出权重最大的关键词作为待扩展关键词,然后根据WordNet[31]获取关键词的同义词,这样对于每个待扩展的关键词都构建了一个同义词集,最后通过2个关键词概念之间的最大语义相似度近似2个关键词的语义相似度,即:

(2)

其中,S(wi),S(wj)是关键词wiwj所包含概念的集合.这里,采用基于信息内容(IC)的David算法[32]来衡量2个概念之间的相似度.

3) 陷门生成

为了更好地反映关键词和文档的关系,在关键词权重中引入了TF-IDF技术,对于每个文档关键词w,如果其在关键词词典中,则将关键词权重设置为关键词权重值和该关键词在文档中的逆文本频率IDF的乘积,即KW×IDF,代替基于原关键词权重值,将扩展关键词的权重值设置为其语义相似度得分、对应的搜索关键词的权重和逆文本频率IDF三者的乘积,即KW×sim×IDF.

4.2 多关键词排序搜索

1) 基于凝聚层次聚类的索引构建

Fig. 6 Index tree construction process
图6 索引树构建过程

在对文档加密之前,需要构建文档的索引,Xia等人[27]提出了基于KBB-Tree的索引结构,相比于线性扫描的MRSE算法[6],通过构建索引树的方式确实大幅提升了搜索效率,但是该算法没有考虑索引之间的关联性,使得相似度高的索引随机分布在索引树的各个子树中,导致多关键词搜索必须遍历所有索引才能最终确定搜索结果.因此,基于凝聚层次聚类(agglomerative hierarchical clustering)[32]的思想将相似索引进行聚类为一个平衡二叉树索引结构.凝聚层次聚类通常是指将每个对象都作为一个单独的聚类簇,然后每一次聚类最相关的2个簇,直至将所有簇聚类为一个簇为止.由于每次仅聚类2个最相关的簇,使得构成树的高度非常大,不利于遍历整棵树.因此,在每一轮的聚类操作中,根据簇集合中簇中心向量的欧几里德距离两两合并,从而构成平衡二叉树形式,其中簇中心向量指簇集合中各节点的均值,如图6所示为索引树构建过程.为了便于描述索引树的构建,先给出了索引树节点的数据结构.

定义2. 索引树节点的数据结构.设索引树节点的数据结构由四元组FID,NV,NL,NR组成.其中,FID表示文档的唯一标识符,NV表示该节点的节点向量,NL表示该节点的左孩子,NR表示该节点的右孩子.如果节点u是叶子节点,则FID是文档的唯一标识,NV是文档的索引向量,NLNR为空;如果节点u是中间节点,则FID为空,NLNR表示节点的左孩子和右孩子,左孩子NL和右孩子NR的簇向量最大值为

NVi=max{NL.NVi,NR.NVi}.

(3)

如图6所示为索引树构建过程,索引树的构建的基本思想是:首先,根据定义4索引树节点的数据结构,创建叶子节点;然后根据凝聚层次聚类生成中间节点直至根节点,具体过程为:

假设8个文档向量{F1,F2,…,F8},根据定义4构建索引树的叶子节点{u4,1,u4,2,…,u4,8},SV表示簇中心,N表示节点u包含的节点个数,则簇中心为

(4)

(1) 计算叶子节点簇中心之间的欧几里德距离为

(5)

将欧几里德距离最小的2个节点进行聚类生成一个簇,该节点的节点向量NV的计算如式(3),簇中心的计算如式(4).然后再计算剩余节点簇中心的欧几里德距离,并聚类最小的2个簇,直至聚类所有节点.聚类后的簇为Cu3,1={F2,F4},Cu3,2={F5,F7},Cu3,3={F1,F3}和Cu3,4={F6,F8}.

(2) 根据步骤1的过程,依次对阶段1生成的簇进行聚类,聚类之后的簇为Cu2,1={F2,F4,F5,F7}和Cu2,2={F1,F3,F6,F8}.

(3) 根据步骤2的过程,对阶段2生成的簇进行聚类,生成索引树的根节点.

通过上述聚类过程,生成一个自底向上的平衡二叉树,该二叉树的高度为lb m+1,能够极大地减少了二叉树的遍历时间.

2) 多关键词的排序搜索

由于通过凝聚层次聚类构建索引树使得相关的索引位于同一个子树中,在索引遍历过程中只需根据搜索关键词和索引的相关性得分找出对应的簇就能实现整个遍历过程,而无需遍历整个索引树.因此,设置一个剪枝参数PT和一个相关性得分阈值sysp来过滤不相关的子树,其中剪枝参数可以根据用户不同偏好设置,相关性得分阈值是结果集中相关性得分最小的取值.通过索引树的构建可知,中间节点的节点向量是该节点的左孩子和右孩子的节点向量的最大值,即如果中间节点的节点向量和搜索关键词的相关性得分小于剪枝参数PT和相关性得分阈值sysp,则以该节点为根节点的索引树的所有节点与搜索关键词的相关性得分都小于剪枝参数PT和相关性得分阈值sysp,对该索引树进行剪枝.

如图7所示为关键词搜索过程,设索引树包含8个文档,返回的文档个数为5,搜索向量为Q=(0.3,0.6,0,0.1),关键词搜索路径为虚线箭头所指方向.首先,搜索叶子节点u4,1,并计算搜索向量Q和叶子节点簇向量的相关性得分.然后判断相关性得分Score(Q,u4,1.NV) 是否大于剪枝参数PT,如果大于剪枝参数,则F2插入结果集中.继续遍历叶子节点u4,2,相关性得分Score(Q,u4,1.NV)>PT,将F4插入结果集Rlist中.继续遍历其他子树,当结果集Rlist={u4,1,u4,2,u4,3,u4,4}时,结果集中节点个数为4,小于需要返回的文档数,继续判断剩余节点得出Score(Q,u4,1.NV)<PT,对该节点所在子树进行剪枝,此时搜索结束,返回结果集.此外,当结果集中满足用户需求的文档数后,将相关性得分阈值设置为结果集中相关性得分最小值.

Fig. 7 Keyword search
图7 关键词搜索过程

由于剪枝参数和相关性得分阈值的设置并没有返回数据使用者想要返回的5个文档而是返回了最为相关的4个文档,且在进行关键词搜索过程中并没有遍历所有节点,而是对于中间节点的相关性得分较小的子树进行剪枝,这样极大地节省了遍历时间.

4.3 算法具体实现

本节基于语义扩展的多关键词排序搜索算法主要包括6个部分:GenKeyBuildIndexTreeQuery-ExtensionGenTrapdoorSearchDecrypt.

1) 初始化GenKey(k)→(SK,sk)

首先,给定一个安全参数k,生成多关键词排序搜索算法的安全密钥SK=(S,M1,M2).其中Sn+2位的由{0,1}组成的分割指示向量,用来对索引和陷门进行分割;M1M2是一组(n+2)×(n+2)维的可逆矩阵,用来加密被分割的索引和陷门,其中n表示字典中关键词的数量,将可逆矩阵M1拆分成d个维度为的可逆矩阵{M1,1,M1,2,…,M1,d},同理,将可逆矩阵M2拆分成d个维度为的可逆矩阵{M2,1,M2,2,…,M2,d},其中d是正整数.此外,系统根据指定的对称加密算法生成对称密钥sk.然后,数据拥有者将密钥(SKsk)发送给授权的数据使用者.

2) 构建索引树

首先,数据所有者提取关键词以构建关键词集W={w1,w2,…,wm} 作为字典.这里,对于每个文件fF,数据所有者生成一个n维的索引向量Ii,如果该向量包含关键词wiW,则数据所有者将相应位设置为其词频TF值,而不是设置为没有权重的数字“1”.然后数据所有者将向量扩展到(n+U+1)维,第(n+1)维到第(n+U)维设置为1,第(n+U+1)维设置为1,并将向量的前(n+U)维赋一个随机数r.那么,索引向量Ii变为(rIi,r,1).然后通过指示向量S拆分索引向量Ii为2个子向量{I′,I″},规则如下:对于索引向量Ii的每个元素ij,如果Sj=0,则设否则,如果Sj=1,则设其中μr是随机数.然后,将索引向量I′和I″分别拆分成d段,即利用可逆矩阵M1M2对索引进行加密最后,根据基于凝聚层次聚类的索引构建方法构建索引树.

3) 关键词扩展QueryExtensionWe

首先,根据关键词权重计算方法计算搜索关键词Wq的权重,并选出需要扩展的关键词.然后,根据基于语义相似度的关键词扩展算法提取关键词的同义词集,将关键词转换为概念,并构建概念层次树,计算关键词之间的语义相似度.最后,选出相似度最大的若干关键词作为扩展关键词,并将扩展关键词和搜索关键词一起作为搜索关键词We.

4) 陷门生成

首先,数据使用者根据扩展后的搜索集合We生成m维的搜索向量Q,其中对于每个搜索关键词qiWe,如果qiW,则将搜索向量的对应位置设置为KW(qiIDF.此外,对于扩展关键词eqj,如果eqjW,则搜索向量的相应位置设置为KW(eqisim×IDF.然后,搜索向量Q扩展到n+U+1维,在Q[n+1]到Q[n+U]之间随机插入V个虚拟关键词,其值设置为0.1,向量Q[n+U+1]赋一个随机数t,则扩展后的搜索向量Q为(Q,εi,t).然后,数据使用者通过指示向量S拆分搜索向量Q为2个子向量{Q′,Q″},拆分规则如下:对于搜索向量的每个元素qi,如果sj=0,则设否则,如果sj=1,则设其中μr′是随机数.最后,将搜索向量{Q′,Q″}分别拆分成d段,即并通过可逆矩阵(M1,M2)分别加密搜索向量Q′和Q″为安全陷门将安全陷门发送给云服务器.

5) 搜索

根据上述步骤生成的安全索引和安全陷门并应用索引遍历方法,计算安全索引和安全陷门的向量内积,即相关性得分,安全索引和安全陷门之间的相关性得分如式(6)所示.并对相关性得分进行排序.最后,返回前top-k个密文文件C给数据使用者.

Score=·=(MT1I′)TM-11Q′+
(MT2I″)TM-12Q″=IQ′+IQ″=
(I′,I″)(Q′,Q″)=rI·Q+Σεvi

(6)

6) 解密Decrypt(C,sk)→F

数据使用者接收到云服务器返回的密文文件,使用对称密钥sk对密文文件C进行解密来恢复原文件的内容.

基于语义扩展的多关键词排序搜索算法具体如算法1所示.

算法1. SEMRS算法.

输入:剪枝阈值PT、相关性得分阈值sysn、需要返回的文档个数k;

输出:明文F.

① 初始化密钥参数x;

SK,skGetkey(x);

③ for i=1;in;i++ do

ucreateNode(Fi,SK);

⑥ end for

WequeryExtension(Q);

⑨ for the node u do

end for

FDecrypt(Rlist,sk);

Return F.

在算法1中,行①是生成密钥的过程,行②~⑤是构建索引的过程,行⑥~⑦是生成安全陷门,行⑧~是多关键词搜索,如果中间节点的相关性得分小于剪枝参数和得分阈值,则进行剪枝,行是对服务器返回的结果集进行解密.

5 安全性和性能分析

5.1 安全性分析

本节将分别从已知密文模型和已知背景模型来分析所提算法的安全性.

1) 已知密文模型中的安全性

攻击者可以通过已知的密文建立线性方程,来计算安全索引和陷门的真实值[6].云服务器通过指示向量S将索引向量拆分成2个子向量{I′,I″},其中云服务器对于拆分前的索引向量I是已知的,但是对于拆分后的向量是未知的.然后使用可逆向量M1M2分别加密拆分后的2个向量{I′,I″},即从而构成一个线性方程组:

(7)

其中,Ip包含2×n×|Ip|个未知数,可逆矩阵M1M2分别包含n×n个未知数.通过式(7)可以得出方程组中仅包含2×n×|Ip|个方程式.根据行列式的性质可知,当未知数的数量大于方程式的数量时,不能计算出方程式的解,即根据式(7)得不到可逆矩阵M1M2.同理,通过安全陷门也得不到可逆矩阵M1M2.因此,本算法采用的拆分索引和搜索向量的加密机制能够保证数据的隐私性.

2) 已知背景模型中的安全性

根据文献[6]中的证明可知,在已知背景模型中,云服务器能够通过分析词频分布图来推断关键词信息,因此,算法需要抵抗随机数引起的词频统计攻击带来的信息泄露.为了最大化相关分数分布的随机性,算法应该存在至少2w个不同的值.假设每个索引向量有2w个不同的随机数,则2个随机数相同的概率应该为12w,此外,不同的数量等于其中当vu=2时,达到最大值.我们设u=2wv=w时,不同随机数的数量应该大于2w.因此,在每个向量中至少存在2w个虚拟项,其中在每个向量中有一半被随机选择生成随机数此外,每一个εi遵循相同的均匀分布M(μ′-cμ′+c),根据中心极限定理可知,遵循正态分布N(μσ2),其中均值μ=ωμ′和方差σ2=vc23.当σ越大,云服务器就越难以学习有关原始相关性得分的统计信息,但搜索准确性会降低.因此,选择σ应该在隐私和搜索准确性之间进行权衡.

在已知背景模型中,数据加密和索引及陷门的加密使用的是相同的加密方法.此外,在已知背景模型中引入了虚拟关键词.因此,SEMRS算法保证了数据的安全性与索引和陷门的安全性.

5.2 性能分析

为了进一步验证算法的性能,本节分别从算法的各主要阶段:1)系统初始化;2)索引构建;3)陷门生成;4)搜索等方面进行分析.假设加密算法采用传统的对称加密算法,文档关键词的数量为n,文档集中包含文档的个数为m,搜索关键词个数为x,扩展的关键词个数为y,分析:

系统初始化阶段,仅进行密钥生成,因此该阶段的时间复杂度为O(1).

索引构建阶段,主要时间消耗为索引加密,先采用的安全kNN算法对索引进行分割,然后使用2个可逆矩阵相乘进行加密,其安全索引构建的时间复杂度为O(me2),其中e是关键词向量的长度.

陷门生成阶段,安全陷门的生成与安全索引构建过程相似,主要时间消耗都是关键词加密和关键词扩展,其时间复杂度也是O((x+y)e2).

搜索阶段,计算索引向量和陷门向量的相关性得分的时间复杂度为O(n+U),其中U是添加的虚拟关键词的个数.索引树的高度为lb m+1,该阶段的

时间复杂度是O((n+U)lb m)(lb m+1).

此外,由于扩展关键词个数y应小于搜索关键词个数x,且x+ym.在陷门生成时,无论搜索关键词集合中有多少关键词,陷门长度始终等于所提取文档关键词字典长度.算法主要的网络通信开销是传输安全陷门T到云服务器的开销,由于在本地无论输入多少关键词,使用安全密钥生成陷门T的大小|T|始终是固定的,因此,即使面对大规模数据集合,陷门传输的通信开销始终为|T|.

6 实验分析

实验采用Java语言编写,并在AMD5 CPU 2.0 GHz的Windows 10环境执行.数据集为联邦能源监管委员会发布的包含517 000多条邮件的Enron email dataset[33].

6.1 准确率和召回率

为了表现扩展关键词数量的影响,设扩展关键词和原搜索关键词之间的比率参数为ρ,其中ρ∈[0,1].即最少关键词扩展数量为0,最多关键词扩展为原关键词的个数.如图8(a)所示,横坐标为扩展关键词和原搜索关键词之间的比率参数ρ,步长为0.1,纵坐标为搜索准确率.设返回的文档数为50,数据使用者搜索相关的文档数量为80,则从图8(a)中,可以得出随着比率参数ρ的增加,搜索准确率逐渐上升,直至比率参数为0.4时,准确率和召回率达到最大值,随后准确率和召回率开始逐渐降低,即在基于多关键词扩展的排序搜索算法中当比率参数为0.4时,搜索性能达到最优.

Fig. 8 Accuracy and recall
图8 准确率和召回率

图8(b)所示为随着搜索关键词的变化,准确率和召回率的变化趋势.随着搜索关键词的不断增加,SEMRS的准确率和召回率也不断提高,即搜索关键词的数量越多,则搜索结果越能够满足需求.

SEMRS的准确性受标准差σ影响,如果为随机变量设置较小的标准差σ,则SEMRS将获得更高的精度性,反之亦然,结果如图9(a)所示.图9(b)在同一标准差、搜索关键词个数和已知背景模型中,SEMRS,EDMRS[27]和MRSE[6]的变化.显然,SEMRS在排名隐私下能够获得更高的准确性.

Fig. 9 Precision change under standard deviation
图9 在不标准差下准确率变化趋势

Fig. 10 Index building time comparison
图10 索引构建时间比较

6.2 索引创建时间

索引构建阶段主要执行索引构建和索引加密.其中索引构建的计算成本主要取决于数据集中的文档个数,而索引加密又与关键词字典包含的关键词数量有关.此外,索引构建过程是一个一次性过程,即只在初始阶段进行索引构建,除非后续对数据集进行了更新操作,才重新构建索引.图10(a)显示了本算法和EDMRS算法[27]在给定不同文档数量情况下,索引构建时间开销的变化趋势.由于关键词数量越大,则索引向量的维度也就越大,因此通过观察可以发现,随着关键词数量的增加,索引构建时间也越来越大.图10(b)为在给定关键词数量的情况下,索引构建时间随着文档数量的变化趋势.随着文档数量的不断增加,索引构建时间也在增加,但SEMRS采用将索引向量分块的方式减少计算复杂性,大大减少了索引加密时间和索引创建时间.

6.3 陷门生成时间

Fig. 11 Trapdoor generation time
图11 陷门生成时间

陷门生成是关键词搜索的重要步骤,如图11所示为陷门生成关键词数量的变化趋势.不难发现,陷门生成时间趋向于一个常数,不会随着搜索关键词的数量增长而增长,这是因为陷门生成时间主要取决于字典中关键词的数量,算法中陷门生成操作的主要耗时是搜索向量的加密.由于本文采用分块的方式加密搜索向量,因此总的陷门生成时间要小于MRSE算法和EDMRS算法的时间.通过图11(b)可以看出,生成陷门的时间成本主要取决于关键词字典中包含的关键词数量,并随着关键词数量的增大而变大.

6.4 搜索时间

搜索时间是权衡算法性能的重要指标.图12(a)所示为在给定文档关键词数量的情况下,搜索时间随文档个数的变化趋势,由于文档向量和索引向量的计算时间相同,因此,搜索时间随文档数量的增加而增加.图12(b)为给定文档数量的情况下,搜索时间随文档关键词数量的变化趋势,通过上文可知,文档关键词数量越大,则索引向量和陷门向量的维度也越大,因此,随着文档关键词数量的增加,搜索时间也越来越多.此外,SEMRS算法基于凝聚层次聚类构建索引树结构,该索引树是平衡二叉树,并设计了一种高效的索引遍历算法,因此,SEMRS的搜索时间要小于MRSE和EDMRS算法的搜索时间.

Fig. 12 Search time
图12 搜索时间

7 总 结

在分析查询关键词之间的关系基础上,提出了一种安全高效的支持语义扩展的多关键词排序搜索算法,解决可搜索加密中的语义检索问题.我们设计了一种基于语义关系的关键词权重算法,并对权重较大的关键词进行语义扩展.为提高查询效率,构造了一种关键词平衡二叉树作为文档的索引结构,并在查询时,根据查询向量和树节点的向量内积,进行“剪枝”操作.此外,为更好地表达查询关键词和文档之间的相关性,在构建索引和陷门时引入了TF-IDF算法,并在陷门中加入关键词权重值.最后,通过使用安全kNN,使得所提算法能够对抗2种不同安全威胁.

参考文献

[1]Ren Kui, Wang Cong, Wang Qian. Security challenges for the public cloud[J]. IEEE Internet Computing, 2012, 16(1): 69-73

[2]Wang Qian, Zhang Yan, Lu Xiao, et al. Real-time and spatio-temporal crowd-sourced social network data publishing with differential privacy[J]. IEEE Transactions on Dependable and Secure Computing, 2016, 15(4): 591-606

[3]Du Minxin, Wang Qian, He Meiqi, et al. Privacy-preserving indexing and query processing for secure dynamic cloud storage[J]. IEEE Transactions on Information Forensics and Security, 2018, 13(9): 2320-2332

[4]Song Dawn Xiaoding, Wagner D, Perrig A. Practical techniques for searches on encrypted data[C] Proc of the 2000 IEEE Security and Privacy Symp. Piscataway, NJ: IEEE, 2000: 44-55

[5]Li Jin, Wang Qian, Wang Cong, et al. Fuzzy keyword search over encrypted data in cloud computing[C] Proc of the 2010 IEEE INFOCOM. Piscataway, NJ: IEEE, 2010: 1-5

[6]Cao Ning, Wang Cong, Li Ming, et al. Privacy-preserving multi-keyword ranked search over encrypted cloud data[J]. IEEE Transactions on Parallel and Distributed Systems, 2013, 25(1): 222-233

[7]Wang Qian, He Meiqi, Du Minxin, et al. Searchable encryption over feature-rich data[J]. IEEE Transactions on Dependable and Secure Computing, 2016, 15(3): 496-510

[8]Hu Shengshan, Wang Qian, Wang Jingjun, et al. Securing SIFT: Privacy-preserving outsourcing computation of feature extractions over encrypted image data[J]. IEEE Transactions on Image Processing, 2016, 25(7): 3411-3425

[9]Song Wei, Wang Bing, Wang Qian, et al. Publicly verifiable computation of polynomials over outsourced data with multiple sources[J]. IEEE Transactions on Information Forensics and Security, 2017, 12(10): 2334-2347

[10]Xia Zhuha, Wang Xinhui, Sun Xingming, et al. A secure and dynamic multi-keyword ranked search scheme over encrypted cloud data[J]. IEEE Transactions on Parallel and Distributed Systems, 2015, 27(2): 340-352

[11]Wang Cong, Cao Ning, Ren Kailli, et al. Enabling secure and efficient ranked keyword search over outsourced cloud data[J]. IEEE Transactions on Parallel and Distributed Systems, 2011, 23(8): 1467-1479

[12]Goh E J. Secure indexes[OL]. IACR Cryptology ePrint Archive, 2004 [2019-06-10]. https:eprint.iacr.orgeprint-bingetfile.pl?entry=2003216&version=20040316:200136 &file=216.pdf

[13]Curtmola R, Garay J, Kamara S, et al. Searchable symmetric encryption: Improved definitions and efficient constructions[J]. Journal of Computer Security, 2011, 19(5): 895-934

[14]Cash D, Jaeger J, Jarecki S, et al. Dynamic searchable encryption in very-large databases: Data structures and implementation[C] Proc of the 2014 Network and Distributed System Security Symp. San Diego, CA:Internet Society, 2014

[15]Stefanov E, Papamanthou C, Shi E. Practical dynamic searchable encryption with small leakage[C] Proc of the 2014 Network and Distributed System Security Symp. San Diego, CA: Internet Society, 2014

[16]Bost R. ∑ oφo: Forward secure searchable encryption[C] Proc of the 2016 ACM SIGSAC Conf on Computer and Communications Security. New York: ACM, 2016: 1143-1154

[17]Kim K S, Kim M, Lee D, et al. Forward secure dynamic searchable symmetric encryption with efficient updates[C] Proc of the 2017 ACM SIGSAC Conf on Computer and Communications Security. New York: ACM, 2017: 1449-1463

[18]Bost R, Minaud B, Ohrimenko O. Forward and backward private searchable encryption from constrained cryptographic primitives[C] Proc of the 2017 ACM SIGSAC Conf on Computer and Communications Security. New York: ACM, 2017: 1465-1482

[19]Golle P, Staddon J, Waters B. Secure conjunctive keyword search over encrypted data[C] Proc of the 2004 Applied Cryptography and Network Security. Berlin: Springer, 2004: 31-45

[20]Byun J W, Lee D H, Lim J. Efficient conjunctive keyword search on encrypted data storage system[C] Proc of European Public Key Infrastructure Workshop. Berlin: Springer, 2006: 184-196

[21]Ballard L, Kamara S, Monrose F. Achieving efficient conjunctive keyword searches over encrypted data[C] Proc of Int Conf on Information and Communications Security. Berlin: Springer, 2005: 414-426

[22]Cash D, Jaeger J, Jarecki S, et al. Dynamic searchable encryption in very-large databases: Data structures and implementation[C] Proc of the 2014 Network and Distributed System Security Symp. San Diego, CA: Internet Society, 2014

[23]Wong W K, Cheung D W, Kao Ben, et al. Secure kNN computation on encrypted databases[C] Proc of the 2009 ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2009: 139-152

[24]Sun Wenhai, Wang Bing, Cao Ning, et al. Privacy-preserving multi-keyword text search in the cloud supporting similarity-based ranking[C] Proc of the 8th ACM SIGSAC Symp on Information, Computer and Communications Security. New York: ACM, 2013: 71-82

[25]Wang Bing, Yu Shucheng, Lou Wenjing, et al. Privacy-preserving multi-keyword fuzzy search over encrypted data in the cloud[C] Proc of the 2014 IEEE INFOCOM. Piscataway, NJ: IEEE, 2014: 2112-2120

[26]Fu Zhangjie, Sun Xingming, Liu Qi, et al. Achieving efficient cloud search services: Multi-keyword ranked search over encrypted cloud data supporting parallel computing[J]. IEICE Transactions on Communications, 2015, 98(1): 190-200

[27]Xia Zhihua, Wang Xinhui, Sun Xingming, et al. A secure and dynamic multi-keyword ranked search scheme over encrypted cloud data[J]. IEEE Transactions on Parallel and Distributed Systems, 2015, 27(2): 340-352

[28]Zheng Jie. NLP Chinese natural language processing[M]. Beijing: Electronic Industry Press, 2017: 287-292 (in Chinese)

(郑捷. NLP汉语自然语言处理[M]. 北京: 电子工业出版社, 2017: 287-292)

[29]Aburas A, Groce A. A method dependence relations guided genetic algorithm[C] Proc of the 2016 Int Symp on Search Based Software Engineering. Berlin: Springer, 2016: 267-273

[30]Gao Jianbo, Zhang Baowen, Chen Xiaohua. A WordNet-based semantic similarity measurement combining edge-counting and information content theory[J]. Engineering Applications of Artificial Intelligence, 2015, 39: 80-88

[31]Sánchez D, Batet M, Isern D. Ontology-based information content computation[J]. Knowledge-Based System, 2011, 24(2): 297-303

[32]Murphy S, Robshaw M J B. Essential algebraic structure within the AES[C] Proc of the 2002 Annual Int Cryptology Conf. Berlin: Springer, 2002: 1-16

[33]Shetty J, Adibi J. The Enron email dataset database schema and brief statistical report[OL]. [2019-06-01]. http:www.isi.edu~adibiEnronEnron_Dataset_Report.pdf

Multi-Keyword Searchable Encryption Algorithm Based on Semantic Extension

Xu Guangwei, Shi Chunhong, Wang Wentao, Pan Qiao, and Li Feng

(College of Computer Science and Technology, Donghua University, Shanghai 201620)

Abstract In cloud storage, to protect the data security and privacy of data owners, data encryption is used to provide on-demand data services. Searchable encryption technology is the key method to solve encrypted data access. However, the multi-keywords in search do not distinguish and ignore the correlation between indexes, which will cause long search time and low accuracy. To this end, this paper proposes a multi-keyword searchable encryption algorithm based on semantic extension. Firstly, the dependency syntax is based on to distinguish the importance of multiple keywords for semantic expansion, and generate multiple keyword trapdoors. Secondly, the condensed hierarchical clustering and the keyword balanced binary tree are based on, and the index tree structure of index relevance is constructed. Finally, the pruning parameter and the correlation score threshold are introduced to prune the index tree, and the index-independent subtree is filtered out in the index tree. Theoretical and experimental analysis based on real data sets shows that the proposed algorithm can resist scale analysis attacks and improve search time efficiency and search accuracy.

Key words cloud storage; searchable encryption; semantic extension; dependency grammar; condensed hierarchical clustering

(gwxu@dhu.edu.cn)

中图法分类号 TP391

收稿日期20190611;修回日期:20190806

基金项目国家自然科学基金项目(61772018,61772128);上海市自然科学基金项目(19ZR1402000,17ZR1400200);上海市教育科研项目(C160076)

This work was supported by the National Natural Science Foundation of China (61772018, 61772128), the Natural Science Foundation of Shanghai (19ZR1402000, 17ZR1400200), and the Shanghai Education and Scientific Research Project (C160076).

Xu Guangwei, born in 1969. PhD, professor. His main research interests include the data integrity verification and data privacy protection, searchable encryption, QoS and routing of the wireless and sensor networks.

Shi Chunhong, born in 1994. Master candidate. Her main research interests include the verification of data integrity and searchable encryption.

Wang Wentao, born in 1992. Master. His main research interests include the searchable encryption and data security.

Pan Qiao, born in 1977. PhD, associate professor. His main research interests include parallel and distributed computing, cloud computing, and big data processing.

Li Feng, born in 1969. PhD, professor. His main research interests include the data service and artificial intelligence.