魏　雪

（北京邮电大学 数学科学学院，北京市　100876）

基于用户偏好的云端加密数据的多关键模糊词检索

魏雪

（北京邮电大学 数学科学学院，北京市100876）

随着云计算技术的发展，数据拥有者可以把数据集外包给云服务商，然后用户可以通过搜索算法得到他们想要的结果。上传给云服务商的数据通常会包含敏感信息，所以用户需要先把数据集加密再上传给云服务商。然而，这就限制了数据的利用率。所以，在这篇文章提出了一个搜索算法，它是基于云端加密数据的多关键模糊词的检索，特别的，在这个算法中，考虑了用户的偏好和用户属性的问题。实验验证基于IEEE的文章，结果证明这篇论文的算法可以获得更多，更加符合用户偏好的结果。

计算理论；

搜索；用户偏好；云端数据；隐私保护

本文著录格式：魏雪. 基于用户偏好的云端加密数据的多关键模糊词检索[J]. 软件，2016，37（8）：27-31

0　引言

随着云计算技术的发展，它作为一个新型的技术受到我们大家的关注。它为我们带了很多方便。比如，云计算可以支持公司和企业把他们的数据集上传给云服务商，这样，在节省了存储空间的同时，也使得用户可以通过在云端检索数据获得他们想要的结果。这就意味着云计算是一个具有规模形的，低成本的，高效的技术。

但是在现实生活中，我们不可以完全信任云服务商，因为它会泄露用户的数据，比如像医疗记录，经济状况这些隐私数据。所以，我们需要一种算法，可以允许用户在云端数据中直接高效检索到用户感兴趣的数据。

到目前为止，在云端加密数据的检索上已经有很大的成就[4]-[11]。特别的，在模糊词搜索上也取到了很大的进步。但是，上述的这些工作都是基于单关键词的检索，其中模糊词的检索是使用编辑距离来列出所有错误拼写的可能性的集合。最近的，王和他的团队提出了一种基于多关键模糊词的搜索，他们首次使用了局部敏感哈希函数来定义模糊词的定义，这样就不在需要字典了。

如今，如何有效的进行多的搜索始终是一个难题。在这我们的文章中，我们提出了一种搜索算法，它基于用户偏好，支持访问权限控制的多关键模糊词在云端数据的检索。所以，在这篇文章中，考虑到基于用户偏好的问题，我们使用了一个超递增序列来表示用户的偏好大小。不仅如此，我们还考虑到了隐私保护问题，我们使用和用户属性和哈希函数来解决这个问题，我们实验室基于IEEE文章，实验结果已经证明了我们的结果可以更加符合用户的偏好。我们的贡献主要总结成以下几点：

1. 在我们所了解的范围中，这是首次使用超递增序列考虑模糊词搜索的用户偏好问题。

2. 基于隐私保护问题，我们使用和用户属性和哈希函数来进行用户的访问权限控制问题，并且保护了用户属性的隐私。

3. 我们已经把我们的算法在IEEE的文章中进行了实验验证，结果表示，我们的算法可以得到更加符合用户偏好的结果。

1　问题陈述

1.1系统模型

正如图1我们所看到的，这个系统模型有四部分组成：数据拥有者，数据使用者，云服务商，可信任的第三方。

为了支持云端数据的模糊词检索，数据拥有者需要为数据集建立一个索引，然后需要把索引和加密的数据集上传给云服务商。为了设置访问权限，数据拥有者还需要为数据设置一个访问控制属性集，然后以加密的形式上传给云服务商。在用户提交他们的搜索请求之前，用户需要把他们的属性提交给第三方，然后第三方会把这个属性的签名返回给用户。为了搜索加密数据，用户需要把搜索需求和他们属性签名提供给云服务上，然后云服务商首先验证他们的属性是否有权限，再根据搜索算法返回相应的结果给用户。我们在这个模型中假设数据拥有者和用户之间完成了相互的认证关系。

1.2威胁模型

在这个算法中我们考虑云服务商是可信但是好奇的。即我们假设云服务商会按照我们设计的算法去做它的工作，但是它会根据他得到的索引和加密数据去分析用户的信息。

图1　云端加密数据检索的模型Fig.1　System model of search over cloud encrypted data.

1.2.1已知明文模型

在这个模型中，云服务商只能得到加密的数据集和索引的信息，而且所有的信息都是由数据拥有者上传给云服务商的。

1.3设计目标

在这个算法中，我们会得到以下的目标：1.3.1多关键模糊词搜索

在这个算法中，我们支持多关键模糊词的搜索，也就是即使输入的搜索请求存在拼写错误或者形式上的问题，这个算法也可以返回理想的结果。

1.3.2隐私保护

在这个算中，我们可以进行隐私保护即不会泄露数据集的信息，也不会泄露用户搜索请求的信息。

1.3.3访问控制

在这个算法中, 数据拥有者可以设置访问权限，也就是它可以定义拥有哪些属性的用户可以搜索这些数据集，与此同时，我们还会保护用户的属性信息。

1.3.4高效性

在这个算法中，因为我们考虑到用户偏好的因素，所以我们的搜索结果更加符合用户的偏好，有着更高的准确度。

1.4知识准备

1.4.1局部敏感哈希函数

给定一个距离定义，例如欧式距离，一个局部敏感哈希函数可以把两个相近的以很高的概率银蛇成相同的值。一个局部敏感哈希家族F中的每一个函数f都满足下列条件：

（1）如果d(x,y)≤d1, 那么f(x)=f(y)的概率至少为p1；

（2）如果d(x,y)≥d2,那么f(x)=f(y)的概率最大是p2；

则称F为（d1,d2,p1,p2）-敏感的函数族。

Bloom过滤器:如果想判断一个元素是不是在?

2　方案设计

2.1初始化

数据拥有者需要输入一个安全的参数m，这个参数可以生成一个密钥SK（M1, M2, S），在这里，M1，M2是两个p*p维的随机可逆矩阵，S是一个p唯的向量上传加密数据集F。

2.2上传加密数据集F，加密索引D，加密访问

权限数据集G

数据拥有者需要把加密的数据集F，加密的索引D和加密的访问权限数据集G上传给云服务商。2.2.1索引生成

2.2.1.1提取

首先需要对每个数据集中的每个数据提取。我们在这里把每个数据表示如下形式：

2.2.1.2转化

我们需要把每个转换成一个二元集，也就是二元集包含着两个连续的字母。以”apple”这个2比特的向量去表示这个集合。在这个向量中，每个元素代表一个二元集。如果这个二元集相应存在，我们把这个元素设置为1；如果这个二元集不存在，我们把相应的元素设置为0.所以我们可以把2维的向量。2.2.1.3建立索引

“apple”表示成一个27

为例，这个二元集为{#a,ap,pp,pl,le,e#}，然后我们用27

在这个算法中，每一个数据都有它自己的索引。每一个数据的索引都由相应的生成。

在初始阶段，每一个索引都是一个m比特的Bloom过滤器，开始每个比特都为0，表示成：一个集合里，一般想到的是将所有元素保存起来，然后通过比较确定。链表，树等等数据结构都是这种思路. 但是随着集合中元素的增加，我们需要的存储空间越来越大，检索速度也越来越慢。不过世界上还有一种叫作散列表（又叫哈希表，Hash table）的数据结构。它可以通过一个Hash函数将一个元素映射成一个位阵列（Bit Array）中的一个点。这样一来，我们只要看看这个点是不是1就知道可以集合中有没有它了。这就是布隆过滤器的基本思想。

Bloom过滤器本来是使用传统的哈希函数，但在我们的算法中，我们使用局部敏感哈希函数来代替传统的哈希函数，因为我们的算法需要支持多关键模糊词的搜索，而传统的哈希函数会使两个相似的词语有完全不同的输出，所以我们使用局部敏感哈希函数来代替。局部敏感哈希函数可以是两个相似的词语以很高的概率输出相同的值，所以我们使用这个函数来解决模糊词搜索。具体的步骤我们以为例来说明：

我们把1F的使用两个局部敏感哈希函数插入到空的bloom过滤器中，如下形式：

规则：为了避免碰撞，我们在这里使用两个局部敏感哈希函数，如果第i比特上的值已经为1，那么不管这个比特被映射多少次，它都始终为1。

我们把每个数据集都用如上规则来进行，我们可以得到每个数据的索引，我们把这些索引表示成如下形式：

在这个算法中，我们使用相关分数来代替原来向量总每个比特的值，这个值的计算方式我们采用TF-IDF模型。具体公式如下：

其中fj,wi表示wi在数据FJ，中的出现的TF，fwi表示有多少个数据集包含这个i；N表示数据集中数据的总数；表示数据FJ的长度，由索引的

决定。所以我们以数据D1为例说明，索引形式如下：

w

2.1.1.4加密索引

数据拥有者使用同态算法加密索引，数据拥有者使用向量S把索引拆成两部分（I’,I”），如果向量S[i]=0，我们就令I’[i]=I”[i]=I[i]；否则我们令I’[i]+I”[i]=I[i]. 最终，我们获得的加密索D可以表示成{M1T*I’，M2T*I”}。

2.2.2访问权限的生成

对于每个文件，数据拥有者首先设置一个访问权限，可以表示成如下形式：

每一个aij表示一个属性。

然后数据拥有者开始计算这个数据的访问属性的哈希值，这个哈希值被表示成h(Di||φ(Di))，其中φ(Di)表示数据集的访问属性。

2.3上传搜索请求，用户属性的签名

当用户想要搜索这个数据集时，他首先需要发送一个搜索请求，和用户自己的属性的签名形式给云服务商。

2.3.1用户属性UA签名的生成

用户首先需要把他的属性表示成UA的形式，发送给第三方，然后第三方需要验证这个属性，把这个属性用哈希函数加密,返回给用户。

2.3.2搜索请求的加密

首先用户需要把搜索的词语转换成二元集的形式，然后转换成二元向量的形式，所以搜索的词语可以表示成272的向量。然后我们使用两个哈希函数来生成这个搜索请求。

在这个过程总，我们需要引进的偏好来代替原有向量中的值，在这里我们用偏好因子来表示这个用户对这个1,w2,w3,…,wn}，我们首先对他进行排序，然后用户可以随机超递增序列来表示偏好因素的大小。所以这个搜索请求可以表示成：

的喜爱程度。因为我们知道，不同的用户对不同的词有不同的偏好程度，所以，我们应该考虑用户偏好的因素。我们在这里规定，如果两篇文章有相同的

用户对它们的偏好一样，我们此时就需要考虑

的相关性分数，相关分数高的论文具有更高的优先集。在这个算法中，我们考虑使用超递增序列来表示用户的偏好因子。所以，我们把搜索请求表示成{w

最后，我们需要对这个搜索请求进行加密。首先我们向量S把搜索请求Q分解成两部分{Q’,Q”}.规则是如果S[i]=0,我们令tQ’[i]+Q”[i]=Q[i];否则，我们令Q’[i]=Q”[i]=Q[i].最终我们将获得加密形式TR 表示成{M1T*Q’, M2T*Q”}。

2.4搜索结果

云服务商首先验证用户的属性信息，然后挑选出这个用户可以搜索的数据集。

在搜索结果中，云服务商按照如下规则jR=来搜索结果，如果RJ> 0，相应的数据集就会被返回。

3　安全性分析

3.1数据隐私

在这个算法中，为了保护数据集，在我们把数据集上传给云服务商之前，我们首先使用传统的加密方式来加密数据集。如果密钥是安全的，我们就可以相信数据集是安全的。

3.2索引隐私

在已知明文下，我们使用密钥来加密索引以后上传给云服务商，因为加密算法已经被证明是安全的，所以，在我们的算法中，索引是安全的。

3.3搜索请求的不可连接性

搜索请求的加密算法和索引的加密算法是一样的。对于两个不同的搜索请求，我们首先使用二元向量来表示这两个请求，然后我们使用哈希函数来产品Bloom 过滤器，最后我们加密这个请求，既然索引的加密算法是安全，那我们也可以确定搜索请求的加密是安全的。

3.4属性的隐私保护

在我们的算法中，为了保护数据集，用户在提交搜索请求之前，用户需要先提交他们的个人属性信息，我们使用哈希函数去加密这些属性，因为我们认为这个第三方是完全可信的，而且哈希函数是安全的，所以我们认为用户的属性是不会被泄露的。

4　实验验证

为了检验算法的有效性，我们实验使用约100万，来自IEEE INFOCOM 出版物的数据集。我们的实验是在配置为Intel Core2 T6670的处理器，2.2 GHz和6 G 1600 MHz DDR3 存储器。

为了验证算法的有效性，我们在同样的环境上对王[17]的算法做了实验来进行对比.具体实验内容如下：

搜索请求：cloud, computing, secure

我们假设用户对每个搜索有不同的偏好，且偏好程度依次递增。

结果如下：

通过实验验证，我们可以发现我们的算法可以返回更多的结果，而且更加符合用户的偏好。

5　结论

在这篇论文中，我们解决了云端加密数据的多搜索问题。

我们的算法支持基于用户偏好多关键模糊词搜索。我们使用了局部敏感哈希哈数和Bloom过滤器，超递增序列来进行搜索。除此之外，我们的算法支持设置访问权限功能。且实验证明，我们算法的高效性。

6　致谢

感谢NSFC (Grant Nos.61300181, 61502044), the Fundamental Research Funds for the Central Universities (Grant No.2015RC23)对这篇论文的支持。

[1] H. Liang, L. X. Cai, D. Huang, X. Shen, and D. Peng, “An smdp-based service model for interdomain resource allocation in mobile cloud networks,” IEEE Transactions on Vehicular Technology, vol. 61, no. 5, pp. 2222–2232, 2012.

[2] M. M. Mahmoud and X. Shen, “A cloud-based scheme for protecting source-location privacy against hotspot-locating attack in wireless sensor networks,” IEEE Transactions on Parallel and Distributed Systems, vol. 23, no. 10, pp. 1805–1818, 2012.

[3] Q. Shen, X. Liang, X. Shen, X. Lin, and H. Luo, “Exploiting geo-distributed clouds for e-health monitoring system with minimum service delay and privacy preservation,” IEEE Journal of Biomedical and Health Informatics, vol. 18, no. 2, pp. 430–439, 2014.

[4] D. Song, D. Wagner, and A. Perrig, “Practical techniques for searches on encrypted data,” in Proc. of S&P, 2000.

[5] E.-J. Goh, “Secure indexes,” Cryptology ePrint Archive, 2003, http:// eprint.iacr.org/2003/216.

[6] Y.-C. Chang and M. Mitzenmacher, “Privacy preserving keyword searches on remote encrypted data,” in Proc. of ACNS, 2005.

[7] R. Curtmola, J. A. Garay, S. Kamara, and R. Ostrovsky,“Searchable symmetric encryption: improved definitions and efficient constructions,” in Proc. of ACM CCS, 2006.

[8] D. Boneh, G. D. Crescenzo, R. Ostrovsky, and G. Persiano,“Public key encryption with keyword search,” in Proc. of EUROCRYPT, 2004.

[9] M. Bellare, A. Boldyreva, and A. ONeill, “Deterministic and efficiently searchable encryption,” in Proc. of CRYPTO, 2007. [11] M. Abdalla, M. Bellare, D. Catalano, E. Kiltz, T. Kohno, T. Lange,

[10] J. Malone-Lee, G. Neven, P. Paillier, and H. Shi, “Searchable encryp- tion revisited: Consistency properties, relation to anonymous ibe, and extensions,” J. Cryptol., vol. 21, no. 3, pp. 350–391, 2008.

[11] J. Li, Q. Wang, C. Wang, N. Cao, K. Ren, and W. Lou, “Fuzzy keyword search over encrypted data in cloud computing,” in Proc. of IEEE INFOCOM’10 Mini-Conference, San Diego, CA, USA, March 2010.

[12] D. Boneh, E. Kushilevitz, R. Ostrovsky, and W. E. S. III,“Public key encryption that allows pir queries,” in Proc. of CRYPTO, 2007.

[13] P.Golle,J.Staddon, and B.Waters, “Secure conjunctive keyword search over encrypted data,” in Proc. of ACNS, 2004, pp. 31–45.

[14] L. Ballard, S. Kamara, and F. Monrose, “Achieving efficient conjunctive keyword searches over encrypted data,” in Proc. of ICICS, 2005.

[15] D. Boneh and B. Waters, “Conjunctive, subset, and range queries on encrypted data,” in Proc. of TCC, 2007, pp. 535–554.

[16] R. Brinkman, “Searching in encrypted data,” in University of Twente, PhD thesis, 2007.

[17] Bing Wang, “Privacy-Preserving Multi-Keyword Fuzzy Search over Encrypted Data in the Cloud ” in Proc. of IEEE INFOCOM’ 2014.

[18] Wenhai Sun,” Verifiable Privacy-Preserving Multi-Keyword Text Search in the Cloud Supporting Similarity-Based Rank”in IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. 25, NO. 11, NOVEMBER 2014.

Multi-Keyword Fuzzy Search with Fine-Grained Access Control based on User Preference over Encrypted Cloud Data

WEI Xue
(School of Science ,Beijing University of Posts and Telecommunications, Beijing 100876, China)

With the growing development of cloud computing, the data owner outsource the data files to the cloud server, then the user can get the ideal results by searching algorithms. The outsourced data usually contain sensitive privacy information, so the data files need to be encrypted before outsourced to the cloud server. However, this will limit the utilization of the data. So, in this paper, a searching algorithm is proposed which supports multi-keyword fuzzy search with fine-grained access control based on user preference over encrypted cloud data. Specially, we considered the user preference and the user attributes to the algorithm. The experiment has shown that the algorithm can get more and better corresponding files based on IEEE INFOCOM publications.

Computing theory; Keywords search; User preference; Data on the cloud; Privacy protection

TP301

A

10.3969/j.issn.1003-6970.2016.08.006