張成， 褚瑩， 凌力(復(fù)旦大學(xué) 通信科學(xué)與工程系， 上海 200433)

一種基于動(dòng)態(tài)索引表的對(duì)稱可搜索加密方案

張成， 褚瑩， 凌力
(復(fù)旦大學(xué) 通信科學(xué)與工程系， 上海 200433)

可搜索加密機(jī)制在現(xiàn)階段的云端存儲(chǔ)服務(wù)中有著廣泛的應(yīng)用，可以在保護(hù)用戶數(shù)據(jù)隱私的情況下快速查詢指定的加密數(shù)據(jù)?；趯?duì)稱密鑰加密的可搜索加密方案SSE計(jì)算開銷小，效率高，特別適合個(gè)人用戶的大規(guī)模數(shù)據(jù)塊加密。針對(duì)傳統(tǒng)SSE方案中BuildIndex算法的不足，提出了改進(jìn)的索引表模型設(shè)計(jì)。實(shí)驗(yàn)證明，該算法建立索引表的時(shí)間花銷更小，同時(shí)保留了查詢速度快的特點(diǎn)，改善了SSE方案的動(dòng)態(tài)性。

可搜索加密； 動(dòng)態(tài)索引表； 對(duì)稱密鑰加密； 云存儲(chǔ)； 數(shù)據(jù)安全

0 引言

早在1996年左右，O. Goldreich和R. Ostrovsky 等人就首次提出過關(guān)于搜索加密數(shù)據(jù)的一些問題：加密云端數(shù)據(jù)可以讓用戶以最小的開銷和較高的安全性來存儲(chǔ)大量的數(shù)據(jù)。然而，任何人都無法對(duì)加密后的數(shù)據(jù)進(jìn)行搜索，上傳者本身也無法選擇性地獲取數(shù)據(jù)片段。要想使用數(shù)據(jù)必須從云端全部下載。這會(huì)帶來兩個(gè)問題：第一，大量文件的下載會(huì)占用大量網(wǎng)絡(luò)帶寬；第二，文件的完全解密費(fèi)時(shí)費(fèi)力，效率極低，浪費(fèi)本地資源。

對(duì)于這個(gè)問題的思考引出了可搜索加密(searchable encryption，簡(jiǎn)稱SE)技術(shù)的雛形，并在近幾年蓬勃發(fā)展。這個(gè)概念在2000年被Song XD[1]等人提出，用戶使用特殊加密方法生成一張關(guān)鍵字索引表，之后將加密數(shù)據(jù)c以及加密索引表γ上傳到云端服務(wù)器。當(dāng)用戶需要查詢某個(gè)關(guān)鍵字w時(shí)，使用密鑰生成一個(gè)關(guān)鍵字搜索憑證τw(search token)，云端服務(wù)器用此搜索憑證在索引表中進(jìn)行查找，如果匹配成功，就將這個(gè)關(guān)鍵字對(duì)應(yīng)的所有文件發(fā)回給用戶。云端服務(wù)器無法獲得關(guān)鍵字內(nèi)容以及文件的明文，保護(hù)了用戶個(gè)人數(shù)據(jù)的隱私；而對(duì)于用戶來說，使用可搜索加密方案大大節(jié)省了網(wǎng)絡(luò)開銷和存儲(chǔ)空間，同時(shí)充分利用了云端服務(wù)器的強(qiáng)大計(jì)算能力，查詢效率很高。

1 對(duì)稱密鑰可搜索加密(SSE)

SE技術(shù)根據(jù)加密方法可以分為對(duì)稱密鑰可搜索加密(SSE)和非對(duì)稱密鑰可搜索加密(ASE)。SSE機(jī)制通常使用偽隨機(jī)函數(shù)或哈希表處理關(guān)鍵字索引表，相比ASE機(jī)制，SSE計(jì)算開銷小，效率高，特別適合個(gè)人用戶的大規(guī)模數(shù)據(jù)塊加密。

在SSE方案中，用戶可以自己組織數(shù)據(jù)的順序，或者引入一些額外的數(shù)據(jù)結(jié)構(gòu)以便于搜索，只有擁有密鑰的用戶才可以獲取數(shù)據(jù)。在這種情況下，用戶的初始工作會(huì)比較繁重，需要預(yù)處理很多數(shù)據(jù)，但是后續(xù)工作例如查詢搜索就比較輕松，且搜索時(shí)間和數(shù)據(jù)大小關(guān)聯(lián)很小，用戶的查詢習(xí)慣也很容易掩蓋。

在Song XD的方案之后, 還有兩種經(jīng)典的SSE構(gòu)造方案。Curtmola R等人[2]提出SSE-1方案，逐漸規(guī)范化了SSE安全方案，構(gòu)建了健全的“關(guān)鍵字-文件”索引表，云服務(wù)器搜索時(shí)間復(fù)雜度僅為O(1)，但是更新索引表較慢，需要O(n)時(shí)間。Kamara等人[3]則在SSE-1方案的基礎(chǔ)上提出了一個(gè)高效動(dòng)態(tài)的方案，額外構(gòu)建了“文件-關(guān)鍵字”索引表，改善了建立索引表的時(shí)間，同時(shí)保留了搜索時(shí)間開銷小和安全性高的特點(diǎn)。

2 索引表建立算法

由于SSE-1作為對(duì)稱密鑰可搜索加密的基本方案已經(jīng)非常成熟，因此近年來SSE的研究基本集中在對(duì)基本方案的功能拓展和安全性優(yōu)化上。例如查詢方式拓展、多關(guān)鍵詞搜索、模糊關(guān)鍵詞檢索、安全性優(yōu)化[4]、以及本文重點(diǎn)研究的密文文件及索引表的動(dòng)態(tài)更新。

2.1 兩種傳統(tǒng)BuildIndex算法

Curtmola等人設(shè)計(jì)的SSE-1方案是當(dāng)時(shí)最為完善的對(duì)稱密鑰可搜索加密方案，在搜索開銷極小的情況下，還保證了很高的安全性，即使攻擊者獲取了過去的搜索憑證和搜索結(jié)果，也無法從中獲取更多信息，做到了真正意義上的不泄露任何信息。基本算法包括密鑰生成Keygen，索引表建立BuildIndex，搜索憑證生成Trapdoor和搜索Search。

為了支持高效的檢索，SSE-1引入了兩個(gè)重要的數(shù)據(jù)結(jié)構(gòu)：第一個(gè)是數(shù)組，用于存儲(chǔ)加密后的文件集合，第二個(gè)則是核心部分，一張存儲(chǔ)了關(guān)鍵字相關(guān)信息的索引表，用于定位對(duì)應(yīng)關(guān)鍵詞的文件在數(shù)組中的位置。索引表建立BuildIndex方法如下：

(1)使用密鑰生成算法生成全局密鑰s,y,z，并設(shè)置全局計(jì)數(shù)器ctr=1。

(2)建立鏈表。以關(guān)鍵字W(i)作為鏈表核心，包含關(guān)鍵字W(i)的文件作為節(jié)點(diǎn)，將這些節(jié)點(diǎn)隨機(jī)存儲(chǔ)在數(shù)組A中。每一個(gè)節(jié)點(diǎn)都使用密鑰生成算法生成節(jié)點(diǎn)密鑰Ki,j。以 “文件標(biāo)識(shí)符||下一個(gè)節(jié)點(diǎn)解密密鑰||下一個(gè)節(jié)點(diǎn)在數(shù)組A的存放位置”這一形式創(chuàng)建鏈表LW(i)的第j個(gè)節(jié)點(diǎn)并存儲(chǔ)至數(shù)組A中。Ψs(ctr)表示使用第一個(gè)對(duì)稱密鑰s加密計(jì)數(shù)器，這個(gè)密文用來表示節(jié)點(diǎn)在數(shù)組中的存放位置。最后使用前一個(gè)節(jié)點(diǎn)的密鑰Ki,j-1加密節(jié)點(diǎn)Ni,j，存儲(chǔ)在A[Ψs(ctr)]中，計(jì)數(shù)器加1，即

A[Ψs(ctr)] =HKi,j-1[id(Fi,j)||Ki,j,||Ψs(ctr+1)]

(3)建立搜索表時(shí)，需要對(duì)每一個(gè)關(guān)鍵字W(i)鏈表的頭節(jié)點(diǎn)地址和頭結(jié)點(diǎn)密鑰打包進(jìn)行加密，方法就是使用第二個(gè)對(duì)稱密鑰y加密W(i)，再將兩者異或，接著使用第三個(gè)對(duì)稱密鑰z加密W(i)，將這個(gè)關(guān)鍵字密文和加密后的鏈表頭節(jié)點(diǎn)做點(diǎn)對(duì)點(diǎn)映射，存放入數(shù)組中，即

T(πz(W(i)))= (addr(Ni,1)||Ki,0)⊕fy(W(i))

由于每個(gè)節(jié)點(diǎn)都存儲(chǔ)了下一個(gè)節(jié)點(diǎn)的地址和密鑰，因此可以遍歷整個(gè)鏈表，獲得所有包含關(guān)鍵字的文件標(biāo)示符。

可以看到SSE-1避免了對(duì)密文逐個(gè)搜索，效率較高。但是對(duì)文件進(jìn)行增刪操作時(shí)需要重構(gòu)索引表，查找增刪鏈表內(nèi)的元素會(huì)造成很大的開銷，因此這個(gè)方案更加適用于穩(wěn)定的文件集合。

在SSE-1的基礎(chǔ)之上，Kamara等人提出了一個(gè)線性搜索時(shí)間的動(dòng)態(tài)更新SSE方案?；舅惴òㄉ擅荑€Gen，建立索引并加密Enc，生成搜索憑證SrchToken，文件添加憑證AddToken，文件刪除憑證DelToken，密文搜索Search，索引表內(nèi)容添加Add，索引表內(nèi)容刪除Del，和密文解密Dec。該方案重新定義了SSE-1的搜索數(shù)組As和搜索表Ts，并且額外加入了刪除數(shù)組Ad和刪除搜索表Td，刪除數(shù)組Ad內(nèi)存儲(chǔ)的是以文件為核心的刪除鏈表，可以跟蹤每個(gè)文件包含的關(guān)鍵字。搜索鏈表的格式為“關(guān)鍵字-文件”，而刪除鏈表的格式為“文件-關(guān)鍵字”，節(jié)點(diǎn)格式呈對(duì)偶關(guān)系。因此刪除搜索表不僅存儲(chǔ)刪除鏈表，也存儲(chǔ)每個(gè)節(jié)點(diǎn)的對(duì)偶節(jié)點(diǎn)在搜索數(shù)組中的位置。[6]通過新算法AddToken和DelToken就可以實(shí)現(xiàn)索引表的動(dòng)態(tài)更新，方法如下：

(1)搜索表和搜索數(shù)組的建立和SSE-1類似，不同點(diǎn)在于除了存儲(chǔ)頭節(jié)點(diǎn)地址，也存頭節(jié)點(diǎn)的對(duì)偶節(jié)點(diǎn)的地址，即

As[Ψs(ctr)] =HKi,j-1[id(Fi,j)||Ki,j||Ψs(ctr+1)]

Ts(πz(W(i)))= (addrs(Ni,1)||

addrd(Ni,1*) )⊕fy(W(i))

(2)以文件集合中的每一個(gè)文件f為核心，建立一個(gè)刪除鏈表，每一個(gè)節(jié)點(diǎn)Di都是搜索鏈表節(jié)點(diǎn)N的對(duì)偶節(jié)點(diǎn)。以 “下一個(gè)節(jié)點(diǎn)解密密鑰||下一個(gè)節(jié)點(diǎn)在刪除數(shù)組Ad的存放位置||對(duì)偶節(jié)點(diǎn)在搜索數(shù)組As存放位置||對(duì)偶節(jié)點(diǎn)的前后節(jié)點(diǎn)在搜索數(shù)組As的存放位置”這一形式創(chuàng)建刪除鏈表并存儲(chǔ)至數(shù)組Ad中，即

Di=Ki,j’||Ψs(ctr+1)||addrs(N)|

|addrs(N-1) ||addrs(N+1)

Ad[Ψs(ctr)] =HKi,j-1[Di]

(3)刪除搜索表的構(gòu)建與之前相同，即

Td(πz(F(i)))= (addrd(D1))⊕fy(F(i))

至此動(dòng)態(tài)搜索表構(gòu)建完成，若需要添加文件，找出此文件包含的關(guān)鍵字，通過關(guān)鍵字鏈表將新的“關(guān)鍵字-文件”組合加入到搜索數(shù)組中。需要?jiǎng)h除文件時(shí)，通過密鑰生成刪除憑證定位需要?jiǎng)h除的文件，利用刪除鏈表找到該文件對(duì)應(yīng)的所有關(guān)鍵字，并利用對(duì)偶節(jié)點(diǎn)找到搜索鏈表中需要?jiǎng)h除的節(jié)點(diǎn)，無需重構(gòu)鏈表。

2.2 改進(jìn)的buildIndex算法

Kamara等人的設(shè)計(jì)擁有非常好的性能，搜索時(shí)間為O(#fw)，復(fù)雜度和所有包含關(guān)鍵字w的f數(shù)量成正比，而且改善了第一代SSE方案的動(dòng)態(tài)性，文件變更時(shí)無須再重做索引表，只需要在之前的索引表上進(jìn)行修改。然而，這個(gè)方案建立索引表需要大量的時(shí)間，時(shí)間復(fù)雜度為O(∑w#fw+#W)，所有鏈表的總長(zhǎng)度為所有“關(guān)鍵字-文件”組合數(shù)，鏈表總數(shù)等于關(guān)鍵字的數(shù)量。隨著文件和關(guān)鍵字總數(shù)的提升，“關(guān)鍵字-文件”組合會(huì)隨之大量增加，建立索引表的時(shí)間也會(huì)成倍增加，影響效率。

改良后的索引表，如圖1所示。

利用跳躍表的思路，將所有的鏈表匯總成一個(gè)多指針鏈表，在這張鏈表當(dāng)中，以文件f作為節(jié)點(diǎn)，所有的關(guān)鍵字w作為指針。設(shè)置頭節(jié)點(diǎn)head，包含所有關(guān)鍵字指針，以“下一個(gè)節(jié)點(diǎn)解密密鑰||指針K1的前后節(jié)點(diǎn)在數(shù)組A中的存儲(chǔ)位置||指針K2的前后節(jié)點(diǎn)在數(shù)組A中的存儲(chǔ)位置||……||指針K#w的前后節(jié)點(diǎn)在數(shù)組A中的存儲(chǔ)位置”的形式創(chuàng)建每一個(gè)節(jié)點(diǎn)。即

Ni=Ki||Ψs(ctr+1)||addrs(NK1-1) ||

addrs(NK1+1)||…||addrs(NK#W-1)||addrs(NK#W+1)

As[Ψs(ctr)] =HKi[Ni]

圖1 動(dòng)態(tài)索引素

由于所有鏈表結(jié)合為一個(gè)，因此索引表和搜索數(shù)組也可以合并，所有的搜索請(qǐng)求都送往頭節(jié)點(diǎn)處理。即

As(0)= (addrs(N0))⊕fy(W(i))

搜索時(shí)只需要通過對(duì)稱密鑰y計(jì)算出fy(w(i))這個(gè)搜索憑證，就可以通過異或得到關(guān)鍵詞對(duì)應(yīng)的密文鏈表頭節(jié)點(diǎn)的存儲(chǔ)位置和節(jié)點(diǎn)的內(nèi)容。另外，通過密鑰s計(jì)算Ψs(ctr), 便可相繼得到鏈表的其他節(jié)點(diǎn)。

其余基本算法與Kamara等人的方案相同。以圖1為例，若對(duì)5個(gè)文件和5個(gè)關(guān)鍵字進(jìn)行處理，存儲(chǔ)時(shí)只需要存儲(chǔ)頭節(jié)點(diǎn)加上文件總數(shù)個(gè)節(jié)點(diǎn)，共6個(gè)節(jié)點(diǎn)。相比Kamara的方案的14個(gè)節(jié)點(diǎn)，本方案的節(jié)點(diǎn)數(shù)量大大減少，可以節(jié)省很多建立索引表和索引數(shù)組的開銷。隨著文件和關(guān)鍵字?jǐn)?shù)量的上升，本方案在建立索引表和數(shù)組方面的性能會(huì)更加突出。添加文件時(shí)，只需整理出文件中包含的關(guān)鍵字，創(chuàng)建一個(gè)新的節(jié)點(diǎn)，將關(guān)鍵字對(duì)應(yīng)的指針鏈接起來。刪除文件時(shí)，由于每一個(gè)節(jié)點(diǎn)的關(guān)鍵字指針都記錄了前后節(jié)點(diǎn)，且鏈表只有一個(gè)，因此拼接鏈表的效率也比Kamara的方案更高，刪除文件的效率也更高。即使需要增刪關(guān)鍵字，也可以直接在鏈表節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)中進(jìn)行修改，無需重建索引表。

3 實(shí)驗(yàn)和結(jié)果分析

與之前的方案相比，本搜索表的搜索時(shí)間復(fù)雜度為O(#Fw)，搜索表建立時(shí)間為O(#F)，#Fw代表所有包含某關(guān)鍵字的文件數(shù)量總和，#F代表所有文件數(shù)量總和，充分改善了建立搜索表的時(shí)間，同時(shí)也沒有損失安全性。

我們測(cè)試了此方案建立索引表以及搜索密文方面的性能。實(shí)驗(yàn)配置如下：intel core i7-4790 CPU，7.87G內(nèi)存。軟件環(huán)境為：WIN7操作系統(tǒng)以及Eclipse編程環(huán)境。我們選擇純文本文件作為測(cè)試對(duì)象，并選擇其中出現(xiàn)頻率最高的一些詞語作為關(guān)鍵詞。選取擁有四組數(shù)據(jù)進(jìn)行測(cè)試，文件大小分別為160M、480M、1.6G和16G。比較結(jié)果如圖2圖3所示。

可以看到，搜索時(shí)間基本和傳統(tǒng)方案相同，而索引表建立時(shí)間明顯少于傳統(tǒng)算法。對(duì)于傳統(tǒng)SSE方案而言，索引表生成的時(shí)間與“關(guān)鍵字-文件”組合的數(shù)量成線性關(guān)系，大約在35微秒/組合左右。這個(gè)數(shù)字基本不隨“關(guān)鍵字-文件”組合數(shù)量的上升而改變。而對(duì)于本文提出的新型模型，時(shí)間復(fù)雜度僅與文件總數(shù)有關(guān)，因此文件越大、數(shù)量越多，表現(xiàn)出的性能越好。

圖2 兩種算法的搜索時(shí)間對(duì)比圖

圖3 兩種算法的索引表建立時(shí)間對(duì)比圖

而對(duì)于SSE方案中的其他基本算法，執(zhí)行時(shí)間與“關(guān)鍵字-文件”組合的數(shù)量無關(guān)，而且針對(duì)每個(gè)單元(關(guān)鍵字或文件)的平均花銷也和關(guān)鍵字或文件總數(shù)無關(guān)，是一個(gè)很小的常量，如表1所示。

表1 各類基本操作單元時(shí)間花銷

從表1中可以看出，搜索、文件刪除憑證生成和添加文件這幾個(gè)操作的效率很高，非常實(shí)用。

4 總結(jié)

由于云存儲(chǔ)服務(wù)概念的普及，可搜索加密現(xiàn)已被廣泛研究和使用。基于對(duì)稱密鑰的可搜索加密SSE機(jī)制計(jì)算開銷小，效率高，特別適合個(gè)人用戶的大規(guī)模數(shù)據(jù)塊加密。SSE方案都應(yīng)當(dāng)滿足搜索速度快，安全性高，動(dòng)態(tài)性好的要求。

本文的工作中都滿足了上述性質(zhì)，另外，相比傳統(tǒng)模型，我們改善了建立索引表的時(shí)間花銷，提升了性能。實(shí)驗(yàn)證明我們的方案非常有效，動(dòng)態(tài)性得到了改進(jìn)。

[1] Song XD, Wagner D, Perrig A. Practical techniques for searches on encrypted data[C]//Proc. of the IEEE Symp. on Security and Privacy. IEEE Press, 2000. 44-55.

[2] Curtmola R, Garay J, Kamara S, Ostrovsky R. Searchable symmetric encryption: Improved definitions and efficient constructions[C]//Proc. of the 13th ACM Conf. on Computer and Communications Security (CCS 2006). New York: ACM Press, 2006. 79-88.

[3] Kamara S, Papamanthou C, Roeder T. Dynamic searchable symmetric encryption[C]//Proc. of the 19th ACM Conf. on Computer and Communications Security (CCS 2012). New York: ACM Press, 2012. 965-976.

[4] 李經(jīng)緯,賈春福,劉哲理,等. 可搜索加密技術(shù)研究綜述[J]. 軟件學(xué)報(bào), 2015, 26(1):109-128.

[5] 沈志榮, 薛巍, 舒繼武. 可搜索加密機(jī)制研究與進(jìn)展[J]. 軟件學(xué)報(bào), 2014, 25(4):880-895.

[6] Ren X, Yan S. Keyword-based Cipher-text Search Algorithm under Cloud Storage [J]. 2016, 61.

ASearchableSymmetricEncryptionSchemeBasedonDynamicIndex

Zhang Cheng, Chu Ying, Ling Li
(College of Information Science and Engineering, Fudan University, Shanghai 200433)

Searchable encryption has been widely applied in cloud storage service now, it can help the user to search over specified cipher-text rapidly without leaking users’ data privacy. Searchable symmetric encryption (searchable encryption based on symmetric key cryptography) has a low calculating overhead and is very suitable for large data block encryption by private user. Because the "Build Index" algorithm of traditional SSE is insufficient, a new index is proposed with an improved algorithm. Experiment results indicate that the overhead of building index becomes smaller and searching time is still satisfactory, and the dynamic performance has been improved.

Searchable encryption; Dynamic index; Symmetric key cryptography; Cloud storage; Data security

張 成(1993-)，男，上海，碩士研究生，研究方向：網(wǎng)絡(luò)與數(shù)據(jù)通信。

褚 瑩(1994-)，女，上海，碩士研究生，研究方向：網(wǎng)絡(luò)與數(shù)據(jù)通信。

凌 力(1967-)，男，浙江，副教授，研究方向：網(wǎng)絡(luò)與數(shù)據(jù)通信。

1007-757X(2017)11-0039-03

TP309

A

2017.07.05)