支持聯(lián)合查詢(xún)的高效可搜索對(duì)稱(chēng)加密方案

古宜平， 馬昌社

(華南師范大學(xué)計(jì)算機(jī)學(xué)院， 廣州 510631)

基于云服務(wù)的數(shù)據(jù)外包技術(shù)可以有效地減負(fù)用戶(hù)的本地資源開(kāi)銷(xiāo). 然而，云服務(wù)器并非完全安全可靠，其一般被認(rèn)為是誠(chéng)實(shí)卻好奇的，它誠(chéng)實(shí)執(zhí)行程序，卻不具有可控性，存在窺探用戶(hù)數(shù)據(jù)的威脅. 因此，用戶(hù)的普遍做法是對(duì)數(shù)據(jù)先加密后上傳. 但對(duì)數(shù)據(jù)采用標(biāo)準(zhǔn)加密算法加密后，完全破壞了數(shù)據(jù)的可搜索性，一個(gè)解決此問(wèn)題的直接方法是用戶(hù)先將所有加密數(shù)據(jù)下載到本地，然后進(jìn)行解密，對(duì)明文進(jìn)行搜索. 但這種操作并不具有可用性，因?yàn)橐环矫嬉蛳螺d了大部分不需要的數(shù)據(jù)而浪費(fèi)帶寬；另一方面解密所有密文又占用了用戶(hù)大量的本地存儲(chǔ)和計(jì)算開(kāi)銷(xiāo). 而理想的做法是由服務(wù)器利用其強(qiáng)大的資源進(jìn)行檢索，將搜索結(jié)果返回給用戶(hù)，同時(shí)保證泄露給服務(wù)器的信息足夠少，以最大限度地保證數(shù)據(jù)隱私安全性.

為解決這類(lèi)問(wèn)題，可搜索對(duì)稱(chēng)加密(Searchable Symmetric Encryption，SSE)技術(shù)[1-4]應(yīng)運(yùn)而生. 自從SONG等[1]于2000年提出第1個(gè)SSE方案后，學(xué)者們提出了一批涉及功能、性能和安全之間權(quán)衡的SSE方案[2-4]. 其中，功能方面描述方案支持的數(shù)據(jù)集結(jié)構(gòu)和查詢(xún)類(lèi)型，性能方面分析方案的存儲(chǔ)大小、用戶(hù)和服務(wù)器的計(jì)算量、交互輪數(shù)及帶寬開(kāi)銷(xiāo)，安全方面分析和概括數(shù)據(jù)集的加密結(jié)果和查詢(xún)過(guò)程的全部泄露. 2004年，GOLLE等[5]最先針對(duì)聯(lián)合查詢(xún)提出2個(gè)SSE方案，此后，一系列工作[6-9]改進(jìn)了聯(lián)合查詢(xún)的性能和安全，包括將IND-CKA(Indistinguishability under Chosen Keyword Attacks)安全從單關(guān)鍵字查詢(xún)推廣到多關(guān)鍵字查詢(xún)，減少查詢(xún)過(guò)程中客戶(hù)端和服務(wù)器的計(jì)算量和交互開(kāi)銷(xiāo)，減少存儲(chǔ)開(kāi)銷(xiāo)，使得數(shù)據(jù)集的文檔不需要關(guān)聯(lián)關(guān)鍵字集. 但是，這些方案的查詢(xún)效率皆與數(shù)據(jù)集的大小呈線(xiàn)性關(guān)系，直到2013年，采用基于Diffie-Hellman類(lèi)型操作的安全兩方計(jì)算，CASH等[10]針對(duì)聯(lián)合查詢(xún)提出第一個(gè)亞線(xiàn)性的SSE方案(Oblivious Cross-Tags，OXT). 但面對(duì)大量數(shù)據(jù)時(shí)，計(jì)算量開(kāi)銷(xiāo)大的Diffie-Hellman類(lèi)型操作[11]將成為該方案的計(jì)算性能瓶頸.

為了提高支持聯(lián)合查詢(xún)的可搜索對(duì)稱(chēng)加密方案的計(jì)算性能，本文提出一個(gè)支持聯(lián)合查詢(xún)的高效可搜索對(duì)稱(chēng)加密方案(Efficient Cross-Tags，EXT). 該方案采用客戶(hù)端單獨(dú)計(jì)算關(guān)鍵字與文檔之間的關(guān)系，并交給服務(wù)器檢驗(yàn)這一關(guān)系的方法來(lái)實(shí)現(xiàn)聯(lián)合查詢(xún)，從而避免Diffie-Hellman類(lèi)型操作. 另外，從正確性、安全性以及性能方面對(duì)該方案進(jìn)行分析.

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

本節(jié)對(duì)本文的符號(hào)進(jìn)行說(shuō)明，并列舉方案構(gòu)造以及分析用到的密碼學(xué)原語(yǔ).

1.1 符號(hào)說(shuō)明

設(shè)C(·)為概率多項(xiàng)式時(shí)間(PPT，Probabilistic Polynomial Time)算法，c←C(·)表示算法C(·)的輸出賦值給變量c. 假設(shè)a和b為正整數(shù)，且aN0，皆有neg()<1/p()，則稱(chēng)neg()是可忽略函數(shù). 令?表示空集或空字符串.

1.2 可搜索對(duì)稱(chēng)加密

一般地，在SSE方案中，客戶(hù)端先在本地加密數(shù)據(jù)集，然后將加密結(jié)果存儲(chǔ)于服務(wù)器. 為了讓服務(wù)器能夠基于加密結(jié)果進(jìn)行查詢(xún)，客戶(hù)端基于明文數(shù)據(jù)集生成加密的索引數(shù)據(jù)結(jié)構(gòu). 以下是可搜索對(duì)稱(chēng)加密方案的形式化定義：

定義1[1](可搜索對(duì)稱(chēng)加密方案)給定安全參數(shù),SSE方案Π=(Setup,Search)由初始化加密算法Setup和查詢(xún)協(xié)議Search組成. 其中，Setup算法運(yùn)行于客戶(hù)端，Search協(xié)議由客戶(hù)端和服務(wù)器通過(guò)交互共同完成. 方案的具體過(guò)程為：

(1)(SK,EDB)←Setup(1,DB)：系統(tǒng)初始化算法. 給定明文數(shù)據(jù)集DB，該算法輸出密鑰SK和數(shù)據(jù)集密文EDB. 其中,客戶(hù)端秘密存儲(chǔ)SK，服務(wù)器存儲(chǔ)EDB.

對(duì)于SSE方案Π，用泄漏函數(shù)表示誠(chéng)實(shí)卻好奇的服務(wù)器能夠從數(shù)據(jù)集的加密結(jié)果和查詢(xún)過(guò)程中分析得到的有用信息. 下面是SSE方案的語(yǔ)義安全的形式化定義：

定義2[12-13](SSE方案的語(yǔ)義安全)給定SSE方案Π=(Setup,Search). 對(duì)于PPT敵手和仿真器，定義算法)和)如下：

1.3 T-Set方案

T-Set方案是倒排索引數(shù)據(jù)結(jié)構(gòu)的具體實(shí)現(xiàn)之一. 一般地，T-Set方案包含3個(gè)算法：TSSetup、TSGetTag和TSRetrieve. 這些算法的具體定義、安全以及實(shí)現(xiàn)均可參照文獻(xiàn)[10]. 本文采用文獻(xiàn)[14]設(shè)計(jì)的T-Set方案Πbas，其具體實(shí)現(xiàn)及安全性描述如下：

(2)stag←TSGetTag(KT,w)：計(jì)算K1||K2←F(KT,w)，令stag←K1||K2作為w的查詢(xún)陷門(mén).

(3)Tw←TSRetrieve(D,stag)：首先，展開(kāi)stag為K1||K2，令Tw←?，c←1，計(jì)算←F(K1,c). 然后，一直執(zhí)行以下循環(huán)直至D[]=⊥：解密Tw[c]←Dec(K2,D[l])，令c←c+1，計(jì)算←F(K1,c).

定理1[14]在隨機(jī)預(yù)言機(jī)模型下，假設(shè)F是安全的偽隨機(jī)函數(shù)，(Enc,Dec)是IND-CPA安全的對(duì)稱(chēng)加密方案，那么Πbas方案在自適應(yīng)式攻擊下是T(T,q)安全的.

1.4 困難性假設(shè)

以下分別給出偽隨機(jī)函數(shù)以及IND-CPA(Indistinguishability under Chosen-Plaintext Attacks)安全的對(duì)稱(chēng)加密方案的定義.

定義3[15](偽隨機(jī)函數(shù))稱(chēng)函數(shù)F:{0,1}×{0,1}n→{0,1}m為偽隨機(jī)函數(shù)，如果對(duì)于任意PPT敵手，都有

成立，其中第1個(gè)概率依賴(lài)于K{0,1}的均勻隨機(jī)性和敵手的隨機(jī)性，第2個(gè)概率依賴(lài)于fFun({0,1}n,{0,1}m)的均勻隨機(jī)性和敵手的隨機(jī)性.

定義4[16](IND-CPA安全的對(duì)稱(chēng)加密方案)對(duì)稱(chēng)加密方案(Symmetric Encryption Scheme，SKE)Ω=(Gen,Enc,Dec)包含3個(gè)算法. 給定安全參數(shù)，算法Gen輸出密鑰K{0,1}. 算法Enc的輸入為密鑰K{0,1}和明文M，輸出為密文C. 算法Dec的輸入為密鑰K{0,1}和密文C，輸出為明文M. 方案需要保證對(duì)任意合法的密鑰K和明文M都具有計(jì)算正確性. 稱(chēng)方案Ω為IND-CPA安全的SKE方案，如果對(duì)任意PPT敵手，都有

2 EXT方案

算法1EXT系統(tǒng)初始化算法

輸入：1，DB

輸出：SK，EDB

Step 2. 分別為偽隨機(jī)函數(shù)FC和FS選擇相應(yīng)的密鑰KC和KS；初始化T←?，XSet←?；

Step 3. 對(duì)每個(gè)wW執(zhí)行以下步驟：

初始化鏈表tw←?；計(jì)算Ke←FS(KS,w)；

e←Enc(Ke,id)，將e添加到tw；

xtag←FC(KC,w||id)，XSet←XSet∪{xtag}；

令T[w]←tw；

Step 4. (D,KT)←TSSetup(T)；

Step 5. 令SK←(KC,KS,KT)，EDB←(D,XSet)，返回SK，EDB.

圖1 EXT查詢(xún)協(xié)議

以下是算法Setup和協(xié)議Search的詳細(xì)過(guò)程：

(1)Setup(1,DB)：首先，展開(kāi)明文數(shù)據(jù)集并分別為偽隨機(jī)函數(shù)FS和FC選擇相應(yīng)密鑰KS和KC，以及初始化數(shù)組T←?和集合XSet←?. 然后，按如下步驟生成D：(i)對(duì)于所有wW，初始化鏈表tw←?并計(jì)算Ke←FS(KS,w);(ii)對(duì)每個(gè)wW,對(duì)每個(gè)idDB[w],加密e←Enc(Ke,id)并將e插入鏈表tw，令T[w]←tw；(iii)調(diào)用算法(D,KT)←TSSetup(T). 其次，對(duì)每對(duì)(w,id)(idDB[w])，計(jì)算xtag←FC(KC,w||id)并更新集合XSet←XSet∪{xtag}. 最后，輸出SK←(KC,KS,KT)和EDB←(D,XSet).

Step 1. 客戶(hù)端調(diào)用算法stag←TSGetTag(KT,w1)并發(fā)送stag給服務(wù)器.

Step 2. 服務(wù)器調(diào)用算法tw1←TSRetrieve(D,stag)并發(fā)送tw1給客戶(hù)端.

Step 3. 客戶(hù)端首先計(jì)算Ke←FS(KS,w1)，然后按如下步驟生成XTags：①對(duì)所有c[1,|tw1|]，令ec←tw1[c]，解密idc←Dec(Ke,ec)；②對(duì)每個(gè)[2,n],計(jì)算XTags[c,]←FC(KC,w||idc). 最后發(fā)送XTags給服務(wù)器.

Step 4. 服務(wù)器首先初始化集合E←?；然后，對(duì)所有c[1,|tw1|]，如果對(duì)所有[2,n]均有XTags[c,]XSet，則更新集合E←E∪{c}；最后，發(fā)送E給客戶(hù)端.

Step 5. 客戶(hù)端首先初始化集合R←?；然后，對(duì)所有cE更新集合R←R∪{idc}；最后，輸出R.

3 方案分析

3.1 正確性分析

以下給出EXT方案的正確性分析.

定理2假設(shè)(TSSetup,TSGetTag,TSRetrieve)是具有計(jì)算正確性的T-Set方案，F(xiàn)C和FS是安全的偽隨機(jī)函數(shù)，那么對(duì)于任意PPT敵手，均有)=1]≤neg()，即EXT具有計(jì)算正確性.

3.2 安全性分析

證明定義一系列游戲G0,G1,…,G6以及仿真器，使得游戲G0與)具有相同的分布，游戲G6與仿真器具有相同的分布. 其中游戲G0,G1,…,G6輸入(DB,q)，仿真器輸入EXT(DB,q)，而游戲G0,G1,…,G6和仿真器均向敵手提供二元組(EDB,Tr). 最后，游戲和仿真器均輸出敵手返回的判斷值. 如果對(duì)任意i(0≤i<6)，都有|Pr[Gi=1]-Pr[Gi+1=1]|≤neg()，則

下面分別構(gòu)造游戲G0,G1,…,G6和仿真器，并分別證明),G0,…,G6,中所有相鄰的2個(gè)分布計(jì)算不可區(qū)分.

(1)游戲G0：

②生成EDB[1]：首先，初始化集合XSet←?；然后，對(duì)每對(duì)(w,id)(idDB[w])，計(jì)算xtag←FC(KC,w‖id)，并更新集合XSet←XSet∪{xtag}；最后，令EDB[1]←XSet.

③生成Tr[1]：(i)對(duì)每個(gè)i[1,Q]，按如下步驟生成XTags[i]：首先，調(diào)用算法ti←TSRetrieve(D,STags[i])，計(jì)算Ke←FS(KS,w1)；其次，對(duì)每個(gè)c[1,|DB[s[i]]|],解密idc←Dec(Ke,ti[c])，并計(jì)算XTags[i,c]←FC(KC,x[i]‖idc). (ii)令Tr[1]←XTags.

(2)游戲G1：

②生成EDB[1]：首先，初始化集合XSet←?；然后，對(duì)每對(duì)(w,id)(idDB[w]),調(diào)用xtag←A[w,id]并更新集合XSet←XSet∪{xtag}；最后,令EDB[1]←XSet.

③生成Tr[1]：(i)對(duì)每個(gè)i[1,Q],按如下步驟生成XTags[i]：首先，展開(kāi)讀取排列σ←Wperms[s[i]]；然后，對(duì)每個(gè)c[1,Ts],令令Tr[1]←XTags.

相較于游戲G0，游戲G1首先生成數(shù)組A，即對(duì)每對(duì)(w,id)計(jì)算A[w,id]←FC(KC,w‖id)；然后，在XSet和XTags的構(gòu)建中需要調(diào)用FC的地方直接引用A相應(yīng)的值. 因?yàn)檫@部分內(nèi)容只包含表達(dá)上的更改，所以

Pr[G1=1]=Pr[G0=1].

(3)游戲G2：將偽隨機(jī)函數(shù)FS和FC替代為隨機(jī)函數(shù). 將游戲G1的②③保持不變，僅將G1的①作如下修改：

因?yàn)镕S與FC是安全的偽隨機(jī)函數(shù)，所以存在PPT敵手2,1和2,2，使得

由于(End,Dec)是IND-CPA安全的SKE，而且對(duì)0的加密次數(shù)是關(guān)于的多項(xiàng)式次，即poly()次，則存在PPT敵手3，使得

|Pr[G3=1]-Pr[G2=1]|≤poly().

(5)游戲G4：將游戲G3第①部分中生成字典D的語(yǔ)句(D,KT)←TSSetup(T)和生成STags的語(yǔ)句STags[i]←TSGetTag(KT,s[i])改為(D,STags)←T(T(T,s))，其中T是T-Set的PPT仿真器.

因?yàn)?TSSetup,TSGetTag,TSRetrieve)是在(非自適應(yīng)式)攻擊下具有T安全的T-Set方案，所以，存在PPT敵手4，使得

(6)游戲G5：將游戲G4的第②部分作如下修改，其他部分保持不變:

生成EDB[1]：首先，初始化集合XSet←?；然后，對(duì)每對(duì)(w,id)(idDB[w])，判斷是否存在i使得idDB[s[i]]∧x[i]=w，是則讀取xtag←A[w,id]，否則隨機(jī)生成并更新集合XSet←XSet∪{xtag}；最后，令EDB[1]←XSet.

Pr[G5=1]=Pr[G4=1].

(7)游戲G6：將游戲G5的第③部分作如下修改，其他部分保持不變.

生成Tr[1]：(i)對(duì)每個(gè)i[1,Q]執(zhí)行如下步驟生成XTags[i]：首先，展開(kāi)讀取排列σ←Wperms[s[i]]；然后，對(duì)每個(gè)c[1,Ts]，如果DB[s[i]]∩DB[x[i]]，則令否則，如果DB[s[j]]∧x[j]=x[i]，則令否則令令Tr[1]←XTags.

游戲G6改變XTags構(gòu)建過(guò)程中訪問(wèn)A的模式. 為保證敵手能夠檢驗(yàn)的XTags模式與游戲G5的相同，對(duì)每對(duì)(w,id)，如果查詢(xún)中XTags[w,id]理應(yīng)含于XSet，則令XTags[w,id]←A[w,id]，如果XTags存在另一個(gè)元素XTags[w′,id′]，使得XTags[w,id]=XTags[w′,id′]，亦令XTags[w,id]←A[w,id]. 這些改變恰好使得敵手能夠檢驗(yàn)的XTags模式與游戲G5的相同,則

Pr[G6=1]=Pr[G5=1].

(1)

(2)

①生成EDB[0]與Tr[0]：(i)對(duì)每對(duì)(w,id)(w∪i(RP[i]∪∪j≠iIP[i,j])),令(ii)按如下步驟生成D和STags：首先，對(duì)所有w選擇生成排列且記錄此排列Wperms[w]←σ，初始化鏈表tw←?并生成密鑰然后，對(duì)每個(gè)w對(duì)每個(gè)c[1,SP[w]]，加密e←Enc(Ke,0)且令tw[c]←e，令T[w]←tw；最后，令且調(diào)用算法(D,STags)←T(T(DB,s)，T[s]). (iii)令EDB[0]←D，Tr[0]←STags.

②生成EDB[1]：首先，初始化集合XSet←?；然后，對(duì)每對(duì)(w,id)(w更新集合XSet←XSet∪{A[w,id]}；其次，令j←|XSet|，并從i=j+1到N，依次隨機(jī)抽取并更新集合XSet←XSet∪{h}；最后，令EDB[1]←XSet.

③生成Tr[1]：(i)對(duì)每個(gè)i[1,Q],按如下步驟生成XTags[i]：首先，生成集合Ri←RP[i]∪∪j≠iIP[i,j]且令T′←|Ri|；然后，讀取排列展開(kāi)最后，對(duì)每個(gè)c[1,SP[i]]，判斷是否有是則令否則令令Tr[1]←XTags.

3.3 性能分析

本節(jié)從計(jì)算量、存儲(chǔ)開(kāi)銷(xiāo)、交互開(kāi)銷(xiāo)等性能方面，對(duì)OXT方案和EXT方案進(jìn)行對(duì)比分析.

在初始化加密算法中，OXT、EXT方案生成的字典D和集合XSet分別包括N個(gè)元組. OXT方案采用一個(gè)PRF計(jì)算和一個(gè)SKE加密生成D的每個(gè)元組，采用一個(gè)DH類(lèi)型操作生成XSet的每個(gè)元組；而EXT方案采用一個(gè)SKE加密生成D的每個(gè)元組，采用一個(gè)PRF計(jì)算生成XSet的每個(gè)元組. 最后，為節(jié)省存儲(chǔ)開(kāi)銷(xiāo)，OXT、EXT方案均把XSet轉(zhuǎn)換成布隆過(guò)濾器進(jìn)行存儲(chǔ). 此過(guò)程中，OXT、EXT方案的計(jì)算量分別為N(TF+TE+Te)+NkTh、N(TE+TF)+NkTh. 另外，OXT、EXT方案的存儲(chǔ)開(kāi)銷(xiāo)分別為N(E+p)+m、N(E)+m.

在查詢(xún)協(xié)議中，假設(shè)查詢(xún)?yōu)閣1∧w2∧…∧wn. 在OXT方案中，首先,客戶(hù)端生成stag和xtoken并傳給服務(wù)器；然后，服務(wù)器生成相應(yīng)的xtag，并查看這些xtag相對(duì)于XSet的子集關(guān)系，把滿(mǎn)足查詢(xún)的加密id傳給客戶(hù)端；最后，客戶(hù)端解密得到查詢(xún)結(jié)果. 這個(gè)過(guò)程中，客戶(hù)端、服務(wù)器的計(jì)算量分別為T(mén)F+α(nTF+(n-1)Te)+βTD、α(n-1)(Te+kTh). 另外，這個(gè)過(guò)程涉及兩輪交互，其帶寬開(kāi)銷(xiāo)為F+|t|+α(n-1)D+βE. 而在EXT方案中，首先，客戶(hù)端生成stag以得到服務(wù)器的查詢(xún)結(jié)果T[w1]；然后，客戶(hù)端據(jù)此生成相應(yīng)的xtag并傳給服務(wù)器；其次，服務(wù)器查看這些xtag相對(duì)于XSet的子集關(guān)系，并把滿(mǎn)足查詢(xún)的id項(xiàng)編號(hào)傳給客戶(hù)端；最后，客戶(hù)端輸出查詢(xún)結(jié)果. 這個(gè)過(guò)程中，客戶(hù)端、服務(wù)器的計(jì)算量分別為T(mén)F+α(TD+(n-1)TF)、α(n-1)kTh. 另外，這個(gè)過(guò)程依舊涉及兩輪交互，其帶寬開(kāi)銷(xiāo)為F+αE+α(n-1)F+β|t|.

表1 OXT方案與EXT方案的性能比較Table 1 Evaluations of the overheads between OXT and EXT %

4 結(jié)論

本文提出了一個(gè)支持聯(lián)合查詢(xún)的高效可搜索對(duì)稱(chēng)加密方案EXT，與OXT方案相比較，EXT方案在保證相同功能和安全的情況下將系統(tǒng)初始化的計(jì)算量、查詢(xún)時(shí)客戶(hù)端的計(jì)算量、查詢(xún)時(shí)服務(wù)器的計(jì)算量、存儲(chǔ)開(kāi)銷(xiāo)分別降低了95.05%、97.67%、98.48%、55.05%.

支持動(dòng)態(tài)操作的SSE方案具有更大的實(shí)用性，而把EXT方案實(shí)現(xiàn)為支持動(dòng)態(tài)操作的SSE方案并同時(shí)保證其前向安全和后向安全，需要使其T-Set方案和集合XSet同時(shí)支持動(dòng)態(tài)操作. 目前已有一些研究[4,18]著力于實(shí)現(xiàn)支持動(dòng)態(tài)操作的T-Set方案，因此，如何實(shí)現(xiàn)支持動(dòng)態(tài)操作的集合XSet可作為進(jìn)一步的研究方向.