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

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

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

0 引言

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

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

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

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

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

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

1 預(yù)備知識

1.1 雙線性映射

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

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 選擇關(guān)鍵詞攻擊IND-CKA安全模型

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

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

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

階段2 攻擊者A向挑戰(zhàn)者C適應(yīng)性地選擇除w'0、w'1外的其余關(guān)鍵詞的密文索引，挑戰(zhàn)者C按照階段1中的方式進(jìn)行回應(yīng)。

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

2 系統(tǒng)模型及索引結(jié)構(gòu)

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

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

圖1 系統(tǒng)模型示意圖Fig.1 Schematic diagram of system model

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

2.2 關(guān)鍵詞索引結(jié)構(gòu)

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

表1 關(guān)鍵詞索引結(jié)構(gòu)Tab.1 Index structure of keywords

3 方案的構(gòu)造

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

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

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

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

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

5) 密文搜索算法Search(T，I，h″):中心服務(wù)器(CS) 執(zhí)行該算法，輸入陷門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) 發(fā)送給存儲服務(wù)器 S1，S2，…，SN。

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

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

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

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

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

c)更新后關(guān)鍵詞索引:(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)假設(shè):由g生成的循環(huán)群為G且階為 p，對于 a，b，c ∈ Z*p，給定(ga，gb，gab) 和(ga，gb，gc)，則DDHP問題為判斷是否c=ab mod p成立。

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

定理1 假如DDHP假設(shè)成立，那么攻擊者不可能選擇關(guān)鍵詞攻擊成功該系統(tǒng)，因此方案是IND-CKA安全的。

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

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

階段1 攻擊者A向挑戰(zhàn)者C詢問關(guān)鍵詞列表Wi={w'1，w'2，…，w'd}的密文索引，而后挑戰(zhàn)者C將Wi加密后發(fā)送給A。具體加密方式:挑戰(zhàn)者C隨機(jī)選擇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))。

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

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

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

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

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

4.2 效率分析

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

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

5 結(jié)語

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