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

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

(1.鵬城實驗室，廣東 深圳 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ù)迅猛增長，云存儲[1]逐漸成為了一種常用的數(shù)據(jù)存儲方式。云存儲技術(shù)給用戶帶來極大的便利，而云上數(shù)據(jù)的安全卻持續(xù)面臨著威脅[2]。當(dāng)用戶的數(shù)據(jù)以明文形式存儲在云上時，云存儲提供商或黑客將很容易查看用戶數(shù)據(jù)，用戶的數(shù)據(jù)安全和隱私將無法保障。因此，云存儲場景下的數(shù)據(jù)安全和隱私保護(hù)成為近年來的熱點話題。作為一種可行的技術(shù)路線，云存儲的可搜索加密技術(shù)[3-4]是指在不解密狀態(tài)下，對云上的加密數(shù)據(jù)進(jìn)行基于關(guān)鍵詞檢索的方法。可搜索加密技術(shù)的引入，使得用戶可以更好地保護(hù)數(shù)據(jù)安全及隱私，同時云存儲服務(wù)商依然可以提供相關(guān)云計算服務(wù)。

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

1 相關(guān)工作

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

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

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

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

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

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

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

2 基本方案

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

2.1 系統(tǒng)模型

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

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

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

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

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

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

2.2 符號與定義

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

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

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

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

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

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

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

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

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

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

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

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

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

3.2 索引信息

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

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

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

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

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

聚合索引原理：

(2)對于新的查詢關(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ū)分選擇明文攻擊的對稱加密方案SKE={Gen,Enc,Dec},一個輸入長度為λ，輸出長度任意的偽隨機數(shù)生成器G，一個偽隨機函數(shù)F：{0,1}λ×{0,1}*→{0,1}λ，一個隨機數(shù)生成器H：{0,1}λ×{0,1}*→{0,1}λ，一個質(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λ)。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

最后添加γc[ID(f)]=index,對集合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)對于存儲在γw的每一條鏈表記錄e,如果ID(f)∈e,則從e中移除ID(f)對應(yīng)的記錄節(jié)點；

(b)之后再從密文數(shù)據(jù)庫中移除密文c，密文數(shù)據(jù)庫更新為C'；

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

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

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

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

4 安全性能分析

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

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

(1)索引表的隱私性。

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

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

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

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

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

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

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

5 性能分析

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

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

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

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

5.3 查詢時間測試

測試數(shù)據(jù)集包括50個英文文檔，從100個文檔中剔除英文標(biāo)點符號后用空格將單詞隔開。其中每個文件只選出前100到900個不同關(guān)鍵詞作為文件內(nèi)容。每次實驗中對于所有文件中每個文件選出的所有關(guān)鍵詞逐個進(jìn)行檢索以確保整體方案性能的穩(wě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))。實驗過程中選取了基礎(chǔ)的數(shù)據(jù)字典、反向索引和提出的聚合索引方案進(jìn)行單個關(guān)鍵詞查詢時間對比，結(jié)果如表1所示。

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

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

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

6 結(jié)束語

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