曹素珍,杜霞玲,王友琛,劉雪艷
(西北師范大學(xué) a.計算機(jī)科學(xué)與工程學(xué)院; b.數(shù)學(xué)與統(tǒng)計學(xué)院,蘭州730070)
云計算技術(shù)[1]在各行業(yè)中的廣泛應(yīng)用,使數(shù)據(jù)用戶更青睞于將大量數(shù)據(jù)存儲到云服務(wù)器中,在降低本地資源開銷的同時實現(xiàn)數(shù)據(jù)資源共享。但將數(shù)據(jù)直接以明文的形式交于云服務(wù)器管理面臨一定的風(fēng)險,如用戶隱私泄露、數(shù)據(jù)非法訪問、數(shù)據(jù)篡改等。為解決此類云安全問題,學(xué)者從保障數(shù)據(jù)機(jī)密性、完整性和可用性方面出發(fā)進(jìn)行了較多研究。
文獻(xiàn)[2]提出對稱可搜索加密的概念,對加密后的數(shù)據(jù)進(jìn)行直接檢索,有效地保護(hù)了數(shù)據(jù)的機(jī)密性。考慮到用對稱密鑰加密的數(shù)據(jù)不易被多個用戶同時使用,文獻(xiàn)[3]提出支持關(guān)鍵字搜索的公鑰加密方案,使可搜索加密技術(shù)更切合于現(xiàn)實環(huán)境的需求。
對數(shù)據(jù)加密僅是解決云安全問題的部分手段,而對數(shù)據(jù)的訪問控制[4]則是解決云安全問題的關(guān)鍵所在。文獻(xiàn)[5]提出屬性基加密的概念,將用戶的屬性嵌套在密文或密鑰中,從而細(xì)粒度地控制用戶訪問數(shù)據(jù)的權(quán)限,有效防止數(shù)據(jù)的非法訪問。文獻(xiàn)[6]將可搜索技術(shù)與屬性基加密技術(shù)結(jié)合,提出屬性基可搜索加密方案。該方案打破了傳統(tǒng)“一對一”的通信方式,使數(shù)據(jù)的共享可以在群組之間進(jìn)行,但方案需要授權(quán)中心為用戶生成搜索憑證,造成了額外的開銷且檢索語義單一,僅支持單個關(guān)鍵字檢索。
此后,屬性基可搜索加密技術(shù)成為密碼學(xué)的研究熱點[7-8]。文獻(xiàn)[8]提出多服務(wù)器多關(guān)鍵字的可搜索加密方案,用多個服務(wù)器存儲數(shù)據(jù)及多關(guān)鍵字的搜索語義表達(dá),提高了檢索數(shù)據(jù)的效率及處理海量數(shù)據(jù)的能力。但該方案中的服務(wù)器被定義為誠實且好奇的,即云服務(wù)器除對存儲在其上的數(shù)據(jù)進(jìn)行好奇的猜測外,也可能會返回錯誤的檢索結(jié)果,缺乏對檢索結(jié)果的正確性驗證。此外,方案通過維護(hù)用戶表和文件訪問權(quán)限表來控制數(shù)據(jù)用戶訪問文件的權(quán)限,當(dāng)涉及大規(guī)模用戶或海量文件時,對表的維護(hù)增加了系統(tǒng)的開銷。由此可見,同時滿足靈活的用戶訪問控制及檢索結(jié)果驗證的可搜索加密方案是云環(huán)境數(shù)據(jù)管理的現(xiàn)實需求。
文獻(xiàn)[9-10]提出支持檢索結(jié)果驗證的屬性基可搜索加密方案,但都不能抵抗關(guān)鍵字猜測攻擊。文獻(xiàn)[11-12]提出能夠有效抵抗關(guān)鍵字猜測攻擊的屬性基可搜索方案,但不能實現(xiàn)對檢索結(jié)果的驗證。為更好地滿足用戶查詢需求,文獻(xiàn)[13]基于安全k近鄰檢索提出支持多關(guān)鍵字排序搜索的密文搜索方案。但該方案沒有考慮不同關(guān)鍵字在不同文檔中的比重,因此,對檢索結(jié)果排序的準(zhǔn)確度不高。文獻(xiàn)[14]運用詞頻和向量空間模型構(gòu)建索引存儲結(jié)構(gòu),并通過計算向量間的余弦值來比較、排序關(guān)鍵字與文檔的相關(guān)性分值,從而提高檢索準(zhǔn)確性。文獻(xiàn)[15]基于數(shù)組和鏈表實現(xiàn)了支持多關(guān)鍵字的排序的可搜索加密,文獻(xiàn)[16]則在屬性密碼體制下提出支持多關(guān)鍵排序的可搜索方案。文獻(xiàn)[17-18]基于樹的索引結(jié)構(gòu)構(gòu)造多關(guān)鍵字排序可搜索方案,雖然都提高了搜索結(jié)果排序的精確度,但未對搜索結(jié)果進(jìn)行驗證,且不支持細(xì)粒度的訪問控制。
本文在多服務(wù)器模式下利用向量空間模型和詞頻統(tǒng)計技術(shù)構(gòu)造多維B+索引存儲結(jié)構(gòu),將索引與密文分開存儲。在此基礎(chǔ)上,利用剪枝搜索策略實現(xiàn)多關(guān)鍵字的排序查找,同時使用指定服務(wù)器驗證搜索結(jié)果,以提高搜索的精確度。
對本文中用到的符號進(jìn)行說明,如表1所示。
假設(shè)G1、G2是階為素數(shù)p、q的循環(huán)群,g是群G1的生成元,雙線性映射:e:G1×G1→G2滿足以下性質(zhì):
2)非退化性:存在g∈G1,使e(g,g)≠1,其中1是G2的單位元。
3)可計算性:對于所有的P,Q∈G1,存在有效的算法計算e(P,Q)。
在向量空間模型中,文檔及用戶的查詢請求可用向量表示[19]。通過計算向量間的余弦值,可以得到文檔索引向量和查詢請求向量間的相關(guān)性分值,將其存儲在下文構(gòu)建的多維索引B+樹中,能夠進(jìn)行多關(guān)鍵字的排序查找。在TF-IDF技術(shù)中:詞頻(Term Frequency,TF)代表一個詞在文檔中出現(xiàn)的次數(shù),用于表示文檔向量;逆向文檔頻率(Inverse Document Frequency,IDF)代表一個詞在整個文檔集中的重要性,用于表示用戶的查詢請求。相關(guān)性分值計算公式如下:
(1)
其中,TFdi,wj表示關(guān)鍵字wj在文檔di中歸一化的TF值,計算公式如下:
(2)
查詢向量IDFwj計算公式如下:
(3)
其中,IDF′wj表示關(guān)鍵字的逆文檔頻率,IDF′wj=ln(1+N/Nwj),N表示總的文檔數(shù)量,Nwj表示包含關(guān)鍵字的文檔數(shù)量。
以樹作為索引存儲結(jié)構(gòu)時,檢索時間與樹的高度成正比,相比其他樹,B+樹的高度低很多,而多維的B+樹[21]相比B+樹更節(jié)約存儲空間。因此,本文采用多維B+樹作為索引存儲結(jié)構(gòu)。多維B+樹的內(nèi)部節(jié)點存儲關(guān)鍵字在文檔中的詞頻值定義如下:
node=<{Dwi,did},ID,ID[wi,did]>
其中,Dwi,did為關(guān)鍵字wi在文檔集(d1,did,…,dN)中的TFwi,did值,ID=(id1,id2,…,idN)為文檔標(biāo)識符集合,fid[wi,did]為指向孩子節(jié)點的指針。
假設(shè)關(guān)鍵字集W={w1,w2,w3}在文檔集(d1,d2,…,d12)中的詞頻分布如表2所示,其中,關(guān)鍵字w1的詞頻值取值范圍為(0.1,0.5,0.9),關(guān)鍵字w2的詞頻值取值范圍為(0.5,0.9,1.0),關(guān)鍵字w3的詞頻值取值范圍為(0.2,0.4,0.5,0.6,0.7,0.8,1.0)。
表2 關(guān)鍵字在文檔中的分值Table 2 Scores of keywords in document
本文采用自下而上的方式建立多維索引B+樹。樹的每一層存儲一個關(guān)鍵字在文檔集中的詞頻值,第1層存儲關(guān)鍵字w1的信息,以此類推hi-1層存儲關(guān)鍵字wi的信息,hi為樹的高度,如圖1所示。
圖1 多維B+樹結(jié)構(gòu)
以檢索包含關(guān)鍵字(w1,w2,w3)的前k(k=3)個文檔為例進(jìn)行說明:為存儲檢索結(jié)果,構(gòu)建一個結(jié)果列表ResultList=
2)遍歷以P1,max-1=0.5為根節(jié)點的子樹,因P1,max-1=0.5 定義1q-BDHE假設(shè)[22] 設(shè)存在階為素數(shù)p的群G,G2、g為G的生成元,有雙線性映射e:G×G→GT,隨機(jī)選取a,s,b1,b2,…,bq∈p。給定一個多元組: y={g,gs,ga,…,gaq,gaq+2,…,ga2q,?1≤j≤q: gs·bj,ga/bj,…,gaq/bj,gaq+2/bj,…,ga2q/bj, ?1≤j,k≤q,k≠j:gasbk/bj,…,gaqsbk/bj} 任何多項式時間敵手獲得y后,不存在概率多項式時間算法B,以不可忽略的優(yōu)勢判斷T的輸出是T=e(g,g)aq+1·s∈G2還是G2中的隨機(jī)元素。算法B的優(yōu)勢定義為: Pr[B(y,T∈G2)=0]| 定義2判定性雙線性(DL)假設(shè)[23] Pr[λ(g,f,h,gs,fμ,hμ+s)=1]- Pr[λ(g,f,h,gs,fμ,Q)=1]≥ε 如圖2所示,本文方案參與實體包括授權(quán)中心、存儲服務(wù)器、搜索服務(wù)器、驗證服務(wù)器、數(shù)據(jù)屬主以及數(shù)據(jù)用戶。 1)授權(quán)中心:將系統(tǒng)公共參數(shù)發(fā)送給數(shù)據(jù)屬主,為數(shù)據(jù)用戶生成屬性密鑰。 3)數(shù)據(jù)用戶:計算搜索憑證Tk1,并將其發(fā)送給存儲服務(wù)器;計算搜索憑證Tk2,并將其發(fā)送給搜索服務(wù)器。 4)存儲服務(wù)器:根據(jù)數(shù)據(jù)用戶發(fā)送的搜索憑證Tk1,完成多關(guān)鍵字的排序查找,并將檢索到的前k個結(jié)果發(fā)送給搜索服務(wù)器。 5)搜索服務(wù)器:根據(jù)數(shù)據(jù)用戶發(fā)送的搜索憑證Tk2,檢驗用戶的合法性,若合法,將包含關(guān)鍵字的前k個文檔發(fā)送給驗證服務(wù)器;否則輸出⊥。 6)驗證服務(wù)器:與搜索服務(wù)器進(jìn)行交互,驗證搜索結(jié)果是否正確,若正確將包含查詢關(guān)鍵字的前k個文檔發(fā)送給數(shù)據(jù)用戶;否則輸出⊥。 圖2 本文方案系統(tǒng)模型 本文方案中選擇明文攻擊游戲建立在判定性q-BDHE困難問題基礎(chǔ)上,挑戰(zhàn)者利用敵手解決困難問題,最終選擇明文攻擊游戲規(guī)約到困難問題的難解性,保證選擇明文攻擊的安全性。選擇明文攻擊游戲定義如下: 1)選擇明文攻擊游戲 初始化敵手提交要挑戰(zhàn)的訪問結(jié)構(gòu)(M*,ρ*)給挑戰(zhàn)者。 系統(tǒng)建立挑戰(zhàn)者運行系統(tǒng)建立算法Setup(1λ,Atts),將公共參數(shù)Params發(fā)送給敵手。 詢問階段1敵手可以在任意時間內(nèi)訪問以下預(yù)言機(jī): OSk(Atts)私鑰提取詢問:敵手向挑戰(zhàn)者詢問關(guān)于選定屬性集Atts的私鑰,挑戰(zhàn)者運行屬性密鑰生成算法,將生成屬性鑰Sk={Atts,K1,K2,Kxi}發(fā)送給敵手。 詢問階段2敵手重復(fù)詢問階段1的操作。 猜測敵手輸出對b′的猜測值。如果b′=b,則敵手猜測成功,獲得任意消息的有效密文,猜測成功的優(yōu)勢定義為AdvA=|Pr[b′=b]-1/2|。 2)選擇關(guān)鍵字攻擊游戲 本文方案選擇關(guān)鍵字攻擊游戲是建立在DL困難問題基礎(chǔ)上,挑戰(zhàn)者利用敵手解決困難問題,最終將選擇關(guān)鍵字攻擊游戲規(guī)約到DL問題的難解性上,保證選擇關(guān)鍵字攻擊的安全性。 初始化敵手提交要挑戰(zhàn)的訪問結(jié)構(gòu)(M*,ρ*)給挑戰(zhàn)者。 系統(tǒng)建立挑戰(zhàn)者運行系統(tǒng)建立算法Setup(1λ,Atts),將公共參數(shù)Params發(fā)送給敵手。 詢問階段1敵手可以在任意時間內(nèi)訪問以下預(yù)言機(jī): OSk(Atts)私鑰提取詢問:敵手向挑戰(zhàn)者詢問關(guān)于選定屬性集Atts的私鑰,挑戰(zhàn)者運行屬性密鑰生成算法,將生成屬性鑰Sk={Atts,K1,K2,Kxi}發(fā)送給敵手。 詢問階段2敵手重復(fù)詢問階段1的操作。 猜測敵手輸出對c′的猜測值。如果c′=c,敵手猜測成功,獲得任意消息的有效密文,猜測成功的優(yōu)勢定義為AdvA=|Pr[c′=c]-1/2|。 數(shù)據(jù)屬主對于文檔集D中每一個文檔di∈[1,N]隨機(jī)生成2個|n+2|×|n+2|維的可逆矩陣M1、M2和|n+2|維的二進(jìn)制向量S,其中1≤i≤N,并將SKIndex={S,M1,M2}發(fā)送給用戶。 1)數(shù)據(jù)屬主為每個文檔di∈[1,N]生成n維索引向量Ddi,j,其中向量Ddi,j的第j位表示關(guān)鍵字wi在文檔di中所占的比重。隨機(jī)選取2個向量D′di,j、D″di,j,并初始化為空。 加密階段2 3)計算λi=Mi·v,λ′i=Mi·ω,其中Mi是矩陣M的第i行,且與某一屬性唯一相關(guān)。 4)計算W0=gb(μ+s)gasH(wi),W1=gcs,B=gμ,Ai=Mide(g,g)bcμ。 6)將索引及文檔簽名信息CT=({Ci},{Sigi})發(fā)送給搜索服務(wù)器。 用戶針對同一個搜索關(guān)鍵字集W′={w1,w2,…,wn}執(zhí)行以下2個步驟: 1)首次搜索 存儲服務(wù)器收到搜索憑證Tk1后,計算數(shù)據(jù)屬主加密向量與用戶關(guān)鍵字請求向量的余弦值: τ(Ddi,jQ+η)+σ (4) 將計算結(jié)果降序排列,返回相關(guān)分?jǐn)?shù)值最高的前k個密文集C=(c′1,c′2,…,c′k)和對應(yīng)的文檔標(biāo)識符集ID=(id′1,id′2,…,id′k)給搜索服務(wù)器。 2)二次搜索 收到搜索陷門Tk2及存儲服務(wù)器返回的首次搜索結(jié)果(C,ID)后,搜索服務(wù)器執(zhí)行以下計算,完成二次搜索: (5) T1=e(W0,tok2)·ER= e(gb(μ+s)gsaH(wi),gcr)e(g,g)μatr= e(g,g)crμb+crsb+crsaH(wi)+μatr (6) e(gcs,gbrgarH(wj))e(gμ,g(bc+at)r)= e(g,g)csbr+csarH(wj)+μcrb+μatr (7) 2)驗證服務(wù)器通過式(8)驗證搜索結(jié)果是否正確,若正確,則將搜索結(jié)果發(fā)送給用戶;否則輸出⊥。 (8) 用戶本地解密階段,即(Ctop-k,Params,SKAtts)→Dtop-k/⊥。輸入用戶私鑰SKAtts,系統(tǒng)公共參數(shù)Params及可信第三方返回的前k個密文文檔Ctop-k。在本地執(zhí)行解密算法,通過計算下式完成解密: (9) Mid=Ai/Z=Mide(g,g)bcμ/e(g,g)bcμ (10) 4.1.1 索引與搜索陷門的機(jī)密性 4.1.2 搜索陷門的不可區(qū)分性 引入隨機(jī)數(shù)τ、σ擴(kuò)充請求向量Q,使生成向量Q的算法不確定。此外,用戶生成搜索憑證Tk2時,每次選取不同的隨機(jī)數(shù)r,使生成搜索憑證Tk2的算法也不確定,即使存儲服務(wù)器和搜索服務(wù)器合謀也不能推斷出搜索陷門(Tk1,Tk2)間的關(guān)聯(lián)信息。因此,本文方案具有搜索陷門的不可區(qū)分性。 定理1給定q-BDHE假設(shè),本文方案在隨機(jī)預(yù)言模型下抗選擇明文攻擊。 證明若存在多項式時間敵手A能以不可忽略的優(yōu)勢ε=AdvA攻破本文方案,則存在一個挑戰(zhàn)者C能夠利用敵手A求解出q-BDHE難題。C和A進(jìn)行如下游戲: 初始化挑戰(zhàn)者C將(p,g,G,GT,e)及q-BDHE問題的實例y發(fā)送給敵手A。A將要挑戰(zhàn)的訪問結(jié)構(gòu)(M*,ρ*)發(fā)送給C,M*是一個(l*×n*)大小的矩陣,其中,l*,n*≤q。 下面介紹如何通過隨機(jī)預(yù)言機(jī)H詢問來建立哈希列表Hlist,該列表是由挑戰(zhàn)者C持有,初始為空,當(dāng)敵手可以在任何時候進(jìn)行適應(yīng)性的詢問隨機(jī)預(yù)言機(jī)H。挑戰(zhàn)者C按如下方式回答詢問。 詢問階段敵手可以在任意多項式時間內(nèi)多次詢問以下預(yù)言機(jī): 挑戰(zhàn)敵手A向挑戰(zhàn)者C發(fā)送2個等長的明文(d1,d2),挑戰(zhàn)者C隨機(jī)選取b∈{0.1},加密消息db并進(jìn)行如下回答: 猜測敵手A輸出對b的猜測b′∈{0,1}。當(dāng)b=b′時,挑戰(zhàn)者C輸出1,表明T=e(g,g)aq+1·s;否則輸出0,表明T是G2的隨機(jī)值,挑戰(zhàn)者解決困難問題的概率計算過程如下: 當(dāng)輸出1時,T=e(g,g)aq+1·s,敵手得到了關(guān)于db的有效密文,由定義可知敵手能正確猜出結(jié)果具有不可忽略的優(yōu)勢ε,則有Pr[b≠b′|(y,T=e(g,g)aq+1·s)=0]=1/2+AdvA。 當(dāng)輸出0時,說明T是群G2中的隨機(jī)值,敵手無法獲得有關(guān)db的任何有效信息,此時的概率為Pr[b≠b′|(y,T∈G2)=0]=1/2。 因此,挑戰(zhàn)者C能成功解決判定性q-BDHE問題的概率為ε/2。證畢。 定理2給定DL假設(shè)和一個抗碰撞的安全哈希函數(shù)H。本文方案在隨機(jī)預(yù)言模型下抗關(guān)鍵字猜測攻擊。 詢問階段敵手可以在任意多項式時間內(nèi)多次詢問以下預(yù)言機(jī),進(jìn)行私鑰提取詢問和陷門值詢問。 2)索引鑰詢問OSKIndex(D):挑戰(zhàn)者C對敵手提交的文檔集D中的每一個文檔di,∈[1,N],隨機(jī)選取兩個|n+2|×|n+2|維的可逆矩陣M1、M2和|n+2|維的二進(jìn)制向量S,其中1≤i≤N,并將索引密鑰SkIndex={S,M1,M2}發(fā)送給敵手。 猜測敵手輸出猜測c′。若c′=c,挑戰(zhàn)者輸出1,則Q=gμ+s;否則輸出0,表明Q是G中的隨機(jī)數(shù)。挑戰(zhàn)者解決困難問題的概率計算過程如下: 當(dāng)輸出1時,Q=gμ+s,表明敵手得到有效的密文。由定義可知敵手能正確猜出結(jié)果具有不可忽略的優(yōu)勢ε,則有Pr[c′≠c|(g,gs,gμ,gμ+s)=1]=1/2+AdvA。 當(dāng)輸出0時,說明Q是群G中的隨機(jī)值,敵手看到得是一串與關(guān)鍵字信息無關(guān)的隨機(jī)數(shù),從而有Pr[λ(g,gs,gμ,Q=R)=1]=1/2。因此,挑戰(zhàn)者C能成功解決DL問題的概率為ε/2。證畢。 對本文方案和文獻(xiàn)[15-17]方案從訪問結(jié)構(gòu)、是否支持多關(guān)鍵字排序查找、索引存儲結(jié)構(gòu)以及是否支持檢索結(jié)果的正確性驗證等方面進(jìn)行分析,比較結(jié)果如表3所示??梢钥闯?在均支持多關(guān)鍵字排序檢索的情況下,本文方案與文獻(xiàn)[16]方案支持細(xì)粒度的訪問控制,同時,本文方案可實現(xiàn)檢索結(jié)果的正確性驗證,而在索引存儲結(jié)構(gòu)上,本文方案采用多維的B+樹,能更快速地實現(xiàn)多關(guān)鍵字的排序查找。 表3 4種方案的特點對比Table 3 Comparison of characteristic of four schemes 基于對理論數(shù)值的分析,將本文方案與文獻(xiàn)[15-17]方案進(jìn)行對比,如表4所示。其中,s代表數(shù)據(jù)用戶的屬性個數(shù),l代表訪問策略中的屬性個數(shù),E和E′分別代表表示群G和GT上的指數(shù)運算,e代表群上的對運算,H1為哈希函數(shù),|D|代表文檔的數(shù)量,|W|代表關(guān)鍵字的個數(shù)。可以看出,在密鑰生成開銷上,本文方案性能明顯優(yōu)于文獻(xiàn)[15-17]方案,在忽略離線階段的數(shù)據(jù)加密向量和關(guān)鍵字請求向量計算的情況下,其在加密、門限生成及搜索開銷上也優(yōu)于其他3種方案。 表4 4種方案的計算開銷對比Table 4 Comparison of computation overhead of four schemes 本文采用向量空間模型和TF-IDF技術(shù)構(gòu)造多維B+樹作為索引存儲結(jié)構(gòu),將索引和密文分開存儲,搜索時利用提前剪枝策略去除相關(guān)性較低的子樹,從而實現(xiàn)多關(guān)鍵字的快速排序查找,并且通過多個服務(wù)器的協(xié)作完成數(shù)據(jù)存儲、數(shù)據(jù)搜索、數(shù)據(jù)驗證等數(shù)據(jù)處理,使用戶快速得到所需數(shù)據(jù)。本文方案利用線性秘密共享技術(shù)定義訪問結(jié)構(gòu),令數(shù)據(jù)屬主將秘密值分割給不同屬性的用戶,只允許屬性滿足訪問結(jié)構(gòu)的用戶可恢復(fù)秘密值,進(jìn)而通過對接索陷門的驗證檢索到包含查詢關(guān)鍵字的文檔,實現(xiàn)搜索行為的可控性。分析結(jié)果表明,該方案可有效提高檢索性能,減小計算開銷。下一步將在無安全信道環(huán)境下實現(xiàn)基于屬性密碼體制的多關(guān)鍵字排序密文檢索。1.7 判斷性q-BDHE假設(shè)
1.8 判定性雙線性假設(shè)
2 系統(tǒng)模型及安全模型
2.1 系統(tǒng)模型
2.2 安全模型
3 方案設(shè)計
3.1 系統(tǒng)建立
3.2 密鑰生成
3.3 數(shù)據(jù)加密
3.4 搜索陷門生成
3.5 搜索
3.6 算法驗證
3.7 用戶本地解密
4 安全性分析與證明
4.1 安全性分析
4.2 安全性證明
5 效率分析
6 結(jié)束語