魏　雪

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

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

魏雪

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

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

計(jì)算理論；

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

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

0　引言

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

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

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

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

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

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

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

1　問題陳述

1.1系統(tǒng)模型

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

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

1.2威脅模型

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

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

1.2.1已知明文模型

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

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

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

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

1.3.2隱私保護(hù)

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

1.3.3訪問控制

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

1.3.4高效性

在這個(gè)算法中，因?yàn)槲覀兛紤]到用戶偏好的因素，所以我們的搜索結(jié)果更加符合用戶的偏好，有著更高的準(zhǔn)確度。

1.4知識(shí)準(zhǔn)備

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

給定一個(gè)距離定義，例如歐式距離，一個(gè)局部敏感哈希函數(shù)可以把兩個(gè)相近的以很高的概率銀蛇成相同的值。一個(gè)局部敏感哈希家族F中的每一個(gè)函數(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過濾器:如果想判斷一個(gè)元素是不是在?

2　方案設(shè)計(jì)

2.1初始化

數(shù)據(jù)擁有者需要輸入一個(gè)安全的參數(shù)m，這個(gè)參數(shù)可以生成一個(gè)密鑰SK（M1, M2, S），在這里，M1，M2是兩個(gè)p*p維的隨機(jī)可逆矩陣，S是一個(gè)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提取

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

2.2.1.2轉(zhuǎn)化

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

“apple”表示成一個(gè)27

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

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

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

Bloom過濾器本來是使用傳統(tǒng)的哈希函數(shù)，但在我們的算法中，我們使用局部敏感哈希函數(shù)來代替?zhèn)鹘y(tǒng)的哈希函數(shù)，因?yàn)槲覀兊乃惴ㄐ枰С侄嚓P(guān)鍵模糊詞的搜索，而傳統(tǒng)的哈希函數(shù)會(huì)使兩個(gè)相似的詞語有完全不同的輸出，所以我們使用局部敏感哈希函數(shù)來代替。局部敏感哈希函數(shù)可以是兩個(gè)相似的詞語以很高的概率輸出相同的值，所以我們使用這個(gè)函數(shù)來解決模糊詞搜索。具體的步驟我們以為例來說明：

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

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

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

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

其中fj,wi表示wi在數(shù)據(jù)FJ，中的出現(xiàn)的TF，fwi表示有多少個(gè)數(shù)據(jù)集包含這個(gè)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)限的生成

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

每一個(gè)aij表示一個(gè)屬性。

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

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

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

2.3.1用戶屬性UA簽名的生成

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

2.3.2搜索請求的加密

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

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

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

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

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

最后，我們需要對這個(gè)搜索請求進(jìn)行加密。首先我們向量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ù)商首先驗(yàn)證用戶的屬性信息，然后挑選出這個(gè)用戶可以搜索的數(shù)據(jù)集。

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

3　安全性分析

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

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

3.2索引隱私

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

3.3搜索請求的不可連接性

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

3.4屬性的隱私保護(hù)

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

4　實(shí)驗(yàn)驗(yàn)證

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

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

搜索請求：cloud, computing, secure

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

結(jié)果如下：

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

5　結(jié)論

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

我們的算法支持基于用戶偏好多關(guān)鍵模糊詞搜索。我們使用了局部敏感哈希哈數(shù)和Bloom過濾器，超遞增序列來進(jìn)行搜索。除此之外，我們的算法支持設(shè)置訪問權(quán)限功能。且實(shí)驗(yà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