基于合數(shù)階雙線性對(duì)的可搜索加密方案分析與改進(jìn)

鄧志輝,王少輝,王 平

(1.南京郵電大學(xué) 計(jì)算機(jī)學(xué)院,南京 210003; 2.江蘇省無線傳感網(wǎng)高技術(shù)研究重點(diǎn)實(shí)驗(yàn)室,南京 210003)

0 概述

隨著互聯(lián)網(wǎng)技術(shù)的迅速發(fā)展,人們?cè)谌粘９ぷ骱蜕钪挟a(chǎn)生及使用的數(shù)據(jù)量不斷增大,數(shù)據(jù)規(guī)模已由PB級(jí)發(fā)展到EB級(jí)甚至ZB級(jí),如何存儲(chǔ)和處理大規(guī)模數(shù)據(jù)成為亟待解決的問題。云計(jì)算是通過互聯(lián)網(wǎng)提供動(dòng)態(tài)、易擴(kuò)展和虛擬化資源的計(jì)算方式,而云存儲(chǔ)是云計(jì)算的應(yīng)用模式,其可遠(yuǎn)程高效存儲(chǔ)數(shù)據(jù),能節(jié)省大量存儲(chǔ)空間,因此引起了人們的廣泛關(guān)注,并成為存儲(chǔ)大數(shù)據(jù)的有效手段。

在云存儲(chǔ)應(yīng)用初期,部分用戶以明文形式上傳數(shù)據(jù),由于云存儲(chǔ)具有開放性和分布性,數(shù)據(jù)脫離用戶的物理控制存儲(chǔ)在云端后,一旦被外部攻擊者截獲或被惡意云服務(wù)提供者泄露,將無法挽回?fù)p失。因此,為保證所傳數(shù)據(jù)的隱私性和安全性,用戶會(huì)將數(shù)據(jù)加密后再上傳到云端。加密存儲(chǔ)數(shù)據(jù)在一定程度上可以保證數(shù)據(jù)的隱私與安全,但卻給數(shù)據(jù)檢索帶來困難。

由于基于明文關(guān)鍵字的傳統(tǒng)檢索模型無法在密文下進(jìn)行檢索,因此2000年SONG等人[1]在對(duì)稱密碼體制的基礎(chǔ)上提出可搜索加密的概念,并設(shè)計(jì)出可在密文下進(jìn)行檢索的SWP方案。2004年BONEH等人[2]首次提出公鑰關(guān)鍵字搜索加密(Public Key Encryption with Keyword Search,PEKS),并設(shè)計(jì)一種應(yīng)用于郵件路由分發(fā)場(chǎng)景的方案,將不同郵件分發(fā)到不同設(shè)備中,公鑰關(guān)鍵字搜索加密允許服務(wù)器根據(jù)接收到的陷門對(duì)不同關(guān)鍵字郵件選擇分發(fā)路由,且不會(huì)泄露郵件內(nèi)容,但是該方案在安全和效率方面存在不足。WATERS等人[3]隨后提出用來構(gòu)造可搜索加密審計(jì)日志的新PEKS方法。GOLLE等人[4]也提出基于連接關(guān)鍵詞的可搜索加密方案,可實(shí)現(xiàn)對(duì)多個(gè)關(guān)鍵詞的搜索功能。2006年BYUN等人[5]分析了文獻(xiàn)[2]中PEKS方案,指出該方案容易遭受關(guān)鍵字猜測(cè)攻擊[6-7],此后研究者們提出大量抗關(guān)鍵字猜測(cè)攻擊的PEKS方案[8-10]。2016年XU等人[11]提出合數(shù)階雙線性群下的PEKS方案,該方案系統(tǒng)參數(shù)比其他方案更少,且其安全性是基于靜態(tài)假設(shè)下合數(shù)階子群的不可區(qū)分性。文獻(xiàn)[12]提出雙服務(wù)器模型,通過2個(gè)獨(dú)立服務(wù)器分享秘密檢索陷門執(zhí)行搜索算法抵抗關(guān)鍵字猜測(cè)攻擊。文獻(xiàn)[13]通過加入發(fā)送者公私鑰生成可搜索密文和陷門,使服務(wù)器無法自行生成關(guān)鍵詞陷門測(cè)試密文。文獻(xiàn)[14]提出一種通過采用非確定算法生成關(guān)鍵字密文和陷門的方案,可高效抵抗關(guān)鍵字猜測(cè)攻擊。

然而PEKS框架本身存在一定不足,即多數(shù)PEKS方案都需在服務(wù)器與接收者之間建立安全信道以傳送陷門,否則外部攻擊者很容易截獲關(guān)鍵字陷門進(jìn)行搜索操作,進(jìn)而得到加密數(shù)據(jù)信息,但是建立安全信道代價(jià)太高且很難實(shí)現(xiàn)。為解決該問題,文獻(xiàn)[15]提出無安全信道的公鑰關(guān)鍵字搜索加密(Secure-Channel Free Public Key Encryption with Keyword Search,SCF-PEKS)方案,由于關(guān)鍵字密文的生成需要云服務(wù)器公鑰參與,因此只有云服務(wù)器能夠使用自身私鑰檢查關(guān)鍵字密文和陷門是否包含相同關(guān)鍵字。通過該方式,用戶可在無安全信道的情況下將關(guān)鍵字陷門發(fā)送到數(shù)據(jù)存儲(chǔ)服務(wù)器。但是上述方案依賴于隨機(jī)oracle模型,而隨機(jī)oracle模型不能真正反映方案在現(xiàn)實(shí)世界中的安全性。2009年FANG等人[16]提出首個(gè)在標(biāo)準(zhǔn)模型下安全的SCF-PEKS方案,但該方案檢測(cè)算法太復(fù)雜,不具備高效性。2011年EMURA等人[17]利用匿名IBE、標(biāo)簽加密方案和一次性簽名提出SCF-PEKS方案的通用設(shè)計(jì)方法。近期LI等人[18]從靜態(tài)假設(shè)出發(fā)提出在標(biāo)準(zhǔn)模型下安全高效的SCF-PEKS方案,該方案主要基于判定性子群假設(shè)和DBDH假設(shè),與現(xiàn)有在標(biāo)準(zhǔn)模型下構(gòu)造的相關(guān)方案相比,具有更簡(jiǎn)潔的結(jié)構(gòu)。

2009年RHEE等人[19]指出SCF-PEKS方案不能抵抗由外部攻擊者發(fā)起的離線關(guān)鍵字猜測(cè)攻擊,并在文獻(xiàn)[20]中引入陷門不可區(qū)分性的概念,證明抵抗關(guān)鍵詞猜測(cè)攻擊的充分條件是陷門的不可區(qū)分性。本文對(duì)文獻(xiàn)[11,18]提出的基于合數(shù)階雙線性對(duì)的可搜索加密方案進(jìn)行分析,發(fā)現(xiàn)上述方案的關(guān)鍵字陷門生成算法無法滿足搜索關(guān)鍵字陷門的不可區(qū)分性。針對(duì)該問題,本文在文獻(xiàn)[11,18]方案的基礎(chǔ)上,提出一種改進(jìn)的無安全信道公鑰可搜索加密方案,同時(shí)基于DBDH假設(shè)對(duì)其是否滿足關(guān)鍵字陷門的不可區(qū)分性進(jìn)行證明,并研究了該方案的計(jì)算復(fù)雜度和空間存儲(chǔ)復(fù)雜度。

1 基本知識(shí)

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

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

1)可計(jì)算性:映射e:G×G→GT可以被有效計(jì)算。

3)非退化性:e(g,g)≠1。

e(h1,h2)=e(gp2p3α1,gp1p3α2)=e(gα1,gp3α2)p1p2p3=1

(1)

如果選取i≤j、hi∈Gpi、hj∈Gpj,則e(hi,hj)是群GT中的單位元,這說明合數(shù)階雙線性群中各子群Gp1、Gp2和Gp3相互正交。

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

假設(shè)1給定群生成器G(λ),定義其分布如下:

(2)

Pr[A(D,T1)=1]|關(guān)于λ是可忽略的。

(3)

1.3 DBDH假設(shè)

1.4 PEKS和SCF-PEKS

PEKS和SCF-PEKS方案都涉及發(fā)送者(數(shù)據(jù)擁有者)、接收者(用戶)和云服務(wù)器三方參與者。發(fā)送者生成關(guān)鍵字的可搜索密文并將其連同密文數(shù)據(jù)發(fā)送給云服務(wù)器,接收者生成關(guān)鍵字陷門,云服務(wù)器根據(jù)關(guān)鍵字密文和陷門執(zhí)行數(shù)據(jù)檢索操作,并將匹配的密文數(shù)據(jù)發(fā)送給接收者。

1.4.1 PEKS方案

定義2公鑰可搜索加密方案由以下4個(gè)算法組成:

1)Setup(λ)算法。輸入安全參數(shù)λ,算法生成全局參數(shù)gp,用戶公鑰pk和私鑰sk。

2)PEKS(gp,pk,ω)算法。由發(fā)送者執(zhí)行,輸入全局參數(shù)gp、用戶公鑰pk和關(guān)鍵字ω,輸出關(guān)于關(guān)鍵字ω的可搜索密文C。

3)Trapdoor(gp,sk,ω)算法。由用戶執(zhí)行,輸入全局參數(shù)gp、用戶私鑰sk和關(guān)鍵字ω,生成關(guān)鍵字陷門Tω。

4)Test(gp,C,Tω)算法。輸入全局參數(shù)gp、可搜索密文C和關(guān)鍵字陷門Tω,服務(wù)器對(duì)關(guān)鍵字密文和陷門進(jìn)行驗(yàn)證,如果驗(yàn)證匹配則輸出1,否則輸出0。

1.4.2 SCF-PEKS方案

SCF-PEKS方案與PEKS方案主要區(qū)別在于云服務(wù)器的公鑰和私鑰是否分別參與了可搜索密文生成算法和檢測(cè)匹配算法。由于PEKS方案沒有使用云服務(wù)器的公私鑰對(duì),因此其傳送關(guān)鍵字陷門時(shí)需要使用安全信道才能避免受到攻擊。而因?yàn)镾CF-PEKS方案中云服務(wù)器的公鑰參與了可搜索關(guān)鍵字密文生成過程,只有擁有對(duì)應(yīng)私鑰的云服務(wù)器才能進(jìn)行檢測(cè)匹配算法,所以傳送關(guān)鍵字陷門時(shí)不需安全信道參與。

定義3無安全信道的公鑰可搜索加密方案由以下4個(gè)算法組成:

1)Setup(λ)算法。輸入安全參數(shù)λ,生成全局參數(shù)gp,并輸出云服務(wù)器的公私鑰對(duì)(pkS,skS),以及接收者的公私鑰對(duì)(pkR,skR)。

2)SCF-PEKS(gp,pkS,pkR,ω)算法。輸入gp、接收者的公鑰pkR、云服務(wù)器的公鑰pkS以及關(guān)鍵字ω,由發(fā)送者輸出關(guān)鍵字ω的可搜索密文C。

3)Trapdoor(gp,skR,ω)算法。輸入gp和接收者的私鑰skR,由接收者輸出關(guān)鍵字ω的陷門Tω。

4)Test(gp,skS,C,Tω)算法。輸入gp、關(guān)鍵字密文C和關(guān)鍵字陷門Tω,云服務(wù)器利用自身私鑰對(duì)密文和陷門進(jìn)行匹配驗(yàn)證,如果匹配則輸出1,否則輸出0。

1.5 陷門不可區(qū)分性

為避免關(guān)鍵字猜測(cè)攻擊,在設(shè)計(jì)方案時(shí)要保證關(guān)鍵字密文和陷門的不可區(qū)分性。本節(jié)只給出陷門不可區(qū)分性的安全性定義,其他可參考文獻(xiàn)[18]。根據(jù)文獻(xiàn)[20]提出的陷門不可區(qū)分性概念及安全模型,假設(shè)敵手A為外部攻擊者(不是服務(wù)器和接收者),關(guān)鍵字陷門的不可區(qū)分性通過多項(xiàng)式時(shí)間的挑戰(zhàn)者B與敵手A之間交互游戲來描述,具體過程如下:

1)Setup。給定安全參數(shù)λ,挑戰(zhàn)者B生成全局參數(shù)gp、云服務(wù)器和接收者的公私鑰對(duì)(pkS,skS)和(pkR,skR),并將gp、pkR和pkS發(fā)送給敵手A。

2)Queryphase1。敵手A可適應(yīng)性的詢問如下預(yù)言機(jī)OT,訪問次數(shù)以多項(xiàng)式時(shí)間限定:

(1)搜索陷門預(yù)言機(jī)OT。輸入接收者的私鑰skR和選擇的關(guān)鍵字ω∈KSω,OT預(yù)言機(jī)返回關(guān)鍵字陷門Tω←Trapdoor(gp,skR,ω)給敵手A。

(2)Challenge。一旦敵手A決定Queryphase1結(jié)束,A選擇未詢問過OT預(yù)言機(jī)的關(guān)鍵字(ω0,ω1),并將其發(fā)送給挑戰(zhàn)者B。挑戰(zhàn)者B隨機(jī)選擇b∈{0,1},計(jì)算關(guān)鍵字ωb對(duì)應(yīng)的陷門Tωb←Trapdoor(gp,skR,ωb)并返回給敵手A。

3)Queryphase2。敵手A可以繼續(xù)訪問OT預(yù)言機(jī),但要求不能就關(guān)鍵字(ω0,ω1)對(duì)預(yù)言機(jī)OT進(jìn)行詢問。

4)Guess。敵手A猜測(cè)b′,如果b′=b,則敵手A獲勝,否則敵手A失敗。

2 可搜索加密方案分析

本節(jié)主要對(duì)文獻(xiàn)[11,18]分別提出的2個(gè)基于合數(shù)階雙線性對(duì)的公鑰可搜索加密方案進(jìn)行分析。上述方案對(duì)關(guān)鍵字陷門的設(shè)計(jì)均無法保證關(guān)鍵字陷門不可區(qū)分性,存在安全問題。

2.1 文獻(xiàn)[11]方案分析

文獻(xiàn)[11]方案的安全性主要基于合數(shù)階雙線性群的子群不可區(qū)分性,該方案具有IND-CKA安全性,方案具體設(shè)計(jì)可參考文獻(xiàn)[11],下文對(duì)其中的Setup算法和Trapdoor算法進(jìn)行闡述。

對(duì)文獻(xiàn)[11]方案的安全性分析如下:

假設(shè)存在1個(gè)外部攻擊者A,給定2個(gè)關(guān)鍵字(ω0,ω1),且A可獲取包含目標(biāo)關(guān)鍵字ωb∈{ω0,ω1}的陷門Tωb=[T1,T2]=[gα(uωbh)rR3′,grR3],外部攻擊者A可通過以下攻擊方式來區(qū)分該陷門中的關(guān)鍵字:

1)外部攻擊者A通過系統(tǒng)參數(shù)gp={G,GT,e,N,u,g,h,e(g,g)α}獲取u、g、h的值。

2)A隨機(jī)選擇ω′∈{ω0,ω1},并計(jì)算得到:

(4)

3)若ωb=ω′,則M=e(g,g)α,由于e(g,g)α已知,外部攻擊者A可不通過驗(yàn)證測(cè)試算法就能區(qū)分并獲取陷門中的關(guān)鍵字,因此該方案不滿足陷門的不可區(qū)分性。

2.2 文獻(xiàn)[18]方案分析

文獻(xiàn)[18]提出在標(biāo)準(zhǔn)模型下利用合數(shù)階雙線性對(duì)的SCF-PEKS方案,該方案具有安全性和高效性,且主要基于判定性子群假設(shè)和DBDH假設(shè),方案具體設(shè)計(jì)可參考文獻(xiàn)[18],以下對(duì)其中的Setup算法、SCF-PEKS算法和Trapdoor算法進(jìn)行闡述。

3)Trapdoor(gp,skR,ω)算法。接收者確認(rèn)關(guān)鍵字后,隨機(jī)選取R3∈Gp3,計(jì)算Tω=u1/(y+ω)R3,返回Tω。

對(duì)文獻(xiàn)[18]方案的安全性分析如下:

由于該方案在無安全信道的環(huán)境下傳送關(guān)鍵字陷門,因此陷門很容易被攻擊者獲取,且攻擊者只需按如下攻擊方式進(jìn)行計(jì)算,便可輕易區(qū)分并獲取陷門中的關(guān)鍵字,具體攻擊過程為:

1)給定2個(gè)關(guān)鍵字(ω0,ω1),假設(shè)存在1個(gè)外部攻擊者A,將包含目標(biāo)關(guān)鍵字ωb∈{ω0,ω1}的陷門Tωb=u1/(y+ωb)R3發(fā)送給A。

3)A隨機(jī)選擇ω′∈{ω0,ω1},并計(jì)算得到:

(5)

4)若ωb=ω′,則M=e(u,g1),由于e(u,g1)在pkR中已知,攻擊者A可區(qū)分陷門中的關(guān)鍵字,因此該方案不滿足陷門的不可區(qū)分性。

3 SCF-PEKS改進(jìn)方案

針對(duì)文獻(xiàn)[11]和文獻(xiàn)[18]方案存在的安全問題,本文提出一種改進(jìn)的基于合數(shù)階雙線性對(duì)的無安全信道可搜索公鑰加密方案,該方案可保證關(guān)鍵字陷門的不可區(qū)分性,且能抵抗外部關(guān)鍵字猜測(cè)攻擊。

3.1 本文方案設(shè)計(jì)

本文方案由4個(gè)算法組成,其中Setup(λ)算法、SCF-PEKS(gp,pkS,pkR,ω)算法與文獻(xiàn)[18]方案中算法一致,另外改進(jìn)的2個(gè)算法具體如下:

2)Test(gp,Tω,C,skS,ω)算法。服務(wù)器先使用自身私鑰計(jì)算t=H(e(U,h)x)和n=H(e(T1,h)x),再檢驗(yàn)e(Vt,T2)=Wn是否成立。若等式成立,則輸出1,否則輸出0。

對(duì)本文方案的正確性證明如下:

(6)

(7)

(8)

由式(6)～式(7)可知,服務(wù)器通過自身私鑰可計(jì)算出正確的t和n,將其代入式(8)計(jì)算得知,陷門和可搜索密文能夠正確匹配,從而證明了本文方案具有正確性。

本文方案主要在生成陷門的Trapdoor算法基礎(chǔ)上進(jìn)行重新設(shè)計(jì)。根據(jù)上述分析,改進(jìn)方案在生成陷門時(shí)增加1個(gè)n次冪,其中n=H(e(X,h)z),z為隨機(jī)值。從而保證陷門即使在被攻擊者獲取的情況下,也無法通過計(jì)算區(qū)分出關(guān)鍵字,且必須計(jì)算出n值才能進(jìn)行驗(yàn)證操作,雖然增加了計(jì)算量,但是可保證關(guān)鍵字陷門的不可區(qū)分性。采用對(duì)文獻(xiàn)[18]方案相同的攻擊方式對(duì)本文方案進(jìn)行攻擊,可以得到:

(9)

若ω′=ωb,則M=e(u,g1)n,此時(shí)對(duì)于外部攻擊者而言,雖然e(u,g1)已知,但n值需要通過云服務(wù)器或接收者的私鑰計(jì)算得到,攻擊者無法通過M值判斷ω′是否等于ωb,不能對(duì)陷門中的關(guān)鍵字進(jìn)行區(qū)分,因此,本文方案能抵抗外部關(guān)鍵字猜測(cè)攻擊。

3.2 安全性證明

本文主要證明改進(jìn)方案關(guān)鍵字陷門的不可區(qū)分性,而由于可搜索密文的不可區(qū)分性等其他安全性基于判定性子群假設(shè)和DBDH假設(shè),因此本文安全性證明過程與文獻(xiàn)[18]中的安全性證明過程基本一致,具體可參考文獻(xiàn)[18]。

定理1如果DBDH假設(shè)是困難的,那么對(duì)于任意概率多項(xiàng)式時(shí)間算法的敵手A,能區(qū)分關(guān)鍵字陷門的概率優(yōu)勢(shì)可忽略。

敵手A和挑戰(zhàn)者B進(jìn)行游戲如下:

4)Guess。敵手A輸出猜測(cè)b′。在驗(yàn)證過程中,當(dāng)b′=b時(shí),n=H(e(T1,h)a)=H(e(g1,g1)abc),T=e(g1,g1)abc,則Tω*為合法輸出,返回1;當(dāng)b′≠b時(shí),T≠e(g1,g1)abc,則T是GT中隨機(jī)元素,返回0。

如果敵手A能區(qū)分陷門中的關(guān)鍵字,那么挑戰(zhàn)者B便可攻破DBDH假設(shè)。因此,本文方案的關(guān)鍵字陷門具有不可區(qū)分性,可抵抗外部攻擊者的關(guān)鍵字猜測(cè)攻擊。

3.3 性能比較

表1 本文方案與其他方案的性能對(duì)比

4 結(jié)束語

本文對(duì)傳統(tǒng)基于合數(shù)階雙線性對(duì)的可搜索公鑰加密方案進(jìn)行研究,指出其中陷門算法不具有關(guān)鍵字不可區(qū)分的安全屬性,并提出一種改進(jìn)的基于合數(shù)階雙線性對(duì)的可搜索加密方案。該方案在陷門、密文尺寸及計(jì)算復(fù)雜度與原方案接近的情況下,可保證關(guān)鍵字陷門的不可區(qū)分性,從而抵抗外部關(guān)鍵字猜測(cè)攻擊。關(guān)鍵字猜測(cè)攻擊較多由外部攻擊者發(fā)起,如果由內(nèi)部攻擊者(惡意服務(wù)器)發(fā)起猜測(cè)攻擊,則更容易造成數(shù)據(jù)泄露。后續(xù)將在本文對(duì)外部關(guān)鍵字猜測(cè)攻擊研究的基礎(chǔ)上,繼續(xù)對(duì)合數(shù)階雙線性對(duì)進(jìn)行改進(jìn),以抵抗內(nèi)部關(guān)鍵字猜測(cè)攻擊并提高計(jì)算效率。