云服务器中基于同态加密的关键词检索方案

刘家森， 王绪安， 王 涵， 赵凯洋， 闫纪宁

(武警工程大学网络与信息安全武警部队重点实验室， 西安 710086)

对于一些机密性较高的数据，如个人隐私数据、病人健康数据、商业机密数据等，为了避免其他人获得真实数据，用户往往将其在本地加密后再上传给云存储系统，由自己保管相关密钥。但是随着云存储系统中的数据量膨胀式增大，用户需要快速准确地从加密数据中检索到自己需要的文件。

最早密文检索的方案由Song等[1]于2000年提出，其方案基于对密文的线性搜索，将关键词与文本内容逐一匹配。之后研究人员在此基础上进行了很多细化的研究，Boneh等[2]于2004年首次提出一种基于公钥机制的非对称可搜索加密方案，其通过双线性映射将公钥和私钥的加密数据合并，使得只有公钥或私钥加密的相同关键字才能匹配。同年，Golle等[3]提出一种基于多关键词的密文检索方案。

近年来，针对云服务器中的密文检索方案主要分为基于密文扫描检索方案和基于安全索引的检索方案。Chang等[4]于2005年基于建立文档索引实现对精准的关键词搜索。Wang等[5]于2010年通过使用倒置索引对加密数据进行安全排序，提出了一种单关键词检索方案。2013年，Cao等[6]通过引入向量空间模型，提出了一种多关键词密文检索方案。但是上述方案仅支持对关键词的精准搜索，输入格式错误会导致检索结果不准确。2010年，Li等[7]通过为每个关键词都建立模糊集，首次提出了一种基于模糊关键词的检索方案。

目前围绕模糊关键词检索和多关键词检索产生了很多研究。Wang等[8]验证了基于属性加密的多关键字搜索方案中外包私钥的正确性。Lang等[9]将复合概念的语义相似性与位置敏感哈希函数和安全k近邻方案相结合，提出了一个多关键词加密检索方案。Xiao等[10]基于映射集匹配提出一种多关键词排序检索方案。陆海虹等[11]使用minhash函数对关键词索引进行加密，但是加密效率和检索精度较低。张全明等[12]和于晓明等[13]分别基于Solr搜索引擎技术和Lucene全文检索引擎实现基于关键词检索和全文检索的应用方案。

为了提高密文检索的精度以及提高方案的安全性，许多研究将同态加密运用到密文检索当中。用户可以通过对文件进行同态加密，在保证数据隐私性的前提下，委托云服务器直接对密文进行同态操作，并且结果等价于明文上的操作。同态加密方案首次由Rivest等[14]于1978年提出，之后Gentry[15]于2009年在理论上实现同态加密，并在此后于2010年以及2013年分别提出DGHV方案[16]和GSW13方案[17]，前者基于近似最大公约数问题实现一个基于整数的全同态加密，后者基于错误学习问题提出第一个基于身份的同态加密方案。同时Brakerski等[18]基于标准格上困难问题提出了BV11方案，有效缩短了密文并降低了方案的解密复杂度，又于2012年和2014年分别提出Bra12方案[19]和BGV12方案[20]。前者通过避免模数转换而建立层次型同态加密方案，后者无需自举就能建立层次经同态加密。

最近Cheon等[21]基于错误学习问题提出CKKS方案，其因为支持对密文的近似运算而得到普及应用。Gong等[22]基于Grover算法提出了一种新的量子同态加密密文检索(QHECR)方案。Wang等[23]提出了一种基于全同态加密企业云存储(ECRS)的加密密文检索方案。

目前的市场上应用的密文检索方案主要分为两种，一种基于关键词与密文匹配的检索方法，另一种基于文件索引的检索方法。然而前者检索效率低，而后者需要建立复杂的索引结构，都难以满足用户对云服务器中海量加密数据的检索需求。

为了在保护用户数据的隐私的同时，实现对云服务器中海量密文文件的高效准确的检索功能，基于错误学习(learning with errors,LWE)问题以及近似最大公约数(approximate greatest common divisor, AGCD)问题提出了一种新型同态加密方案。并针对云服务器中大数据存储及检索的需求，在加密文件的同时，通过建立加密关键词索引提出了一种模糊密文检索方案。

1 加密检索机制设计

基于同态加密的关键词密文检索方案包括同态加密方案以及基于关键词密文检索方案两个部分。

1.1 系统模型

一般来说，云存储系统都会诚实地按照规定对用户提供高效的存储服务，不会恶意地对用户数据进行改动。但是有些云服务器为了自身利益，会有意收集用户的各种数据，甚至将用户数据出售给其他公司。

在数据隐私保护的前提下，针对云服务器中大数据存储及检索的需求，基于建立关键词索引并利用全同态加密实现加密文档检索，系统模型如图1所示。

图1中，用户首先对要上传的文件建立关键词索引，之后通过同态加密方案，将加密后的文件以及关键词上传至云服务器。云服务器只能获得密文文档及关键词。当用户需要检索相关文档时，首先将相关关键词加密，并把加密后的关键词上传至云服务器中进行检索。云服务器通过计算检索请求的加密关键词索引与云中存储的关键词索引的相似度，将匹配结果返回给用户。最后用户根据自己需求下载对应的密文文件，并解密获得明文文件。符号定义如表1所示。

图1 系统模型Fig.1 System model

表1 符号定义

1.2 预备知识

1.2.1 LWE：Learning with errors

Regev等[24]用量子规约算法证明了LWE问题的困难性等同于n维格上的最短向量问题(shortest vector problem, SVP)和最短线性无关向量问题(shortest linear independent vector problem,SIVP)。

1.2.2 AGCD：Approximate-GCD

Howgrave-Graham[25]提出AGCD问题。给定集合{x1,x2,…,xn|xi=pqi+ri}，其中qi和ri都是整数，且根据xi的不同而变化。求出隐藏的近似公约数p。DGHV[16]方案将该问题归于基于因式分解加密体系中经典的硬核位的证明，结果证明其具有语义安全特性，且在选择性明文攻击模型下具有密文不可区分性。

1.3 同态加密方案

1.3.1 系统参数生成函数：ParamGen(1λ)

随机选取两个大素数q=q(λ)∈Z+，p=p(λ)∈Z+，使得gcd(p,q)=1，返回安全参数Param(p,q)。之后根据加密效率选取加密参数l,n∈R+。

1.3.2 密钥生成函数：KeyGen(1λ)

1.3.3 加密函数：Enc(key,F∈Zp)

1.3.4 解密函数：Dec[key,C=(r,c)]

计算明文

1.4 单关键词密文检索方案

当用户需要查询文件时，首先选取一个或几个关键词F∈Zp，通过上述方案加密后上传至云服务器，之后在云服务器中进行密文检索。

最后云服务器按照设定，返回r>θ的密文给用户。

1.5 多关键词密文检索方案

2 理论分析

2.1 正确性分析

正确拥有密钥[S,K(l)]的用户可以通过解密函数Dec()对密文C=(r,c)解密得到正确的明文F。

Dec[S,K(l),C=(r,c))=

2.2 同态性分析

2.2.1 同态加法

给定两个关键词及其对应的密文F1、F2∈Zp,C1=(r1,c1),C2=(r2,c2)，对密文上的运算满足加法同态性Dec(r1,c1)+Dec(r2,c2)=Dec(r1+r2,c1+c2)。

Dec(r1+r2,c1+c2)=

[(r1+r2)S+c1+c2]lmodp=

F1+F2。

2.2.2 同态乘法

给定两个关键词及其对应的密文F1、F2∈Zp,C1=(r1,c1),C2=(r2,c2)，对密文上的运算满足乘法同态性Dec(r1,c1)·Dec(r2,c2)=Dec[(r1,c1)(r2,c2)]。

Dec(c1r2,c1c2)=

c1F2；

Dec(r1r2,r1c2)=r1F2；

Dec[(r1,c1)·(r2,c2)]=Dec(r1F2,c1F2)=

F1F2。

2.3 安全性分析

在用户对密文进行上传存储与检索过程中，对于用户数据的隐私性要保证两方面：一是要保证云服务器无法从用户存储的密文破解出真实数据，二是要保证云服务器无法从检索请求破解出用户数据。

2.3.1 存储方案安全性

2.3.2 检索方案安全性

3 实验分析

为了进一步分析方案的效率，在Intel®CoreTMi7-7700HQ CPU @ 2.80 GHz/16 GB Ram的环境下，在Windows10操作系统下使用IntelliJ IDEA Community Edition 2019.3 x64测试方案的效率。经对比多次试验结果，确定系统参数Param(p,q)为128位。

3.1 加密效率测试

首先通过建立单一关键词，对应不同的加密维度，对方案的加密效率进行测试。在测试过程中选取3个中文字符的关键词，对应48位的比特长度。在每一对加密维度(l,n)进行30次加密试验，取其平均计算时间作为最终结果，如图2所示。

图2 不同维度的加密效率Fig.2 Encryption efficiency in different dimensions

可见，当加密维度处于(128,128)之后，加密时间呈指数型上升，加密效率过低。因此后续实验中选取(128,128)作为加密维度进行试验。

下一步测试中，通过选取确定的加密维度，分别对不同比特的明文F构造密文索引，并与Wang等[23]的基于全同态加密企业云存储的加密密文检索方案(ECRS)进行对比，并取30次试验的平均运行时间作为最终结果，如图3所示。

图3 加密索引构建效率Fig.3 Encrypted index construction efficiency

可见，随着明文的比特长度增加，两种加密方案所用的时间基本不变，证明本方案可有效地对任意长度的明文进行加密。

3.2 检索效率测试

通过建立不同的关键词索引，对不同数量的关键词对进行检索匹配试验。建立100个文本文件作为测试文件，对每个文本建立4个关键词，每个关键词长度为3个中文字符。以(128,128)为加密维度对关键词进行加密，建立加密关键词索引。选取1～4个关键词进行检索，分别测试本文方案和ECRS的检索效率，结果如图4所示。

图4 不同数量关键词的检索效率Fig.4 Retrieving efficiency of different number of keywords

3.3 检索准确率测试

由于ECRS在进行多关键词检索的任务时需要逐一计算所有的关键词权重的相似度，因此对其计算单个关键词的检索时间，并进行叠加。

可见，两种方案对于单关键词检索速度相差不大，但是随着关键词数量增长，云端需要计算的匹配对数增多，ECRS的计算开销呈线性增长趋势，本文方案的计算开销增长较为缓慢。

仍以上述100个文本文件作为测试文件，测试本文方案以及ECRS的检索准确率并进行对比。分别取1到4个关键词进行检索，在每个条件下分别取10种关键词组合进行测试并取平均值，结果如图5所示。

图5 不同数量关键词的检索准确率Fig.5 Retrieval accuracy of different number of keywords

可见，随着待检索的关键词数量的增加，两种方案的准确率基本不变，证明本文方案的可靠性。

4 结论

为满足用户在云存储系统中海量加密数据进行密文检索的操作需求，基于同态加密提出了一种加密关键词检索方案。首先通过LWE问题以及AGCD问题提出了一种针对关键词的同态加密方案，并通过理论分析证明了加密方案的安全性以及同态性。之后参考余弦夹角相似度度量方法，在上面所提出的同态加密方案基础上，提出了一种基于建立加密关键词索引的密文检索方案。通过实验分析，测试不同加密维度下的加密效率，证明了加密方案的高效性。最后通过实验对比，测试检索方案的检索效率以及检索准确率，证明了检索方案的有效性。