支持用戶撤銷的可驗證密文檢索方案

白 平，張 薇，李 聰， 王緒安

(1.武警工程大學密碼工程學院，西安710086; 2.網絡與信息安全武警部隊重點實驗室，西安710086)(*通信作者電子郵箱bp15771937011@163.com)

0 引言

隨著云計算技術［1］快速發展，越來越多用戶傾向于將個人隱私數據存儲在云端，以便減少用戶的本地計算和維護開銷。然而，用戶在享受云端帶來高效快捷服務的同時，如何才能保證這些隱私數據不被竊取或者破壞也成為人們關注的問題?，F如今，對于外包的隱私數據主要是通過各類加密［2－4］手段進行保障，在一定程度上可以達到保護隱私數據的目的。然而，在保護了數據機密性的同時，卻引發出另一個問題，即用戶如何能準確無誤地對這些外包的密文數據進行檢索呢?由于云端上儲存的數據是密文數據，故用戶無法按照傳統的檢索方法進行檢索，即服務器在明文上進行搜索操作。此外，假如我們將所有密文數據重新下載到本地解密后進行檢索查詢，固然可以實現安全檢索，但這樣會極大地增加用戶開銷，同時也削弱了外包的價值。因此，尋找一種能夠在不可信的云環境下實現密文安全精確的檢索成為人們亟待解決的問題。

基于上述提出的問題，Boneh等［5］最早提出基于關鍵詞的公鑰搜索(Public Key Encryption with Keyword Search，PEKS)算法，并在Boneh和Franklin設計的IBE(Identity-Based Encryption)加密方案——BF-IBE加密方案的基礎上構造了第1個基于公鑰的可搜索加密方案，隨后不同功能的搜索加密方案［6－9］應運而生。這些方案從構造模型上大體可以分為以下四類:單用戶單關鍵詞模型、單用戶多關鍵詞模型、多用戶單關鍵詞模型，以及多用戶多關鍵詞模型，它們均不同程度地存在一些缺陷。例如，文獻［10］提出的基于混合結構可實現單關鍵詞精確檢索的可搜索加密系統，優點在于能夠實現對密文的精確檢索，但方案中用戶關鍵詞信息對于外部服務器是公開透明的，從而極大降低了用戶數據的安全系數。為了增強用戶數據的安全性，Golle等［11］在單關鍵詞基礎上進行改進優化，提出了多關鍵詞的構想。文獻［12］首次提出非結構化文本的多關鍵詞可搜索加密方案，相比單關鍵詞的方案而言，優點在于無需事先指定關鍵詞的位置，每次搜索遍歷所有關鍵詞，但這樣帶來的后果是延長搜索時間，影響檢索效率。

為了保證用戶數據的安全性和隱私性，同時使外包數據的利用率達到最大化，本文主要進行如下的工作:

1)提出了一種多服務器多關鍵詞方案，用戶可以將數據分別存儲在不同的云服務器，有效防止了單個云服務器的某些惡意行為，提高了用戶隱私數據的安全性。此外，多關鍵詞的設定縮短了用戶搜索時間，提高了檢索效率。

2)提供了一種可驗證返回結果是否具有完整性的算法，實現對云服務器返回結果的有效驗證，提高了檢索準確率。

3)通過重加密方法實現了用戶撤銷，從而靈活地控制了用戶對密文的訪問權限，防止授權用戶的非法操作，有效解決云端共享數據的安全問題。

1 預備知識

1.1 雙線性映射

G、GT是兩個階為p的循環群，g為生成元，則雙線性映射e:G×G→GT滿足下列性質:

1)雙線性性:對任意 r，s∈ G 和 a，b∈ Zp，都有e(ra，sb)=e(r，s)ab。

2) 非退化性:存在 r，s∈ G，使得 e(r，s) ≠1。

3)可計算性:存在有效的多項式算法對任意r，s∈GT，都可以計算出e(r，s)。

1.2 選擇關鍵詞攻擊IND-CKA安全模型

初始化 設定安全參數為k，運用初始化算法Setup(k)生成密鑰s'并將其發給挑戰者C;同時，將生成的參數h'發給攻擊者A。

階段1 攻擊者A不斷對關鍵詞W*={w1，w2，…，wn}進行詢問，挑戰者C自適應地選擇多項式個關鍵詞密文索引Ii(i=1，2，…，n)。

挑戰 攻擊者A隨機選擇兩個關鍵詞w'0、w'1發送給挑戰者C，要求這兩個關鍵詞w'0、w'1在階段1中未向挑戰者C查詢過。C隨機選取一個比特值b∈{0，1}，計算密文索引Ib發送給攻擊者A。

階段2 攻擊者A向挑戰者C適應性地選擇除w'0、w'1外的其余關鍵詞的密文索引，挑戰者C按照階段1中的方式進行回應。

猜測 攻擊者A輸出猜測結果，如果b=b'，則A攻擊成功。A贏得游戲的概率定義為 AdvA(k)=|Pr［bA=b'］－1/2|。

2 系統模型及索引結構

2.1 支持用戶撤銷的可驗證密文檢索方案的系統模型

本文的系統模型主要由五部分組成:授權用戶(Authorized Users，AU)、密鑰授權中心(Key Authorized Center，KAC)、中心服務器(Central Server，CS)、審計服務器(Audit Server，AS)和存儲服務器 S1，S2，…，SN。授權用戶(AU)是數據的實際操作者，主要擔負兩項任務:一是加密文檔后上傳至存儲服務器S1，S2，…，SN;二是加密關鍵詞索引后上傳至中心服務器，同時負責和密鑰授權中心和審計服務器的交互。密鑰授權中心(KAC)負責為授權用戶生成密鑰以及上傳密鑰至中心服務器。中心服務器(CS)負責存儲用戶密文文檔和關鍵詞索引結構。審計服務器(AS)負責驗證搜索結果的完整性。存儲S1，S2，…，SN負責存儲密文文檔和中心服務器重加密后的密文索引。支持用戶撤銷的可驗證密文檢索方案的系統模型如圖1所示。

圖1 系統模型示意圖Fig.1 Schematic diagram of system model

通過圖1可以看出，本文方案的中心服務器不要求必須是誠實可信的。假如中心服務器返回的檢索結果是錯誤或者偽造的，授權用戶是可以通過和審計服務器的交互成功識別這些錯誤反饋。此外，對于授權用戶也不要求必須始終是誠實可信的，當授權用戶完成其任務后，可以通過用戶撤銷機制刪除該授權用戶的檢索權限，從而防止其進行一些惡意的操作行為。

2.2 關鍵詞索引結構

假設有m個授權用戶具有訪問權限，即AU={v1，v2，…，vm}，被加密上傳到中心服務器(CS)的密文文檔有n個，即Files={f1，f2，…，fn}，取文檔Files中的一部分作為其關鍵詞信息，即 W={w1，w2，…，wd}。為了更精確地實現密文檢索，需要創建關鍵詞的索引結構，具體過程如下:首先、關鍵詞被上傳到中心服務器之前，授權用戶會對這些關鍵詞進行簽名及加密以形成關鍵詞的索引I;其次，授權用戶將索引I上傳給中心服務器(CS)，CS對這些索引再進行一次加密操作;最后，為這些最新生成的文件關鍵詞索引創建索引結構，如表1所示，并發送給存儲服務器S1，S2，…，SN進行存儲。這樣就完成了對用戶文檔、關鍵詞的加密保護，同時，也為將來實現精確檢察外包密文文檔打下基礎，云服務器可以通過表1中關鍵詞進行檢索查詢，從而找出用戶想要檢索的文檔。

表1 關鍵詞索引結構Tab.1 Index structure of keywords

3 方案的構造

云環境下支持多服務器多關鍵詞的可驗證密文檢索及用戶撤銷方案主要包括以下8個算法。

1)初始化算法Setup(k):選擇一個完全可信的授權用戶執行該算法，輸入安全參數k，輸出一個由g生成階為p的循環群G，隨機選取兩個密鑰s，s'∈，計算 h=gs，h'=gs－s';并選取防碰撞的哈希函數H1:{0，1}*→，H2:{0，1}*→和分組加密算法AES(·)的對稱密鑰K，此密鑰僅被可信授權用戶所擁有。公開參數 params=(G，g，H1，H2，h)，用戶私鑰 sk=(K，s，s')。

2)密鑰生成算法KeyGen(AU，r):授權用戶(AU)執行該算法，隨機選取參數r，計算gr，h″=(h')r和hr，并將h″發送給中心服務器(CS)作為其私鑰SKCS=h″。

3)加密算法Encrypt(K，ID，D，W):授權用戶執行該算法，輸入密鑰 s和 s'，身份標識列表 ID={id1，id2，…，idn} ∈G，文檔D、分組密鑰K及其關鍵詞列表W={w1，w2，…，wd}，對關鍵詞進行簽名 δi=［H1(wi)idi］s，加密關鍵詞為E(wi)=gr(s'+δi)，其中1 ≤i≤n。令索引為I=(gr，hr，E(w1)，E(w2)，…，E(wn))。將索引I和加密后的文檔關鍵詞索引結構發送給中心服務器，中心服務器接收到索引I后，隨即用其擁有的私鑰 SKCS=h″再一次對關鍵詞進行如下計算:E'(w1) =gr(s'+δi)·h″=(h·gδi)r，E'(w2) =gr(s'+δ2)·h″=(h·gδ2)r，…，E'(wn) =gr(s'+δn)·h″=(h·gδn)r，并更新索引為 I'=(gr，hr，E'(w1)，E'(w2)，…，E'(wn))，將表 1 中原有對 應 的 關 鍵 詞 用 {H2［E'(w1)］，H2［E'(w2)］，…，H2［E'(wn)］}進行替換;將新文檔關鍵詞索引結構發送給存儲服務器 S1，S2，…，SN;最后，運用分組加密算法 AES(·)加密文檔D，即C=AESK(D)。

4) 陷門生成算法 GenerateTrapdoor(s，s'，t″，w'1，w'2，…，w'd):授權用戶執行該算法，生成陷門的主要作用是允許任意一個授權用戶均可以對密文文檔進行搜索，輸入密鑰s，s'和需要檢索的關鍵詞 w'1，w'2，…，w'd，隨機選擇參數 t″∈，計算 Y = (gr)t″。對每個關鍵詞 w'i，計算 Ti= t″+［H1(w'i)idi］s+s'，其中 1 ≤ i≤ d，將陷門 T=(T1，T2，…，Td，Y)發送給中心服務器。

5) 密文搜索算法Search(T，I，h″):中心服務器(CS) 執行該算法，輸入陷門T=(T1，T2，…，Td，Y)，索引I和私鑰SKCS=h″，計算(gr)TI·h″/Y=(gr［t″+［H1(w'i)idi)］s+s'］·(gs－s')r)/(gr)t″=(h·gδ'i)r，其中 δ'i= ［H1(w'i)idi］s，再計算 H'i=H2［(h·gδ'i)r］，其中1 ≤ i≤ d，將 I″=(H'1，H'2，…，H'd) 發送給存儲服務器 S1，S2，…，SN。

接下來存儲服務器S1，S2，…，SN開始進行匹配檢索，具體過程是將I″=(H'1，H'2，…，H'd)中計算所得的哈希值與關鍵詞索引結構中(見表1)中每個id(fi)中所包含的關鍵詞的哈希值H2［E'(wi)］進行比較。如果匹配成功，則表明搜索成功，中心服務器把相關密文C'(C'表示通過密文搜索算法搜索到的密文)發送給審計服務器;否則，重新進行搜索操作。

6) 驗證算法 Verify({id1，id2，…，ids}，C'):審計服務器(AS)執行該算法，為了驗證返回結果的正確性，審計服務器首先生成隨機數 z1，z2，…zs∈，然后把{(τ，zτ)|1 ≤ τ ≤s}發給中心服務器。中心服務器得到挑戰信息(τ，zτ)后，計，并把回復信息{π，ID'={idr，1≤τ≤s}} 發給審計服務器(AS)，最后 AS通過驗證等式 e(π，g) =來進行判斷。假如驗證等式成立，則發送C'給授權用戶;否則，重新進行搜索匹配。

7)用戶撤銷算法UserRevocation(SK'CS):授權中心(KAC)執行該算法，當授權用戶完成其任務后，為了防止授權用戶的某些惡意行為，系統會將其系統權限收回。此時，授權中心(KAC)會選擇新的隨機值，通過安全途徑發送給其他合法的用戶。隨后合法授權用戶將向中心服務器請求重加密操作以便可以正常解密，同時更新中心服務器私鑰為SK'CS=(h″)a，具體步驟如下:

a) 生成新的簽名 γi= ［H1(wi)idi］as，E(wi) =gar(s'+γi)，其中1≤ i≤n。

b)中心服務器通過更新的私鑰 SK'CS=(h″)a，計算E'(wi) =gar(s'+γi)·(h″)a=(h·gγi)ar，其中 1 ≤ i≤ n。

c)更新后關鍵詞索引:(gar)Ti·SK'CS/(gar)t″={gar(t″+［H1(w'i)idi］as+s')·(gs－s')ar}/(gar)t″=(h·gγi)ar。

8)解密算法Decrypt(K，C'):輸入分組密鑰K和通過驗證算法的密文 C'，對于任意的 fi∈ C'，計算 fi=DecK(AESK(fi))。

4 方案的分析

4.1 安全性分析

定義1 判定Diffe-Hellman問題(Decisional Diffe-Hellman Problem，DDHP)假設:由g生成的循環群為G且階為 p，對于 a，b，c ∈ Z*p，給定(ga，gb，gab) 和(ga，gb，gc)，則DDHP問題為判斷是否c=ab mod p成立。

定義2 多項式函數μ(x):N→R，如果對于任何一個正多項式 poly(n)，有一個自然數 c，使得對于所有 G，有μ(x) ＜1/poly(x)，則稱函數μ是可忽略的，記為negl(x)。

定理1 假如DDHP假設成立，那么攻擊者不可能選擇關鍵詞攻擊成功該系統，因此方案是IND-CKA安全的。

證明 如果攻擊者A能夠以不可忽略的概率ε贏得游戲IND-CPA，則挑戰者C能以不可忽略的概率ε解決DDHP問題，具體過程如下:

初始化 設定參數h1=ga，h2=gb，h3=gc，隨機選取參數t∈{0，1}k和哈希函數H(x):{0，1}*→;令h=h1=ga，公開參數為 params=(G，g，p，H，h)。

階段1 攻擊者A向挑戰者C詢問關鍵詞列表Wi={w'1，w'2，…，w'd}的密文索引，而后挑戰者C將Wi加密后發送給A。具體加密方式:挑戰者C隨機選擇r∈，計算 gr和hr，對于任意的 w'i，計算 δ'i= ［H(w'i)idi］s，E(w'n) =gr(s'+δ'n)·h″=(h·gδ'n)r，輸出 I'=(gr，hr，E(w'1)，E(w'2)，…，E(w'n))。

挑戰 攻擊者A隨機選擇兩個關鍵詞w'0、w'1發送給挑戰者C，要求這兩個關鍵詞w'0、w'1未向挑戰者C查詢過。挑戰者C隨機選擇b∈{0，1}，計算δ'b=［H(w'b)idb］s，同時隨機選擇 r'∈，計算 E(w'b)=(h3·)r'，輸出密文索引Ib=(，E(w'b)) 并返回給 A。

階段2 挑戰者A向攻擊者C查詢除了w'0、w'1其余關鍵詞的密文索引。

猜測 攻擊者A輸出密文索引Ib中對b的猜測bA∈{0，1}。如果bA=b，則稱A攻擊成功，此時攻擊者C回答DDHP挑戰中c=ab，否則C回答c≠ab。

若敵手A想要贏得游戲，必定存在c=ab，則w'b的關鍵詞索引密文 Ib=(，，(h3·hδ'b2)) =(gbr'，gabr'，(gabr'·gδ'b)) =(gbr'，hbr'，(h·gδ'b)br') 是一個正確的關鍵詞密文;若A無法贏得游戲，必定存在c≠ab，則Ib不是一個正確關鍵詞列表的密文。綜上所述，如果A能夠贏得游戲，則挑戰者C就能夠以不可忽略概率解決DDHP挑戰。故本文滿足IND-CKA安全。

此外，方案使用哈希函數和用戶私鑰s來共同對關鍵詞進行簽名，運用隨機參數r和私鑰s'完成對關鍵詞的加密，故關鍵詞的安全性取決于私鑰s、s'和參數r，敵手只有同時獲取這三個參數，才能解密得到完整的關鍵詞信息。此外，關于數據完整性的驗證，由于挑戰信息{(τ，zτ)|1≤τ≤s}是審計服務器隨機產生的，如果服務器返回錯誤的結果，則無法通過等式的驗證，因此惡意云服務器是無法偽造檢索結果來通過審計服務器的驗證的。

4.2 效率分析

表2中:n表示用戶文檔數目，m表示文檔中關鍵詞數量，ω表示用戶檢索的關鍵詞數目，ξ表示授權用戶的數目;pr表示雙線性運算，exp表示指數運算。下面分別從關鍵詞加密運算量、搜索運算量、是否支持多用戶、是否支持多服務器、是否支持對搜索結果驗證以及是否支持授權用戶撤銷等方面與文獻［13－15］方案展開比較。由于雙線性運算的時間消耗要遠高于指數運算，從表2可以看到，本文方案對關鍵詞的加密只要(m+ξ+4)次指數運算，其余運算均由服務器來完成，故效率要高于其他方案。本文方案中可以提供多關鍵詞的檢索，因此檢索的準確率要高于其他方案。另外，本文方案可以支持多用戶和多服務器模型，可以極大提高檢索效率;同時，可以對檢索的結果提供有效的驗證，對于已經完成檢索任務的授權用戶可以對他們的檢索權限進行撤銷，從而極大地提高了用戶數據的安全性。

表2 不同方案效率對比Tab.2 Efficiency comparison of different schemes

5 結語

針對云環境中數據檢索過程中所存在的偽造查詢結果和密鑰信息泄露問題，提出支持用戶撤銷的可驗證密文檢索方案，可以通過運用多個關鍵詞對用戶外包的密文數據進行精確檢索查詢，并能夠對最終檢索結果的完整性進行有效驗證，有效防止了惡意服務器的不誠實操作。此外，該方案通過用戶撤銷機制可以防止不誠實授權用戶的某些非法操作，從而保護了隱私數據的安全性。在下一步工作中，我們將嘗試改進文中方案，使其擁有更高效的檢索效率以及更靈活的搜索方式。