面向多关键字的模糊密文搜索方法
王恺璇;李宇溪;周福才;王权琦
【摘 要】Cloud computing is one of the most important and promising technologies .Data owners can outsource their nsitive data in a cloud and retrieve them whenever and wherever they want .But for protecting data privacy ,nsitive data have to be encrypted before storing ,which abandons traditional data utilization bad on plaintext keyword arch .Around the multi-keyword fuzzy matching and data curity protection problems ,we propo a multi-keyword fuzzy arch method on the encrypted data . Bad on the Bloom filter , our scheme us dual coding function and the position nsitive Hash function to build file index .In the meantime ,it us the distance recoverable encryption arithmetic to encrypt the file index ,conquently achieving the function which is facing the multi-keyword to fuzzy arch over the encrypted data .Meanwhile ,the scheme does not need to t index storage space in advance ,which greatly reduces the complexity of the arch .Compared with the existing solutions , the scheme does not need predefined dictionary libr
ary which lowers the storage overhead in conquence .Experimental analysis and curity analysis show that the propod scheme not only achieves the multi-keyword fuzzy arch over the encrypted data ,and guarantees the confidentiality and privacy .%围绕多关键字的模糊匹配和数据安全性保障问题,展开对多关键字模糊搜索方法的研究,提出一种面向多关键字的模糊密文搜索方案.该方案以布隆过滤器(Bloom filter)为基础,使用对偶编码函数和位置敏感Hash函数来对文件索引进行构建,并使用距离可恢复加密算法对该索引进行加密,实现了对多关键字的密文模糊搜索.同时方案不需要提前设置索引存储空间,从而大大降低了搜索的复杂度.除此之外,该方案与已有方案相比不需要预定义字典库,降低了存储开销.实验分析和安全分析表明,该方案不仅能够实现面向多关键字的密文模糊搜索,而且保证了方案的机密性和隐私性.
【期刊名称】《计算机研究与发展》
【年(卷),期】我的棉被2017(054)002五一放假
【总页数】13页(P348-360)
【关键词】云存储;布隆过滤器;可搜索加密机制;位置敏感Hash函数;多关键字模糊搜索
雨俊的故事
【作 者】王恺璇;李宇溪;周福才;王权琦
【作者单位】东北大学软件学院 沈阳 110819;东北大学软件学院 沈阳 110819;东北大学软件学院 沈阳 110819;东北大学软件学院 沈阳 110819
【正文语种】中 文
【中图分类】TP309.2
随着云存储的迅速发展以及用户对个人数据隐私性的愈加重视,如何对存储在服务器中的密文进行搜索就显得格外重要.可搜索加密方法(archable encryption, SE)是解决密文搜索的有效方法.
可搜索加密方法首次由Song和Wagner等人[1]提出,开创了将搜索机制应用于关键字密文搜索的先河;2005年,Chang等人[2]提出了基于预定义字典的可搜索加密机制.这种机制不仅优化了关键字的搜索效率,而且还缩减了计算开销.但是,由于预定义字典的设定,同时也给用户带来了额外的存储开支.随后Dong等人[3]在2008年针对安全性进行了改进,提出了能够抵抗自适应性攻击的搜索加密模型.2015年,Revathy等人[4]提出了排序的搜索加密机制.以上几
种搜索关键字均是基于对称密码学的精确的单关键字搜索机制,用户只能在一次搜索过程中发送1个单词,这种搜索机制与现实的搜索需求极为不符.
2014年,Cao和Wang等人[5]提出了多关键字可搜索加密机制.该机制在搜索时为索引和关键字构建向量,并通过向量运算实现了搜索结果的排序.2016年，文献[6]提出了多关键字的排序搜索方案，该方案利用树构建索引结构，减少了搜索时间.
从以上方案可以看出,不论是面向单关键字还是多关键字，现有研究都是针对精确搜索的.而针对用户输入错误关键字的情况,精确的单关键字搜索加密机制或者基于连接词的搜索加密机制还需要改进.研究学者在精确搜索的基础上相继提出了基于关键字的模糊搜索方案.Bringer等人[7]在2009年提出了面向明文的模糊搜索方案,该方案主要基于布隆过滤器实现数据存储.Van Liesdonk等人[8]在2010年研究了模糊关键字搜索加密方案,但这种方案最大的缺陷是需要用户额外花费时间来执行关键字的循环搜索.2010年,文献[9]实现了关键字模糊搜索的加密机制,但该方案需要用户付出庞大的数据存储空间,且只实现了基于单关键字的模糊密文搜索.之后在2013年,文献[10-11]也相继提出了不同的模糊关键字搜索方法.其中，文献[10]给出了单关键字可排序模糊关键字搜索方法，文献[11]提出的是一种可验证的模糊关键字搜索方案.
本文针对密文的多关键字模糊搜索展开研究,以提高搜索效率为目标,提出了一种面向多关键字的模糊密文搜索方案,该方案利用布隆过滤器和位置敏感Hash函数技术,能够有效实现多关键字的密文模糊搜索.主要研究内容包括:将上传文件利用对偶编码函数将其关键字转换成向量,再利用位置敏感Hash函数将其映射到布隆过滤器中;服务器在执行密文搜索时,需要先对输入的查询关键字进行上述转换,再通过计算安全索引参数和陷门的内积来搜索到符合条件的密文文件.与已有方案相比,本方案不需要提前设置索引存储空间,从而大大降低了搜索的复杂度;同时,该方案不需要预定义字典库,降低了存储开销.安全性分析表明方案不仅保证了可用性,而且满足了机密性和隐私性.因而,该方案具有重要的理论价值和应用前景.
大学生学习
怎么拉人进群聊1.1 位置敏感Hash函数
位置敏感Hash函数于1998年由Indyk等人[12]提出,主要用于解决高维数据的搜索问题.里约大冒险2
定义1. 位置敏感Hash函数.给定n个d维的点集S以及各点之间的相似性度量D,Hash族H={h:H→U}被称为(r1,r2,p1,p2)-敏感Hash函数,需要满足以下条件,对于q∈S:
莲雾的功效如果v∈d(q,r1),那么Pr[h(q)=h(v)]≥p1;
如果v∉d(q,r1),那么Pr[h(q)=h(v)]≤p2.
其中,r1<r2,p1≥p2,d(q,r1)是距离度量.
本文方案将使用文献[13]中的基于p -stable的位置敏感Hash函数.p -stable分布可以有效对高维向量进行降维.随机构建1个d维的向量v,如果向量中的每个元素均满足p -stable分布,随机变量a·v和同分布,则a·v和的值大致相同.位置敏感Hash函数的计算公式如下:
,
其中,参数a和b分别是d维的向量和[0,w]间的一个随机数,向量a中的每个元素都满足p -stable分布.
普会寺
式(1)的计算过程实际是向量的映射过程,如图1所示.a·v即把向量a映射到以向量v为基向量的数轴上,如果将此数轴等分为w份,同时每份做上标记,a·v的值对应哪个区间就将这个区间的标记号作为向量a的Hash函数值.
判断2点是否可以通过位置敏感Hash函数映射到1个桶中,主要通过计算Hash值相等的概率来进行.假设给定2个向量v1,v2,让,那么向量v1,v2的位置敏感Hash函数值相等的概率如下:
，
其中,fp是分布D的密度函数,p1=p(r1),p2=p(r2).
1.2 布隆过滤器
Bloom[14]在1970年提出了布隆过滤器(Bloom filter, BF)的概念.BF是一种概率型数据结构,主要用于判断某个元素是否存在于集合中.
布隆过滤器的主要工作原理是:运用一个m(单位为b)长的数组表示这个布隆过滤器,数组的每一位元素初始化为0.随后随机选择k个Hash函数,将数据域S={y1,y2,…,yn}中的n个元素分别一一映射到上面的数组中,当需要映射1个元素时,计算每个元素的k个Hash函数对应的k个Hash值,然后把数组中对应的位置设置为1.如果Hash值对应的位置已经设置成为1,就保留第1次作用的效果.如图2所示:
判断元素x是否存在于数据域中,计算元素x对应的上面的k个Hash函数的Hash值,如果该元素的所有Hash值对应的位置都为1,就说明元素x存在于数据域中.
向布隆过滤器中加入1个新的元素时,需要使用k个不同的Hash函数对其进行Hash计算,将这个元素映射到布隆过滤器的k个比特位中,同时将这些比特位设置为1.
查询某个元素是否存在于布隆过滤器中时,需要利用提前定义的k个Hash函数将其映射到BF的k个比特位上.如果这k个比特位对应的值都是1,则说明该元素存在于集合中, 只要有一个位置不为1,则此元素不存在于该集合中.
1.3 对偶编码函数
在面向密文的多关键字模糊搜索方案中,构建索引、构建陷门和关键字查询的过程都是基于向量的操作过程.数据拥有者输入的关键字都由字符组成,由于字符的不可计算性,需要将其转换成向量的形式.
定义2. 对偶编码函数.给定字符串S1=C1C2…Cn和二进制向量S2=b0b1…bm-1,S2中每位元素的初始值为0,其中n<m.通过Hash函数H,把S1中相邻2个字符散列映射为0～(m-1)之间的数,当且仅当H(Cj,Cj+1)=i时,bi=1.把S1→S2的函数称为对偶编码函数.
