基于用戶偏好的云端加密數(shù)據(jù)的多關(guān)鍵模糊詞檢索

魏　雪

（北京郵電大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，北京市　100876）

基于用戶偏好的云端加密數(shù)據(jù)的多關(guān)鍵模糊詞檢索

魏雪

（北京郵電大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，北京市100876）

隨著云計算技術(shù)的發(fā)展，數(shù)據(jù)擁有者可以把數(shù)據(jù)集外包給云服務(wù)商，然后用戶可以通過搜索算法得到他們想要的結(jié)果。上傳給云服務(wù)商的數(shù)據(jù)通常會包含敏感信息，所以用戶需要先把數(shù)據(jù)集加密再上傳給云服務(wù)商。然而，這就限制了數(shù)據(jù)的利用率。所以，在這篇文章提出了一個搜索算法，它是基于云端加密數(shù)據(jù)的多關(guān)鍵模糊詞的檢索，特別的，在這個算法中，考慮了用戶的偏好和用戶屬性的問題。實驗驗證基于IEEE的文章，結(jié)果證明這篇論文的算法可以獲得更多，更加符合用戶偏好的結(jié)果。

計算理論；

搜索；用戶偏好；云端數(shù)據(jù)；隱私保護

本文著錄格式：魏雪. 基于用戶偏好的云端加密數(shù)據(jù)的多關(guān)鍵模糊詞檢索[J]. 軟件，2016，37（8）：27-31

0　引言

隨著云計算技術(shù)的發(fā)展，它作為一個新型的技術(shù)受到我們大家的關(guān)注。它為我們帶了很多方便。比如，云計算可以支持公司和企業(yè)把他們的數(shù)據(jù)集上傳給云服務(wù)商，這樣，在節(jié)省了存儲空間的同時，也使得用戶可以通過在云端檢索數(shù)據(jù)獲得他們想要的結(jié)果。這就意味著云計算是一個具有規(guī)模形的，低成本的，高效的技術(shù)。

但是在現(xiàn)實生活中，我們不可以完全信任云服務(wù)商，因為它會泄露用戶的數(shù)據(jù)，比如像醫(yī)療記錄，經(jīng)濟狀況這些隱私數(shù)據(jù)。所以，我們需要一種算法，可以允許用戶在云端數(shù)據(jù)中直接高效檢索到用戶感興趣的數(shù)據(jù)。

到目前為止，在云端加密數(shù)據(jù)的檢索上已經(jīng)有很大的成就[4]-[11]。特別的，在模糊詞搜索上也取到了很大的進步。但是，上述的這些工作都是基于單關(guān)鍵詞的檢索，其中模糊詞的檢索是使用編輯距離來列出所有錯誤拼寫的可能性的集合。最近的，王和他的團隊提出了一種基于多關(guān)鍵模糊詞的搜索，他們首次使用了局部敏感哈希函數(shù)來定義模糊詞的定義，這樣就不在需要字典了。

如今，如何有效的進行多的搜索始終是一個難題。在這我們的文章中，我們提出了一種搜索算法，它基于用戶偏好，支持訪問權(quán)限控制的多關(guān)鍵模糊詞在云端數(shù)據(jù)的檢索。所以，在這篇文章中，考慮到基于用戶偏好的問題，我們使用了一個超遞增序列來表示用戶的偏好大小。不僅如此，我們還考慮到了隱私保護問題，我們使用和用戶屬性和哈希函數(shù)來解決這個問題，我們實驗室基于IEEE文章，實驗結(jié)果已經(jīng)證明了我們的結(jié)果可以更加符合用戶的偏好。我們的貢獻主要總結(jié)成以下幾點：

1. 在我們所了解的范圍中，這是首次使用超遞增序列考慮模糊詞搜索的用戶偏好問題。

2. 基于隱私保護問題，我們使用和用戶屬性和哈希函數(shù)來進行用戶的訪問權(quán)限控制問題，并且保護了用戶屬性的隱私。

3. 我們已經(jīng)把我們的算法在IEEE的文章中進行了實驗驗證，結(jié)果表示，我們的算法可以得到更加符合用戶偏好的結(jié)果。

1　問題陳述

1.1系統(tǒng)模型

正如圖1我們所看到的，這個系統(tǒng)模型有四部分組成：數(shù)據(jù)擁有者，數(shù)據(jù)使用者，云服務(wù)商，可信任的第三方。

為了支持云端數(shù)據(jù)的模糊詞檢索，數(shù)據(jù)擁有者需要為數(shù)據(jù)集建立一個索引，然后需要把索引和加密的數(shù)據(jù)集上傳給云服務(wù)商。為了設(shè)置訪問權(quán)限，數(shù)據(jù)擁有者還需要為數(shù)據(jù)設(shè)置一個訪問控制屬性集，然后以加密的形式上傳給云服務(wù)商。在用戶提交他們的搜索請求之前，用戶需要把他們的屬性提交給第三方，然后第三方會把這個屬性的簽名返回給用戶。為了搜索加密數(shù)據(jù)，用戶需要把搜索需求和他們屬性簽名提供給云服務(wù)上，然后云服務(wù)商首先驗證他們的屬性是否有權(quán)限，再根據(jù)搜索算法返回相應(yīng)的結(jié)果給用戶。我們在這個模型中假設(shè)數(shù)據(jù)擁有者和用戶之間完成了相互的認(rèn)證關(guān)系。

1.2威脅模型

在這個算法中我們考慮云服務(wù)商是可信但是好奇的。即我們假設(shè)云服務(wù)商會按照我們設(shè)計的算法去做它的工作，但是它會根據(jù)他得到的索引和加密數(shù)據(jù)去分析用戶的信息。

圖1　云端加密數(shù)據(jù)檢索的模型Fig.1　System model of search over cloud encrypted data.

1.2.1已知明文模型

在這個模型中，云服務(wù)商只能得到加密的數(shù)據(jù)集和索引的信息，而且所有的信息都是由數(shù)據(jù)擁有者上傳給云服務(wù)商的。

1.3設(shè)計目標(biāo)

在這個算法中，我們會得到以下的目標(biāo)：1.3.1多關(guān)鍵模糊詞搜索

在這個算法中，我們支持多關(guān)鍵模糊詞的搜索，也就是即使輸入的搜索請求存在拼寫錯誤或者形式上的問題，這個算法也可以返回理想的結(jié)果。

1.3.2隱私保護

在這個算中，我們可以進行隱私保護即不會泄露數(shù)據(jù)集的信息，也不會泄露用戶搜索請求的信息。

1.3.3訪問控制

在這個算法中, 數(shù)據(jù)擁有者可以設(shè)置訪問權(quán)限，也就是它可以定義擁有哪些屬性的用戶可以搜索這些數(shù)據(jù)集，與此同時，我們還會保護用戶的屬性信息。

1.3.4高效性

在這個算法中，因為我們考慮到用戶偏好的因素，所以我們的搜索結(jié)果更加符合用戶的偏好，有著更高的準(zhǔn)確度。

1.4知識準(zhǔn)備

1.4.1局部敏感哈希函數(shù)

給定一個距離定義，例如歐式距離，一個局部敏感哈希函數(shù)可以把兩個相近的以很高的概率銀蛇成相同的值。一個局部敏感哈希家族F中的每一個函數(shù)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）-敏感的函數(shù)族。

Bloom過濾器:如果想判斷一個元素是不是在?

2　方案設(shè)計

2.1初始化

數(shù)據(jù)擁有者需要輸入一個安全的參數(shù)m，這個參數(shù)可以生成一個密鑰SK（M1, M2, S），在這里，M1，M2是兩個p*p維的隨機可逆矩陣，S是一個p唯的向量上傳加密數(shù)據(jù)集F。

2.2上傳加密數(shù)據(jù)集F，加密索引D，加密訪問

權(quán)限數(shù)據(jù)集G

數(shù)據(jù)擁有者需要把加密的數(shù)據(jù)集F，加密的索引D和加密的訪問權(quán)限數(shù)據(jù)集G上傳給云服務(wù)商。2.2.1索引生成

2.2.1.1提取

首先需要對每個數(shù)據(jù)集中的每個數(shù)據(jù)提取。我們在這里把每個數(shù)據(jù)表示如下形式：

2.2.1.2轉(zhuǎn)化

我們需要把每個轉(zhuǎn)換成一個二元集，也就是二元集包含著兩個連續(xù)的字母。以”apple”這個2比特的向量去表示這個集合。在這個向量中，每個元素代表一個二元集。如果這個二元集相應(yīng)存在，我們把這個元素設(shè)置為1；如果這個二元集不存在，我們把相應(yīng)的元素設(shè)置為0.所以我們可以把2維的向量。2.2.1.3建立索引

“apple”表示成一個27

為例，這個二元集為{#a,ap,pp,pl,le,e#}，然后我們用27

在這個算法中，每一個數(shù)據(jù)都有它自己的索引。每一個數(shù)據(jù)的索引都由相應(yīng)的生成。

在初始階段，每一個索引都是一個m比特的Bloom過濾器，開始每個比特都為0，表示成：一個集合里，一般想到的是將所有元素保存起來，然后通過比較確定。鏈表，樹等等數(shù)據(jù)結(jié)構(gòu)都是這種思路. 但是隨著集合中元素的增加，我們需要的存儲空間越來越大，檢索速度也越來越慢。不過世界上還有一種叫作散列表（又叫哈希表，Hash table）的數(shù)據(jù)結(jié)構(gòu)。它可以通過一個Hash函數(shù)將一個元素映射成一個位陣列（Bit Array）中的一個點。這樣一來，我們只要看看這個點是不是1就知道可以集合中有沒有它了。這就是布隆過濾器的基本思想。

Bloom過濾器本來是使用傳統(tǒng)的哈希函數(shù)，但在我們的算法中，我們使用局部敏感哈希函數(shù)來代替?zhèn)鹘y(tǒng)的哈希函數(shù)，因為我們的算法需要支持多關(guān)鍵模糊詞的搜索，而傳統(tǒng)的哈希函數(shù)會使兩個相似的詞語有完全不同的輸出，所以我們使用局部敏感哈希函數(shù)來代替。局部敏感哈希函數(shù)可以是兩個相似的詞語以很高的概率輸出相同的值，所以我們使用這個函數(shù)來解決模糊詞搜索。具體的步驟我們以為例來說明：

我們把1F的使用兩個局部敏感哈希函數(shù)插入到空的bloom過濾器中，如下形式：

規(guī)則：為了避免碰撞，我們在這里使用兩個局部敏感哈希函數(shù)，如果第i比特上的值已經(jīng)為1，那么不管這個比特被映射多少次，它都始終為1。

我們把每個數(shù)據(jù)集都用如上規(guī)則來進行，我們可以得到每個數(shù)據(jù)的索引，我們把這些索引表示成如下形式：

在這個算法中，我們使用相關(guān)分?jǐn)?shù)來代替原來向量總每個比特的值，這個值的計算方式我們采用TF-IDF模型。具體公式如下：

其中fj,wi表示wi在數(shù)據(jù)FJ，中的出現(xiàn)的TF，fwi表示有多少個數(shù)據(jù)集包含這個i；N表示數(shù)據(jù)集中數(shù)據(jù)的總數(shù)；表示數(shù)據(jù)FJ的長度，由索引的

決定。所以我們以數(shù)據(jù)D1為例說明，索引形式如下：

w

2.1.1.4加密索引

數(shù)據(jù)擁有者使用同態(tài)算法加密索引，數(shù)據(jù)擁有者使用向量S把索引拆成兩部分（I’,I”），如果向量S[i]=0，我們就令I(lǐng)’[i]=I”[i]=I[i]；否則我們令I(lǐng)’[i]+I”[i]=I[i]. 最終，我們獲得的加密索D可以表示成{M1T*I’，M2T*I”}。

2.2.2訪問權(quán)限的生成

對于每個文件，數(shù)據(jù)擁有者首先設(shè)置一個訪問權(quán)限，可以表示成如下形式：

每一個aij表示一個屬性。

然后數(shù)據(jù)擁有者開始計算這個數(shù)據(jù)的訪問屬性的哈希值，這個哈希值被表示成h(Di||φ(Di))，其中φ(Di)表示數(shù)據(jù)集的訪問屬性。

2.3上傳搜索請求，用戶屬性的簽名

當(dāng)用戶想要搜索這個數(shù)據(jù)集時，他首先需要發(fā)送一個搜索請求，和用戶自己的屬性的簽名形式給云服務(wù)商。

2.3.1用戶屬性UA簽名的生成

用戶首先需要把他的屬性表示成UA的形式，發(fā)送給第三方，然后第三方需要驗證這個屬性，把這個屬性用哈希函數(shù)加密,返回給用戶。

2.3.2搜索請求的加密

首先用戶需要把搜索的詞語轉(zhuǎn)換成二元集的形式，然后轉(zhuǎn)換成二元向量的形式，所以搜索的詞語可以表示成272的向量。然后我們使用兩個哈希函數(shù)來生成這個搜索請求。

在這個過程總，我們需要引進的偏好來代替原有向量中的值，在這里我們用偏好因子來表示這個用戶對這個1,w2,w3,…,wn}，我們首先對他進行排序，然后用戶可以隨機超遞增序列來表示偏好因素的大小。所以這個搜索請求可以表示成：

的喜愛程度。因為我們知道，不同的用戶對不同的詞有不同的偏好程度，所以，我們應(yīng)該考慮用戶偏好的因素。我們在這里規(guī)定，如果兩篇文章有相同的

用戶對它們的偏好一樣，我們此時就需要考慮

的相關(guān)性分?jǐn)?shù)，相關(guān)分?jǐn)?shù)高的論文具有更高的優(yōu)先集。在這個算法中，我們考慮使用超遞增序列來表示用戶的偏好因子。所以，我們把搜索請求表示成{w

最后，我們需要對這個搜索請求進行加密。首先我們向量S把搜索請求Q分解成兩部分{Q’,Q”}.規(guī)則是如果S[i]=0,我們令tQ’[i]+Q”[i]=Q[i];否則，我們令Q’[i]=Q”[i]=Q[i].最終我們將獲得加密形式TR 表示成{M1T*Q’, M2T*Q”}。

2.4搜索結(jié)果

云服務(wù)商首先驗證用戶的屬性信息，然后挑選出這個用戶可以搜索的數(shù)據(jù)集。

在搜索結(jié)果中，云服務(wù)商按照如下規(guī)則jR=來搜索結(jié)果，如果RJ> 0，相應(yīng)的數(shù)據(jù)集就會被返回。

3　安全性分析

3.1數(shù)據(jù)隱私

在這個算法中，為了保護數(shù)據(jù)集，在我們把數(shù)據(jù)集上傳給云服務(wù)商之前，我們首先使用傳統(tǒng)的加密方式來加密數(shù)據(jù)集。如果密鑰是安全的，我們就可以相信數(shù)據(jù)集是安全的。

3.2索引隱私

在已知明文下，我們使用密鑰來加密索引以后上傳給云服務(wù)商，因為加密算法已經(jīng)被證明是安全的，所以，在我們的算法中，索引是安全的。

3.3搜索請求的不可連接性

搜索請求的加密算法和索引的加密算法是一樣的。對于兩個不同的搜索請求，我們首先使用二元向量來表示這兩個請求，然后我們使用哈希函數(shù)來產(chǎn)品Bloom 過濾器，最后我們加密這個請求，既然索引的加密算法是安全，那我們也可以確定搜索請求的加密是安全的。

3.4屬性的隱私保護

在我們的算法中，為了保護數(shù)據(jù)集，用戶在提交搜索請求之前，用戶需要先提交他們的個人屬性信息，我們使用哈希函數(shù)去加密這些屬性，因為我們認(rèn)為這個第三方是完全可信的，而且哈希函數(shù)是安全的，所以我們認(rèn)為用戶的屬性是不會被泄露的。

4　實驗驗證

為了檢驗算法的有效性，我們實驗使用約100萬，來自IEEE INFOCOM 出版物的數(shù)據(jù)集。我們的實驗是在配置為Intel Core2 T6670的處理器，2.2 GHz和6 G 1600 MHz DDR3 存儲器。

為了驗證算法的有效性，我們在同樣的環(huán)境上對王[17]的算法做了實驗來進行對比.具體實驗內(nèi)容如下：

搜索請求：cloud, computing, secure

我們假設(shè)用戶對每個搜索有不同的偏好，且偏好程度依次遞增。

結(jié)果如下：

通過實驗驗證，我們可以發(fā)現(xiàn)我們的算法可以返回更多的結(jié)果，而且更加符合用戶的偏好。

5　結(jié)論

在這篇論文中，我們解決了云端加密數(shù)據(jù)的多搜索問題。

我們的算法支持基于用戶偏好多關(guān)鍵模糊詞搜索。我們使用了局部敏感哈希哈數(shù)和Bloom過濾器，超遞增序列來進行搜索。除此之外，我們的算法支持設(shè)置訪問權(quán)限功能。且實驗證明，我們算法的高效性。

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