基于安全字典樹的關(guān)鍵詞密文模糊搜索方案

張成， 褚瑩， 凌力

(復(fù)旦大學(xué) 通信科學(xué)與工程系，上海 200433)

0 引言

近年來，大數(shù)據(jù)的出現(xiàn)引發(fā)了云計(jì)算、云存儲的蓬勃發(fā)展。現(xiàn)在，個(gè)人和企業(yè)都傾向于將重要的本地?cái)?shù)據(jù)存儲到云端當(dāng)中以節(jié)省開銷。加密云端數(shù)據(jù)讓用戶減少了本地開銷，也保證了數(shù)據(jù)不會(huì)被云端竊取。然而，用戶無法直接對密文進(jìn)行搜索，選擇自己需要的數(shù)據(jù)資源。下載所有密文又費(fèi)時(shí)費(fèi)力，浪費(fèi)大量網(wǎng)絡(luò)開銷，為了解決這個(gè)問題，提出了可搜索加密的概念。利用安全索引表來對密文進(jìn)行分類和搜索能夠同時(shí)滿足系統(tǒng)的安全性和高效性。

由于拼寫錯(cuò)誤會(huì)不可避免地出現(xiàn)，傳統(tǒng)精確密文搜索方案便具有較大的局限性。2010年，Li等人首先提出了密文關(guān)鍵詞模糊搜索的概念[1]。在明文搜索中，利用關(guān)鍵詞相似度就可以返回最可能匹配的文檔，因此拼寫錯(cuò)誤的問題比較容易解決，例如輸入關(guān)鍵詞“hamberger”沒有精確匹配文件，但是可以模糊匹配到“hamburger”對應(yīng)的文件集合。然而，密文搜索時(shí)需要搜索的關(guān)鍵詞會(huì)加密上傳到云端，一個(gè)簡單的拼寫錯(cuò)誤在加密后就會(huì)與正確結(jié)果千差萬別。因此密文關(guān)鍵詞模糊搜索方案可以顯著提升系統(tǒng)的可用性以及用戶的搜索體驗(yàn)，擁有廣闊的應(yīng)用環(huán)境。

文獻(xiàn)[1-5]是近年來研究的云端針對加密數(shù)據(jù)的關(guān)鍵詞模糊搜索方案，主要方法是通過編輯距離來度量關(guān)鍵詞，制作關(guān)鍵詞模糊搜索集合，通過這個(gè)集合構(gòu)建索引表和搜索憑證。利用用戶制作好的搜索憑證和存儲在云端的索引表進(jìn)行匹配，將匹配成功的文檔集合返回給用戶。2012年，文獻(xiàn)[2]在文獻(xiàn)[1]的基礎(chǔ)上提出了一套較為完備的關(guān)鍵詞密文模糊搜索方案。和文獻(xiàn)[1]的方案相比，Wang等人的方案擁有更好的安全性和可用性。方案使用編輯距離來度量詞語之間的相似度，基于通配符來構(gòu)造空間效率極好的相似詞語集合。為了提高這個(gè)加密集合的搜索效率，文中使用了字典樹(trie)的數(shù)據(jù)結(jié)構(gòu)來存儲關(guān)鍵詞加密后的hash值和制作索引表，搜索效率上有了新的突破。

然而，如果用戶使用通配符關(guān)鍵詞集合，則搜索關(guān)鍵詞時(shí)需要預(yù)先計(jì)算關(guān)鍵詞所對應(yīng)的通配符集合，將集合中的每一個(gè)元素單獨(dú)制作一個(gè)搜索憑證，再上傳到云端進(jìn)行搜索，增加用戶的計(jì)算開銷以及云端的搜索時(shí)間，也增加了泄露相關(guān)信息的風(fēng)險(xiǎn)。因此基于通配符的模糊關(guān)鍵詞依舊值得改進(jìn)。

文獻(xiàn)[4,5]在構(gòu)造關(guān)鍵詞模糊集合時(shí)，不使用編輯距離以及通配符來度量詞語相似度，而是使用詞語字典內(nèi)包含的詞語和關(guān)鍵詞進(jìn)行對比并制作模糊集合，這種方法可以減小索引表的總數(shù)據(jù)量，但是依舊不能有效解決單詞拼寫錯(cuò)誤的問題。

針對基于通配符的關(guān)鍵詞集合的不足，本文提出了一種新型的模糊關(guān)鍵詞搜索方案。本文著重解決的是搜索時(shí)不可避免出現(xiàn)的拼寫錯(cuò)誤，因此本文會(huì)基于鍵盤按鍵位置來制作模糊關(guān)鍵詞集合，雖然相比通配符集合會(huì)增加存儲的節(jié)點(diǎn)數(shù)量，但是可以減少用戶端的工作，降低用戶計(jì)算開銷，同時(shí)由于只制作一個(gè)搜索憑證，因此搜索效率也得到了提高，節(jié)省了云端的計(jì)算開銷和帶寬資源。在索引表中還混入一些虛假節(jié)點(diǎn)，提高云端分析文檔和索引表的難度，提高了方案的安全性。

1 系統(tǒng)模型

我們構(gòu)建一個(gè)高階云端數(shù)據(jù)服務(wù)模型，如圖1所示。

圖1 系統(tǒng)模型

模型中存在3個(gè)部分：數(shù)據(jù)擁有者、用戶以及云服務(wù)器。數(shù)據(jù)擁有者可能是個(gè)人或者企業(yè)，加密的數(shù)據(jù)集合C={F1,F2…Fn}存儲在云服務(wù)器中。數(shù)據(jù)集合C當(dāng)中包含關(guān)鍵詞集合W={W1,W2…Wp}。為了保證敏感數(shù)據(jù)不被盜取，數(shù)據(jù)擁有者會(huì)對數(shù)據(jù)集合C加密后再上傳至云服務(wù)器。除此之外，數(shù)據(jù)擁有者還需要根據(jù)關(guān)鍵詞集合W構(gòu)建關(guān)鍵詞迷糊集合，根據(jù)模糊集合生成搜索憑證Tw，并加入一些混淆憑證，構(gòu)成索引表Index上傳至云端。數(shù)據(jù)擁有者會(huì)將搜索憑證制作秘鑰Sk分發(fā)給授權(quán)用戶，用戶利用秘鑰以及hash等單向函數(shù)產(chǎn)生搜索請求憑證。云端在不解密數(shù)據(jù)的情況下，對數(shù)據(jù)集合C進(jìn)行搜索，返回包含指定關(guān)鍵詞w的加密文件集合FIDw。搜索方案會(huì)根據(jù)關(guān)鍵詞相似度返回最有可能的文件集合。

在這個(gè)模型當(dāng)中，云服務(wù)器只知道數(shù)據(jù)擁有者上傳的密文數(shù)據(jù)集合C以及索引表Index。云服務(wù)器也會(huì)誠實(shí)地根據(jù)用戶的搜索請求返回所有符合條件的文件集合，但是會(huì)根據(jù)數(shù)據(jù)流分析獲取額外信息。

2 關(guān)鍵詞模糊搜索方案

2.1 關(guān)鍵詞模糊集合的構(gòu)建

和文獻(xiàn)[2～5]相同，本文也使用編輯距離(edit distance)來判定詞語之間的相似度。編輯距離，又稱為Levenshtein距離，是指將一個(gè)字符串轉(zhuǎn)換為另一個(gè)字符串所需要的最少編輯次數(shù)，許可的編輯操作包括替換字符、插入字符以及刪除字符。編輯距離edit(i,j)用于記錄str[1…i]和str[1…j]的編輯距離，動(dòng)態(tài)規(guī)劃公式如下：

1) If i==0&&j==0, edit(i,j) = 0;

2) If i==0&&j>0, edit(i,j) = j;

3) If i>0&&j==0, edit(i,j) = i;

4) If i1&&j1, edit(I,j)==min{edit(i-1,j)+1, edit(i,j-1)+1, edit(i-1,j-1)+f(i,j)}，當(dāng)?shù)谝粋€(gè)字符串的第i個(gè)字符不等于第二個(gè)字符串的第j個(gè)字符時(shí)，f(i,j)=1;否則，f(i,j)=0。

本文當(dāng)中，我們定義Sw,d為某個(gè)關(guān)鍵詞w對應(yīng)的相似詞語集合，整數(shù)d為數(shù)據(jù)擁有者在制作集合時(shí)定義的編輯距離最大值，對于任何w′∈Sw,d，都滿足edit(w,w′)≤d。傳統(tǒng)模糊關(guān)鍵詞集合的構(gòu)造[2,4-7]都使用基于通配符的模糊集構(gòu)造方法，對關(guān)鍵詞的每個(gè)位置的編輯操作都用通配符*表示。例如，對關(guān)鍵詞array，構(gòu)造的基于通配符*編輯距離為1的模糊集合Sarray,1={array，*array，*rray，a*rray，a*ray，arr*ay…arra*，array*}。假設(shè)模糊關(guān)鍵詞集合的編輯距離是d，那么長度為L的關(guān)鍵詞的模糊集合大小為O(Ld)。

基于通配符的方案在明文狀態(tài)下似乎是一種很合理的方案，但是在對密文搜索時(shí)，用戶在制作搜索憑證時(shí)必須對需要搜索的關(guān)鍵詞w計(jì)算它的模糊關(guān)鍵詞集合Sw,d，這個(gè)過程增加了用戶的額外開銷，也增加了信息泄露的風(fēng)險(xiǎn)。因此本文提出了一種新的基于鍵盤按鍵位置的模糊集構(gòu)造方法。一般的英語單詞拼寫錯(cuò)誤都與鍵盤相鄰按鍵有關(guān)，因此我們可以在構(gòu)造索引表時(shí)只考慮這些元素。例如，按鍵q的相鄰按鍵為a和w，按鍵h的相鄰按鍵有y,g,b,n,j等等，經(jīng)過統(tǒng)計(jì)和計(jì)算，所有字母可能出現(xiàn)的拼寫錯(cuò)誤按鍵總數(shù)為92個(gè)，因此對于每一個(gè)字母按鍵，將通配符換為相鄰字母，平均相鄰按鍵約為3.5個(gè)，因此假設(shè)模糊關(guān)鍵詞集合的編輯距離為d，那么本方案的長度為L的關(guān)鍵詞模糊集合大小為

可以看到索引表的大小確實(shí)有所增加，但是實(shí)際上編輯距離d一般只會(huì)選擇小于等于2的值，編輯距離d=1時(shí)，模糊集合大小約為通配符集合大小的3.5倍；編輯距離d=2時(shí)，模糊集合大小約為通配符集合大小的12倍。鑒于基于通配符的索引表一般以MB為計(jì)量單位，即使在編輯距離d=2的情況下，我們的方案的索引表數(shù)據(jù)量依舊是可以接受的。但是在使用本方案后，用戶在搜索時(shí)不需要制作很多搜索憑證，只需要一條憑證就可以得到需要的結(jié)果，節(jié)省了用戶端和云端兩方的計(jì)算開銷以及時(shí)間開銷，同時(shí)防止了用戶制作模糊集合時(shí)潛在的信息泄露問題。

2.2 安全字典樹索引表結(jié)構(gòu)

為了進(jìn)一步提高索引表的搜索效率，我們使用一種基于hash值排列的字典樹搜索結(jié)構(gòu)來構(gòu)造索引表，這種多路搜索樹用于存儲模糊搜索集的所有元素{Sw,d}w∈W。核心思想就是一些元素的hash值會(huì)共享一段相同的前綴。定義關(guān)鍵詞的hash值αi1αi2…αiτ/λ，樹根是一個(gè)空集，樹的每一條路徑αi代表一個(gè)字符串，擁有相同前綴的會(huì)共用節(jié)點(diǎn)。λ為每一個(gè)αi包含的比特位，τ為hash值得總比特位，因此總共可以分為τ/λ段。隨著樹的深入，將從樹根到葉子節(jié)點(diǎn)的路徑上所有字符串拼接在一起，就是葉子節(jié)點(diǎn)代表的某個(gè)模糊集元素的搜索憑證hash值。

索引字典樹通過模糊集合構(gòu)造而成，計(jì)算w的hash值，計(jì)算結(jié)果平均分為τ/λ段，在字典樹的最后一個(gè)節(jié)點(diǎn)之后，會(huì)附加文件索引表，即通往關(guān)鍵詞對應(yīng)的文件集合ID的路徑。對每個(gè)文件的關(guān)鍵詞模糊集合的每一個(gè)w作上述操作，直到字典樹的完成。結(jié)構(gòu)如圖2所示。

圖2 字典索引樹結(jié)構(gòu)示意圖

由于元素之間的hash值都不同，因此模糊集合的這種分割也是獨(dú)立不同的。另外，使用這種多路樹結(jié)構(gòu)可以完全隱藏關(guān)鍵詞w的信息。由于在字典樹中不同搜索憑證的路徑會(huì)共享一些相同的前綴，因此深度搜索可以在常數(shù)時(shí)間O(τ/λ)完成，和文件總數(shù)、關(guān)鍵詞總數(shù)以及模糊集合節(jié)點(diǎn)總數(shù)都無關(guān)，具有很高的搜索效率。

2.3 索引表建立算法以及搜索算法

預(yù)處理階段：

搜索階段：

1) 授權(quán)用戶和數(shù)據(jù)擁有者安全交互，得到能夠獲得搜索憑證TWI=f(sk,wi)的秘鑰sk。授權(quán)用戶輸入需要查詢的關(guān)鍵詞w，得到索引憑證Tw。

2) 云端服務(wù)器將這些搜索憑證形式上分解為αi1αi2…αiτ/λ的字符串，通過建立好的字典樹索引表進(jìn)行搜索，將對應(yīng)的文件集合{FIDWI}edit(w,wi)≤d返回給用戶。

3) 用戶再和數(shù)據(jù)擁有者進(jìn)行秘密交互，獲得解密秘鑰，獲得需要的明文文件集合。

由于本文使用的模糊關(guān)鍵詞集合無需在制作索引憑證時(shí)計(jì)算模糊關(guān)鍵詞集合，因此搜索時(shí)間為O(τ/λ)，即為O(1)的常數(shù)時(shí)間。而之前文獻(xiàn)[2]等人的方案雖然也是用字典樹這一數(shù)據(jù)結(jié)構(gòu)，但是實(shí)際搜索之前需要構(gòu)造{Sw,d}個(gè)索引憑證，因此搜索時(shí)間需要O(Sw,d)。在編輯距離d=1時(shí)約為O(L)，編輯距離d=2時(shí)約為O(L2)，時(shí)間開銷明顯降低，減少了很多無意義的搜索。性能對比,如表1所示。

表1 兩種方案的性能對比

φ為最大模糊關(guān)鍵詞集合的元素個(gè)數(shù)，|W|為關(guān)鍵詞總數(shù)。

3 實(shí)驗(yàn)性能測試與分析

表1已經(jīng)在理論上證明，我們的方案能夠保護(hù)密文的搜索模式和搜索結(jié)果，并且增強(qiáng)了搜索效率，達(dá)到了常數(shù)時(shí)間級別。為了證明這一結(jié)論，我們使用真實(shí)數(shù)據(jù)集合來驗(yàn)證。我們選擇一個(gè)包含7000個(gè)左右的文件的文本數(shù)據(jù)集，大小約為400MB。實(shí)驗(yàn)配置如下：intel core i7-4790 CPU，7.87G內(nèi)存。軟件環(huán)境為：WIN8操作系統(tǒng)以及Java Eclipse編程環(huán)境。由于性能的重點(diǎn)在于關(guān)鍵詞的數(shù)量而不是文件集合的數(shù)量，因此我們的實(shí)驗(yàn)結(jié)果以關(guān)鍵詞數(shù)量作為橫坐標(biāo)。

設(shè)定編輯距離d為1和2時(shí)的索引字典樹的大小比較。如圖3圖4所示可以看到基本都是線性增長，d=1時(shí)的字典樹遠(yuǎn)遠(yuǎn)小于d=2的字典樹，超過2時(shí)效率就會(huì)很低，因此方案中不作考慮。制作字典樹時(shí)使用SHA-1計(jì)算hash值，每個(gè)搜索憑證的總長度為160 bit。每個(gè)子字符串的長度取4 bit，因此樹可以分為40層。我們的方案確實(shí)在索引大小上高于傳統(tǒng)方案，但是大小依舊在MB單位以內(nèi)，可以接受。由于制作索引只是一次性的，而且可以在線下操作，而且得到了搜索時(shí)間性能的提升，因此是可以接受的。

圖3 編輯距離為1時(shí)的索引大小

圖4 編輯距離為2時(shí)的索引大小

本文方案和傳統(tǒng)方案在搜索時(shí)間上的對比。如圖5所示。

圖5 搜索時(shí)間對比

可以看到傳統(tǒng)方案在編輯距離不同時(shí)得到的搜索時(shí)間也不相同，因?yàn)橛脩糁谱鞯乃阉鲬{證數(shù)量不同，因此搜索次數(shù)不同。而本文的方案只需要搜索一次，效率上大大提升。

4 總結(jié)

針對目前模糊密文搜索中用戶制作索引憑證開銷大、安全性低的問題，本文提出了一種基于鍵盤按鍵位置的模糊關(guān)鍵詞集合定義方法。通過分析可能出現(xiàn)的拼寫錯(cuò)誤，構(gòu)建了新型的模糊關(guān)鍵詞集合以及字典樹索引表。盡管提高了字典樹索引的大小，但是有效地減少了用戶搜索時(shí)的計(jì)算開銷和時(shí)間開銷，防止用戶制作索引憑證的信息泄露，增加了系統(tǒng)的安全性。未來工作中，還可以引入更多有關(guān)詞語語義的模糊搜索集合，提高搜索效率。

[1] Li J, Wang Q, Wang C, et al. Fuzzy keyword search over encrypted data in cloud computing[J]. Infocom, 2010, 3(9):1-5.

[2] Wang C, Ren K, Yu S, et al. Achieving usable and privacy-assured similarity search over outsourced cloud data[J]. Proceedings - IEEE INFOCOM, 2012, 131(5):451-459.

[3] Kuzu M, Islam M S, Kantarcioglu M. Efficient Similarity Search over Encrypted Data[C]// IEEE, International Conference on Data Engineering. IEEE, 2012:1156-1167.

[4] Liu C, Zhu L, Li L, et al. Fuzzy keyword search on encrypted cloud storage data with small index[J]. 2011:269-273.

[5] Ke T, Zhang W, Ke L I, et al. A Novel Fuzzy Keyword Retrieval Scheme over Encrypted Cloud Data[J]. Wuhan University Journal of Natural Sciences, 2013, 18(5):393-401.

[6] 吳陽, 林柏鋼, 楊旸,等. 加密云數(shù)據(jù)下的關(guān)鍵詞模糊搜索方案[J]. 計(jì)算機(jī)工程與應(yīng)用, 2015, 51(24):90-96.

[7] 杜軍強(qiáng), 楊波. 云計(jì)算中加密數(shù)據(jù)的模糊關(guān)鍵字搜索方法[J]. 計(jì)算機(jī)工程與應(yīng)用, 2015, 51(5):146-152.