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

(西北師范大學(xué) a.計(jì)算機(jī)科學(xué)與工程學(xué)院; b.數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,蘭州 730070)

0 概述

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

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

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

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

1 基礎(chǔ)知識(shí)

1.1 雙線性對(duì)

令(G1,+)和(G2,×)是階為素?cái)?shù)p、q的循環(huán)群,雙線性映射e:G1×G1→G2滿足以下性質(zhì):

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

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

1.2 相關(guān)的困難問題

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 方案摸型

本節(jié)提出面向電子郵件高效支持關(guān)鍵字搜索的PRE方案。本方案實(shí)現(xiàn)了密文授權(quán)和密文搜索的功能,具體如下:郵件發(fā)送者將已加密的郵件發(fā)送給用戶i,而用戶i希望將該郵件授權(quán)給用戶j處理,便由加密郵箱服務(wù)器作為代理者對(duì)密文進(jìn)行重加密,將郵箱網(wǎng)關(guān)搜索重加密郵件密文,并發(fā)送給用戶j解密。該方案包括如下算法:

1)Setup(I):輸入安全參數(shù)Il,輸出系統(tǒng)參數(shù)Params。

2)KeyGen(Params):輸入系統(tǒng)參數(shù)Params,輸出用戶和加密郵箱服務(wù)器S的公私鑰對(duì)。

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

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

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

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

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

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

2.2 安全模型

在標(biāo)準(zhǔn)模型下,本文方案滿足關(guān)鍵字密文隱私安全和陷門隱私安全[20-22]。

2.2.1 關(guān)鍵字密文隱私安全

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

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

系統(tǒng)建立挑戰(zhàn)者B產(chǎn)生公共參數(shù)并將其給敵手A1。

詢問階段1敵手A1進(jìn)行如下詢問:

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

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

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

4)陷門預(yù)言階段OT(w,Xj):敵手進(jìn)行詢問,挑戰(zhàn)者B則回應(yīng)相對(duì)應(yīng)的陷門。

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

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

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

游戲2該游戲的目的是證明關(guān)鍵字的不可區(qū)分性。在游戲中,本文方案假設(shè)敵手A2是外部攻擊者,在游戲中,挑戰(zhàn)者B和敵手A2進(jìn)行如下交互:

系統(tǒng)建立挑戰(zhàn)者B產(chǎn)生公共參數(shù)并將其給敵手A2。

詢問階段1重復(fù)游戲1中的詢問階段1。

挑戰(zhàn)當(dāng)詢問階段1結(jié)束,敵手A2選擇2個(gè)關(guān)鍵字(w1,w2)、明文m和公鑰Y*一起發(fā)送給挑戰(zhàn)者B。挑戰(zhàn)者B隨機(jī)選擇δ∈{0,1},并設(shè)置嵌入困難問題的挑戰(zhàn)密文發(fā)送給敵手A2。

詢問階段2敵手A2進(jìn)行詢問時(shí),除了不能詢問挑戰(zhàn)密文及其衍生外,其他詢問同詢問階段1一致。

2.2.2 陷門隱私安全

為了抵抗關(guān)鍵字猜測攻擊,文獻(xiàn)[12]引入了陷門不可區(qū)分性。

游戲3假設(shè)敵手A3是外部攻擊者,在游戲中,挑戰(zhàn)者B和敵手A3進(jìn)行如下交互:

系統(tǒng)建立挑戰(zhàn)者B產(chǎn)生公共參數(shù)并公開。

詢問階段1敵手A3對(duì)關(guān)鍵字w進(jìn)行陷門詢問,挑戰(zhàn)者B回應(yīng)陷門。

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

詢問階段2除了不能詢問挑戰(zhàn)關(guān)鍵字及其衍生外,其他詢問同詢問階段1一致。

3 方案設(shè)計(jì)

3.1 方案構(gòu)造

本文提出的方案包括8個(gè)部分,具體設(shè)計(jì)如下:

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

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

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

(1)

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

e(B′,T)=D1

(2)

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

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

(3)

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

(4)

3.2 正確性證明

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

因此本文方案是正確的。

4 安全性證明

4.1 關(guān)鍵字密文隱私安全

定理1假設(shè)解決QDBDH和DBDH問題困難,本文方案在標(biāo)準(zhǔn)模型下可證明IND-CCA和IND-CKA是安全的。

引理1假設(shè)解決QDBDH問題困難,本文方案在標(biāo)準(zhǔn)模型下可證明IND-CCA是安全的。

系統(tǒng)建立挑戰(zhàn)者B選取隨機(jī)數(shù)a0,a1,a2,a3,b1,b2,b3,計(jì)算系統(tǒng)參數(shù)g2=Ma0,h=Mb,u=ga1Nb1,v=ga2Nb2,d=ga3Nb3。

詢問階段1敵手A1進(jìn)行如下詢問:

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

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

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

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

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

(5)

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

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

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

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

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

引理2假設(shè)解決DBDH問題困難。本文方案在標(biāo)準(zhǔn)模型下可證明IND-CKA是安全的。

系統(tǒng)建立挑戰(zhàn)者B隨機(jī)選取數(shù)a0,a1,a2,a3,b1,b2,b3,計(jì)算系統(tǒng)參數(shù)g2=Ma0,h=Mb,u=ga1Nb1,v=ga2Nb2,d=ga3Nb3。

詢問階段1敵手A2進(jìn)行如下詢問:

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

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

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

4.2 陷門隱私安全

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

系統(tǒng)建立挑戰(zhàn)者B選取隨機(jī)數(shù)a0、a1、a2、a3、b1、b2、b3、并計(jì)算系統(tǒng)參數(shù)g2=Ma0,h=Mb。

詢問階段1敵手A3進(jìn)行如下詢問:

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

詢問階段2敵手A3進(jìn)行詢問,除了不能詢問挑戰(zhàn)關(guān)鍵字及其衍生外,其他同詢問階段1一致。

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

5 效率分析

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

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

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

為了更直觀地顯示結(jié)果,本節(jié)從數(shù)值分析上對(duì)方案的計(jì)算成本進(jìn)行了模擬。在Linux系統(tǒng)上使用PBC庫,基于C語言編程實(shí)現(xiàn)dPRES方案和本方案。數(shù)值環(huán)境配置參數(shù)如表2所示。

表2 環(huán)境配置參數(shù)

本文方案和dPRES方案均能實(shí)現(xiàn)密文授權(quán)和搜索功能。在數(shù)值實(shí)驗(yàn)中,加密和解密階段兩方案均加密相同數(shù)量的關(guān)鍵字,隨著關(guān)鍵字?jǐn)?shù)量的變化,統(tǒng)計(jì)在不同數(shù)量關(guān)鍵字下的加密時(shí)間,結(jié)果如圖1所示。

圖1 關(guān)鍵字?jǐn)?shù)量對(duì)加密時(shí)間的影響

由圖1可知,在加密階段,本文方案的時(shí)間開銷較dPRES方案高。搜索階段是統(tǒng)計(jì)搜索不同數(shù)量關(guān)鍵字的時(shí)間開銷,如圖2所示。

圖2 關(guān)鍵字?jǐn)?shù)量對(duì)搜索時(shí)間的影響

由圖2可知,在搜索階段,當(dāng)關(guān)鍵字?jǐn)?shù)量為10個(gè)時(shí),本文方案的時(shí)間開銷為42 ms,而dPRES方案的時(shí)間開銷為164.4 ms;當(dāng)關(guān)鍵字?jǐn)?shù)量為30個(gè)時(shí),本文方案的時(shí)間開銷為122.4 ms,而dPRES方案的時(shí)間開銷為456.2 ms;當(dāng)關(guān)鍵字?jǐn)?shù)量為50個(gè)時(shí),本文方案的時(shí)間開銷為198.9 ms,而dPRES方案的時(shí)間開銷為762.2 ms。隨著關(guān)鍵字?jǐn)?shù)量的增加,dPRES方案的時(shí)間開銷增長速率比本文方案大,說明本文方案的搜索效率優(yōu)于dPRES方案。

統(tǒng)計(jì)在不同數(shù)量關(guān)鍵字下的解密開銷時(shí)間,如圖3所示。

圖3 關(guān)鍵字?jǐn)?shù)量對(duì)解密時(shí)間的影響

由圖3可以看出,在解密階段,隨著關(guān)鍵字?jǐn)?shù)量的增大,本文方案的時(shí)間開銷幾乎保持不變;當(dāng)關(guān)鍵字?jǐn)?shù)量為10個(gè)時(shí),dPRES方案的時(shí)間開銷為85.7 ms;當(dāng)關(guān)鍵字?jǐn)?shù)量為30個(gè)時(shí),dPRES方案的時(shí)間開銷為236.5 ms;當(dāng)關(guān)鍵字?jǐn)?shù)量為50個(gè)時(shí),dPRES方案的時(shí)間開銷為390.8 ms,說明dPRES方案的時(shí)間開銷與關(guān)鍵字?jǐn)?shù)量之間呈線性增長。因此,本文方案的解密效率優(yōu)于dPRES方案。

由圖1～圖3可知,雖然在加密階段,本文方案的時(shí)間開銷較dPRES方案高,但是在搜索階段,本文方案時(shí)間開銷遠(yuǎn)遠(yuǎn)小于dPRES方案,且在解密階段,本文方案時(shí)間開銷也低于dPRES方案。因此,本文方案在解密算法和搜索算法的計(jì)算代價(jià)上有明顯優(yōu)勢,減少了電子郵箱服務(wù)器和用戶之間的通信代價(jià),提高了系統(tǒng)的性能。

6 結(jié)束語

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