電子郵件系統中支持關鍵字搜索的代理重加密方案

牛淑芬,陳俐霞,劉文科,王彩芬,杜小妮

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

0 概述

在電子郵件系統中,當數據發送者發給用戶的郵件因用戶的私人原因而無法及時處理時,用戶希望將該郵件共享給被委托者,并由對方幫助其處理該郵件。一般情況下,用戶先下載某個郵件,用其私鑰解密該郵件并使用被委托者的公鑰進行加密處理,最后發送給被委托者,該方式需要較大的計算代價和通信代價,而代理重加密(Proxy Re-Encryption,PRE)技術可有效解決這一問題。

1998年,BLAZE等人[1]提出PRE的概念,主要內容是委托者通過一個半可信的代理者將密文授權給被委托者,且在這個過程中,代理者得不到消息的任何信息。文獻[2]提出一個單向的PRE方案,但是該方案只能達到選擇明文安全的要求,文獻[3]提出第一個滿足IND-CCA2的雙向PRE方案。文獻[4]在文獻[5]的基礎上,改進了方案的安全模型,并構造一個安全的IND-CCA2單向的PRE方案。文獻[6]提出多跳PRE方案,同年,文獻[7]提出電子病歷中帶關鍵字搜索的公鑰加密方案。為解決復雜證書問題和密鑰管理問題,文獻[8]提出新的基于證書條件的PRE方案。文獻[9]構造管理云端數據訪問授權確定性更新的PRE方案。為解決云端數據共享問題,文獻[10]提出標準模型下CPA安全的格上PRE方案。

隨著電子郵件服務器上數據的增加,為了實現密文搜索和數據共享2個功能,文獻[11]提出帶關鍵字搜索的PRE的概念,且構造在隨機預言模型下可證明安全的PRES方案,但文獻[12]指出文獻[11]存在使用了一次性強不可偽造簽名來保證方案安全性的限制。文獻[13]構造出有效且不使用一次性強不可偽造簽名的PRE方案,并證明該方案可使選擇密文安全。為提高方案的效率,文獻[14]依據文獻[11,15]構造出只對部分文件的密文進行重加密的方案模型。為抵抗由不可信服務器執行的關鍵字猜測攻擊,文獻[16]提出新的支持關鍵字搜索的加密方案,文獻[17]提出基于關鍵字搜索屬性的PRE方案。

現有的支持關鍵字搜索的PRE方案存在一些問題需要解決,如抵抗關鍵字猜測攻擊和數據篡改等。在文獻[18-19]中,驗證等式的信息都是公開信息或對方發送的信息,易遭受篡改攻擊。針對這一問題,本文提出在加密電子郵件背景下支持關鍵字搜索的PRE方案。在該方案中,服務器、郵箱網關與被委托者的驗證方式均不同,并且其采用更加高效的對稱加密方式,以提高搜索效率和解密效率。

1 基礎知識

1.1 雙線性對

令(G1,+)和(G2,×)是階為素數p、q的循環群,雙線性映射e:G1×G1→G2滿足以下性質:

2)非退化性:存在P,Q∈G1,滿足e(P,Q)≠1。

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

1.2 相關的困難問題

1)判定Diffie-Hellman(Decisional Diffie-Hellman,DDH)問題。

2)雙線性判定Diffie-Hellman(Decisional Bilinear Diffie-Hellman,DBDH)問題。

3)商判定Bilinear Diffie-Hellman(Quotient Decisional Bilinear Diffie-Hellman,QDBDH)問題。

2 方案模型和安全模型

2.1 方案摸型

本節提出面向電子郵件高效支持關鍵字搜索的PRE方案。本方案實現了密文授權和密文搜索的功能,具體如下:郵件發送者將已加密的郵件發送給用戶i,而用戶i希望將該郵件授權給用戶j處理,便由加密郵箱服務器作為代理者對密文進行重加密,將郵箱網關搜索重加密郵件密文,并發送給用戶j解密。該方案包括如下算法:

1)Setup(I):輸入安全參數Il,輸出系統參數Params。

2)KeyGen(Params):輸入系統參數Params,輸出用戶和加密郵箱服務器S的公私鑰對。

3)ReKeyGen(Xi,Xj):輸入用戶i的私鑰Xi和用戶j的私鑰Xj,加密郵箱服務器S生成重加密密鑰RKi→j。

4)Enc(Yi,YS,w,m):輸入用戶i的公鑰Yi、加密郵箱服務器S的公鑰YS、關鍵字w和明文m∈{0,1}*,輸出基于用戶i公鑰的密文CTi。

5)ReEnc(CTi,Yi,XS):輸入基于用戶i公鑰的密文CTi、用戶i的公鑰Yi、加密郵箱服務器S的私鑰XS、重加密密鑰RKi→j,加密郵箱服務器S輸出基于用戶j公鑰的密文CTj。

6)Trapdoor(Xj,Ys,w,CTj):輸入用戶j的私鑰Xj、加密郵箱服務器S的公鑰YS、基于用戶j公鑰的密文CTj和關鍵字w,用戶j生成陷門T。

7)Test(CTj,T):輸入基于公鑰的密文CTj和關鍵字陷門T,郵件網關通過算法Test(CTj,T)驗證陷門與密文是否匹配。若陷門與密文相匹配,郵件網關發送基于用戶j公鑰的密文給用戶j,否則,郵箱網關輸出⊥。

8)Dec(CTj):輸入密文CTj和私鑰Xj,用戶j輸出明文m。

2.2 安全模型

在標準模型下,本文方案滿足關鍵字密文隱私安全和陷門隱私安全[20-22]。

2.2.1 關鍵字密文隱私安全

為滿足關鍵字密文的不可區分性,本文方案考慮敵手Ai(i=1,2)和挑戰者B之間的2個游戲。

游戲1該游戲的目的是證明密文的不可區分性。在游戲中,本文方案假設敵手A1是惡意的郵箱服務器。

系統建立挑戰者B產生公共參數并將其給敵手A1。

詢問階段1敵手A1進行如下詢問:

1)公鑰預言詢問OYi(i):挑戰者B模擬算法KeyGen產生公私鑰對(Yi,Xi)并將公鑰Yi公開;敵手A1模擬算法KeyGen產生它的公私鑰對(Yj,Xj)并將公鑰Yj公開。

2)重加密密鑰詢問階段ORK(Xi,Xj):挑戰者B模擬ReKeyGen算法產生重加密密鑰RKi→j并輸出給敵手A1。

3)重加密預言階段ORe(Yi,Yj,CTi):挑戰者B模擬重加密算法生成基于被委托者公鑰的密文CTj并將其發送給敵手A1。

4)陷門預言階段OT(w,Xj):敵手進行詢問,挑戰者B則回應相對應的陷門。

5)解密預言階段ODec(Yi,CTj):挑戰者B輸出Dec(CTj)給敵手A1。

挑戰當詢問階段1完畢,敵手A1選擇2個明文(m0,m1)發送給挑戰者B。挑戰者B隨機選取δ∈{0,1},并設置嵌入困難問題的挑戰密文發送給敵手A1。

詢問階段2除了不能詢問挑戰密文及其衍生外,其他詢問同詢問階段1一致。

游戲2該游戲的目的是證明關鍵字的不可區分性。在游戲中,本文方案假設敵手A2是外部攻擊者,在游戲中,挑戰者B和敵手A2進行如下交互:

系統建立挑戰者B產生公共參數并將其給敵手A2。

詢問階段1重復游戲1中的詢問階段1。

挑戰當詢問階段1結束,敵手A2選擇2個關鍵字(w1,w2)、明文m和公鑰Y*一起發送給挑戰者B。挑戰者B隨機選擇δ∈{0,1},并設置嵌入困難問題的挑戰密文發送給敵手A2。

詢問階段2敵手A2進行詢問時,除了不能詢問挑戰密文及其衍生外,其他詢問同詢問階段1一致。

2.2.2 陷門隱私安全

為了抵抗關鍵字猜測攻擊,文獻[12]引入了陷門不可區分性。

游戲3假設敵手A3是外部攻擊者,在游戲中,挑戰者B和敵手A3進行如下交互:

系統建立挑戰者B產生公共參數并公開。

詢問階段1敵手A3對關鍵字w進行陷門詢問,挑戰者B回應陷門。

挑戰階段敵手A3選擇2個關鍵字(w1,w2)、明文m和公鑰Y*一起發送給挑戰者B。挑戰者B隨機選取δ∈{0,1},并計算陷門發送給敵手A3。

詢問階段2除了不能詢問挑戰關鍵字及其衍生外,其他詢問同詢問階段1一致。

3 方案設計

3.1 方案構造

本文提出的方案包括8個部分,具體設計如下:

4)Enc(Yi,YS,w,m):輸入用戶i的公鑰Yi、加密郵箱服務器S的公鑰YS、關鍵字w和明文m∈{0,1}*,用戶i進行如下操作:

(4)輸出基于用戶i公鑰的密文CTi=(t,A,B,C,D,D1,E,F,G)。

5)ReEnc(CTi,Yi,XS):輸入密文CTi、用戶i的公鑰Yi、加密郵件服務器S的私鑰XS和重加密密鑰RKi→j,郵件服務器S計算h=H1(A,C,E),并驗證式(1)是否成立:

(1)

7)Test(CTj,T):輸入基于用戶j公鑰的密文CTj=(t,A,B′,C,D,D1,E,F,G)和關鍵字w的陷門T,加密郵件網關驗證式(2)是否成立:

e(B′,T)=D1

(2)

若式(2)成立,用加密郵件網關將基于用戶j公鑰的密文CTj發送給用戶j;否則輸出⊥。

8)Dec(CTj):輸入密文CTj,用戶j計算h=H1(A,C,E),并驗證式(3)是否成立:

(3)

若式(3)成立,用戶j通過式(4)計算對稱密鑰K′,則明文m=DecK′(C);否則輸出⊥。

(4)

3.2 正確性證明

本文方案滿足正確性。在重加密過程中,郵件服務器驗證式(1)是為了證明密文CTi在傳輸過程中并沒有被篡改。在搜索過程中,加密郵件網關通過驗證式(2)來實現關鍵字與密文之間的匹配。在解密過程中,用戶j通過式(3)驗證重加密密文是否被篡改,通過式(4)解密密文。驗證過程如下:

因此本文方案是正確的。

4 安全性證明

4.1 關鍵字密文隱私安全

定理1假設解決QDBDH和DBDH問題困難,本文方案在標準模型下可證明IND-CCA和IND-CKA是安全的。

引理1假設解決QDBDH問題困難,本文方案在標準模型下可證明IND-CCA是安全的。

系統建立挑戰者B選取隨機數a0,a1,a2,a3,b1,b2,b3,計算系統參數g2=Ma0,h=Mb,u=ga1Nb1,v=ga2Nb2,d=ga3Nb3。

詢問階段1敵手A1進行如下詢問:

2)重加密密鑰詢問階段ORK(Xi,Xj):從列表Llist中調用三元組(Yi,Xi,ci),并查詢Xi和Xj是否存在三元組中,若不存在,則調用公鑰預言詢問OYi(i),否則進行如下操作:

(3)否則,挑戰者B輸出⊥。

3)陷門預言階段OT(w,Xj):挑戰者B從列表Llist中調用三元組(Yi,Xi,ci)并查詢Xj是否存在三元組中,若不存在,則調用公鑰預言詢問OYi(i),否則進行如下操作:

4)重加密預言階段ORE(Yi,Yj,CTi):若式(1)驗證失敗,則挑戰者B輸出⊥;否則挑戰者B從列表Llist中恢復三元組(Yi,Xi,ci)并執行如下操作:

(1)若ci和cj均為1或均為0,則挑戰者B調用重加密密鑰詢問ORK(Xi,Xj),生成重加密密鑰RKi→j,然后將ReEnc(CTi,RKi→j)返回給敵手A1。

(5)

(3)若ci=1∧cj=0,則意味著用戶i的私鑰為aXi和用戶j的私鑰為Xj,挑戰者B計算B′=gaXjr=(Mr)Xj=AaXj。

5)解密預言階段ODec(Yi,CTj):挑戰者B從列表Llist中恢復三元組(Yi,Xi,ci)并執行如下操作:

(2)若cj=1,則用戶j的私鑰為Xj,挑戰者B將輸出Dec(CTj)給敵手。

詢問階段2敵手A1進行詢問,除了挑戰密文及其衍生不能詢問外,其他與詢問階段1一致。

猜測最后敵手返回猜測δ′,如果δ′=δ,則挑戰成功,輸出1;否則輸出0。

引理2假設解決DBDH問題困難。本文方案在標準模型下可證明IND-CKA是安全的。

系統建立挑戰者B隨機選取數a0,a1,a2,a3,b1,b2,b3,計算系統參數g2=Ma0,h=Mb,u=ga1Nb1,v=ga2Nb2,d=ga3Nb3。

詢問階段1敵手A2進行如下詢問:

5)解密預言階段ODec(Yi,CTj):挑戰者B輸出Dec(CTj)給敵手A2。

詢問階段2敵手A2進行詢問,除了挑戰密文及其衍生不能詢問外,其他同詢問階段1一致。

猜測敵手返回猜測δ′,若δ′=δ,則挑戰成功,輸出1;否則輸出0。

4.2 陷門隱私安全

定理2假設解決DDH問題困難。本文方案可證明在陷門上是安全的。

系統建立挑戰者B選取隨機數a0、a1、a2、a3、b1、b2、b3、并計算系統參數g2=Ma0,h=Mb。

詢問階段1敵手A3進行如下詢問:

2)陷門預言階段OT(w,Xj):挑戰者B從列表Llist中調用三元組(Yi,Xi,ci)并查詢Xj是否存在三元組中,若不存在,則調用公鑰預言詢問OYi(i),否則進行如下操作:

詢問階段2敵手A3進行詢問,除了不能詢問挑戰關鍵字及其衍生外,其他同詢問階段1一致。

猜測敵手A3返回猜測δ′,若δ′=δ,則挑戰成功,輸出1;否則輸出0。

5 效率分析

通過理論和數值實驗對dPRES[18]方案和本文方案進行分析。首先從理論上對計算開銷進行分析,dPRES方案和本文方案效率比較結果見表1,其中Tp、TF、Th、Te、Teo分別為雙線性運算、偽隨機函數族運算、哈希運算、指數運算和異或運算的計算代價。

表1 dPRES方案與本文方案的效率比較

由表1可知,在搜索階段,本文方案比dPRES方案少一個指數運算和兩個哈希運算。此外,在解密階段,本文方案比dPRES方案少一個雙線性對運算。因此,與dPRES方案相比,本文方案在計算效率上有較大的提高。

為了更直觀地顯示結果,本節從數值分析上對方案的計算成本進行了模擬。在Linux系統上使用PBC庫,基于C語言編程實現dPRES方案和本方案。數值環境配置參數如表2所示。

表2 環境配置參數

本文方案和dPRES方案均能實現密文授權和搜索功能。在數值實驗中,加密和解密階段兩方案均加密相同數量的關鍵字,隨著關鍵字數量的變化,統計在不同數量關鍵字下的加密時間,結果如圖1所示。

圖1 關鍵字數量對加密時間的影響

由圖1可知,在加密階段,本文方案的時間開銷較dPRES方案高。搜索階段是統計搜索不同數量關鍵字的時間開銷,如圖2所示。

圖2 關鍵字數量對搜索時間的影響

由圖2可知,在搜索階段,當關鍵字數量為10個時,本文方案的時間開銷為42 ms,而dPRES方案的時間開銷為164.4 ms;當關鍵字數量為30個時,本文方案的時間開銷為122.4 ms,而dPRES方案的時間開銷為456.2 ms;當關鍵字數量為50個時,本文方案的時間開銷為198.9 ms,而dPRES方案的時間開銷為762.2 ms。隨著關鍵字數量的增加,dPRES方案的時間開銷增長速率比本文方案大,說明本文方案的搜索效率優于dPRES方案。

統計在不同數量關鍵字下的解密開銷時間,如圖3所示。

圖3 關鍵字數量對解密時間的影響

由圖3可以看出,在解密階段,隨著關鍵字數量的增大,本文方案的時間開銷幾乎保持不變;當關鍵字數量為10個時,dPRES方案的時間開銷為85.7 ms;當關鍵字數量為30個時,dPRES方案的時間開銷為236.5 ms;當關鍵字數量為50個時,dPRES方案的時間開銷為390.8 ms,說明dPRES方案的時間開銷與關鍵字數量之間呈線性增長。因此,本文方案的解密效率優于dPRES方案。

由圖1～圖3可知,雖然在加密階段,本文方案的時間開銷較dPRES方案高,但是在搜索階段,本文方案時間開銷遠遠小于dPRES方案,且在解密階段,本文方案時間開銷也低于dPRES方案。因此,本文方案在解密算法和搜索算法的計算代價上有明顯優勢,減少了電子郵箱服務器和用戶之間的通信代價,提高了系統的性能。

6 結束語

為解決密文授權和密文搜索問題,本文提出一種面向電子郵件支持高效關鍵字搜索的PRE方案。該方案在搜索過程中只用了一個雙線性對,因此搜索效率較高。同時,本文方案在標準模型下關鍵字隱私、密文隱私和陷門隱私是安全的,還可以抵抗篡改攻擊和關鍵字猜測攻擊。分析結果表明,相對dPRES方案,本文方案在搜索效率上有較大的提升。目前,支持關鍵字搜索的PRE方案還有一些問題需要解決,如進一步減少時間開銷,提高方案的計算效率和通信效率等,這將是下一步的研究方向。