支持关键字更新的可搜索加密方案



支持关键字更新的可搜索加密方案

引文格式： 谭彭超,张应辉,郑东.支持关键字更新的可搜索加密方案[J].桂林电子科技大学学报,2016,36(1):44-47.

谭彭超1,张应辉1,2,郑东1

(1.西安邮电大学 无线网络安全技术国家工程实验室，西安710121;

2.中国科学院 信息安全国家重点实验室，北京100093)

摘要：针对可搜索加密方案不支持关键字更新的问题，采用带计数器的布隆过滤器，设计了一种支持关键字更新的可搜索加密方案。该方案允许在索引密文中增加或者删除关键字，能够对文件的索引密文进行动态修正，使得文件索引和文件的关联更加紧密，提高了检索效率。分析结果表明，该方案在已知密文模型下是安全的，可保证查询关键字陷门信息不被云存储服务器获取。

关键词：可搜索加密；隐私保护；关键字更新；云存储

伴随着计算机网络的快速扩张，数据存储已经变成网络世界中一项费时费力的任务。为了节省存储空间，简化存储过程，科学家提出了云存储。然而服务器可能成为“内部攻击者”[1]。可搜索加密技术有效防范系统内部攻击的同时，允许用户对自己的隐私数据进行高效查询。

在可搜索加密研究领域，众多专家学者做出了杰出的贡献。Song等[2]率先提出“可搜索加密”的概念，并构建出首个基于全文本扫描的对称可搜索加密方案。随后Boneh等[3]于2004年提出PEKS方案，也是第一种公钥可搜索加密方案。Goh[4]提出了基于索引的Z-IDX方案，使用布隆过滤器作为单个文件的索引结构。2011年Wang等[5]提出了支持多关键字排序的密文检索算法(multi-keyword ranked search over encrypted，简称MRSE)，其相似性匹配的特性借鉴了knn算法[6]，向量内积的运用使得该算法支持多关键字和相似度排序，极大丰富了可搜索加密的内涵。MRSE算法是一种非常高效的可搜索加密算法，Wang等[7]也不遗余力地进行改进，在2014年提出了云环境下支持多关键字模糊查询的可搜索加密隐私保护方案。

然而上述方案一旦生成一个文件的索引并为之加密，该索引的密文将不可更改，这大大限制了方案的灵活性。存储是一个动态过程，数据也不可能一成不变，因此关键字变动的功能对于可搜索加密而言是非常适用的，而上述方案尚未考虑该功能。为此，结合一种带计数器的布隆过滤器，构建了一种支持关键字变动的可搜索加密方案。

1预备知识

符号及其说明如表1所示。

表1　符号说明

布隆过滤器[8]是一种简单的数据结构，其实质是一个x位的向量．若存在集合W={w1,w2,…,wl}，利用y个相互独立的Hash函数H={h：{0,1}*→{1,x}}，将集合中每个元素wi∈W(1≤i≤l)的Hash值作为布隆过滤器的下标，对应位置为1。判断一个元素x是否属于集合P，将元素p作用于y个独立的哈希函数：若输出结果对应布隆过滤器的相应位有一位为0，则元素p不属于集合P；若y个相应位置均为1，则元素p属于P或者不属于P，不属于P的现象称为假阳性。一个x位的布隆过滤器出现假阳性的概率大约为(1-e-ly/x)t，其中x为布隆过滤器的长度，y为Hash函数的个数，l为插入布隆过滤器中关键字的个数。

带计数器的布隆过滤器是一种在布隆过滤器基础上的改进型过滤器[9]。当多个关键字wi(i=1,2,3,…)通过y个相互独立的哈希函数映射到同一个j下标时，对应下标位置上的值将不再是1，而是多个映射结果的叠加。图1为布隆过滤器结构，图2为带计数器的布隆过滤器结构。其中X、Y为过滤器中已存在的关键字，Z为向过滤器中新添加的关键字。

图1　布隆过滤器结构Fig.1　The structure of Bloom filter

图2　带计数器的布隆过滤器结构Fig.2　The structure of counting Bloom filter

2方案模型及性能

2.1系统模型

基于云储存的可搜索加密系统模型涉及云服务器、数据拥有者和用户。为保证数据隐私性，数据拥有者对文件加密后将密文上传至云服务器。此外，数据拥有者需通过特定机制，为数据集中的每个文件构建唯一对应的文件索引，将文件索引的密文与文件的密文一起上传至云端。用户通过安全渠道获得数据使用权后，利用选定的关键字构建查询陷门，加密后发送给服务器。服务器在接收到查询陷门后，通过特定的搜索机制返回相关密文文件。有关访问控制见文献[10]。

2.2安全模型

服务器是“honest-but-curious”，即云服务器是不完全可信的，服务器会根据方案设计协议执行所有过程并提供相应的服务，但有可能会收集用户的查询信息并进行分析。基于服务器获取数据的能力，本研究选用已知密文的威胁模型。在该模型中，服务器仅能获取数据拥有者上传文件的密文、索引密文、查询向量密文及检索结果。

2.3方案性能

为有效利用加密数据，本方案具有如下性能：

1)支持索引密文中关键字的更新。允许用户对文件索引密文进行动态更新。

2)隐私保护。保障服务器不能获取文件明文信息，也不能获取相应的索引明文信息和查询陷门明文信息。

3)提高效率。尽可能提高执行效率，降低执行的复杂度。

3方案构造与分析

3.1方案构造

本方案采用带计数器的布隆过滤器，由Setup、BuildIndex、Trapdoor和Query四个算法组成。其功能分别为：初始化方案所需的对称密钥；构造文件索引并加密；构建查询陷门并加密；利用生成的查询陷门，提交给服务器进行查询。方案如下：

1)Setup。输出Sk={S,M1,M2}。其中：k为最相似的文件的个数；(M1,M2)为m+2维随机矩阵；S为长度为m+2的随机0、1比特串，m为过滤器的长度。

2)BuildIndex(I,Sk)。利用带计数器的布隆过滤器(m位，y个相互独立的Hash函数H={h：{0,1}*→{1,m}})为选定的多个关键字wi(i=1,2,3,…)生成索引I，并填充为I=(I,εi,1)，其中εi为随机数。根据S上每个bit的值，索引I分裂为(I′,I″)，若S[j](j=0,1,…,m+1)的值为1，则分裂后的子向量I′[j]、I″[j]对应位置上的值与I[j]相等；否则，子向量I′[j]、I″[j]可设置为任意随机数，但需I′[j]+I″[j]=I[j]。分裂完成后便可对明文索引加密，密文形式为：

其结果r(IQ+εi)+t越大，表明相似度越高。根据参数k向用户返回k个分数最高的文件。

3.2方案分析

2)正确性分析。将{w1,w2,…,w5}的索引密文与{w6,w7,w8}的索引密文相加，其效果等同于{w1,w2,…,w8}的索引密文。具体分析如下。

当S[j]=0时，Q′[j]、Q″[j]、Q[j]三者相等，则

又因为

而I[j]+Ii[j]是关键字集{w1,w2,…,w5}和{w6,w7,w8}通过布隆过滤器在相应位置上的结果，与关键字集{w1,w2…,w8}通过布隆过滤器的结果相同。因此，可得出结论：遍历Q[j](I′[j]+I″[j]+I′i[j]+I″i[j])中的每个j(j=0,1,…,m-1)，最终结果是向量积QI。同理可得S[j]=1的情况。

计算结果表明，利用带计数器的布隆过滤器产生的索引，可以实现关键字的更新。

3)安全性分析。对于数据隐私，可利用已经成熟的加密算法[11]。而索引隐私可确保：只要密钥SK不被泄露，这种向量加密的方法在已知密文模型中被证明是安全的[5]。随机因子r、t的引入以及随机分裂过程的应用，可以针对同一查询向量产生完全不同的2个陷门，保证了陷门的无关联，即无法从一个可能已经泄露的陷门信息推测出另外未泄露的陷门信息。文件索引或查询向量加密过程中的算法复杂度为O(m2)，检索过程中的内积计算复杂度为O(m)。在已知密文模型的条件下，密钥S是未知的，向量I分裂为2个m+2位的随机向量I′、I″。假定有n个加密的文件索引，可列出2(m+2)n个线性方程，其中有2(m+2)n个未知量，且矩阵M1、M2中有2(m+2)2个未知量，由于未知量多于已知量，所以无法求解方程组，也就无法获得索引的明文信息。同样地，查询向量q可分裂为q1、q2，也是2个m+2位随机向量，能够列出2(m+2)个方程，其中有2(m+2)个未知量和逆矩阵中的2(m+2)2个未知量，由于未知量多于已知量，本方案在已知密文模型下的安全性是有保障的。

4)效率分析。本方案结合文献[5]、[9]进行了改进。假定本方案与文献[5]的方案初始化参数相同，比较本方案和文献[5]的方案，结果表明，本方案只有文件索引生成时间有微小的增加，而文件索引的生成时间、查询向量的生成时间、文件索引的加密时间、查询向量的加密时间、搜索时间等指标维持不变。查询向量生成时间与关键字数量呈正相关增长；更新文件索引中的关键字耗时与待更新关键字的数量呈线性关系；搜索时间与文件集大小呈线性增长；查询向量中的关键字数量对搜索时间几乎无影响。

4结束语

采用带计数器的布隆过滤器，设计了一种支持关键字更新的可搜索加密方案，允许用户对已构建的文件索引进行修改。在已知密文模型下对该方案的安全性进行分析，结果表明，该方案能够保证在已知密文模型下的数据安全。同时，对该方案的性能作了定性分析，分析结果表明，该方案在生成文件索引向量时，耗时有微小的增加，但能够动态更新文件索引密文中的关键字，更新过程的耗时和更新的关键字数量呈线性增长关系。

参考文献:

[1]CHENGFangquan,PENGZhiyong,SONGWei,etal.Anellicientprivacy-preservingrankqueryoverencrypteddataincloudcomputing[J].JournalofComputers,2012,35(11):2215-2227.

[2]SONGDX,WAGNERD,PERRIGA.Practicaltechniquesforsearchesonencrypteddata[C]//ProceedingsoftheIEEESymposiumonSecurityandPrivacy,2000:44-55.

[3]BONEHD,DICRESCENZOG,OSTROVSKYR,etal.Publickeyencryptionwithkeywordsearch[C]//AdvancesinCryptology-EUROCRYPT.Heidelberg:Springer,2004:223-238.

[4]GOHEJ.Secureindexes[R/OL].(2004-03-16)[2015-08-15].http://eprint.iacr.org/2003/216.

[5]CAON,WANGC,LIM,etal.Privacy-preservingmulti-keywordrankedsearchoverencryptedclouddata[J].IEEETransactionsonParallelandDistributedSystems,2014，25(1):222-233.

[6]WONGWK,CHEUNGDWL,KAOB,etal.SecureKNNcomputationonencrypteddatabases[C]//Proceedingsofthe2009ACMSIGMODInternationalConferenceonManagementofData.[S.l.]:ACM,2009:39-152.

[7]WANGBing,YUShucheng,LOUWenjing,etal.Privacy-preservingmulti-keywordfuzzysearchoverencrypteddatainthecloud[C]//IEEEConferenceonComputerCommunications,2014:2112-2120.

[8]BLOOMBH.Space/timetrade-offsinhashcodingwithallowableerrors[J].CommunicationsoftheACM,1970,13(7):422-426.

[9]ROTTENSTREICHO,KANIZOY,KESLASSYI.Thevariable-incrementcountingBloomfilter[J].IEEEACMTransactionsonNetworking,2014,22(4):1092-1105.

[10]BYUNJW,LEEDH,LIMJ.Efficientconjunctivekeywordsearchonencrypteddatastoragesystem[C]//3rdEuropeanPKIWorkshop:TheoryandPractice.Berlin:Springer,2006:184-196.

[11]张应辉，郑东，赵庆兰.密码学综述[J].西安邮电大学学报，2013,18(6):1-10.

编辑：张所滨

A searchable encryption scheme for supporting keyword update

TAN Pengchao1, ZHANG Yinghui1.2, ZHENG Dong1

(1.National Engineering Laboratory for Wireless Security, Xi’an University of Posts and Telecommunications, Xi’an 710121, China;

2.State Key Laboratory of Information Security, Chinese Academy of Sciences, Beijing 100093, China)

Abstract：Keyword update is not supported by the exiting searchable encryption scheme, so a searchable encryption scheme for supporting keyword update with counting Bloom filter is designed. Fixing cipher index through adding or deleting keyword is allowed in the scheme, the cipher of file index can be revised. And association of file and its index can be made more closely. It is very convenient to improve the efficiency of data retrieval. The analysis result shows that the new scheme is safe in the known cipher model, which can protect the query keyword and the trapdoor information from being elicited by cloud storage server.

Key words：searchable encryption; privacy protection; keyword update; cloud storage

中图分类号：TP309.2

文献标志码：A

文章编号：1673-808X(2016)01-0044-04

通信作者：郑东(1964-)，男，山西翼城人，教授，博士，研究方向为密码学、云存储安全。E-mail:zhengdong@xupt.edu.cn

基金项目：国家自然科学基金(61272037，61402366，61472472)；陕西省自然科学基础研究计划(2013JZ020,2015JQ6236)；西安邮电大学研究生创新基金(CXL2014-10，CXL2014-04)

收稿日期：2015-10-10