支持多關(guān)鍵字的可搜索公鑰加密方案

李昊星,李鳳華,宋承根,蘇 铓,劉 歆

(1.西安電子科技大學(xué)綜合業(yè)務(wù)網(wǎng)理論及關(guān)鍵技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室,陜西西安 710071;2.中國(guó)科學(xué)院信息工程研究所,北京 100093;3.北京電子科技學(xué)院信息安全研究所,北京 100070)

支持多關(guān)鍵字的可搜索公鑰加密方案

李昊星1,李鳳華2,宋承根3,蘇 铓1,劉 歆3

(1.西安電子科技大學(xué)綜合業(yè)務(wù)網(wǎng)理論及關(guān)鍵技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室,陜西西安 710071;2.中國(guó)科學(xué)院信息工程研究所,北京 100093;3.北京電子科技學(xué)院信息安全研究所,北京 100070)

為了提升可搜索公鑰加密方案中服務(wù)器端關(guān)鍵字的搜索效率,提出了基于拉格朗日多項(xiàng)式的互逆映射構(gòu)造方法和支持多關(guān)鍵字的可搜索加密公鑰方案.該方案中,每組關(guān)鍵字對(duì)應(yīng)一對(duì)互逆映射,發(fā)送者將該組關(guān)鍵字密文的變換結(jié)果輸出給服務(wù)器,接收者向服務(wù)器發(fā)送陷門,只有當(dāng)陷門關(guān)鍵字屬于該組關(guān)鍵字時(shí),服務(wù)器才能還原出陷門關(guān)鍵字的密文以進(jìn)行匹配計(jì)算,僅需一次雙線性對(duì)計(jì)算即可搜索多個(gè)關(guān)鍵字.該方案在標(biāo)準(zhǔn)模型中是語(yǔ)義安全的,關(guān)鍵字匹配效率較高且沒(méi)有限制條件.

可搜索加密;多關(guān)鍵字搜索;安全性證明;隱私;云存儲(chǔ)

2004年,Boneh等[1]利用基于身份的加密方案[2-5]構(gòu)造了一種可搜索的公鑰加密方案(BDOP方案),簡(jiǎn)稱PEKS.在BDOP方案中,發(fā)送者Bob想要給接收者Alice發(fā)送一封帶有關(guān)鍵詞W1,W2,…,Wk的郵件M,Bob會(huì)用Alice的公鑰Apub同時(shí)對(duì)M和關(guān)鍵詞W1,W2,…,Wk進(jìn)行加密,隨后Bob將如下密文發(fā)送給郵件服務(wù)器:

其中,PPEKS表示PEKS密文生成函數(shù).當(dāng)Alice想要取回帶有關(guān)鍵詞W的郵件時(shí),她通過(guò)一個(gè)安全渠道將關(guān)于關(guān)鍵詞W的陷門TW發(fā)送給郵件服務(wù)器.郵件服務(wù)器可以利用PPEKS(Apub,W′)和TW判斷是否有W′=W,并且不會(huì)學(xué)習(xí)到關(guān)于W′的任何信息.該方案支持單個(gè)關(guān)鍵詞的匹配,但匹配計(jì)算是一對(duì)一的,k個(gè)關(guān)鍵詞至少需要k次匹配計(jì)算.

2007年,Boneh和Waters[6]基于隱藏向量加密方案構(gòu)造了支持比較、子集、范圍和任意多次邏輯“與”等檢索操作的可搜索公鑰加密方案(BW方案).該方案要求關(guān)鍵詞總體集合T的大小是以多項(xiàng)式為上界的,并且是能排序的,如T={1,2,…,n},而且生成的密文長(zhǎng)度與關(guān)鍵詞的總數(shù)呈線性關(guān)系.針對(duì)此問(wèn)題,Zhang等[7]提出了一個(gè)更有效的支持子集“與”檢索功能的可搜索公鑰加密方案(ZZ方案).ZZ方案不要求關(guān)鍵詞總體集合T的大小以多項(xiàng)式為上界,也不需要對(duì)T進(jìn)行排序.實(shí)際上,ZZ方案是一種支持內(nèi)積的可搜索加密方案[8],在搜索時(shí)需要O(k)個(gè)雙線性對(duì)計(jì)算.2014年B?sch等人[9]總結(jié)了可搜索加密的研究現(xiàn)狀.

基于身份的可搜索加密無(wú)需數(shù)字證書,密鑰管理機(jī)制簡(jiǎn)單,適合在云存儲(chǔ)環(huán)境中應(yīng)用.但上述方案均沒(méi)有很好地切合可搜索加密的主要目的,引入了多余的計(jì)算量或引入了不必要的限制條件,使得方案整體效率或?qū)蝹€(gè)文件進(jìn)行關(guān)鍵字搜索的效率較低.

根據(jù)雙線性對(duì)和拉格朗日多項(xiàng)式的性質(zhì),筆者提出了一種構(gòu)造互逆映射的方法.指出了可搜索加密的主要目的是判斷一個(gè)關(guān)鍵詞是否屬于某一關(guān)鍵詞集合,而不需要精確匹配關(guān)鍵詞所在位置.針對(duì)此目的,提出了一個(gè)支持多關(guān)鍵字的可搜索加密方案模型(Public Key Encryption with Multi-Keywords Search, PEMKS),并利用筆者提出的互逆映射構(gòu)造出了一種在標(biāo)準(zhǔn)模型下具有可證明安全性的PEMKS方案.與現(xiàn)有方案相比,該方案在沒(méi)有額外限定條件的情況下,將單次搜索的O(k)個(gè)雙線性對(duì)的計(jì)算復(fù)雜度降低到O(1)個(gè),有效地提高了多關(guān)鍵字匹配的效率.

1 預(yù)備知識(shí)

1.1 判定性截?cái)?t,q,∈)-ABDHE假設(shè)

假設(shè)G是階為素?cái)?shù)p的循環(huán)群,g為G中的生成元.GT是乘法循環(huán)群,且與G同階.e:G×G→GT是一個(gè)雙線性對(duì).

定義敵手B的優(yōu)勢(shì)函數(shù)AqG-,ABBDHE(λ)如下:

此處,P表示事件發(fā)生的概率,g′=gz∈G,a,z,r∈Zp,是隨機(jī)選取的.如果在時(shí)間t內(nèi),對(duì)于所有敵手B的＜∈,則稱判定性截?cái)?t,q,∈)-ABDHE假設(shè)成立.優(yōu)勢(shì)函數(shù)中減號(hào)左邊的分布記為Pq-ABDHE,減號(hào)右邊的分布記為Rq-ABDHE.

1.2 拉格朗日插值多項(xiàng)式

對(duì)于k個(gè)不同的數(shù)xi(i=1,2,…,k)可以得到k個(gè)k-1次多項(xiàng)式

且有

多項(xiàng)式Ft(x)和xt-1的次數(shù)最大為k-1,而它們?cè)趉個(gè)相同的點(diǎn)取值相同,所以有

進(jìn)而有

設(shè)G是階為素?cái)?shù)p的循環(huán)群,對(duì)于k個(gè)不同的數(shù)xi∈Zp,i=1,2,…,k,可以構(gòu)建出兩個(gè)與上述fi(x)定義有關(guān)的從Gk到Gk的映射^r和^R.

定義1映射:Gk→Gk定義如下:(r1,r2,…,rk)→(R1,R2,…,Rk),其中…,k.

定義2映射:Gk→Gk定義如下:(R,R,…,R)→(r,r,…,r),其中

12k12k2,…,k.

引理1若G、fi(x)和均如上述定義,則有和,即和互逆.

2 支持多關(guān)鍵字搜索的公鑰加密

2.1 基本定義

在PEMKS方案中,Bob向Alice發(fā)送一封加密郵件,郵件包含關(guān)鍵字(W1,…,Wk),Bob發(fā)送以下消息內(nèi)容:EApub(msg)‖PPEMKS(Apub,W1,…,Wk).其中,PPEMKS表示PEMKS密文生成函數(shù),Apub是Alice的公鑰,msg是郵件數(shù)據(jù).

下面分別給出PEMKS模型、挑戰(zhàn)者和活躍攻擊者之間的游戲以及PEMKS語(yǔ)義安全的定義.

定義3PEMKS方案包含以下概率多項(xiàng)式時(shí)間算法:

KeyGen(s):密鑰生成中心(KGC)選擇安全參數(shù)s,并根據(jù)此安全參數(shù)為Alice產(chǎn)生公鑰Apub和私鑰Apriv.公布Apub,將Apriv安全傳遞給Alice.

PEMKS(Apub,W1,…,Wk):Bob根據(jù)Alice的公鑰和關(guān)鍵字W1,…,Wk構(gòu)造一個(gè)多關(guān)鍵詞密文,簡(jiǎn)稱S.

Trapdoor(Apriv,W):Alice利用自身的私鑰和關(guān)鍵字W構(gòu)造一個(gè)陷門TW,Alice通過(guò)安全信道將陷門發(fā)送給服務(wù)器,防止他人利用該陷門進(jìn)行搜索.

Test(Apub,S,TW):給定Alice的公鑰,服務(wù)器根據(jù)多關(guān)鍵詞密文S和陷門TW計(jì)算并輸出結(jié)果.如果W∈{W1,…,Wk},輸出yes;否則,輸出no.

定義4挑戰(zhàn)者C和活躍攻擊者A之間的游戲定義如下:

C執(zhí)行KeyGen(s)生成公鑰Apub和私鑰Apriv,A獲得Apub.

A可以適應(yīng)性地向C詢問(wèn)任意關(guān)鍵字W∈{0,1}*的陷門TW.

A可以在任意時(shí)刻向C發(fā)送t+1個(gè)關(guān)鍵字W0,W1,…,Wt.C隨機(jī)選擇b∈{0,1},并將PEMKS(Apub, Wb,W2,…,Wt)的運(yùn)算結(jié)果返回給A.惟一的限制條件是A不能預(yù)先詢問(wèn)W0和W1的陷門.

A可以繼續(xù)向C詢問(wèn)任意關(guān)鍵字W∈{0,1}*(W≠W0,W1)的陷門TW.

最后,A輸出b′∈{0,1},如果b′=b,則A贏得游戲.

換言之,如果敵手能準(zhǔn)確猜出挑戰(zhàn)者隨機(jī)選擇的是W0還是W1,則贏得游戲.

定義5PEMKS是(t,qW,∈)語(yǔ)義安全的,如果所有滿足上述條件的攻擊者在t時(shí)間內(nèi),至少進(jìn)行qW次陷門詢問(wèn),才能以至多∈的優(yōu)勢(shì)贏得上述游戲.

2.2 方案構(gòu)造

假設(shè)G和GT是階為p的循環(huán)群,e:G×G→GT是雙線性對(duì),H:{0,1}*→Zp,是安全無(wú)碰撞的哈希函數(shù).PEMKS方案構(gòu)造如下:

Key Gen(s):KGC隨機(jī)選取g,h∈G和α∈Zp,計(jì)算g1=gα∈G.(g,g1,h)為Alice的公鑰,α為Alice的私鑰.將α安全遞送給Alice.

PEMKS(Apub,W1,…,Wk):Bob為關(guān)鍵字(W1,…,Wk)生成多關(guān)鍵詞密文PEMKS,步驟如下:

(1)計(jì)算H(Wi)=wi,i=1,2,…,k.

(2)根據(jù)w1,…,wk,構(gòu)造從Gk到Gk的映射和,并構(gòu)造從到的映射和.

(3)選取k個(gè)隨機(jī)數(shù)si∈Zp,i=1,2,…,k.

(6)S=〈U1,…,Uk,V1,…,Vk,M1,…,Mk〉即為PEMKS密文.

Trapdoor(Apriv,W):Alice產(chǎn)生隨機(jī)數(shù)rW∈Zp,TW=(w,rW,hW).其中w=H(W),hW=(hg-rW)1/(α-w).

Test(Apub,S,TW):郵件服務(wù)器匹配關(guān)鍵字,過(guò)程如下:

(2)判斷e(U,hW)VrW=M,是否成立,成立輸出yes;否則,輸出no.

2.2.1 正確性分析

如果Wl∈W1,…,Wk,則根據(jù)映射^r和^R的定義和式(5),有

同理可得,U=gs1lg-slwl,M=e(g,h)sl.所以有

2.2.2 安全性分析

定理1令q=qW+1.假設(shè)判定性截?cái)?t,q∈,)-ABDHE困難問(wèn)題在(G,GT,e)上成立.那么上述PEMKS系統(tǒng)是(t′,qW,∈′)語(yǔ)義安全的.其中,t′=t-O(texp·q2)∈,′=∈+2/p,texp是G上指數(shù)運(yùn)算需要的時(shí)間.

證明 假設(shè)攻擊者A在t′時(shí)間內(nèi),進(jìn)行qW次陷門詢問(wèn),以至少不可忽略的優(yōu)勢(shì)∈′攻破PEMKS系統(tǒng),那么可以構(gòu)造算法B解決判定性截?cái)?t,q,∈)-ABDHE問(wèn)題.

假設(shè)B接收到的隨機(jī)挑戰(zhàn)為(g,gα,…,gαq,g′,g′αq+2,Z),算法B處理流程如下:

KeyGen:B生成一個(gè)q次隨機(jī)多項(xiàng)式f(x)∈Zp[x].令h=gf(α),利用(g,gα,…,gαq)可計(jì)算h.將公鑰(g,gα,h)發(fā)送給A.由于g,α和f(x)都是均勻隨機(jī)選擇的,所以h是均勻隨機(jī)的,因此公鑰有著與實(shí)際構(gòu)造相同的分布.

Trapdoor queries:A進(jìn)行陷門詢問(wèn),B對(duì)詢問(wèn)W∈{0,1}*按照以下方式應(yīng)答.如果H(W)=α,B立即用α解判定性截?cái)鄎-ABDHE問(wèn)題.否則,B用FW(x)表示q-1 次多項(xiàng)式(f(x)-f(H(W)))(x-H(W)),將陷門(w,rW,hW)設(shè)置成(H(W),f(H(W)),gFW(α)).因?yàn)間FW(α)=g(f(α)-f(w))/(α-w)= (hg-f(w))1/(α-w),所以這對(duì)于關(guān)鍵字W來(lái)說(shuō),是一個(gè)有效的陷門.又因?yàn)閒(x)是一個(gè)嚴(yán)格的q次隨機(jī)多項(xiàng)式,所以在A看來(lái),這個(gè)陷門是正確生成的.

Challenge:A輸出k+1個(gè)關(guān)鍵字(W0,W1,…,Wk).同樣,如果α∈(w0=H(W0),w1=H(W1),…, wk=H(Wk)),則B立即用α解判定性截?cái)鄎-ABDHE問(wèn)題.否則,B產(chǎn)生比特b∈{0,1},并按照Trapdoor queries的方式生成Wb的陷門(wb,rWb,hWb).令f2(x)=xq+2,F2,Wi(x)=(f2(x)-f2(wi))(x-wi), i=1,2,…,k,F2,Wi(x)是q+1次多項(xiàng)式.令F2,Wi,l表示xl在F2,Wi(x)中的系數(shù).B執(zhí)行以下步驟:

(1)根據(jù)w1,…,wk,構(gòu)造從Gk到Gk的映射^r和^R,并構(gòu)造從GkT到GkT的映射^rT和^RT.

(2)選取k-1個(gè)隨機(jī)數(shù)si∈Zp,i=2,…,k.

(3)為每個(gè)i=b,2,…,k分別計(jì)算

A繼續(xù)進(jìn)行密鑰制作詢問(wèn),B按照階段1描述的方式進(jìn)行應(yīng)答.最后,敵手輸出結(jié)果b′∈{0,1}.如果b′=b,即Z=e(gαq+1,g′),則B輸出0;否則,輸出1.

1)概率分析

假設(shè)詢問(wèn)的關(guān)鍵詞中沒(méi)有某個(gè)H(W)=α(這將增加B的成功概率).可以看出,當(dāng)(g′,g′αq+2,g,gα,…,gαq,Z)選自RABDHE時(shí),然而當(dāng)(g′,g′αq+2,g,gα,…,gαq,Z)選自PABDHE時(shí),因此,對(duì)于均勻隨機(jī)的g,g′,α,Z,可以得出

此時(shí)A將以不可忽略的概率∈′-2/p正確地猜出b.

2)時(shí)間復(fù)雜度

在模擬過(guò)程中,B的計(jì)算花銷集中在為A針對(duì)關(guān)鍵字W陷門詢問(wèn)計(jì)算gFW(α),此處FW(x)是一個(gè)q-1次多項(xiàng)式,計(jì)算需要O(q)個(gè)G上的指數(shù)運(yùn)算.由于A最多可執(zhí)行q-1次陷門詢問(wèn),所以t=t′+O(texp·q2).

定理證明完畢.定理1說(shuō)明了在標(biāo)準(zhǔn)模型下PEMKS方案滿足定義5的語(yǔ)義安全條件.

2.2.3 效率比較

本節(jié)將比較BDOP[1]、BW[6]、ZZ[7]以及文中方案的效率,給出各方案在生成密文、生成陷門和關(guān)鍵詞匹配等關(guān)鍵步驟的運(yùn)算量.其中,a表示群G中一次冪運(yùn)算,b表示群GT中的一次冪運(yùn)算,e表示一次雙線性對(duì)運(yùn)算,n表示關(guān)鍵字總數(shù),k表示密文攜帶的關(guān)鍵字?jǐn)?shù)量.效率比較結(jié)果如表1所示.

一般地,在構(gòu)造具有雙線性對(duì)運(yùn)算的橢圓曲線時(shí),嵌入次數(shù)選擇2或3,此時(shí)e的運(yùn)算量遠(yuǎn)大于a和b.一般將全體字符串集作為關(guān)鍵字集合,可以認(rèn)為n遠(yuǎn)大于k.效率分析如下:

表1 效率比較

(1)生成密文:BDOP方案和ZZ方案需要e運(yùn)算,BW方案需要大量a,而文中方案僅需要較少的a和b,效率優(yōu)勢(shì)明顯.

(2)生成陷門:ZZ方案a運(yùn)算的次數(shù)與k相關(guān),但通常k(k＞1)較小.所以,可認(rèn)為BDOP方案的效率較高,但各方案運(yùn)算量差別不大.

(3)關(guān)鍵詞匹配:關(guān)鍵詞匹配需要服務(wù)器根據(jù)用戶請(qǐng)求及時(shí)給出結(jié)果.針對(duì)單個(gè)密文的關(guān)鍵字匹配過(guò)程中,BDOP方案和ZZ方案e運(yùn)算的次數(shù)與k(k＞1)相關(guān),BW方案需要3次e運(yùn)算,而文中方案僅需要1次e運(yùn)算,效率優(yōu)勢(shì)明顯.

綜上,文中方案與其他3個(gè)方案相比具有較高的效率.

3 結(jié)束語(yǔ)

筆者研究了可搜索公鑰加密方案中如何快速判定某一關(guān)鍵字是否屬于某關(guān)鍵詞集合的問(wèn)題.提出了支持多關(guān)鍵字的可搜索加密模型PEMKS,并利用拉格朗日插值多項(xiàng)式構(gòu)造出一種高效的、具有可證明安全性的PEMKS方案.該方案將密文搜索的雙線性對(duì)計(jì)算量降低到O(1),并且沒(méi)有類似于BW方案中的關(guān)鍵詞假設(shè)和其它限制條件.未來(lái)將針對(duì)云存儲(chǔ)環(huán)境繼續(xù)改進(jìn)該方案,使其擁有更短的關(guān)鍵字密文、更高的搜索效率以及更強(qiáng)的搜索能力.

[1]Boneh D,Di C G,Ostrovsky R,et al.Public Key Encryption with Keyword Search[C]//Lecture Notes in Computer Science:3027.Berlin:Springer-Verlag,2004:506-522.

[2]Boneh D,Franklin M.Identity-based Encryption from the Weil Pairing[C]//Lecture Notes in Computer Science:2139. Berlin:Springer-Verlag,2001:213-229.

[3]Blazy O,Kiltz E,Pan J X.(Hierarchical)Identity-based Encryption from Affine Message Authentication[C]//Lecture Notes in Computer Science:8617.Berlin:Springer-Verlag,2014:408-425.

[4]Lai J Z,Deng R H,Liu S L,et al.Identity-based Encryption Secure Against Selective Opening Chosen-ciphertext Attack [C]//Lecture Notes in Computer Science:8441.Berlin:Springer-Verlag,2014:77-92.

[5]Chen J,Wee H.Fully,(almost)Tightly Secure IBE and Dual System Groups[C]//Lecture Notes in Computer Science: 8043.Berlin:Springer-Verlag,2013:435-460.

[6]Boneh D,Waters B.Conjunctive,Subset,and Range Queries on Encrypted Data[C]//Lecture Notes in Computer Science:4392.Berlin:Springer-Verlag,2007:535-554.

[7]Zhang B,Zhang F G.An Efficient Public Key Encryption with Conjunctive-subset Keywords Search[J].Journal of Network and Computer Applications,2011,34(1):262-267.

[8]Kawai Y,Takashima K.Predicate-and Attribute-hiding Inner Product Encryption in a Public Key Setting[C]//Lecture Notes in Computer Science:8365.Berlin:Springer-Verlag,2013:113-130.

[9]B?sch C,Hartel P,Jonker W,et al.A Survey of Provably Secure Searchable Encryption[J].ACM Computing Surveys, 2014,47(2):03600300.

(編輯:王 瑞)

Public key encryption with multi-keywords search

LI Haoxing1,LI Fenghua2,SONG Chenggen3,SU Mang3,LIU Xin3
(1.State Key Lab.of Integrated Service Networks,Xidian Univ.,Xi’an 710071,China;2.Institute of Information Engineering,Chinese Academy of Sciences,Beijing 100093,China;3.Institute of Information Security,Beijing Electronic Science and Technology Institute,Beijing 100070,China)

In order to improve the server-side keywords-searching efficiency in public key encryption by keyword search schemes,we propose a method of constructing reciprocal maps based on lagrange polynomial and a public key encryption by multi-keywords search scheme.In the scheme,each couple of reciprocal maps corresponds to a set of keywords.The sender makes ciphertext transformation for the set of keywords,and sends the result to the server.The receiver sends a searching-keyword trapdoor to the server.The server can restore the ciphertext of the keyword corresponding to the trapdoor for matching, only if the keyword belongs to the set.Only one pair computing is required to finish multi-keywords searching.The scheme is semantically secure in the standard model,and has a high efficiency of keywords searching with no restriction.

searchable encryption;multikeywords search;security proof;privacy;cloud storage

TN918.1

A

1001-2400(2015)05-0020-06

2014-09-03< class="emphasis_bold">網(wǎng)絡(luò)出版時(shí)間:

時(shí)間:2014-12-23

國(guó)家自然科學(xué)基金資助項(xiàng)目(61170251);數(shù)字版權(quán)保護(hù)技術(shù)研發(fā)工程資助項(xiàng)目(1681300000119);國(guó)家863高技術(shù)研究發(fā)展計(jì)劃資助項(xiàng)目(2012AA013102);國(guó)家863高技術(shù)研究發(fā)展計(jì)劃資助項(xiàng)目(2012AA01A401)

李昊星(1982-),男,西安電子科技大學(xué)博士研究生,E-mail:lhx595@126.com.

李鳳華(1965-),男,教授,博士,E-mail:fhli@iie.ac.cn.

http://www.cnki.net/kcms/detail/61.1076.TN.20141223.0946.004.html

10.3969/j.issn.1001-2400.2015.05.004