古宜平， 馬昌社

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

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

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

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

1 預(yù)備知識

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

1.1 符號說明

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

1.2 可搜索對稱加密

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

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

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

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

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

1.3 T-Set方案

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

(2)stag←TSGetTag(KT,w)：計算K1||K2←F(KT,w)，令stag←K1||K2作為w的查詢陷門.

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

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

1.4 困難性假設(shè)

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

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

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

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

2 EXT方案

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

輸入：1，DB

輸出：SK，EDB

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

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

初始化鏈表tw←?；計算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查詢協(xié)議

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

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

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

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

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

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

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

3 方案分析

3.1 正確性分析

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

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

3.2 安全性分析

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

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

(1)游戲G0：

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

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

(2)游戲G1：

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

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

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

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

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

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

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

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

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

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

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

生成EDB[1]：首先，初始化集合XSet←?；然后，對每對(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)對每個i[1,Q]執(zhí)行如下步驟生成XTags[i]：首先，展開讀取排列σ←Wperms[s[i]]；然后，對每個c[1,Ts]，如果DB[s[i]]∩DB[x[i]]，則令否則，如果DB[s[j]]∧x[j]=x[i]，則令否則令令Tr[1]←XTags.

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

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

(1)

(2)

①生成EDB[0]與Tr[0]：(i)對每對(w,id)(w∪i(RP[i]∪∪j≠iIP[i,j])),令(ii)按如下步驟生成D和STags：首先，對所有w選擇生成排列且記錄此排列Wperms[w]←σ，初始化鏈表tw←?并生成密鑰然后，對每個w對每個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←?；然后，對每對(w,id)(w更新集合XSet←XSet∪{A[w,id]}；其次，令j←|XSet|，并從i=j+1到N，依次隨機(jī)抽取并更新集合XSet←XSet∪{h}；最后，令EDB[1]←XSet.

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

3.3 性能分析

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

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

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

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

4 結(jié)論

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

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