一種高效的基于聚合索引的可搜索加密方案

劉 政，王瑾璠，齊竹云，呂幸諭,4，楊镕瑋

(1.鵬城實(shí)驗(yàn)室，廣東 深圳 518055; 2.深圳大學(xué)，廣東 深圳 518061; 3.南方科技大學(xué)，廣東 深圳 518055; 4.廣州大學(xué)，廣東 廣州 510006)

0 引 言

伴隨著互聯(lián)網(wǎng)應(yīng)用的快速發(fā)展，用戶在網(wǎng)絡(luò)環(huán)境中所產(chǎn)生的數(shù)據(jù)迅猛增長(zhǎng)，云存儲(chǔ)[1]逐漸成為了一種常用的數(shù)據(jù)存儲(chǔ)方式。云存儲(chǔ)技術(shù)給用戶帶來極大的便利，而云上數(shù)據(jù)的安全卻持續(xù)面臨著威脅[2]。當(dāng)用戶的數(shù)據(jù)以明文形式存儲(chǔ)在云上時(shí)，云存儲(chǔ)提供商或黑客將很容易查看用戶數(shù)據(jù)，用戶的數(shù)據(jù)安全和隱私將無法保障。因此，云存儲(chǔ)場(chǎng)景下的數(shù)據(jù)安全和隱私保護(hù)成為近年來的熱點(diǎn)話題。作為一種可行的技術(shù)路線，云存儲(chǔ)的可搜索加密技術(shù)[3-4]是指在不解密狀態(tài)下，對(duì)云上的加密數(shù)據(jù)進(jìn)行基于關(guān)鍵詞檢索的方法?？伤阉骷用芗夹g(shù)的引入，使得用戶可以更好地保護(hù)數(shù)據(jù)安全及隱私，同時(shí)云存儲(chǔ)服務(wù)商依然可以提供相關(guān)云計(jì)算服務(wù)。

不同于以往的“先解密，后檢索”的密文查詢方式，面向云存儲(chǔ)的可搜索加密的檢索過程是將搜索關(guān)鍵詞加密后發(fā)送至云端，在云端完成搜索過程后，將包含加密關(guān)鍵詞的文件返回到客戶端。在整個(gè)加密搜索過程中，用戶的數(shù)據(jù)全程處于加密狀態(tài)，用戶的檢索關(guān)鍵字也被加密保護(hù)，因此用戶的數(shù)據(jù)安全和隱私得到了保障。

1 相關(guān)工作

可搜索加密技術(shù)最早是由Song等人[5]在2000年提出，最初的可搜索加密方案不僅無法證明其安全性而且檢索性能與數(shù)據(jù)庫(kù)內(nèi)數(shù)據(jù)規(guī)模線性相關(guān)。后續(xù)經(jīng)過眾多學(xué)者的深入研究，使得可搜索加密模型不斷發(fā)展和完善。2003年，Goh等人[6]提出了利用布隆過濾器對(duì)每一個(gè)文件做一個(gè)索引，之后通過多重哈希函數(shù)將單個(gè)文件中的關(guān)鍵詞映射到較短的比特?cái)?shù)組。相比較之前的方案，這種方法查詢速度快，但是卻引入了查詢時(shí)誤判率。并且當(dāng)文件更新數(shù)據(jù)內(nèi)容時(shí)索引更新代價(jià)較大，因此主要適用于靜態(tài)文件可搜索加密方案上。之后，Chang等[7]又提出了“數(shù)據(jù)字典”的設(shè)計(jì)以滿足對(duì)文件內(nèi)關(guān)鍵詞的精確查找。2006年，Curtmola等[8]基于對(duì)數(shù)據(jù)大量檢索后的狀態(tài)分析提出了著名的反向索引(Inverted Index)結(jié)構(gòu)。前期的可搜索加密研究工作主要聚焦于靜態(tài)文件的可搜索加密，但是實(shí)際的應(yīng)用環(huán)境中對(duì)于文件的修改、增加和刪除等操作都是十分常見。因此，2012年Kamara[9]提出了動(dòng)態(tài)可搜索加密方案，該方案支持關(guān)鍵詞與文件的在線增加或刪除。考慮到動(dòng)態(tài)可搜索加密方案的性能，Kamara等[10]又在原有工作的基礎(chǔ)上采用了紅黑樹數(shù)據(jù)結(jié)構(gòu)優(yōu)化查詢速度。之后，2014年Hahn等[11]提出了新的可搜索加密方案，這種方案初始化時(shí)只構(gòu)建基礎(chǔ)的數(shù)據(jù)字典，后續(xù)伴隨著更新和查詢不斷地更新可搜索密文結(jié)構(gòu)。同時(shí)，Emil[12]和Cash[13]等都提出了各自的動(dòng)態(tài)可搜索加密方案。

在其他方面，Damiani等[14-15]將可搜索加密技術(shù)應(yīng)用與數(shù)據(jù)庫(kù)上，Li等[16-18]針對(duì)模糊語句的可搜索加密查詢做了進(jìn)一步的研究。Nepolean等[19-20]又在可搜索加密方案上實(shí)現(xiàn)了多關(guān)鍵詞排列查詢和多維范圍查詢。Fu等[21-22]又提出了一種有效解決同義詞查詢的多關(guān)鍵詞排序搜索問題。Xia等[23]針對(duì)文件動(dòng)態(tài)增刪做出改進(jìn)，提出了一個(gè)可以動(dòng)態(tài)進(jìn)行文件增刪的多關(guān)鍵詞查詢檢索方案。

在上述研究的基礎(chǔ)上，該文提出了一種基于聚合索引的云存儲(chǔ)可搜索加密方案。該方案具有以下特點(diǎn)：

(1)動(dòng)態(tài)性：支持文件的在線添加或者刪除；

(2)高效性：即使在方案初始化階段或者搜索最壞的情況下仍能保持著較好的查詢效率；

(3)安全性：該方案在更新時(shí)僅透露一個(gè)查找集合。

引入了聚合索引提升關(guān)鍵詞的查詢效率，通過使用聚合索引可以將單個(gè)文件的多個(gè)關(guān)鍵詞通過聚合函數(shù)累加在一起形成聚合索引值，后續(xù)按照文件-聚合索引值存儲(chǔ)形成一個(gè)新的索引表。新的索引表可以在查找過程中快速地定位到查詢關(guān)鍵詞所在的文件位置，大量減少關(guān)鍵詞的比對(duì)次數(shù)，提升查詢效率。在云存儲(chǔ)實(shí)際業(yè)務(wù)場(chǎng)景的運(yùn)用中，該方案具有明顯優(yōu)勢(shì)。

2 基本方案

可搜索加密技術(shù)按照不同的使用場(chǎng)景可能有多種定義和模型，該文的主要研究?jī)?nèi)容是基于對(duì)稱可搜索加密模型進(jìn)行的。一個(gè)常見的對(duì)稱可搜索加密模型定義如下：

2.1 系統(tǒng)模型

在傳統(tǒng)的對(duì)稱可搜索加密方案中，參與者可抽象為數(shù)據(jù)擁有者、用戶和云存儲(chǔ)提供商，操作流程如下：

(1)數(shù)據(jù)加密上傳階段：數(shù)據(jù)擁有者在本地使用對(duì)稱加密方式對(duì)明文數(shù)據(jù)進(jìn)行加密，將加密后的數(shù)據(jù)上傳至云端服務(wù)器。

(2)生成檢索陷門階段：用戶使用密鑰和關(guān)鍵字生成對(duì)應(yīng)的檢索陷門，并將該陷門發(fā)送給云端服務(wù)器。

(3)密文檢索階段：基于收到的關(guān)鍵字檢索陷門，云端服務(wù)器在密文數(shù)據(jù)庫(kù)上對(duì)密文進(jìn)行檢索，并將滿足檢索條件的密文發(fā)送給用戶。

(4)密文解密階段：用戶從云端獲得返回的密文后，使用密鑰解密密文。

可搜索加密技術(shù)可以分為對(duì)稱可搜索加密方案和非對(duì)稱可搜索加密方案，對(duì)稱可搜索加密方案[1]具有計(jì)算量小、算法簡(jiǎn)單、計(jì)算速度快等優(yōu)點(diǎn)。相對(duì)而言，基于公鑰密碼體制的非對(duì)稱可搜索加密方案[24-25]則無需事先建立安全信道即可實(shí)現(xiàn)用戶在公共網(wǎng)絡(luò)中的保密通信和安全檢索，但加密性能較低。考慮到云存儲(chǔ)可搜索加密的實(shí)際應(yīng)用情況，文中的研究工作主要圍繞對(duì)稱可搜索加密方案展開。

2.2 符號(hào)與定義

方案定義：一個(gè)安全的基于索引的動(dòng)態(tài)可搜索加密方案包含的算法具體如下：SUISE=(Gen,Enc,SearchToken,Search,AddToken,Add,Delete,Dec)

(K,γ,σ)←Gen(1λ):一個(gè)概率算法，輸入安全參數(shù)λ，輸出密鑰K，搜索索引γ和空的搜索歷史σ。

c←Enc(K,f):一個(gè)概率算法，輸入密鑰K和文件集合f，輸出加密后的文件集合c。

(σ',τw)←SearchToken(K,w,σ):一個(gè)概率算法，輸入密鑰K，關(guān)鍵詞w和搜索歷史σ，輸出更新后的搜索歷史σ'和搜索憑證τw。

(Iw,γ')←Search(τw,γ):一個(gè)確定算法，輸入搜索憑證τw，文件密文集合C和搜索索引γ，輸出文件標(biāo)志符集合Iw和更新后的搜索索引γ'。

τa←AddToken(K,f,σ):一個(gè)概率算法，輸入密鑰K,文件f和搜索歷史σ，輸出添加憑證τa。

(C',γ')←Add(τa,c,C,γ):一個(gè)確定算法，輸入一個(gè)添加憑證τa,一個(gè)加密文件c，加密文件集合C和搜索索引γ，輸出更新后的密文集合C'和更新后的搜索索引γ'。

(C',γ')←Delete(ID(f),C,γ):一個(gè)確定算法，輸入一個(gè)文件標(biāo)志符ID(f)，加密文件集合C和搜索索引γ，輸出更新后的密文集合C'和更新后的搜索索引γ'。

f←Dec(K,c):一個(gè)確定算法，輸入密鑰K和一個(gè)文件密文c，輸出解密后的文件f。

3 基于聚合索引的可搜索加密方案

在本章節(jié)，將從采用的數(shù)據(jù)結(jié)構(gòu)、索引信息和具體算法三個(gè)部分詳細(xì)闡述基于聚合索引的可搜索加密方案。

3.1 使用數(shù)據(jù)結(jié)構(gòu)

在本方案中，構(gòu)建索引表的過程中采用的數(shù)據(jù)結(jié)構(gòu)有鏈表和哈希表。對(duì)于鏈表L，使用len(L)來表示列表的實(shí)際存儲(chǔ)的元素個(gè)數(shù)，x∈L表示列表中包含x元素，位置在i的元素表示為L(zhǎng)(i)。對(duì)于哈希表Map，其存儲(chǔ)結(jié)構(gòu)是k-v形式的鍵值對(duì)，而存儲(chǔ)在Map鍵值為k的元素表示為Map[k]=v，v可能是一個(gè)元素，也有可能是一個(gè)鏈表。

3.2 索引信息

新方案采用了三個(gè)索引表來支持服務(wù)端的查詢功能，三個(gè)索引表分別是數(shù)據(jù)字典、反向索引和聚合索引表。

數(shù)據(jù)字典γf用于記錄每個(gè)文件存儲(chǔ)的具體的關(guān)鍵詞信息或者關(guān)鍵詞加密后的信息。設(shè)初始情況下文件集合為f=(f1,f2,…,flen(f))，設(shè)fi的關(guān)鍵詞為fi=(wi1,wi2,…,wilen(fi))，對(duì)應(yīng)的關(guān)鍵詞密文集合為ci=(ci1,ci2,…,cilen(ci))，文件標(biāo)識(shí)符為ID(fi)。以文件標(biāo)識(shí)符的關(guān)鍵詞作為哈希的鍵值，將文件內(nèi)關(guān)鍵詞密文集合經(jīng)過哈希運(yùn)算后以鏈表形式存儲(chǔ)在數(shù)據(jù)字典中。

反向索引表γw用于記錄重復(fù)搜索關(guān)鍵詞所對(duì)應(yīng)的文件集合，對(duì)于每一個(gè)已經(jīng)搜索過的關(guān)鍵詞，可以通過查詢?chǔ)脀提升對(duì)重復(fù)關(guān)鍵詞的查找效率。

最后，在本方案中引入了新的聚合索引表γc來優(yōu)化查詢性能，具體過程為在數(shù)據(jù)字典的基礎(chǔ)上對(duì)于每一個(gè)文件所有的密文關(guān)鍵詞利用質(zhì)數(shù)哈希函數(shù)生成唯一的大質(zhì)數(shù)，并且將單個(gè)文件中生成的所有質(zhì)數(shù)累乘后以文件ID為鍵保存在哈希鏈表γc中。在后續(xù)檢索過程中，通過使用質(zhì)數(shù)哈希函數(shù)將關(guān)鍵詞哈希成質(zhì)數(shù)，再通過聚合索引表γc快速判斷關(guān)鍵詞是否在文件中。

證明：假設(shè)質(zhì)數(shù)w不在集合A中并且MAmodw=0，則w必定是MA的一個(gè)因數(shù)，而w又是一個(gè)質(zhì)數(shù)，因此w必定是MA的一個(gè)質(zhì)因數(shù)。假設(shè)中質(zhì)數(shù)w不在集合A中，與假設(shè)矛盾，因此w一定不在集合A中。

聚合索引原理：

(2)對(duì)于新的查詢關(guān)鍵詞w，其搜索陷門為τw。令Pw=H'(τw),Pw為經(jīng)過質(zhì)數(shù)哈希函數(shù)后生成的質(zhì)數(shù)；

(3)如果Pw屬于聚合索引值中的一部分，即Pw∈(p1,p2,…,pn)，則AcmodPw=0，否則AcmodPw>0。

3.3 具體算法

假設(shè)有抗不可區(qū)分選擇明文攻擊的對(duì)稱加密方案SKE={Gen,Enc,Dec},一個(gè)輸入長(zhǎng)度為λ，輸出長(zhǎng)度任意的偽隨機(jī)數(shù)生成器G，一個(gè)偽隨機(jī)函數(shù)F：{0,1}λ×{0,1}*→{0,1}λ，一個(gè)隨機(jī)數(shù)生成器H：{0,1}λ×{0,1}*→{0,1}λ，一個(gè)質(zhì)數(shù)哈希函數(shù)H′: {0,1}λ×{0,1}*→{0,1}λ。

文中構(gòu)建的方案SUISE=(Gen,Enc,SearchToken,Search,AddToken,Add,Delete,Dec)描述如下：

(1)(K,γ,σ)←Gen(1λ)。

初始化三個(gè)哈希表γf，γw，γc。生成兩個(gè)λ比特長(zhǎng)的二進(jìn)制串k1←Gen(1λ)，k2←{0,1}λ，初始化一個(gè)集合σ，返回(K,γ,σ)，其中K=(k1,k2)，γ=(γf,γw,γc)。

(2)c←Enc(K,f)。

對(duì)輸入的文件f，輸出c=SKE.Enck1(f)。

(3)(τw,σ')←SearchToken(K,w,σ)。

K=(k1,k2),對(duì)于輸入的關(guān)鍵詞w，計(jì)算w的搜索憑證，將τw=Fk1(w)添加到σ中，最后返回τw和更新后的σ'。

(4)(Iw,γ')←Search(τw,γ)。

根據(jù)采用的三個(gè)索引γ=(γw,γf,γc)，然后判斷γw中是否含有鍵值τw。

(a)如果有Iw=γw[τw]，γ'=γ。

(b)否則令ac=H'(τw)，γc中逐條記錄即γc[ID(fi)]對(duì)ac取余，判斷結(jié)果是否為0。如果取余結(jié)果為0，則對(duì)于密文集合c'=γf[ID(fi)]，其中對(duì)于每一個(gè)密文關(guān)鍵詞ci∈c'，ci=li‖ri驗(yàn)證Hτw(ri)是否和li相同，相同則將ID(fi)加入到Iw中。

(5)αf←AddToken(K,f,σ)。

對(duì)于給定的K=(k1,k2),f是一個(gè)包含了文件中唯一關(guān)鍵詞的集合，即f?f'，f'=(w1,w2,…,wlen(f))。使用偽隨機(jī)函數(shù)G生成一系列偽隨機(jī)值s1,s2,…,slen(f)，同時(shí)生成一個(gè)空的列表x和一個(gè)初始化為1的數(shù)字index，對(duì)于每一個(gè)wi∈f'進(jìn)行如下操作：

(a)計(jì)算wi對(duì)應(yīng)的搜索陷門，即τwi=Fk1(wi)；

(b)如果τwi在之前檢索歷史集合σ中，則將τwi加入到x中；

(c)令ci=Hτwi(si)‖si；

(d)index=index*H'(τw)。

最后添加γc[ID(f)]=index,對(duì)集合c'=(c1,c2,…,clen(f))按照字典序排序，然后返回αf=(ID(f),c',X)。

(6)(C',γ')←Add(τa,c,C,γ)。

(7)(C',γ')←Delete(ID(f),C,γ):

給定γ=(γw,γf,γc)

(a)對(duì)于存儲(chǔ)在γw的每一條鏈表記錄e,如果ID(f)∈e,則從e中移除ID(f)對(duì)應(yīng)的記錄節(jié)點(diǎn)；

(b)之后再?gòu)拿芪臄?shù)據(jù)庫(kù)中移除密文c，密文數(shù)據(jù)庫(kù)更新為C'；

(c)移除γf中鍵為ID(f)的鏈表并刪除鍵值；

(d)移除γc中鍵為ID(f)的記錄。

(8)f←Dec(K,c)。

對(duì)于給定的K=(k1,k2),數(shù)據(jù)輸出解密后的文件f=SKE.Deck2(c)。

4 安全性能分析

在本方案中，希望盡量降低在查詢、更新和刪除操作中泄露原有數(shù)據(jù)信息給服務(wù)端的可能性。因此，詳細(xì)地評(píng)估新方案中這些操作過程的安全性。

做出如下定義：假設(shè)有文件集合F，基于該文件集合的查詢歷史可以定義為一個(gè)二元組(F，phrase)，F(xiàn)代表查詢文件集合，phrase代表歷史查詢集合。

(1)索引表的隱私性。

為了提供高效率的查詢性能，采用了多個(gè)基于哈希鏈表的數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)相關(guān)索引信息。索引表存儲(chǔ)的信息都進(jìn)行了加密處理，這樣可以避免明文的索引泄露F及phrase的特征信息(包括文件的內(nèi)容或用戶隱私)。因此，云服務(wù)提供者或者對(duì)手在沒有獲取密鑰的情況下是無法得到索引存儲(chǔ)內(nèi)容的原有信息。

證明：假設(shè)這里有一個(gè)非統(tǒng)一對(duì)手A=(A1,A2)。k∈N，k是一個(gè)安全參數(shù)。根據(jù)k生成密鑰K，K=KeyGen(1k)。之后，A1根據(jù)密鑰參數(shù)作為輸入生成(stA,H0,H1),stA是一個(gè)根據(jù)A狀態(tài)生成的字符串。下一步，選擇β←{0,1}，令Hβ=(Fβ,phraseβ)，生成方案中的索引表集合Iβ和密文結(jié)構(gòu)Cβ。對(duì)于2≤i≤q，通過搜索陷門生成函數(shù)生成Tβ,i并作為查詢憑證。同樣的，令β'←A2(stA,Iβ,Cβ,Tβ)。

通過保證Pr[β'=β]≤1/2+negl(k),而negl(k)可以忽略不計(jì)，可以確保新方案是語義安全的。同時(shí)新方案能夠很好地保證文件關(guān)鍵詞及索引信息不會(huì)泄露給服務(wù)端，從而保護(hù)了數(shù)據(jù)安全及用戶的隱私。

(2)搜索陷門生成的安全性。

在新方案的查詢過程中，為了確保原有查詢關(guān)鍵詞不會(huì)被用戶泄露，使用了偽隨機(jī)的加密和哈希算法對(duì)原有查詢關(guān)鍵詞進(jìn)行混淆。因此，服務(wù)端無法通過基于關(guān)鍵詞生成的搜索陷門猜解原有查詢關(guān)鍵詞的內(nèi)容信息。

(3)云端存儲(chǔ)文件的安全性。

在本方案中，用戶存儲(chǔ)在云上的數(shù)據(jù)全程均處于加密狀態(tài)。文件擁有者或者得到文件擁有者授權(quán)的用戶通過密鑰對(duì)加密存儲(chǔ)的文件進(jìn)行解密而獲得明文，但密鑰的生成、分發(fā)和加密、解密過程，均不是在云上完成的。因此，云服務(wù)提供商并不掌握用戶對(duì)文件進(jìn)行加密的密鑰，無法解密用戶文件。由此可以得出結(jié)論，在本方案中，用戶的文件在云端存儲(chǔ)的過程中是安全的。

5 性能分析

5.1 空間復(fù)雜度分析

5.2 時(shí)間復(fù)雜度分析

假設(shè)m為γf中存儲(chǔ)的所有關(guān)鍵詞的總量，m'為γf中存儲(chǔ)的唯一關(guān)鍵詞總量。在本方案中，在經(jīng)過一段時(shí)間運(yùn)行后所有關(guān)鍵詞都被檢索過，此時(shí)時(shí)間復(fù)雜度經(jīng)過均攤后為O(m/m')。

考慮到數(shù)據(jù)庫(kù)所有關(guān)鍵詞都是獨(dú)一無二的情況下，新的方案相比較之前反向索引的方案，在整體方案初始化運(yùn)行情況下使單個(gè)關(guān)鍵詞的查詢時(shí)間復(fù)雜度從O(n*len(fi))降到O(n+len(fi)),其中l(wèi)en(fi)代表了單個(gè)文件平均關(guān)鍵詞的個(gè)數(shù)。

5.3 查詢時(shí)間測(cè)試

測(cè)試數(shù)據(jù)集包括50個(gè)英文文檔，從100個(gè)文檔中剔除英文標(biāo)點(diǎn)符號(hào)后用空格將單詞隔開。其中每個(gè)文件只選出前100到900個(gè)不同關(guān)鍵詞作為文件內(nèi)容。每次實(shí)驗(yàn)中對(duì)于所有文件中每個(gè)文件選出的所有關(guān)鍵詞逐個(gè)進(jìn)行檢索以確保整體方案性能的穩(wěn)定性。

實(shí)驗(yàn)環(huán)境在Intel Core i7-8565U CPU 1,99 GHz，16 GB內(nèi)存，windows10 professional系統(tǒng)環(huán)境下進(jìn)行， 開發(fā)環(huán)境為java JDK1.8，開發(fā)工具為Eclipse(版本為2019-06(4.12.0))。實(shí)驗(yàn)過程中選取了基礎(chǔ)的數(shù)據(jù)字典、反向索引和提出的聚合索引方案進(jìn)行單個(gè)關(guān)鍵詞查詢時(shí)間對(duì)比，結(jié)果如表1所示。

表1 不同方案在不同文件關(guān)鍵詞個(gè)數(shù)下的查詢時(shí)間 s

圖1 不同方案的查詢時(shí)間和文件關(guān)鍵詞個(gè)數(shù)的關(guān)系

圖1是根據(jù)單次查詢所消耗時(shí)間進(jìn)行繪制的折線圖，橫軸為給定不同的關(guān)鍵詞數(shù)量，縱軸為單次查詢所消耗的時(shí)間經(jīng)過以10為底對(duì)數(shù)運(yùn)算后的結(jié)果，不同標(biāo)注的線代表了不同的方案。

6 結(jié)束語

針對(duì)云存儲(chǔ)場(chǎng)景中的數(shù)據(jù)安全和隱私保護(hù)問題，提出了一種高效的基于聚合索引的加密搜索方案。在該方案中，查詢過程中的關(guān)鍵詞比對(duì)次數(shù)大幅度減少，查詢性能得到優(yōu)化。對(duì)該方案進(jìn)行了理論分析和實(shí)現(xiàn)，實(shí)驗(yàn)結(jié)果表明，該方案相較于現(xiàn)有方案展示出了更佳的查詢性能，同時(shí)提供了良好的動(dòng)態(tài)更新能力和安全性能。