無安全信道的高效可搜索公鑰加密方案*

李士強(qiáng), 楊 波, 王 濤, 周彥偉

1.陜西師范大學(xué)計算機(jī)科學(xué)學(xué)院, 西安710119

2.密碼科學(xué)技術(shù)國家重點(diǎn)實(shí)驗(yàn)室, 北京100878

3.中國科學(xué)院信息工程研究所信息安全國家重點(diǎn)實(shí)驗(yàn)室, 北京100093

1 引言

云計算自出現(xiàn)以來, 便迅速得到了人們的廣泛關(guān)注.當(dāng)云計算系統(tǒng)運(yùn)算和處理大量的數(shù)據(jù)存儲與管理時, 云計算系統(tǒng)便轉(zhuǎn)變?yōu)橐粋€云存儲系統(tǒng).簡而言之, 云存儲就是將存儲資源放在云上供用戶存取的一種新興方案, 且使用者可以在任何時間、任何地點(diǎn), 通過網(wǎng)絡(luò)訪問云上所存儲的數(shù)據(jù).在云存儲帶來巨大便利的同時, 數(shù)據(jù)的隱私安全問題成為了用戶使用云的主要顧慮, 文獻(xiàn)[1,2]對云計算中的安全需求進(jìn)行了細(xì)致全面的分析和闡釋.大多數(shù)用戶是以明文的形式將數(shù)據(jù)上傳到云服務(wù)器, 那么如果這部分?jǐn)?shù)據(jù)被黑客截獲, 或云端的管理員進(jìn)行了違反職業(yè)道德的操作, 文件泄漏等安全隱患便不可避免.出于對數(shù)據(jù)隱私安全的保護(hù)訴求, 用戶通常將數(shù)據(jù)加密后再上傳至云端保存.然而, 由于現(xiàn)有的加密原語缺乏對密文相關(guān)操作的研究, 用戶只能從云端下載加密數(shù)據(jù), 對其解密后再進(jìn)行搜索操作, 該方式不僅冗雜還造成了計算資源和網(wǎng)絡(luò)帶寬的浪費(fèi).

為了解決存儲數(shù)據(jù)的保密性與搜索的高效性之間的矛盾, 2004年, Boneh 等人[3]提出了公鑰可搜索加密(public key encryption with keyword search, PEKS)的概念.在PEKS 中, 用戶讓網(wǎng)關(guān)檢索原始郵件中是否含有關(guān)鍵詞, 與此同時, 網(wǎng)關(guān)不能得到郵件的任何信息.換句話說, 郵件網(wǎng)關(guān)可以搜索需要的關(guān)鍵詞, 但是不會得到除關(guān)鍵詞之外的任何信息.PEKS 具有廣泛的實(shí)際應(yīng)用價值, 如郵件路由[3,4]、電子健康記錄系統(tǒng)[5,6]等相關(guān)工作.

在Boneh 等人的開創(chuàng)性工作之后, Water 等人[7]展示了PEKS 可以用來構(gòu)造可搜索的加密審計日志.Golle 等人[8]提出了一種基于連接關(guān)鍵詞的可搜索加密方案, 實(shí)現(xiàn)了對多個關(guān)鍵詞進(jìn)行搜索的功能.Boneh 和Waters[9]將PEKS 方案對關(guān)鍵詞的搜索擴(kuò)展到連接、子集和范圍比較搜索, 支持對復(fù)雜邏輯結(jié)構(gòu)進(jìn)行搜索.此外, 相關(guān)文獻(xiàn)[10,11]研究了如何將公鑰可搜索加密與公鑰加密進(jìn)行安全的組合.由于關(guān)鍵詞空間過小, 而且用戶會頻繁使用常見的關(guān)鍵詞進(jìn)行搜索, 所以文獻(xiàn)[12–15]對PEKS 的關(guān)鍵詞離線猜測攻擊做出了研究.

然而, Boneh 等人[3]的方案存在著接收者與服務(wù)器之間需要由安全信道來傳送陷門的缺陷, 安全信道的使用造成了計算資源上的浪費(fèi), 但若沒有安全信道, 攻擊者截獲陷門便可進(jìn)行搜索操作, 進(jìn)而可以區(qū)分出與陷門匹配的加密消息.為解決此問題, Baek 等人[16]提出了無安全信道的公鑰可搜索加密(secure-channel free public key encryption with keyword search, SCF-PEKS)方案.2007年, Gu 等人[17]基于雙線性對運(yùn)算給出了一個有趣的PEKS 方案, 該方案在加密過程中沒有進(jìn)行雙線性對運(yùn)算.之后, 他們進(jìn)一步探究了安全信道的問題, 給出了一個高效的SCF-PEKS 方案.Rhee 等人[18]給出了新的方案, 增強(qiáng)了Baek 等人[16]方案的安全性模型, 允許攻擊者獲得非挑戰(zhàn)密文與陷門的關(guān)系.后來Fang 等人[19]給出了首個在標(biāo)準(zhǔn)模型下安全的SCF-PEKS 方案, 但該方案檢測算法過于復(fù)雜, 不夠高效.Emura等人[20]展示了由匿名的IBE (identity-based encryption)機(jī)制可以構(gòu)造通用的自適應(yīng)的SCF-PEKS 方案.隨后, Emura 和Rahman 等人拓展了Emura 等人[20]的工作, 使用劃分密文結(jié)構(gòu)的IBE 構(gòu)造了更加高效的SCF-PEKS 方案[21].Rhee 等人[22]也提出兩種轉(zhuǎn)換模式, 用兩個并行的或依次的IBE 機(jī)制來構(gòu)造SCF-PEKS 方案.徐磊等人[23]基于靜態(tài)假設(shè)提出了一個合數(shù)階群下的PEKS 方案, 跟上述方案相比, 提升了現(xiàn)有方案的安全性能.

本文給出了一個在標(biāo)準(zhǔn)模型下安全的高效的SCF-PEKS 方案, 跟Fang 等人[19]在標(biāo)準(zhǔn)模型下構(gòu)造的方案相比, 本文方案具有更簡潔的構(gòu)造, 且在靜態(tài)假設(shè)下證明了安全性, 有著更好的安全性能.同文獻(xiàn)[23]相比, 本文方案有著更小的陷門尺寸, 而且不需要安全信道的參與.基于判定性子群假設(shè)和DBDH假設(shè)(decisional bilinear Diffie-Hellman assumption), 我們證明了該方案在選擇關(guān)鍵詞的攻擊下是安全的.

2 預(yù)備知識

2.1 合數(shù)階雙線性群

令G 表示雙線性群生成算法, 該算法以安全參數(shù)λ 作為輸入, 輸出元組(N = p1p2p3,G,GT,e), 其中p1,p2,p3是三個互不相同的素數(shù).

定義1 (合數(shù)階雙線性群)設(shè)G 和GT是階為N =p1p2p3的循環(huán)群, g 是G 的生成元.e:G×G →GT是雙線性映射, 滿足下列性質(zhì):

(1)雙線性: 對于任意g,h ∈G, a,b ∈ZN, 有e(ga,hb)=e(g,h)ab;

(2)非退化性: 存在g ∈G, 使得e(g,g)在GT中的階是N.

進(jìn)一步要求群G 和GT中的運(yùn)算以及雙線性運(yùn)算e 都可以在多項(xiàng)式時間內(nèi)完成.令G=Gp1Gp2Gp3,其中Gp1, Gp2和Gp3分別是群G 中階為p1, p2和p3的子群.此外, 用表示Gpi{1}.注意到,若ij, hi∈Gpi, hj∈Gpj, 則e(hi,hj)是群GT中的單位元.

2.2 判定性子群假設(shè)

(1)給定一個群生成器G, 定義如下分布：

假設(shè)1若對于公開元組D, 存在一個任意概率多項(xiàng)式時間的敵手A, 那么敵手A 區(qū)分T0與T1的優(yōu)勢:=|Pr[A(D,T0)=1]?Pr[A(D,T1)=1]| 關(guān)于λ 是可忽略的.

(2)給定一個群生成器G, 定義如下分布：

假設(shè)2若對于公開元組D, 存在一個任意概率多項(xiàng)式時間的敵手A, 那么敵手A 區(qū)分T0與T1的優(yōu)勢:=|Pr[A(D,T0)=1]?Pr[A(D,T1)=1]| 關(guān)于λ 是可忽略的.

2.3 DBDH 假設(shè)

設(shè)G1和G2是階為素數(shù)q 的循環(huán)群, g 是G1的生成元.設(shè)e:G1×G1→G2是雙線性映射.定義敵手A 區(qū)分e(g,g)abc與e(g,g)r的優(yōu)勢為:

其中a,b,c,r ∈Zp是隨機(jī)選取的.

2.4 核心引理

引理1[24]確定一個素數(shù)q 并定義那么對任意可進(jìn)行最多q 次詢問的敵手A, 我們有

其中RF:Zp→Zp為真隨機(jī)函數(shù).

2.5 SCF-PEKS 的概念

圖1 SCF-PEKS 安全模型Figure 1 Security model of SCF-PEKS

如圖1 所示, SCF-PEKS 的參與者主要涉及三方: 發(fā)送者(數(shù)據(jù)擁有者)、接收者R (數(shù)據(jù)使用者)、云服務(wù)器S.發(fā)送者生成和發(fā)送加密關(guān)鍵詞.接收者對目標(biāo)文件的關(guān)鍵詞生成陷門, 并發(fā)送到云服務(wù)器.云服務(wù)器接收到發(fā)送者的加密關(guān)鍵詞和接收者的陷門, 執(zhí)行搜索操作, 最終將匹配的文件發(fā)送給接收者.

SCF-PEKS 的基本思想是令服務(wù)器保管它的公私鑰對.為了生成PEKS 密文, 發(fā)送者同時使用服務(wù)器和接收者的公鑰進(jìn)行加密.然后, 接收者發(fā)送陷門去檢索與加密關(guān)鍵詞相關(guān)的數(shù)據(jù), 但是在這個過程中,陷門可以通過公共信道發(fā)送.在接收到陷門后, 服務(wù)器使用它的私鑰去檢測與陷門匹配的PEKS 密文.下面我們定義這個模型.

定義2一個無安全信道的公鑰可搜索加密(SCF-PEKS)方案由下列幾個算法組成:

GlobalSetup(λ): 輸入安全參數(shù)λ, 生成全局參數(shù)GP.

KeyGenServer(GP): 輸入全局參數(shù)GP, 生成服務(wù)器S 的公私鑰對(pkS,skS).

KeyGenReceiver(GP): 輸入GP, 生成接收者R 的公私鑰對(pkR,skR).

SCF-PEKS(GP,pkS,pkR,w): 輸入GP, 接收者的公鑰pkR, 服務(wù)器的公鑰pkS以及關(guān)鍵詞w, 生成關(guān)于關(guān)鍵詞w 的PEKS 密文C.

Trapdoor(GP,skR,w): 輸入GP, 接收者的私鑰skR以及關(guān)鍵詞w, 生成陷門Tw.

Test(GP,Tw,skS,C): 輸入GP, 陷門Tw, 服務(wù)器的私鑰skS以及w′的PEKS 密文C, 若w =w′,輸出“yes”, 否則, 輸出“no”.

2.6 安全性定義及攻擊游戲的描述

定義3IND-SCF-CKA (indistinguishability of SCF-PEKS against chosen keyword attack)游戲.

設(shè)λ 為安全參數(shù), A 為多項(xiàng)式時間敵手.我們考慮關(guān)于敵手A 和模擬者B 的兩個游戲模型:

GameX: 假設(shè)A 是服務(wù)器.

Setup : 運(yùn)行系統(tǒng)初始化算法GlobalSetup(λ), KeyGenServer(GP)和KeyGenReceiver(GP), 生成系統(tǒng)公共參數(shù)GP, 接收者和服務(wù)器的公私鑰對(pkR,skR)、(pkS,skS).然后, B 將(pkS,skS)和pkR發(fā)送給A.

Queryphase1 : A 自適應(yīng)的向模擬者B 詢問關(guān)鍵詞w ∈KSw的陷門, 然后, B 計算Tw=Trapdoor(GP,skR,w), 并返回給A.

Challenge: 一旦A 決定phase1 結(jié)束, 他向B 發(fā)送挑戰(zhàn)關(guān)鍵詞對(w0,w1), 唯一的要求是w0和w1不能出現(xiàn)在phase1 的訊問過程中.B 隨機(jī)選取b ∈{0,1}, 并計算C?= SCF-PEKS(GP,pkS,pkR,wb)作為挑戰(zhàn)密文返回給A.

Queryphase2: A 繼續(xù)進(jìn)行關(guān)鍵詞的陷門詢問, 但是不能詢問w0和w1.

Guess: A 輸出猜測b′.如果b′=b, A 獲得勝利.否則, A 失敗.

定義A 攻破GameX 的優(yōu)勢為:

GameY: 假設(shè)A 是外部攻擊者(包括接收者).

Setup : 運(yùn)行系統(tǒng)初始化算法GlobalSetup(λ), KeyGenServer(GP)和KeyGenReceiver(GP), 生成系統(tǒng)公共參數(shù)GP, 接收者和服務(wù)器的公私鑰對(pkR,skR)、(pkS,skS).然后, B 將(pkR,skR)和pkS發(fā)送給A.

Challenge:A 向B 發(fā)送目標(biāo)關(guān)鍵詞對(w0,w1).B 隨機(jī)選取b ∈{0,1}, 并計算挑戰(zhàn)密文C?=SCFPEKS(GP,pkS,pkR,wb)返回給A.

Guess: A 輸出猜測b′.如果b′=b, A 獲得勝利.否則, A 失敗.

定義A 攻破GameY 的優(yōu)勢為:

3 新的SCF-PEKS 方案

在本節(jié)中, 本文采用合數(shù)階雙線性對在標(biāo)準(zhǔn)模型下基于Wee[25]的IBE 方案構(gòu)造SCF-PEKS 方案.

3.1 我們的構(gòu)造

GlobalSetup(λ): 設(shè)λ 為安全參數(shù), (N,G,GT,e)為雙線性映射參數(shù).選取一個抗碰撞單向哈希函數(shù)H :{0,1}?→ZN, 令關(guān)鍵詞空間為KSw=ZN.設(shè)全局參數(shù)為GP =(N,G,GT,e,H,KSw).

KeyGenServer(GP): 從中選擇大于1 的隨機(jī)數(shù)x, h ∈Gp1, 計算X =Y = e(X,h).輸出pkS=(g1,h,Y), skS=x, 分別作為服務(wù)器的公私鑰.

KeyGenReceiver(GP): 隨機(jī)選取y ∈ZN, u ∈Gp1, g3∈輸出pkR= (g1,e(g1,u)),skR=(y,u,g3), 分別作為接收者的公私鑰.

SCF-PEKS(GP,pkS,pkR,w): 隨機(jī)選取r,s ∈ZN, 計算U =t=H(e(X,h)s), V =W =e(g1,u)r.輸出密文C =(U,V,W).

Trapdoor(GP,skR,w): 隨機(jī)選取R3∈Gp3, 計算Tw=u1/(y+w)R3.返回Tw.

Test(GP,Tw,skS,C): 計算t=H(e(U,h)x), 檢驗(yàn)e(Vt,Tw)=W.若等式成立, 輸出“yes”, 否則,輸出“no”.

方案正確性:

3.2 安全性證明

定理1如果判定性子群假設(shè)和DBDH 假設(shè)是困難的, 那么3.1 節(jié)方案是IND-SCF-CKA 安全的.

引理2如果判定性子群假設(shè)是困難的, 那么我們的方案在內(nèi)部敵手的游戲中是語義安全的.

證明:設(shè)任意敵手A 至多可進(jìn)行q 次詢問, 存在與A 運(yùn)行時間一致的敵手A1、A2, 使得

接下來我們進(jìn)行一系列游戲, 并使用Advi表示敵手A 在Gamei中的優(yōu)勢.

Game0這是定義2 的真實(shí)攻擊游戲.不失一般性, 我們做出如下假設(shè):

(1)我們不會遇到這樣一個關(guān)鍵詞w, 使得w = y mod p1, 因?yàn)檫@樣的關(guān)鍵詞能直接構(gòu)成的離散對數(shù), 使判定性子群假設(shè)不成立.

(2)敵手的詢問w1,··· ,wq∈ZN是不同的, 因此給定g3我們可以完美的隨機(jī)化陷門Tw=u1/(y+w)R3.

(3)w1,··· ,wq在mod p2下是不同的; 給定wiwy∈ZN使得wi= wymod p2, 通過計算gcd(wi?wj,N)可以分解N.

我們將上述假設(shè)整合為一個整體, 從Game1 開始, 如果違背了第一個或第三個條件就中斷游戲, 并且使用隨機(jī)化處理重復(fù)的關(guān)鍵詞詢問.

Game1對(U0,V0,W0)←PEKS(pkS,pkR,w?)做出如下改變:

隨機(jī)選取C ∈Gp1, 輸出(U0,V0,W0)=(U0,C,e(C,Tw?)).

因?yàn)镚ame1 的改變對游戲成立的優(yōu)勢是不產(chǎn)生影響的, 所以,

其中negl(λ)是可忽略函數(shù).

Game2將C 的分布由C ∈Gp1變?yōu)镃 ∈Gp1Gp2.構(gòu)造一個攻擊假設(shè)1 的敵手A1.

A1輸入(g1,g3,C), 其中C ∈Gp1或者C ∈Gp1Gp2, 模擬敵手A 在Game1 中的實(shí)驗(yàn): 誠實(shí)地運(yùn)行KeyGenReceiver, 得到(y,u), 然后使用(y,u)回答所有的陷門詢問, 同(U0,C,e(C,Tw?))一樣計算(U0,V,W0).

由2.2 節(jié)假設(shè)1 可知

Game3將Tw分布中的u1/(y+w)R3變?yōu)槠渲衦1,···,rq+1,y1,···,yq+1∈ZN.然后進(jìn)行一系列的子游戲, 定義為sub-game3.j.0 和sub-game3.j.1, j =1,2,··· ,q+1, 具體過程描述如下:

(1)在sub-game3.j.0 中, Tw的分布為

(2)在sub-game3.j.1 中, Tw的分布為

可以看出, Game2 對應(yīng)著sub-game3.0.1,Game3 對應(yīng)著sub-game3.q+1.1.

首先, 可以觀察到, 在給定pkR和挑戰(zhàn)密文下, y mod p2是完全隱藏的, 因此我們可以用yimod p2代替y mod p2.于是有

接下來, 對于j =1,··· ,q+1, 我們構(gòu)造敵手A2.

A2輸入(G,g1,g{2,3},g3,C,T), 其中C ∈Gp1Gp2, T = uR3∈Gp1Gp3或T =∈Gp1Gp2Gp3, 模擬敵手A 在Game3 中的實(shí)驗(yàn):

(1)隨機(jī)選取y ∈ZN, 公布pkR=(g1,e(g1,T),H), 其中e(g1,T)=e(g1,u);

(2)隨機(jī)選取r1,··· ,rj?1,y1,··· ,yj?1∈ZN;

(3)模擬Trapdoor 輸入w, 隨機(jī)選取R′3∈Gp3, 輸出

(4)用C 計算(U0,V0,W0).

觀察到, 如果T = uR3, 那么這是sub-game3.j ?1.1; 如果T =那么這是sub-game3.j.0.由2.2 節(jié)假設(shè)2 可得,

因此可以得到

Game4用RF(w)替換Tw中的其中RF : ZN→Zp2是真隨機(jī)函數(shù); 也就是說, Tw現(xiàn)在為由引理1 很容易得到

Game5用W0∈GT替換W0=e(C,Tw?).

因此,

由以上游戲可得, 我們的方案在內(nèi)部敵手的游戲中是語義安全的.

引理3如果DBDH 問題是困難的, 那么我們的方案在外部敵手的游戲中是語義安全的.

證明:假設(shè)存在多項(xiàng)式時間敵手A 可以攻擊我們的方案, 我們構(gòu)造一個可以進(jìn)行DBDH 游戲的模擬者B.模擬過程如下:

挑戰(zhàn)者設(shè)置階為p1的群以及雙線性映射其中分別為合數(shù)階群G、GT的素數(shù)階子群.輸出DBDH 實(shí)例給B, B 的目標(biāo)是要區(qū)分T =e(g1,g1)abc還是GT中的隨機(jī)元素.

B 和A 進(jìn)行以下游戲：

Setup : 設(shè)λ 為安全參數(shù),(N,G,GT,e)為雙線性映射參數(shù).選取一個抗碰撞單向哈希函數(shù)H :{0,1}?→ZN, 令關(guān)鍵詞空間為KSw=ZN.設(shè)全局參數(shù)為GP =(N,G,GT,e,H,KSw).

Challenge : A 輸出關(guān)鍵詞對(w0,w1).作為回應(yīng), B 隨機(jī)選取b ∈{0,1}, 設(shè)挑戰(zhàn)關(guān)鍵詞為w?= wb, 隨機(jī)選取r ∈ZN, U?=t?= H(T), V?= g(y+w?)r/t?1, W?= e(g1,u)r.挑戰(zhàn)密文C?=(U?,V?,W?), 將C?發(fā)送給A.

Guess : A 輸出猜測b′.若b′= b 返回1, 意味著T = e(g1,g1)abc; 否則返回0, 意味著T 是GT中的隨機(jī)元素.

容易看出, 若敵手A 能夠攻破我們的方案, 那么模擬者B 便能攻破DBDH 假設(shè), 所以我們的方案在外部敵手的游戲中是語義安全的.

由以上兩個游戲可知, 我們的方案是IND-SCF-CKA 安全的.

4 性能對比

我們在下面列舉了一些經(jīng)典的可搜索加密方案, 配合本文方案進(jìn)行性能對比.表1 中給出了各方案的安全模型、有無安全信道以及采用的困難性假設(shè)等信息.圖2 給出了在Inter(R)Core(TM)i5-2450M CPU 2.5 GHz 4.00 GB RAM 的計算機(jī)下, 利用JPBC 庫實(shí)現(xiàn)各算法所需要的平均時間.

表1 一些PEKS 方案對比分析數(shù)據(jù)表Table 1 Comparisons among various PEKS schemes

圖2 方案每個算法的平均運(yùn)行時間Figure 2 Average run time of each algorithm

我們發(fā)現(xiàn), Gu 等人[17]的方案需要在隨機(jī)諭言機(jī)模型下證明安全性, Gu 等人[17]和Fang 等人[19]的方案構(gòu)造于素數(shù)階群, 計算開銷更少, 但是安全性證明采用了假設(shè)性較強(qiáng)的非靜態(tài)假設(shè).相較于素數(shù)階的方案, 徐磊等人[23]和我們的方案在盡量少的損耗搜索速度的情況下, 實(shí)現(xiàn)了靜態(tài)假設(shè)下的安全性, 有著更好的安全性能.與徐磊等人的方案相比, 我們的方案不需要安全信道的參與, 而且明顯提升了陷門生成效率.

5 總結(jié)

在本文中, 我們討論了云存儲上的數(shù)據(jù)檢索方法, 并提出了一個高效的SCF-PEKS 方案, 基于判定性子群假設(shè)和DBDH 假設(shè), 該方案在標(biāo)準(zhǔn)模型下是IND-SCF-CKA 安全的.我們的方案保證了一定的搜索效率, 同時極大地提高了安全性能, 適用于實(shí)際中需要高安全性的云存儲環(huán)境.下一階段, 我們將基于靜態(tài)假設(shè)在素數(shù)階群下構(gòu)造新的SCF-PEKS 方案, 在保證安全性能的基礎(chǔ)上實(shí)現(xiàn)更高的計算效率.