支持多關鍵字的可搜索公鑰加密方案

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

(1.西安電子科技大學綜合業務網理論及關鍵技術國家重點實驗室,陜西西安 710071;2.中國科學院信息工程研究所,北京 100093;3.北京電子科技學院信息安全研究所,北京 100070)

支持多關鍵字的可搜索公鑰加密方案

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

(1.西安電子科技大學綜合業務網理論及關鍵技術國家重點實驗室,陜西西安 710071;2.中國科學院信息工程研究所,北京 100093;3.北京電子科技學院信息安全研究所,北京 100070)

為了提升可搜索公鑰加密方案中服務器端關鍵字的搜索效率,提出了基于拉格朗日多項式的互逆映射構造方法和支持多關鍵字的可搜索加密公鑰方案.該方案中,每組關鍵字對應一對互逆映射,發送者將該組關鍵字密文的變換結果輸出給服務器,接收者向服務器發送陷門,只有當陷門關鍵字屬于該組關鍵字時,服務器才能還原出陷門關鍵字的密文以進行匹配計算,僅需一次雙線性對計算即可搜索多個關鍵字.該方案在標準模型中是語義安全的,關鍵字匹配效率較高且沒有限制條件.

可搜索加密;多關鍵字搜索;安全性證明;隱私;云存儲

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

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

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

基于身份的可搜索加密無需數字證書,密鑰管理機制簡單,適合在云存儲環境中應用.但上述方案均沒有很好地切合可搜索加密的主要目的,引入了多余的計算量或引入了不必要的限制條件,使得方案整體效率或對單個文件進行關鍵字搜索的效率較低.

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

1 預備知識

1.1 判定性截斷(t,q,∈)-ABDHE假設

假設G是階為素數p的循環群,g為G中的生成元.GT是乘法循環群,且與G同階.e:G×G→GT是一個雙線性對.

定義敵手B的優勢函數AqG-,ABBDHE(λ)如下:

此處,P表示事件發生的概率,g′=gz∈G,a,z,r∈Zp,是隨機選取的.如果在時間t內,對于所有敵手B的＜∈,則稱判定性截斷(t,q,∈)-ABDHE假設成立.優勢函數中減號左邊的分布記為Pq-ABDHE,減號右邊的分布記為Rq-ABDHE.

1.2 拉格朗日插值多項式

對于k個不同的數xi(i=1,2,…,k)可以得到k個k-1次多項式

且有

多項式Ft(x)和xt-1的次數最大為k-1,而它們在k個相同的點取值相同,所以有

進而有

設G是階為素數p的循環群,對于k個不同的數xi∈Zp,i=1,2,…,k,可以構建出兩個與上述fi(x)定義有關的從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 支持多關鍵字搜索的公鑰加密

2.1 基本定義

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

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

定義3PEMKS方案包含以下概率多項式時間算法:

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

PEMKS(Apub,W1,…,Wk):Bob根據Alice的公鑰和關鍵字W1,…,Wk構造一個多關鍵詞密文,簡稱S.

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

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

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

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

A可以適應性地向C詢問任意關鍵字W∈{0,1}*的陷門TW.

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

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

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

換言之,如果敵手能準確猜出挑戰者隨機選擇的是W0還是W1,則贏得游戲.

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

2.2 方案構造

假設G和GT是階為p的循環群,e:G×G→GT是雙線性對,H:{0,1}*→Zp,是安全無碰撞的哈希函數.PEMKS方案構造如下:

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

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

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

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

(3)選取k個隨機數si∈Zp,i=1,2,…,k.

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

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

Test(Apub,S,TW):郵件服務器匹配關鍵字,過程如下:

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

2.2.1 正確性分析

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

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

2.2.2 安全性分析

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

證明 假設攻擊者A在t′時間內,進行qW次陷門詢問,以至少不可忽略的優勢∈′攻破PEMKS系統,那么可以構造算法B解決判定性截斷(t,q,∈)-ABDHE問題.

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

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

Trapdoor queries:A進行陷門詢問,B對詢問W∈{0,1}*按照以下方式應答.如果H(W)=α,B立即用α解判定性截斷q-ABDHE問題.否則,B用FW(x)表示q-1 次多項式(f(x)-f(H(W)))(x-H(W)),將陷門(w,rW,hW)設置成(H(W),f(H(W)),gFW(α)).因為gFW(α)=g(f(α)-f(w))/(α-w)= (hg-f(w))1/(α-w),所以這對于關鍵字W來說,是一個有效的陷門.又因為f(x)是一個嚴格的q次隨機多項式,所以在A看來,這個陷門是正確生成的.

Challenge:A輸出k+1個關鍵字(W0,W1,…,Wk).同樣,如果α∈(w0=H(W0),w1=H(W1),…, wk=H(Wk)),則B立即用α解判定性截斷q-ABDHE問題.否則,B產生比特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次多項式.令F2,Wi,l表示xl在F2,Wi(x)中的系數.B執行以下步驟:

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

(2)選取k-1個隨機數si∈Zp,i=2,…,k.

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

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

1)概率分析

假設詢問的關鍵詞中沒有某個H(W)=α(這將增加B的成功概率).可以看出,當(g′,g′αq+2,g,gα,…,gαq,Z)選自RABDHE時,然而當(g′,g′αq+2,g,gα,…,gαq,Z)選自PABDHE時,因此,對于均勻隨機的g,g′,α,Z,可以得出

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

2)時間復雜度

在模擬過程中,B的計算花銷集中在為A針對關鍵字W陷門詢問計算gFW(α),此處FW(x)是一個q-1次多項式,計算需要O(q)個G上的指數運算.由于A最多可執行q-1次陷門詢問,所以t=t′+O(texp·q2).

定理證明完畢.定理1說明了在標準模型下PEMKS方案滿足定義5的語義安全條件.

2.2.3 效率比較

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

一般地,在構造具有雙線性對運算的橢圓曲線時,嵌入次數選擇2或3,此時e的運算量遠大于a和b.一般將全體字符串集作為關鍵字集合,可以認為n遠大于k.效率分析如下:

表1 效率比較

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

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

(3)關鍵詞匹配:關鍵詞匹配需要服務器根據用戶請求及時給出結果.針對單個密文的關鍵字匹配過程中,BDOP方案和ZZ方案e運算的次數與k(k＞1)相關,BW方案需要3次e運算,而文中方案僅需要1次e運算,效率優勢明顯.

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

3 結束語

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

[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">網絡出版時間:

時間:2014-12-23

國家自然科學基金資助項目(61170251);數字版權保護技術研發工程資助項目(1681300000119);國家863高技術研究發展計劃資助項目(2012AA013102);國家863高技術研究發展計劃資助項目(2012AA01A401)

李昊星(1982-),男,西安電子科技大學博士研究生,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