面向多關(guān)鍵字的模糊密文搜索方法

王愷璇 李宇溪 周福才 王權(quán)琦

(東北大學(xué)軟件學(xué)院 沈陽 110819) (wkx_king@126.com)

面向多關(guān)鍵字的模糊密文搜索方法

王愷璇 李宇溪 周福才 王權(quán)琦

(東北大學(xué)軟件學(xué)院 沈陽 110819) (wkx_king@126.com)

圍繞多關(guān)鍵字的模糊匹配和數(shù)據(jù)安全性保障問題,展開對多關(guān)鍵字模糊搜索方法的研究,提出一種面向多關(guān)鍵字的模糊密文搜索方案.該方案以布隆過濾器(Bloom filter)為基礎(chǔ),使用對偶編碼函數(shù)和位置敏感Hash函數(shù)來對文件索引進(jìn)行構(gòu)建,并使用距離可恢復(fù)加密算法對該索引進(jìn)行加密,實現(xiàn)了對多關(guān)鍵字的密文模糊搜索.同時方案不需要提前設(shè)置索引存儲空間,從而大大降低了搜索的復(fù)雜度.除此之外,該方案與已有方案相比不需要預(yù)定義字典庫,降低了存儲開銷.實驗分析和安全分析表明,該方案不僅能夠?qū)崿F(xiàn)面向多關(guān)鍵字的密文模糊搜索,而且保證了方案的機密性和隱私性.

云存儲;布隆過濾器;可搜索加密機制;位置敏感Hash函數(shù);多關(guān)鍵字模糊搜索

隨著云存儲的迅速發(fā)展以及用戶對個人數(shù)據(jù)隱私性的愈加重視,如何對存儲在服務(wù)器中的密文進(jìn)行搜索就顯得格外重要.可搜索加密方法(searchable encryption, SE)是解決密文搜索的有效方法.

可搜索加密方法首次由Song和Wagner等人[1]提出,開創(chuàng)了將搜索機制應(yīng)用于關(guān)鍵字密文搜索的先河;2005年,Chang等人[2]提出了基于預(yù)定義字典的可搜索加密機制.這種機制不僅優(yōu)化了關(guān)鍵字的搜索效率,而且還縮減了計算開銷.但是,由于預(yù)定義字典的設(shè)定,同時也給用戶帶來了額外的存儲開支.隨后Dong等人[3]在2008年針對安全性進(jìn)行了改進(jìn),提出了能夠抵抗自適應(yīng)性攻擊的搜索加密模型.2015年,Revathy等人[4]提出了排序的搜索加密機制.以上幾種搜索關(guān)鍵字均是基于對稱密碼學(xué)的精確的單關(guān)鍵字搜索機制,用戶只能在一次搜索過程中發(fā)送1個單詞,這種搜索機制與現(xiàn)實的搜索需求極為不符.

2014年,Cao和Wang等人[5]提出了多關(guān)鍵字可搜索加密機制.該機制在搜索時為索引和關(guān)鍵字構(gòu)建向量,并通過向量運算實現(xiàn)了搜索結(jié)果的排序.2016年，文獻(xiàn)[6]提出了多關(guān)鍵字的排序搜索方案，該方案利用樹構(gòu)建索引結(jié)構(gòu)，減少了搜索時間.

從以上方案可以看出,不論是面向單關(guān)鍵字還是多關(guān)鍵字，現(xiàn)有研究都是針對精確搜索的.而針對用戶輸入錯誤關(guān)鍵字的情況,精確的單關(guān)鍵字搜索加密機制或者基于連接詞的搜索加密機制還需要改進(jìn).研究學(xué)者在精確搜索的基礎(chǔ)上相繼提出了基于關(guān)鍵字的模糊搜索方案.Bringer等人[7]在2009年提出了面向明文的模糊搜索方案,該方案主要基于布隆過濾器實現(xiàn)數(shù)據(jù)存儲.Van Liesdonk等人[8]在2010年研究了模糊關(guān)鍵字搜索加密方案,但這種方案最大的缺陷是需要用戶額外花費時間來執(zhí)行關(guān)鍵字的循環(huán)搜索.2010年,文獻(xiàn)[9]實現(xiàn)了關(guān)鍵字模糊搜索的加密機制,但該方案需要用戶付出龐大的數(shù)據(jù)存儲空間,且只實現(xiàn)了基于單關(guān)鍵字的模糊密文搜索.之后在2013年,文獻(xiàn)[10-11]也相繼提出了不同的模糊關(guān)鍵字搜索方法.其中，文獻(xiàn)[10]給出了單關(guān)鍵字可排序模糊關(guān)鍵字搜索方法，文獻(xiàn)[11]提出的是一種可驗證的模糊關(guān)鍵字搜索方案.

本文針對密文的多關(guān)鍵字模糊搜索展開研究,以提高搜索效率為目標(biāo),提出了一種面向多關(guān)鍵字的模糊密文搜索方案,該方案利用布隆過濾器和位置敏感Hash函數(shù)技術(shù),能夠有效實現(xiàn)多關(guān)鍵字的密文模糊搜索.主要研究內(nèi)容包括:將上傳文件利用對偶編碼函數(shù)將其關(guān)鍵字轉(zhuǎn)換成向量,再利用位置敏感Hash函數(shù)將其映射到布隆過濾器中;服務(wù)器在執(zhí)行密文搜索時,需要先對輸入的查詢關(guān)鍵字進(jìn)行上述轉(zhuǎn)換,再通過計算安全索引參數(shù)和陷門的內(nèi)積來搜索到符合條件的密文文件.與已有方案相比,本方案不需要提前設(shè)置索引存儲空間,從而大大降低了搜索的復(fù)雜度;同時,該方案不需要預(yù)定義字典庫,降低了存儲開銷.安全性分析表明方案不僅保證了可用性,而且滿足了機密性和隱私性.因而,該方案具有重要的理論價值和應(yīng)用前景.

1 預(yù)備知識

1.1 位置敏感Hash函數(shù)

位置敏感Hash函數(shù)于1998年由Indyk等人[12]提出,主要用于解決高維數(shù)據(jù)的搜索問題.

定義1. 位置敏感Hash函數(shù).給定n個d維的點集S以及各點之間的相似性度量D,Hash族H={h:H→U}被稱為(r1,r2,p1,p2)-敏感Hash函數(shù),需要滿足以下條件,對于q∈S:

如果v∈d(q,r1),那么Pr[h(q)=h(v)]≥p1;

如果v?d(q,r1),那么Pr[h(q)=h(v)]≤p2.

其中,r1

(1)

其中,參數(shù)a和b分別是d維的向量和[0,w]間的一個隨機數(shù),向量a中的每個元素都滿足p-stable分布.

式(1)的計算過程實際是向量的映射過程,如圖1所示.a·v即把向量a映射到以向量v為基向量的數(shù)軸上,如果將此數(shù)軸等分為w份,同時每份做上標(biāo)記,a·v的值對應(yīng)哪個區(qū)間就將這個區(qū)間的標(biāo)記號作為向量a的Hash函數(shù)值.

Fig. 1 p -stable distribution definition圖1 p穩(wěn)定分布定義圖

p(c)=Pra,b[ha,b(v1)=ha,b(v2)]=

其中,fp是分布D的密度函數(shù),p1=p(r1),p2=p(r2).

1.2 布隆過濾器

Bloom[14]在1970年提出了布隆過濾器(Bloom filter, BF)的概念.BF是一種概率型數(shù)據(jù)結(jié)構(gòu),主要用于判斷某個元素是否存在于集合中.

布隆過濾器的主要工作原理是:運用一個m(單位為b)長的數(shù)組表示這個布隆過濾器,數(shù)組的每一位元素初始化為0.隨后隨機選擇k個Hash函數(shù),將數(shù)據(jù)域S={y1,y2,…,yn}中的n個元素分別一一映射到上面的數(shù)組中,當(dāng)需要映射1個元素時,計算每個元素的k個Hash函數(shù)對應(yīng)的k個Hash值,然后把數(shù)組中對應(yīng)的位置設(shè)置為1.如果Hash值對應(yīng)的位置已經(jīng)設(shè)置成為1,就保留第1次作用的效果.如圖2所示:

Fig. 2 The sample figure of Bloom filter圖2 布隆過濾器示例圖

判斷元素x是否存在于數(shù)據(jù)域中,計算元素x對應(yīng)的上面的k個Hash函數(shù)的Hash值,如果該元素的所有Hash值對應(yīng)的位置都為1,就說明元素x存在于數(shù)據(jù)域中.

向布隆過濾器中加入1個新的元素時,需要使用k個不同的Hash函數(shù)對其進(jìn)行Hash計算,將這個元素映射到布隆過濾器的k個比特位中,同時將這些比特位設(shè)置為1.

查詢某個元素是否存在于布隆過濾器中時,需要利用提前定義的k個Hash函數(shù)將其映射到BF的k個比特位上.如果這k個比特位對應(yīng)的值都是1,則說明該元素存在于集合中, 只要有一個位置不為1,則此元素不存在于該集合中.

1.3 對偶編碼函數(shù)

在面向密文的多關(guān)鍵字模糊搜索方案中,構(gòu)建索引、構(gòu)建陷門和關(guān)鍵字查詢的過程都是基于向量的操作過程.數(shù)據(jù)擁有者輸入的關(guān)鍵字都由字符組成,由于字符的不可計算性,需要將其轉(zhuǎn)換成向量的形式.

定義2. 對偶編碼函數(shù).給定字符串S1=C1C2…Cn和二進(jìn)制向量S2=b0b1…bm-1,S2中每位元素的初始值為0,其中n

1.4 距離可恢復(fù)加密方案

距離可恢復(fù)加密算法可以將數(shù)據(jù)庫中的各個元素表示成1個多維的點,其中屬性作為該點的維度,屬性對應(yīng)的值作為該維度上的值.

定義3. 距離可恢復(fù)加密(distance recovery encryption, DRE)[15-16].給定加密函數(shù)E以及加密密鑰K,則數(shù)據(jù)庫DB中的點p對應(yīng)的密文為E(p,K).當(dāng)且僅當(dāng)E滿足以下條件,E可稱為距離可恢復(fù)加密.對于任意2點p1,p2,以及密鑰K,存在函數(shù)f,使得

f(E(p1,K),E(p2,K))=d(p1,p2)

成立.其中d(p1,p2)為p1,p2的距離.如果函數(shù)f是歐氏距離計算函數(shù),則E被稱為距離保留轉(zhuǎn)換函數(shù).

2 多關(guān)鍵字模糊密文搜索方案

本節(jié)將描述該方案的模型、形式化和安全性定義以及方案的詳細(xì)設(shè)計.

2.1 模 型

如圖3所示,方案中涉及3個實體:1)數(shù)據(jù)擁有者.該實體把數(shù)據(jù)外包給服務(wù)器進(jìn)行加密存儲.2)可信賴用戶.該實體并不持有數(shù)據(jù)但是可以對數(shù)據(jù)進(jìn)行搜索,最終獲取需要的數(shù)據(jù).3)服務(wù)器.此實體提供存儲服務(wù),存儲用戶的密文數(shù)據(jù),并在收到用戶的搜索請求時,執(zhí)行密文的搜索操作.

數(shù)據(jù)擁有者在本地選擇待存儲的文件集,對其進(jìn)行處理后上傳到服務(wù)器端.文件集的處理包括2個部分：1)對文件進(jìn)行加密,之后生成相應(yīng)的密文;2)為待存儲的文件設(shè)置索引,利用預(yù)定義的加密算法對其進(jìn)行加密,最終生成加密索引.數(shù)據(jù)擁有者需要將處理之后的文件上傳至服務(wù)器,由于存儲文件和索引的工作由服務(wù)器負(fù)責(zé),所以數(shù)據(jù)擁有者只需要執(zhí)行上傳操作即可,不需要再關(guān)心具體的存儲細(xì)節(jié).

Fig. 3 Basic architecture圖3 方案基本架構(gòu)

各個實體的功能介紹如下:

1) 數(shù)據(jù)擁有者.它是一個特殊的可信賴用戶,因為具體的明文是由數(shù)據(jù)擁有者確定,所以數(shù)據(jù)擁有者是3個實體中唯一能夠與明文直接接觸的實體.數(shù)據(jù)擁有者首先選擇明文數(shù)據(jù),然后加密這些明文,同時構(gòu)建這些明文相對應(yīng)的索引,最后把密文以及加密后的索引發(fā)送給云服務(wù)器進(jìn)行存儲.數(shù)據(jù)擁有者還需要選擇可信賴用戶(包括自己),并向其發(fā)送搜索陷門.

2) 可信賴用戶.即數(shù)據(jù)擁有者授權(quán)的可信實體.它主要接收數(shù)據(jù)擁有者發(fā)送的搜索陷門,然后生成安全陷門,向服務(wù)器端發(fā)送搜索請求.接收到服務(wù)器發(fā)送回來的搜索結(jié)果后,對搜索結(jié)果進(jìn)行解密,從而獲取需要的明文數(shù)據(jù).

3) 服務(wù)器.它主要進(jìn)行數(shù)據(jù)密文以及索引密文的存儲,同時對于數(shù)據(jù)擁有者以及可信賴用戶發(fā)來的搜索請求進(jìn)行相應(yīng)的搜索以及應(yīng)答.

對于基于布隆過濾器以及位置敏感Hash函數(shù)實現(xiàn)的面向多關(guān)鍵字的模糊密文搜索方案,在該方案中不需要設(shè)置預(yù)定義字典存儲錯誤的關(guān)鍵字.根據(jù)上述描述提出面向多關(guān)鍵字的模糊密文搜索方案的基本架構(gòu).

2.2 形式化定義

本方案主要由4個主要算法組成:初始化算法、生成索引算法、生成陷門算法、搜索算法.形式化地表示為MKFS=(KeyGen,BuildIndex,Trapdoor,Search).下面分別對其進(jìn)行具體的描述.

1)sk←KeyGen(1k):初始化算法.運行于數(shù)據(jù)擁有者端,主要用于生成密鑰.輸入安全參數(shù)1k,輸出密鑰sk.加密索引和查詢關(guān)鍵字都需要該密鑰.如果該密鑰丟失,數(shù)據(jù)擁有者將無法從服務(wù)器端再獲取目標(biāo)數(shù)據(jù).

2)I←BuildIndex(sk,F,W):生成索引算法.運行于數(shù)據(jù)擁有者端,主要用于生成文件對應(yīng)的安全索引.輸入密鑰sk、文件標(biāo)記序號F以及文件F對應(yīng)的關(guān)鍵詞集合δ,輸出安全索引I.

3)t←Trapdoor(sk,Q):生成陷門算法.運行于用戶端,用于加密查詢關(guān)鍵字集合生成安全陷門.輸入密鑰sk以及查詢關(guān)鍵詞集合Q,輸出安全陷門t.用于加密查詢關(guān)鍵詞集合Q,輸出安全陷門t.

4)FR←Search(I,t):搜索算法.運行于第三方服務(wù)器端.輸入安全索引和安全陷門，輸出文件序列集合.主要進(jìn)行安全索引與安全陷門的匹配,如果匹配成功就返回該索引對應(yīng)的文件標(biāo)識符;如果匹配不成功,則無返回結(jié)果.

當(dāng)服務(wù)器端搜索到滿足搜索條件的結(jié)果時,就將結(jié)果集合返回給用戶,用戶需要利用數(shù)據(jù)擁有者傳送的搜索陷門進(jìn)行解密,最后得到需要的目標(biāo)文件.

2.3 安全性定義

根據(jù)本文提出的方案,在給出安全模型之前,首先定義以下幾個與安全性模型相關(guān)的概念,方便后續(xù)的安全性定義.

定義4. 數(shù)據(jù)擁有者所持有的所有明文信息以及查詢關(guān)鍵字歸納定義為明文信息集H=(F,W,Q).其中F為文件集合，W為各文件對應(yīng)的關(guān)鍵字集合，Q為查詢關(guān)鍵字集合.

定義5. 明文信息集H加密生成的密文信息集V(H).該集合包括文件集合F對應(yīng)的密文集合Encs k(F)，關(guān)鍵字集合W加密后對應(yīng)的安全索引集合I和查詢關(guān)鍵字集合Q加密后對應(yīng)的安全陷門t.

定義6. 將服務(wù)器能夠獲取的信息統(tǒng)稱為足跡集合Tr(H).Tr(H)主要由服務(wù)器搜索到的結(jié)果組成,即Tr(H)={Tr(w1),Tr(w2),…,Tr(wt)}.

為了更好更直觀地評估搜索方案的安全性,本文根據(jù)敵手能夠獲取的資源SA將攻擊模型分為3個級別.

級別1. 已知密文模型.在這個安全級別中,敵手只能獲取密文信息V(H),即SA=〈V(H)〉.實際應(yīng)用中,服務(wù)器除了能夠獲取密文資源外,無法獲取其他任何的資源.

級別2. 已知密文與某些明文.在這個安全級別中,敵手除了能夠獲取密文資源,還能夠獲取一組明文信息H′∈H,但是敵手無法確認(rèn)這些信息所對應(yīng)的密文,即SA=〈V(H)，H′〉.

級別3. 已知密文與某些明文以及這些明文對應(yīng)的密文.在這個攻擊模型中,敵手除了能夠獲取密文資源、一組明文信息H′∈H,還能夠獲取這些明文信息對應(yīng)的密文V(H′),即SA=〈V(H),H′,V(H′)〉.

上述3個級別中,級別越高說明該方案安全性越高,所以如果一個加密方案能夠抵抗級別高的攻擊模型,那么該模型也能夠抵抗級別低的模型.在上訴定義的3個級別的安全模型中,級別2與現(xiàn)實環(huán)境更接近.由于實際應(yīng)用中,敵手無法在不知道密鑰的情況下,由密文關(guān)聯(lián)明文,所以級別3在實際應(yīng)用中很少會發(fā)生.

在上述安全模型中,一個能夠保證數(shù)據(jù)安全性的密文搜索方案應(yīng)該滿足以下安全特性:

1) 文件隱私性.文件隱私性表示存儲在第三方服務(wù)器中的密文文件不應(yīng)向服務(wù)器泄露任何與明文文件相關(guān)的信息.

2) 關(guān)鍵字隱私性.服務(wù)器能夠獲取的不僅是搜索結(jié)果,還能夠獲取安全索引以及安全陷門.關(guān)鍵字隱私性要求服務(wù)器無法通過安全索引以及安全陷門獲取任何與關(guān)鍵字相關(guān)的信息.

3) 陷門不可鏈接性.服務(wù)器無法將獲取到的一個安全陷門擴展到另一個安全陷門,即進(jìn)行2次搜索操作時,輸入同一組關(guān)鍵詞,服務(wù)器無法對這2次生成的陷門進(jìn)行區(qū)分.

除此之外,提出面向多關(guān)鍵字的模糊密文搜索方案能夠抵抗選擇明文攻擊.方案的安全性證明主要是敵手和用戶模擬器之間的交互性游戲.

定義RealS1(sk)為模擬器S1執(zhí)行真實方案的1次實驗,在整個實驗過程中均使用真實的方案算法.用戶首先執(zhí)行初始化算法,然后分別根據(jù)敵手需要挑戰(zhàn)的內(nèi)容生成不同的內(nèi)容,并保存已獲取的信息構(gòu)成VReal.該實驗最終輸出1個比特b作為輸出結(jié)果.

定義IdealS2(sk)為模擬器S2的1次模擬仿真實驗.與RealS1(sk)不同的是IdealS2(sk)實驗中并不運行真實的算法,而是把真實算法中服務(wù)器可以獲取的資源作為IdealS2(sk)實驗的輸入,然后模擬器通過生成隨機數(shù)據(jù)作為實驗輸出.同RealS1(sk)一樣,S2收集所有已獲取的信息構(gòu)成VIdeal.該實驗最終輸出1個比特b′作為輸出結(jié)果.

選擇關(guān)鍵字安全性指的是,存在任意模擬器,使得任意敵手都無法將VIdeal和VReal區(qū)分開來.即敵手無法真正區(qū)分整個實驗過程中到底是真實的用戶還是模擬器在與其進(jìn)行交互.下面將給出面向多關(guān)鍵字的模糊密文搜索方案的安全模型的形式化定義.

定義7. 自適應(yīng)選擇關(guān)鍵字安全性.給定一個面向多關(guān)鍵字的模糊密文搜索方案,令A(yù)為一個敵手,S1,S2為2個模擬器.函數(shù)G1，G2，G3分別是在生成密文階段、生成安全索引階段、生成陷門階段中實驗RealS1(sk)和實驗IdealS2(sk)之間互相共享的信息,即實驗RealS1(sk)的泄露函數(shù).下面是實驗的交互過程:

實驗RealS1(sk)和實驗IdealS2(sk)在文件加密階段的形式化定義如下：

RealS1(sk):

sk←KenGen(1k),

F←S1(m),

X←Enc(F,sk:S1),

outputb1←S1(X).

IdealS2(sk):

sk′←KenGen(1k),

X′←Enc(F′,sk′:S2),

實驗RealS1(sk)和實驗IdealS2(sk)在生成陷門階段的形式化定義如下:

RealS1(sk):

sk←KenGen(1k),

(l)←S1,

Q←S1(l),

t←BuildTrapdoor(Q,sk:S1),

outputb2←S1(t).

IdealS2(sk):

sk′←KenGen(1k′),

t′←BuildTrapdoor(Q′,sk′:S2),

實驗RealS1(sk)和實驗IdealS2(sk)在生成安全索引階段的形式化定義如下:

RealS1(sk):

sk←KenGen(1k),

(fi,t)←S1,

Wi←S1(t,fi),

I←BuildIndex(fi,Wi,sk:S1),

outputb3←S1(I).

IdealS2(sk):

sk′←KenGen(1k′),

在前文已對敵手具有的能力進(jìn)行了分析,并且定義了方案在安全目標(biāo)為不可區(qū)分性的條件下的安全模型.下面利用敵手和挑戰(zhàn)者之間的攻擊游戲來定義面向多關(guān)鍵字的模糊密文搜索方案的安全性.

1) 挑戰(zhàn)密文

① 初始階段.挑戰(zhàn)者執(zhí)行初始化算法KenGen(1k),密鑰sk作為該階段的輸出結(jié)果.

如果完成上述游戲后,對所有的敵手A,均存在一個模擬器S,使:

其中p(sk)是以sk為輸入的多項式,那么面向多關(guān)鍵字的模糊密文搜索方案針對密文是選擇明文攻擊安全的.

2) 挑戰(zhàn)安全陷門

① 初始階段.挑戰(zhàn)者執(zhí)行初始化算法KenGen(1k),密鑰sk作為該階段的輸出結(jié)果.

3) 挑戰(zhàn)安全索引

① 初始階段.挑戰(zhàn)者執(zhí)行初始化算法KenGen(1k),密鑰sk作為該階段的輸出結(jié)果.

2.4 算法詳細(xì)設(shè)計

2.4.1 密鑰生成算法

sk←KeyGen(1k):該算法用于方案的初始化、生成密鑰,其中k需要取足夠長,例如128 b,這樣才能夠有效阻止蠻力攻擊.該算法的主要步驟如下:

1) 隨機構(gòu)建2個k×k維的矩陣M1,M2∈k×k;

2) 隨機構(gòu)建1個k維的向量S∈{0,1}k,為了使引入?yún)?shù)向量S的隨機性最大化,S中0和1的數(shù)量需要大致相同.

3) 輸出sk=(M1,M2,S)作為生成加密索引和生成陷門的密鑰.

2.4.2 生成安全索引算法

I←BuildIndex(sk,F,W):該算法用于加密用戶輸入的索引.主要步驟如下:

1) 對于文件集合F={f1,f2,…,fn}中的每一個文件fi:

① 為文件fi構(gòu)建一個k位的Bloom過濾器Bi;

② 對于文件fi所對應(yīng)的關(guān)鍵字集合Wi={w1,w2,…,wt},使用對偶編碼函數(shù)將其轉(zhuǎn)換成向量集合V={v1,v2,…,vt},其中每個向量vi∈{0,1}676;

③ 對于向量集合V={v1,v2,…,vt}中的每個向量vi,使用位置敏感Hash函數(shù){H1,H2,…,Hl}進(jìn)行計算(H1(vi),H2(vi),…,Hl(vi)),并將結(jié)果插入到Bloom過濾器Bi中.

2) 將私鑰sk中的S表示為S=(s1,s2,…,sk).對于每一個文件fi所得到的Bloom過濾器Bi,

① 隨機選擇參數(shù)r∈.

3) 輸出I=(F,I1,I2,…,In).

Fig. 4 Sample of generation security index圖4 生成安全索引示例

根據(jù)上述生成安全索引的步驟,給出一組具體的示例.給定3個關(guān)鍵詞:Network,Search,Bloom.先將這3個關(guān)鍵詞轉(zhuǎn)換成676 B長的數(shù)組表示,其中每個元素都表示每2個字符的組合,然后利用選擇的l個位置敏感Hash函數(shù)(這個示例中l(wèi)=2),計算單個關(guān)鍵詞在布隆過濾器中對應(yīng)的位置,最后該對應(yīng)的位置置位為1.該示例的具體操作如圖4所示:

2.4.3 陷門算法

t←Trapdoor(sk,Q):根據(jù)查詢關(guān)鍵詞集合生成安全陷門.主要步驟如下：

1) 構(gòu)建1個k位的Bloom過濾器B.

2) 對于查詢關(guān)鍵字集合Q={q1,q2,…,qt},使用對偶編碼函數(shù)將其轉(zhuǎn)換成向量集合V={v1,v2,…,vt},其中每個向量vi∈{0,1}676.

3) 對于向量集合V={v1,v2,…,vt}中的每個向量v,使用位置敏感Hash函數(shù){H1,H2,…,Hl}進(jìn)行計算,并將結(jié)果插入到Bloom過濾器B中.

4) 將私鑰sk中的S表示為S=(s1,s2,…,sk).對于Bloom過濾器B:

① 隨機選擇數(shù)r′∈.

⑤ 令t=(t′,t″).

5) 輸出陷門t.

針對上述給出的生成陷門的具體步驟,給定2個查詢關(guān)鍵詞對上述的步驟進(jìn)行形象化的表示.假設(shè)給定的2個查詢關(guān)鍵詞為Netword,Search.對比索引示例圖中的關(guān)鍵詞,Netword與Network之間僅僅相差了1個字符,但是通過同一組位置敏感Hash函數(shù)計算后Netword在布隆過濾器中對應(yīng)的位置與Network的位置相同.下面給出示例中2個查詢關(guān)鍵詞的布隆過濾器表示,如圖5所示:

Fig. 5 Example of generating the trapdoor圖5 生成陷門示例

2.4.4 搜索算法

FR←Search(I,t):服務(wù)器根據(jù)陷門和加密索引執(zhí)行搜索.主要步驟如下：

1) 令FR為一個初始為空的文件集合.

2) 將I表示為I=(F,I1,I2,…,In).對于其中的每一個Ii:

② 計算向量的數(shù)量積

(2)

③ 按排序算法將計算的向量內(nèi)積作排序,將排序序列中的前λ條記錄加入到結(jié)果集合FR中.

3) 輸出FR作為最終搜索結(jié)果.

圖6是通過2.4.2～2.4.3節(jié)中給出的生成安全索引的示例以及生成陷門的示例給出的最終搜索示例結(jié)果,按照上述搜索步驟,實際服務(wù)器執(zhí)行的就是2個向量之間的內(nèi)積,然后獲取內(nèi)積結(jié)果,找出對應(yīng)的文件標(biāo)識.

為了確保索引以及查詢關(guān)鍵詞經(jīng)過上述加密后能否返回正確的結(jié)果,只要保證RI=Bi·B就說明該搜索方案能夠?qū)崿F(xiàn)面向多關(guān)鍵字的模糊密文搜索.下面就給出上述過程的正確性推導(dǎo):

3)RI=Ii·t,安全索引與陷門作內(nèi)積運算.

由上述推算結(jié)果可以看出,參數(shù)r′與最終的結(jié)果沒有關(guān)系,所以可以隨機選擇.

由上述推算結(jié)果可以看出,參數(shù)r′與最終的結(jié)果沒有關(guān)系,所以可以隨機選擇.

7) 通過5) 6)的推導(dǎo),得出

RI={bi,j·bj,bi,j∈Bi,bj∈B}=Bi·B.

由7)中最終的推算結(jié)果,可知本文提出的面向多關(guān)鍵字的模糊密文搜索方案是正確的.

2.5 方案詳細(xì)設(shè)計

本節(jié)將通過對數(shù)據(jù)擁有者、可信賴用戶和服務(wù)器這3個實體間的交互對方案的詳細(xì)設(shè)計進(jìn)行描述.

1) 在初始化階段,數(shù)據(jù)擁有者首先選定待存儲的文件集;然后運行算法KeyGen(1k)為系統(tǒng)生成密鑰.

2) 對于已選定的文件集,數(shù)據(jù)擁有者將采用傳統(tǒng)的對稱加密算法對其進(jìn)行加密.

3) 數(shù)據(jù)擁有者為待存儲的文件設(shè)置索引,即運行算法BuildIndex(sk,F,W)得到文件的安全索引;然后將加密后的文件集與安全索引一同存儲到服務(wù)器中.

4) 數(shù)據(jù)擁有者根據(jù)判斷選擇自己的可信賴用戶.

5) 當(dāng)可信賴用戶想要在服務(wù)器中搜索特定文件時,他將給定關(guān)鍵字集合,并將其發(fā)送給數(shù)據(jù)擁有者.

6) 數(shù)據(jù)擁有者在接收到用戶發(fā)送的關(guān)鍵字集合后,運行Trapdoor(sk,Q)算法為關(guān)鍵字集合生成搜索陷門,并返回給可信賴用戶.

7) 可信賴用戶將搜索陷門發(fā)送給服務(wù)器進(jìn)行搜索請求.

8) 服務(wù)器在接收到搜索陷門后將對搜索陷門和加密的安全索引運行Search(I,t)算法,得到的結(jié)果為加密的目標(biāo)文件集;然后將目標(biāo)文件集返回給可信賴用戶.

9) 可信賴用戶在接收到搜索結(jié)果后,通過數(shù)據(jù)擁有者的協(xié)助將搜索結(jié)果進(jìn)行解密,得到最終的明文文件.

3 方案分析

3.1 正確性分析

本文提出的面向多關(guān)鍵字的密文搜索方法既可對準(zhǔn)確的關(guān)鍵字進(jìn)行搜索,又可對模糊的關(guān)鍵字進(jìn)行搜索.因此我們將從下面2個方面對方案的搜索結(jié)果的正確性進(jìn)行分析.

1) 本文方案能夠返回對于準(zhǔn)確的關(guān)鍵字搜索的正確結(jié)果.如果查詢關(guān)鍵字Q?WD,云服務(wù)器應(yīng)該包含結(jié)果集中的文件D.回想一下在構(gòu)建索引和查詢的過程中,我們使用了相同的l個Hash函數(shù)hj∈H,1≤j≤l.那么在查詢Q中被設(shè)為1的位置,同樣在索引ID中也設(shè)為1.這就表明查詢能夠產(chǎn)生內(nèi)積操作的最大值.因此,文件D一定包含在結(jié)果集中.

2) 本文方案能夠以高的概率返回對于模糊的關(guān)鍵字搜索的正確結(jié)果.假設(shè)關(guān)鍵字w∈Q與關(guān)鍵字w′∈WD稍有不同,也就是說d(w,w′)≤r1,其中r1是位置敏感Hash函數(shù)中的距離閾值.如果對于所有l(wèi)個位置敏感Hash函數(shù)有hj(w)=hj(w′),hi∈H,1≤i≤l,那么搜索結(jié)果將返回如同精確關(guān)鍵字搜索一樣的內(nèi)積操作最大值.

而如果d(w,w′)>r1,那么位置敏感Hash函數(shù)將它們散列在一起的概率就會非常低.因此,本文方案會以高的概率返回相當(dāng)高的內(nèi)積計算結(jié)果.

3.2 安全性證明

目前大多數(shù)的密文搜索方案或多或少會泄露用戶的某些相關(guān)信息.本文在這些泄露信息存在的條件下,給出方案的選擇關(guān)鍵字安全性證明.安全性證明過程中,將方案的執(zhí)行過程描述成敵手與用戶或者模擬器之間的交互游戲,證明對于所有敵手,都無法從搜索過程中獲取除了允許泄露的信息之外的任何信息.

接下來首先分析在方案的密文生成過程、安全索引生成過程以及陷門生成過程允許向服務(wù)器泄露的信息,然后給出這些泄露函數(shù)的形式化定義.

1) 生成密文

2) 生成陷門

3) 生成安全索引

在生成陷門過程中,實驗IdealS2(sk)可以了解在實驗RealS1(sk)中關(guān)鍵字集合Q中每一個元素qi是否存在于文件fj中,可以將這些信息記為G3.

定理1. 如果文件加密方案、生成安全索引方案、生成陷門方案都是CPA安全的,則本文提出的面向多關(guān)鍵字的模糊密文搜索方案在隨機預(yù)言機模型下是針對自適應(yīng)選擇關(guān)鍵字攻擊的(G1,G2,G3) 安全的.

定理1表明,在給定上述泄露函數(shù)的情況下,本文提出的面向多關(guān)鍵字的模糊密文搜索方案在預(yù)言機模型下是安全的.

證明. 構(gòu)造一個多項式模擬器,與敵手進(jìn)行交互,在這個過程中,模擬器需要分別執(zhí)行實驗RealS1(sk)和實驗IdealS2(sk),最后敵手無法區(qū)分收到的結(jié)果是實驗RealS1(sk)的結(jié)果還是實驗IdealS2(sk)的結(jié)果.

1) 生成密文階段

初始階段:挑戰(zhàn)者執(zhí)行初始化算法KenGen(1k),密鑰sk作為該階段的輸出結(jié)果.

挑戰(zhàn)階段:敵手A選擇想要挑戰(zhàn)的明文信息F,并將其發(fā)送給挑戰(zhàn)者,挑戰(zhàn)者分別執(zhí)行實驗RealS1(sk)和實驗IdealS2(sk).

生成隨機參數(shù)b∈{0,1}.b=0時,將X發(fā)送給敵手;當(dāng)b=1時,將X′發(fā)送給敵手.

猜測:最后,敵手輸出對b的1個猜測b″.

密文加密采用AES加密方案,由于該方案是CPA安全的,因此,保證了對于任何多項式敵手來說,都無法區(qū)分模擬值X′與真實值X,即敵手獲勝的概率是可忽略的.

2) 生成陷門階段

初始階段:挑戰(zhàn)者執(zhí)行初始化算法KenGen(1k),密鑰sk=(M1,M2,S)作為該階段的輸出結(jié)果,其中M1,M2∈(×)k,S∈k.

挑戰(zhàn)階段:敵手A選擇想要挑戰(zhàn)的查詢關(guān)鍵字Q,并將其發(fā)送給挑戰(zhàn)者,挑戰(zhàn)者分別執(zhí)行實驗RealS1(sk)和實驗IdealS2(sk).

實驗RealS1(sk):挑戰(zhàn)者將Q作為輸入,執(zhí)行算法BuildTrapdoor(sk,Q),輸出真實陷門值t.

實驗IdealS2(sk):根據(jù)泄露函數(shù)G1,G2,按下面步驟生成模擬的陷門值.

② 執(zhí)行BuildTrapdoor(sk′,Q′),輸出安全索引模擬值t′.

生成隨機參數(shù)b∈{0,1}.b=0時,將X發(fā)送給敵手;當(dāng)b=1時,將X′發(fā)送給敵手.

猜測:最后,敵手輸出對b的1個猜測b″.

由于加密查詢關(guān)鍵字中參數(shù)r和密鑰sk的偽隨機性,保證了對于任何多項式敵手來說,都無法區(qū)分模擬值X′與真實值X,即敵手獲勝的概率是可忽略的.

3) 生成安全索引階段

初始階段:挑戰(zhàn)者執(zhí)行初始化算法KenGen(1k),密鑰sk=(M1,M2,S)作為該階段的輸出結(jié)果,其中M1,M2∈(×)k,S∈k.

挑戰(zhàn)階段:敵手A選擇想要挑戰(zhàn)的對于關(guān)鍵字W的安全索引,并將其發(fā)送給挑戰(zhàn)者,挑戰(zhàn)者分別執(zhí)行實驗RealS1(sk)和實驗IdealS2(sk).

實驗RealS1(sk):挑戰(zhàn)者將W作為輸入,執(zhí)行算法BuildIndex(sk,fi,W),輸出真實的安全索引Ii.

實驗IdealS2(sk):根據(jù)泄露函數(shù)G1,G2,G3, 按下面步驟生成模擬的安全索引的值.

生成隨機參數(shù)b∈{0,1}.b=0時,將X發(fā)送給敵手;當(dāng)b=1時,將X′發(fā)送給敵手.

猜測:最后,敵手輸出對b的1個猜測b″.

由于生成安全索引中參數(shù)r′和密鑰sk的偽隨機性,保證了對于任何多項式敵手來說,都無法區(qū)分模擬值X′與真實值X,即敵手獲勝的概率是可忽略的.

綜上所述,對任意多項式敵手,實驗RealS1(sk)和實驗IdealS2(sk)的輸出是一致的,即存在可忽略概率negl(k),使得:

因此,本文提出的面向多關(guān)鍵字的模糊密文搜索方案在隨機預(yù)言機模型下針對選擇關(guān)鍵字攻擊是(G1,G2,G3)安全的.

證畢.

4 測試分析

4.1 性能比較

本節(jié)我們對本文方案與文獻(xiàn)[11]進(jìn)行對比.為了使得對比更加清晰，假設(shè)本方案中存儲文件總個數(shù)為N，使用到的Bloom過濾器大小為k；文獻(xiàn)[11]中關(guān)鍵字的總個數(shù)為W，模糊關(guān)鍵字集合大小的最大值為M.

表1給出了2個方案在效率方面的對比結(jié)果.與文獻(xiàn)[11]相比，本文方案的存儲代價與文件總個數(shù)呈線性關(guān)系，而文獻(xiàn)[11]的存儲代價與關(guān)鍵字總個數(shù)呈線性關(guān)系.從初始化時間復(fù)雜度和搜索時間復(fù)雜度上看，2個方案都有較好的效率.而對于索引生成代價，本文顯然具有更少的代價.

表2給出了2個方案在性能方面的對比分析.首先，2個方案都能進(jìn)行模糊關(guān)鍵字搜索，而文獻(xiàn)[11]在此基礎(chǔ)上還能夠進(jìn)行可驗證搜索.但本文方案支持多關(guān)鍵字搜索，而文獻(xiàn)[11]只能進(jìn)行單關(guān)鍵字搜索.

Table 1 Efficiency Analysis

Table 2 Performance Analysis

4.2 性能測試

本節(jié)主要分析各個影響因素對系統(tǒng)耗時的影響;然后針對不同的影響因素,設(shè)計測試數(shù)據(jù)進(jìn)行性能測試.該系統(tǒng)的測試指標(biāo)可分為:文件的大小、文件對應(yīng)的關(guān)鍵字個數(shù)和文件的數(shù)量.根據(jù)這3類測試指標(biāo)的劃分,設(shè)定3種測試數(shù)據(jù).第1組數(shù)據(jù)主要用于測試文件大小對該系統(tǒng)性能的影響，所以需要設(shè)定固定數(shù)量的文件和每個文件所擁有的關(guān)鍵字個數(shù)；第2組數(shù)據(jù)主要用于測試文件擁有的關(guān)鍵字個數(shù)對系統(tǒng)性能的影響,因而需要提前設(shè)定文件的數(shù)量以及文件的大小；第3組數(shù)據(jù)主要用于測試系統(tǒng)中文件的數(shù)量對其性能的影響,也要將文件的大小固定在一定區(qū)間內(nèi),而且每個文件所擁有的關(guān)鍵字個數(shù)相同.

定義完測試數(shù)據(jù)后,要在模型系統(tǒng)中測試每一組數(shù)據(jù)在系統(tǒng)中的表現(xiàn).影響系統(tǒng)耗時的主要操作分為:構(gòu)建索引以及陷門、加密索引以及陷門、搜索.所以進(jìn)行數(shù)據(jù)測試時,需要分別記錄各指標(biāo)對這些操作耗時的影響.現(xiàn)實應(yīng)用中,模型系統(tǒng)中的客戶端和服務(wù)器端分別在2臺獨立的計算機上運行,主機需要裝載Windows 7旗艦版,內(nèi)存一般為4 GB.性能測試實驗中,僅用1臺計算機模擬該系統(tǒng).記錄的結(jié)果都是每組數(shù)據(jù)10次運行后的結(jié)果的平均值.

實驗1. 測試文件的大小對系統(tǒng)耗時的影響.

按文件大小所在區(qū)間分組,將測試數(shù)據(jù)分為4類,分別記為A類文件、B類文件、C類文件、D類文件,A類文件中文件大小為1～50 KB,B類文件中文件大小為100～300 KB,C類文件中文件大小為400～500 KB,D類文件中文件的大小為1 000～2 000 KB的值.這4類文件中都包含500個文件,且每個文件都包含4個關(guān)鍵字.該模塊測試結(jié)果如圖7所示：

Fig. 7 Influence of file size圖7 文件大小的影響

從圖7可以看出,文件體積越大系統(tǒng)耗時越多.文件的大小對系統(tǒng)搜索過程幾乎沒有什么影響.

實驗2. 測試文件的數(shù)量對系統(tǒng)耗時的影響.

按照文件的數(shù)量將實驗的數(shù)據(jù)分為5組,第1組含有500個文件,第2組有1 000個文件,第3個有1 500個文件,第4組有2 000個文件,第5組有2 500個文件.每組文件集合中各文件的大小均在50～100 KB,而且每個文件所對應(yīng)的關(guān)鍵字個數(shù)都為4.執(zhí)行文件的上傳操作,整理并分析每組操作的耗時，如圖8所示:

Fig. 8 Influence of file number圖8 文件數(shù)量的影響

文件數(shù)量對加密過程和搜索過程耗時的影響如圖8所示,隨著文件數(shù)量的增多,系統(tǒng)在生成文件密文階段所耗費的時間就越多,同樣系統(tǒng)在搜索過程耗時也就越多.

實驗3. 測試單個文件所對應(yīng)的關(guān)鍵字個數(shù)對系統(tǒng)的影響.

按每個文件包含的關(guān)鍵字個數(shù)將實驗數(shù)據(jù)分為4組,第1組數(shù)據(jù)中單個文件對應(yīng)的關(guān)鍵字?jǐn)?shù)量為5,第2組數(shù)據(jù)中單個文件對應(yīng)的關(guān)鍵字?jǐn)?shù)量為10,第3組數(shù)據(jù)中單個文件對應(yīng)的關(guān)鍵字?jǐn)?shù)量為15,第4組中單個文件對應(yīng)的關(guān)鍵字?jǐn)?shù)量為20.每組數(shù)據(jù)中一共包括100個文件,其中每個文件的大小都在50～100 KB之間.該實驗結(jié)果分析如圖9所示:

Fig. 9 Influence of keyword number圖9 關(guān)鍵字個數(shù)的影響

從圖9可以看出，隨著每個文件對應(yīng)的關(guān)鍵字?jǐn)?shù)量的增多,系統(tǒng)在生成安全索引階段和搜索階段的耗時就會增多.但通過對圖中實驗結(jié)果的詳細(xì)分析可知,當(dāng)關(guān)鍵字個數(shù)由10個變?yōu)?5個時,系統(tǒng)對于搜索階段的耗時僅由175 ms增長到205 ms.所以系統(tǒng)搜索耗時的增長幅度相對于關(guān)鍵字的增長幅度來說是比較小的.因而我們說文件對應(yīng)的關(guān)鍵字個數(shù)對系統(tǒng)搜索階段耗費的時間影響是可以忽略的.

5 總 結(jié)

本文深入系統(tǒng)地研究了國內(nèi)外的可搜索加密機制,總結(jié)各方案的優(yōu)缺點,并進(jìn)一步研究了布隆過濾器以及位置敏感Hash函數(shù)等相關(guān)理論,提出面向多關(guān)鍵字的模糊密文搜索方案.

面向多關(guān)鍵字的模糊密文搜索方案使用布隆過濾器和位置敏感Hash函數(shù)技術(shù),能夠有效實現(xiàn)密文的多關(guān)鍵字的模糊搜索.利用對偶編碼函數(shù)將關(guān)鍵字轉(zhuǎn)換成向量,實現(xiàn)關(guān)鍵字的內(nèi)積運算.在安全性方面,通過攻擊性游戲,模擬用戶和服務(wù)器之間的交互,并利用參數(shù)的隨機性,證明該方法是選擇關(guān)鍵字攻擊安全的.因此,本方案具有很強的理論與實踐意義.

[1]Song D, Wagner D, Perrig A. Practical techniques for searches on encrypted data[C] //Proc 2000 IEEE Symp on Security and Privacy. Piscataway, NJ: IEEE, 2000: 44-55

[2]Chang Y C, Mitzenmacher M. Privacy preserving keyword searches on remote encrypted data[C] //Proc of Applied Cryptography and Network Security. Berlin: Springer, 2005: 442-455

[3]Dong C, Russello G, Dulay N. Shared and Searchable Encrypted Data for Untrusted Servers[M]. Berlin: Springer, 2008: 127-143

[4]Revathy B, Anbumani A, Ravishankar M. Enabling secure and efficient keyword ranked search over encrypted data in the cloud[J]. International Journal of Recent Advances in Science & Engineering, 2015, 1(1): 28-32

[5]Cao N, Wang C, Li M, et al. Privacy-preserving multi-keyword ranked search over encrypted cloud data[J]. IEEE Trans on Parallel and Distributed Systems, 2014, 25(1): 222-233

[6]Xia Zhihua, Wang Xinhui, Sun Xingming, et al. A secure and dynamic multi-keyword ranked search scheme over encrypted cloud data[J]. IEEE Trans on Parallel and Distributed Systems, 2016, 27(2): 340-352

[7]Bringer J, Chabanne H, Kindarji B. Error-tolerant searchable encryption[C] //Proc of the IEEE Int Conf on Communications. Piscataway, NJ: IEEE, 2009: 1-6

[8]Van Liesdonk P, Sedghi S, Doumen J, et al. Computationally efficient searchable symmetric encryption[C] //Proc of Secure Data Management. Berlin: Springer, 2010: 87-100

[9]Li J, Wang Q, Wang C, et al. Fuzzy keyword search over encrypted data in cloud computing[C] //Proc of the IEEE on INFOCOM. Piscataway, NJ: IEEE, 2010: 1-5

[10]Zhou Wei, Liu Lixi, Jing He, et al.K-gram based fuzzy keyword search over encrypted cloud computing[J]. Journal of Software Engineering and Applications, 2013, 6: 29-32

[11]Wang Jianfeng, Ma Hua, Tang Qiang, et al. Efficient verifiable fuzzy keyword search over encrypted data in cloud computing[J]. Computer Science and Information System, 2013, 10(2): 667-684

[12]Indyk P, Motwani R. Approximate nearest neighbors: Towards removing the curse of dimensionality[C] //Proc of the 13th Annual ACM Symp on Theory of Computing. New York: ACM, 1998: 604-613

[13]Datar M, Immorlica N, Indyk P, et al. Locality-sensitive Hashing scheme based onp-stable distributions[C] //Proc of the 12th Annual Symp on Computational Geometry. New York: ACM, 2004: 253-262

[14]Bloom B H. Space/time trade-offs in Hash coding with allowable errors[J]. Communications of the ACM, 1970, 13(7): 422-426

[15]Zhang Zhen, Dai Guanzhong, Liu Hang, et al. Safe and resumable secret key management mechanism based on database encryption[J]. Computer Measurement and Control, 2008, 16(10): 1469-1471 (in Chinese)(張貞, 戴冠中, 劉航, 等. 一種基于數(shù)據(jù)庫加密的安全可恢復(fù)密鑰管理機制[J]. 計算機測量與控制, 2008, 16(10): 1469-1471)

[16]Zhang Chuanrong, Yin Zhonghai, Xiao Guozhen. Authenticated encryption schemes without using Hash and redundancy functions[J]. Acta Electronica Sinica, 2006, 34(5): 874-877(in Chinese)(張串絨, 尹忠海, 肖國鎮(zhèn). 不使用Hash和Redundancy函數(shù)的認(rèn)證加密方案[J]. 電子學(xué)報, 2006, 34(5): 874-877)

Wang Kaixuan, born in 1992. Master in Software College, Northeastern University. Her main research interest is searchable encryption.

Li Yuxi, born in 1990. PhD candidate. Her main research interest is secure cloud storage (eliyuxi@gmail.com).

Zhou Fucai, born in 1964. PhD, professor and PhD supervisor. Senior member of CCF. His main research interests include cryptography and network security, trusted computing, and critical technology in electronic commerence.

Wang Quanqi, born in 1992. Master. His main research interest is mobile computing (wqq_7622@126.com).

Multi-Keyword Fuzzy Search over Encrypted Data

Wang Kaixuan, Li Yuxi, Zhou Fucai, and Wang Quanqi

(SoftwareCollege,NortheasternUniversity,Shenyang110819)

Cloud computing is one of the most important and promising technologies. Data owners can outsource their sensitive data in a cloud and retrieve them whenever and wherever they want. But for protecting data privacy, sensitive data have to be encrypted before storing, which abandons traditional data utilization based on plaintext keyword search. Around the multi-keyword fuzzy matching and data security protection problems, we propose a multi-keyword fuzzy search method on the encrypted data. Based on the Bloom filter, our scheme uses dual coding function and the position sensitive Hash function to build file index. In the meantime, it uses the distance recoverable encryption arithmetic to encrypt the file index, consequently achieving the function which is facing the multi-keyword to fuzzy search over the encrypted data. Meanwhile, the scheme does not need to set index storage space in advance, which greatly reduces the complexity of the search. Compared with the existing solutions, the scheme does not need predefined dictionary library which lowers the storage overhead in consequence. Experimental analysis and security analysis show that the proposed scheme not only achieves the multi-keyword fuzzy search over the encrypted data, and guarantees the confidentiality and privacy.

cloud storage; Bloom filter (BF); searchable encryption; position sensitive Hash function; multi-keyword fuzzy search

2015-12-21；

2016-10-10

國家科技重大專項基金項目(2013ZX03002006);遼寧省科技攻關(guān)項目(2013217004);中央高校基本科研業(yè)務(wù)費專項資金(N130317002);沈陽市科技基金項目(F14-231-1-08) This work was supported by the Major National Science and Technology Program (2013ZX03002006), the Liaoning Province Science and Technology Project (2013217004), the Fundamental Research Funds for the Central Universities (N130317002), and the Shenyang Science and Technology Project (F14-231-1-08).

周福才(fczhou@mail.neu.edu.cn)

TP309.2