基于用戶偏好的云端加密數據的多關鍵模糊詞檢索

魏　雪

（北京郵電大學 數學科學學院，北京市　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