多服務器可驗證的屬性基多關鍵字排序檢索方案

曹素珍,杜霞玲,王友琛,劉雪艷

(西北師范大學 a.計算機科學與工程學院; b.數學與統計學院,蘭州730070)

0 概述

云計算技術[1]在各行業中的廣泛應用,使數據用戶更青睞于將大量數據存儲到云服務器中,在降低本地資源開銷的同時實現數據資源共享。但將數據直接以明文的形式交于云服務器管理面臨一定的風險,如用戶隱私泄露、數據非法訪問、數據篡改等。為解決此類云安全問題,學者從保障數據機密性、完整性和可用性方面出發進行了較多研究。

文獻[2]提出對稱可搜索加密的概念,對加密后的數據進行直接檢索,有效地保護了數據的機密性。考慮到用對稱密鑰加密的數據不易被多個用戶同時使用,文獻[3]提出支持關鍵字搜索的公鑰加密方案,使可搜索加密技術更切合于現實環境的需求。

對數據加密僅是解決云安全問題的部分手段,而對數據的訪問控制[4]則是解決云安全問題的關鍵所在。文獻[5]提出屬性基加密的概念,將用戶的屬性嵌套在密文或密鑰中,從而細粒度地控制用戶訪問數據的權限,有效防止數據的非法訪問。文獻[6]將可搜索技術與屬性基加密技術結合,提出屬性基可搜索加密方案。該方案打破了傳統“一對一”的通信方式,使數據的共享可以在群組之間進行,但方案需要授權中心為用戶生成搜索憑證,造成了額外的開銷且檢索語義單一,僅支持單個關鍵字檢索。

此后,屬性基可搜索加密技術成為密碼學的研究熱點[7-8]。文獻[8]提出多服務器多關鍵字的可搜索加密方案,用多個服務器存儲數據及多關鍵字的搜索語義表達,提高了檢索數據的效率及處理海量數據的能力。但該方案中的服務器被定義為誠實且好奇的,即云服務器除對存儲在其上的數據進行好奇的猜測外,也可能會返回錯誤的檢索結果,缺乏對檢索結果的正確性驗證。此外,方案通過維護用戶表和文件訪問權限表來控制數據用戶訪問文件的權限,當涉及大規模用戶或海量文件時,對表的維護增加了系統的開銷。由此可見,同時滿足靈活的用戶訪問控制及檢索結果驗證的可搜索加密方案是云環境數據管理的現實需求。

文獻[9-10]提出支持檢索結果驗證的屬性基可搜索加密方案,但都不能抵抗關鍵字猜測攻擊。文獻[11-12]提出能夠有效抵抗關鍵字猜測攻擊的屬性基可搜索方案,但不能實現對檢索結果的驗證。為更好地滿足用戶查詢需求,文獻[13]基于安全k近鄰檢索提出支持多關鍵字排序搜索的密文搜索方案。但該方案沒有考慮不同關鍵字在不同文檔中的比重,因此,對檢索結果排序的準確度不高。文獻[14]運用詞頻和向量空間模型構建索引存儲結構,并通過計算向量間的余弦值來比較、排序關鍵字與文檔的相關性分值,從而提高檢索準確性。文獻[15]基于數組和鏈表實現了支持多關鍵字的排序的可搜索加密,文獻[16]則在屬性密碼體制下提出支持多關鍵排序的可搜索方案。文獻[17-18]基于樹的索引結構構造多關鍵字排序可搜索方案,雖然都提高了搜索結果排序的精確度,但未對搜索結果進行驗證,且不支持細粒度的訪問控制。

本文在多服務器模式下利用向量空間模型和詞頻統計技術構造多維B+索引存儲結構,將索引與密文分開存儲。在此基礎上,利用剪枝搜索策略實現多關鍵字的排序查找,同時使用指定服務器驗證搜索結果,以提高搜索的精確度。

1 預備知識

1.1 符號說明

對本文中用到的符號進行說明,如表1所示。

1.2 雙線性映射

假設G1、G2是階為素數p、q的循環群,g是群G1的生成元,雙線性映射:e:G1×G1→G2滿足以下性質:

2)非退化性:存在g∈G1,使e(g,g)≠1,其中1是G2的單位元。

3)可計算性:對于所有的P,Q∈G1,存在有效的算法計算e(P,Q)。

1.3 向量空間模型及TF-IDF技術

在向量空間模型中,文檔及用戶的查詢請求可用向量表示[19]。通過計算向量間的余弦值,可以得到文檔索引向量和查詢請求向量間的相關性分值,將其存儲在下文構建的多維索引B+樹中,能夠進行多關鍵字的排序查找。在TF-IDF技術中:詞頻(Term Frequency,TF)代表一個詞在文檔中出現的次數,用于表示文檔向量;逆向文檔頻率(Inverse Document Frequency,IDF)代表一個詞在整個文檔集中的重要性,用于表示用戶的查詢請求。相關性分值計算公式如下:

(1)

其中,TFdi,wj表示關鍵字wj在文檔di中歸一化的TF值,計算公式如下:

(2)

查詢向量IDFwj計算公式如下:

(3)

其中,IDF′wj表示關鍵字的逆文檔頻率,IDF′wj=ln(1+N/Nwj),N表示總的文檔數量,Nwj表示包含關鍵字的文檔數量。

1.4 線性秘密共享技術

1.5 多維B+索引樹的構建

以樹作為索引存儲結構時,檢索時間與樹的高度成正比,相比其他樹,B+樹的高度低很多,而多維的B+樹[21]相比B+樹更節約存儲空間。因此,本文采用多維B+樹作為索引存儲結構。多維B+樹的內部節點存儲關鍵字在文檔中的詞頻值定義如下:

node=<{Dwi,did},ID,ID[wi,did]>

其中,Dwi,did為關鍵字wi在文檔集(d1,did,…,dN)中的TFwi,did值,ID=(id1,id2,…,idN)為文檔標識符集合,fid[wi,did]為指向孩子節點的指針。

假設關鍵字集W={w1,w2,w3}在文檔集(d1,d2,…,d12)中的詞頻分布如表2所示,其中,關鍵字w1的詞頻值取值范圍為(0.1,0.5,0.9),關鍵字w2的詞頻值取值范圍為(0.5,0.9,1.0),關鍵字w3的詞頻值取值范圍為(0.2,0.4,0.5,0.6,0.7,0.8,1.0)。

表2 關鍵字在文檔中的分值Table 2 Scores of keywords in document

本文采用自下而上的方式建立多維索引B+樹。樹的每一層存儲一個關鍵字在文檔集中的詞頻值,第1層存儲關鍵字w1的信息,以此類推hi-1層存儲關鍵字wi的信息,hi為樹的高度,如圖1所示。

圖1 多維B+樹結構

1.6 基于多維索引B+樹的檢索

以檢索包含關鍵字(w1,w2,w3)的前k(k=3)個文檔為例進行說明:為存儲檢索結果,構建一個結果列表ResultList=,其中,Cor是通過式(1)計算得到的用戶查詢向量與文檔fid的相關性分值,num是文檔個數,初值為0。

2)遍歷以P1,max-1=0.5為根節點的子樹,因P1,max-1=0.5

1.7 判斷性q-BDHE假設

定義1q-BDHE假設[22]

設存在階為素數p的群G,G2、g為G的生成元,有雙線性映射e:G×G→GT,隨機選取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,以不可忽略的優勢判斷T的輸出是T=e(g,g)aq+1·s∈G2還是G2中的隨機元素。算法B的優勢定義為:

Pr[B(y,T∈G2)=0]|

1.8 判定性雙線性假設

定義2判定性雙線性(DL)假設[23]

Pr[λ(g,f,h,gs,fμ,hμ+s)=1]-

Pr[λ(g,f,h,gs,fμ,Q)=1]≥ε

2 系統模型及安全模型

2.1 系統模型

如圖2所示,本文方案參與實體包括授權中心、存儲服務器、搜索服務器、驗證服務器、數據屬主以及數據用戶。

1)授權中心:將系統公共參數發送給數據屬主,為數據用戶生成屬性密鑰。

3)數據用戶:計算搜索憑證Tk1,并將其發送給存儲服務器;計算搜索憑證Tk2,并將其發送給搜索服務器。

4)存儲服務器:根據數據用戶發送的搜索憑證Tk1,完成多關鍵字的排序查找,并將檢索到的前k個結果發送給搜索服務器。

5)搜索服務器:根據數據用戶發送的搜索憑證Tk2,檢驗用戶的合法性,若合法,將包含關鍵字的前k個文檔發送給驗證服務器;否則輸出⊥。

6)驗證服務器:與搜索服務器進行交互,驗證搜索結果是否正確,若正確將包含查詢關鍵字的前k個文檔發送給數據用戶;否則輸出⊥。

圖2 本文方案系統模型

2.2 安全模型

本文方案中選擇明文攻擊游戲建立在判定性q-BDHE困難問題基礎上,挑戰者利用敵手解決困難問題,最終選擇明文攻擊游戲規約到困難問題的難解性,保證選擇明文攻擊的安全性。選擇明文攻擊游戲定義如下:

1)選擇明文攻擊游戲

初始化敵手提交要挑戰的訪問結構(M*,ρ*)給挑戰者。

系統建立挑戰者運行系統建立算法Setup(1λ,Atts),將公共參數Params發送給敵手。

詢問階段1敵手可以在任意時間內訪問以下預言機:

OSk(Atts)私鑰提取詢問:敵手向挑戰者詢問關于選定屬性集Atts的私鑰,挑戰者運行屬性密鑰生成算法,將生成屬性鑰Sk={Atts,K1,K2,Kxi}發送給敵手。

詢問階段2敵手重復詢問階段1的操作。

猜測敵手輸出對b′的猜測值。如果b′=b,則敵手猜測成功,獲得任意消息的有效密文,猜測成功的優勢定義為AdvA=|Pr[b′=b]-1/2|。

2)選擇關鍵字攻擊游戲

本文方案選擇關鍵字攻擊游戲是建立在DL困難問題基礎上,挑戰者利用敵手解決困難問題,最終將選擇關鍵字攻擊游戲規約到DL問題的難解性上,保證選擇關鍵字攻擊的安全性。

初始化敵手提交要挑戰的訪問結構(M*,ρ*)給挑戰者。

系統建立挑戰者運行系統建立算法Setup(1λ,Atts),將公共參數Params發送給敵手。

詢問階段1敵手可以在任意時間內訪問以下預言機:

OSk(Atts)私鑰提取詢問:敵手向挑戰者詢問關于選定屬性集Atts的私鑰,挑戰者運行屬性密鑰生成算法,將生成屬性鑰Sk={Atts,K1,K2,Kxi}發送給敵手。

詢問階段2敵手重復詢問階段1的操作。

猜測敵手輸出對c′的猜測值。如果c′=c,敵手猜測成功,獲得任意消息的有效密文,猜測成功的優勢定義為AdvA=|Pr[c′=c]-1/2|。

3 方案設計

3.1 系統建立

3.2 密鑰生成

數據屬主對于文檔集D中每一個文檔di∈[1,N]隨機生成2個|n+2|×|n+2|維的可逆矩陣M1、M2和|n+2|維的二進制向量S,其中1≤i≤N,并將SKIndex={S,M1,M2}發送給用戶。

3.3 數據加密

1)數據屬主為每個文檔di∈[1,N]生成n維索引向量Ddi,j,其中向量Ddi,j的第j位表示關鍵字wi在文檔di中所占的比重。隨機選取2個向量D′di,j、D″di,j,并初始化為空。

加密階段2

3)計算λi=Mi·v,λ′i=Mi·ω,其中Mi是矩陣M的第i行,且與某一屬性唯一相關。

4)計算W0=gb(μ+s)gasH(wi),W1=gcs,B=gμ,Ai=Mide(g,g)bcμ。

6)將索引及文檔簽名信息CT=({Ci},{Sigi})發送給搜索服務器。

3.4 搜索陷門生成

用戶針對同一個搜索關鍵字集W′={w1,w2,…,wn}執行以下2個步驟:

3.5 搜索

1)首次搜索

存儲服務器收到搜索憑證Tk1后,計算數據屬主加密向量與用戶關鍵字請求向量的余弦值:

τ(Ddi,jQ+η)+σ

(4)

將計算結果降序排列,返回相關分數值最高的前k個密文集C=(c′1,c′2,…,c′k)和對應的文檔標識符集ID=(id′1,id′2,…,id′k)給搜索服務器。

2)二次搜索

收到搜索陷門Tk2及存儲服務器返回的首次搜索結果(C,ID)后,搜索服務器執行以下計算,完成二次搜索:

(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)

3.6 算法驗證

2)驗證服務器通過式(8)驗證搜索結果是否正確,若正確,則將搜索結果發送給用戶;否則輸出⊥。

(8)

3.7 用戶本地解密

用戶本地解密階段,即(Ctop-k,Params,SKAtts)→Dtop-k/⊥。輸入用戶私鑰SKAtts,系統公共參數Params及可信第三方返回的前k個密文文檔Ctop-k。在本地執行解密算法,通過計算下式完成解密:

(9)

Mid=Ai/Z=Mide(g,g)bcμ/e(g,g)bcμ

(10)

4 安全性分析與證明

4.1 安全性分析

4.1.1 索引與搜索陷門的機密性

4.1.2 搜索陷門的不可區分性

引入隨機數τ、σ擴充請求向量Q,使生成向量Q的算法不確定。此外,用戶生成搜索憑證Tk2時,每次選取不同的隨機數r,使生成搜索憑證Tk2的算法也不確定,即使存儲服務器和搜索服務器合謀也不能推斷出搜索陷門(Tk1,Tk2)間的關聯信息。因此,本文方案具有搜索陷門的不可區分性。

4.2 安全性證明

定理1給定q-BDHE假設,本文方案在隨機預言模型下抗選擇明文攻擊。

證明若存在多項式時間敵手A能以不可忽略的優勢ε=AdvA攻破本文方案,則存在一個挑戰者C能夠利用敵手A求解出q-BDHE難題。C和A進行如下游戲:

初始化挑戰者C將(p,g,G,GT,e)及q-BDHE問題的實例y發送給敵手A。A將要挑戰的訪問結構(M*,ρ*)發送給C,M*是一個(l*×n*)大小的矩陣,其中,l*,n*≤q。

下面介紹如何通過隨機預言機H詢問來建立哈希列表Hlist,該列表是由挑戰者C持有,初始為空,當敵手可以在任何時候進行適應性的詢問隨機預言機H。挑戰者C按如下方式回答詢問。

詢問階段敵手可以在任意多項式時間內多次詢問以下預言機:

挑戰敵手A向挑戰者C發送2個等長的明文(d1,d2),挑戰者C隨機選取b∈{0.1},加密消息db并進行如下回答:

猜測敵手A輸出對b的猜測b′∈{0,1}。當b=b′時,挑戰者C輸出1,表明T=e(g,g)aq+1·s;否則輸出0,表明T是G2的隨機值,挑戰者解決困難問題的概率計算過程如下:

當輸出1時,T=e(g,g)aq+1·s,敵手得到了關于db的有效密文,由定義可知敵手能正確猜出結果具有不可忽略的優勢ε,則有Pr[b≠b′|(y,T=e(g,g)aq+1·s)=0]=1/2+AdvA。

當輸出0時,說明T是群G2中的隨機值,敵手無法獲得有關db的任何有效信息,此時的概率為Pr[b≠b′|(y,T∈G2)=0]=1/2。

因此,挑戰者C能成功解決判定性q-BDHE問題的概率為ε/2。證畢。

定理2給定DL假設和一個抗碰撞的安全哈希函數H。本文方案在隨機預言模型下抗關鍵字猜測攻擊。

詢問階段敵手可以在任意多項式時間內多次詢問以下預言機,進行私鑰提取詢問和陷門值詢問。

2)索引鑰詢問OSKIndex(D):挑戰者C對敵手提交的文檔集D中的每一個文檔di,∈[1,N],隨機選取兩個|n+2|×|n+2|維的可逆矩陣M1、M2和|n+2|維的二進制向量S,其中1≤i≤N,并將索引密鑰SkIndex={S,M1,M2}發送給敵手。

猜測敵手輸出猜測c′。若c′=c,挑戰者輸出1,則Q=gμ+s;否則輸出0,表明Q是G中的隨機數。挑戰者解決困難問題的概率計算過程如下:

當輸出1時,Q=gμ+s,表明敵手得到有效的密文。由定義可知敵手能正確猜出結果具有不可忽略的優勢ε,則有Pr[c′≠c|(g,gs,gμ,gμ+s)=1]=1/2+AdvA。

當輸出0時,說明Q是群G中的隨機值,敵手看到得是一串與關鍵字信息無關的隨機數,從而有Pr[λ(g,gs,gμ,Q=R)=1]=1/2。因此,挑戰者C能成功解決DL問題的概率為ε/2。證畢。

5 效率分析

對本文方案和文獻[15-17]方案從訪問結構、是否支持多關鍵字排序查找、索引存儲結構以及是否支持檢索結果的正確性驗證等方面進行分析,比較結果如表3所示。可以看出,在均支持多關鍵字排序檢索的情況下,本文方案與文獻[16]方案支持細粒度的訪問控制,同時,本文方案可實現檢索結果的正確性驗證,而在索引存儲結構上,本文方案采用多維的B+樹,能更快速地實現多關鍵字的排序查找。

表3 4種方案的特點對比Table 3 Comparison of characteristic of four schemes

基于對理論數值的分析,將本文方案與文獻[15-17]方案進行對比,如表4所示。其中,s代表數據用戶的屬性個數,l代表訪問策略中的屬性個數,E和E′分別代表表示群G和GT上的指數運算,e代表群上的對運算,H1為哈希函數,|D|代表文檔的數量,|W|代表關鍵字的個數。可以看出,在密鑰生成開銷上,本文方案性能明顯優于文獻[15-17]方案,在忽略離線階段的數據加密向量和關鍵字請求向量計算的情況下,其在加密、門限生成及搜索開銷上也優于其他3種方案。

表4 4種方案的計算開銷對比Table 4 Comparison of computation overhead of four schemes

6 結束語

本文采用向量空間模型和TF-IDF技術構造多維B+樹作為索引存儲結構,將索引和密文分開存儲,搜索時利用提前剪枝策略去除相關性較低的子樹,從而實現多關鍵字的快速排序查找,并且通過多個服務器的協作完成數據存儲、數據搜索、數據驗證等數據處理,使用戶快速得到所需數據。本文方案利用線性秘密共享技術定義訪問結構,令數據屬主將秘密值分割給不同屬性的用戶,只允許屬性滿足訪問結構的用戶可恢復秘密值,進而通過對接索陷門的驗證檢索到包含查詢關鍵字的文檔,實現搜索行為的可控性。分析結果表明,該方案可有效提高檢索性能,減小計算開銷。下一步將在無安全信道環境下實現基于屬性密碼體制的多關鍵字排序密文檢索。