一種靈活的精度可控的可搜索對稱加密方案

李西明 陶汝裕 粟 晨 黃 瓊 黃欣沂

1(華南農業大學數學與信息學院 廣州 510642)2(福建師范大學數學與信息學院 福州 350117)

隨著云計算的快速發展,數據外包在數據存儲市場的應用也越來越廣泛.通常情況下,用戶會選擇將數據外包給云服務器存儲,同時又不公開數據.為了保護數據和隱私,數據擁有者會先選擇加密數據,然后將加密數據上傳到云端.然而當用戶搜索關鍵詞獲得了一系列包含關鍵詞的文檔都太大時并且用戶只想查詢這些文檔中的一部分內容時,檢索就顯得十分麻煩，例如在線DNA測序等.最簡單的解決方法是將所有加密文檔下載到客戶端解密并檢索.但是,這不僅會造成巨大的網絡開銷,還會帶來不必要的計算成本.如果服務器不可信，那么用戶數據的安全性就很難得到保護.因此,可搜索的對稱加密方案(searchable symmetric encryption, SSE)迅速成為研究者們研究的熱點.

關鍵詞搜索技術通常分為精確關鍵詞搜索和模糊關鍵詞搜索.但是目前精確關鍵詞搜索存在很大的問題.當用戶描述不準確或輸入錯誤時，精確關鍵詞搜索可能無法找到用戶真正需要的文件.因為模糊搜索技術的引入可以靈活地找到與用戶輸入的搜索詞相關的文件，所以模糊關鍵詞搜索技術迅速發展了起來.但是由于數據是以密文形式存儲的，因此明文中使用的模糊搜索方法不能直接應用于密文搜索.從而模糊可搜索的加密機制是研究者重點研究的方向之一.

1 相關工作

近年來，研究人員針對不同的問題提出了許多可搜索的對稱加密方案(SSE).Popa等人[1]在2011年SOSP會議上首次提出CryptDB，它可以在加密文本上執行搜索操作，如MySQL中的LIKE等操作，并且提供了很好的安全性保證.陳萍等人[2]首次提出了可以在密文上執行所有SQL語句的CryptDB系統.CryptDB是以第三方中間代理人的形式來對數據庫提供安全高效的加密和解密方案.其主要核心分為3個模塊:加密策略、洋蔥加密模型和密鑰鏈管理模塊.但CryptDB存在著一些明顯的缺陷，例如，當前的同態加密只支持整數型運算不支持浮點型運算、不能做到對原始數據庫不作任何修改.在文獻[3]中汪海偉等人提出一個可搜索數據庫加密系統，解決了傳統的加密數據庫無法在保證數據安全性的同時實現執行復雜的SQL語句并解決了文獻[1]中的缺陷.Cash等人提出了一種針對不同數據庫規模的安全有效的數據處理方案[4]，特別是對于大型數據庫，它可以高效并秘密地搜索具有數百億記錄-關鍵詞對的加密的服務器數據庫.文獻[4]的基本構造方案支持單個關鍵詞搜索，并提供漸近優化的服務器索引大小、完全并行的搜索和最小的泄露，同時其所有方案和優化都被證明是安全的，并且泄露給不可信服務器的信息被精確地量化.

一方面可搜索加密方案[1-4]側重于解決密文數據庫存儲以及查詢的問題.另一方面在密文文本中搜索實現文本文件的可搜索加密技術也是當下研究的熱點.當服務器返回許多文檔到本地時，用戶無法將每個匹配了關鍵詞的文檔都下載到客戶端以確定哪些文檔是需要的，尤其是查詢結果中存在許多大型文檔時.這個問題是通常的SSE所不能解決的.此時子串可搜索對稱加密成為必要手段.在文獻[5]中Faber為了支持子串查詢需要構建重疊k-gram的索引，但是這個方案需要大量的存儲開銷來存儲所有的k-gram，這顯然是不現實的.Chase等人在文獻[6]中使用后綴樹來構建搜索框架.相比之下，后綴樹的數據結構沒有固定的大小，最多達2n個節點，每個節點存儲其邊、父節點和子節點的信息，從而增加了存儲需求.

傳統的精確關鍵詞加密搜索是不能容忍任何的拼寫錯誤，否則將返回錯誤的結果，這顯然不能滿足用戶的需求.Hu等人通過使用通配符來構建模糊關鍵詞集的方法來實現加密搜索[7].Zhou等人使用了編輯距離(edit distance)來設計加密搜索方案[8]，通過保存與關鍵詞在一定編輯距離內的所有單詞來緩解這種情況.雖然Zhou等人的這種方法可以實現對關鍵詞的模糊搜索，但是需要的存儲開銷較大并且最終得到的搜索結果中存在大量的弱相關性文檔從而導致計算開銷和網絡開銷的增加.Zhang等人提出一種高效的模糊關鍵詞集構建方法[9]，它是基于gram來構建模糊關鍵詞集，達到了較好的效果.

本文提出了一種基于Leontiadis等人[10]的靈活精度可控的可搜索對稱加密方案(flexible accuracy-controllable searchable symmetric encryption, FASSE)，FASSE方案支持靈活精度可控的加密搜索并且節省了大量的存儲開銷.FASSE考慮使用Leontiadis的方案為底層框架主要是因為其基于后綴數組的索引設計，其所允許的最佳存儲成本是O(n)，且在大小為n的字符串中具有小的隱藏因子.

相比許多基于關鍵詞集查詢的SSE方案，本文方案在4個方面有提高:

1) FASSE方案允許動態發出可變大小的子字符串查詢，而無需事先定義固定的查詢大小.

2) FASSE方案通過搜索加密的文檔摘要的FM索引(abstract FM index)，即AFM索引，解決了傳統的基于關鍵詞集查詢的SSE方案中可能會由于關鍵詞集創建的不友好從而導致沒有在關鍵詞集中查到任何記錄的問題;FM索引的結構和使用詳見第2節.

3) FASSE方案通過一次命中搜索、增強搜索和過濾搜索這3種搜索方法解決了在基于關鍵詞集合查詢的SSE中用戶得到許多低相關性文檔的問題.

4) 為了提升搜索的實用性，FASSE方案通過調節在模糊搜索中的一些參數實現了靈活搜索精度可控的模糊增強搜索.

2 預備知識

2.1 BWT數據轉換算法

Burrows Wheeler Transform(BWT)轉換[11]將原始文本數據轉換為一個相似的文本，轉換后使得相同的字符位置連續或者相鄰，經過BWT操作之后的文本數據可以使用其他編碼技術如Move-to-front transform和游程編碼進行文本壓縮.

BWT有4個主要步驟：

1) 在原始字符串S=“banana”的末尾添加一個‘$’字符，令S=“banana$”；

2) 字符串S循環向左旋轉n次得到矩陣W′；

3) 按字典順序排列矩陣的每一行字符串以獲得新的矩陣W；

4) 分別取矩陣W的第1列和最后1列，并將它們定義為F和L列，把L列作為BWT(S)的結果.

算法1給出了BWT轉換的具體描述.值得注意的是BWT中有一個十分重要的屬性就是第i次出現在F列中的字符x是對應于第i次出現在L列中的字符x，Burrows和Wheeler在文獻[11]中給出了證明.

算法1.BWT轉換算法.

輸入：字符串S；

輸出：轉換結果矩陣W.

l=S.length()+1;

S.append(‘$’);

i=0;

charW′[l][l];

S往左旋轉l次，每次的結果保存在W′的第i行中;

whilei

W′[i++]=rotate(S,i);

將矩陣W′的每一行按照字典順序重新排列最終得到W;

end while

returnW=SortedW′.

2.2 后綴和后綴數組

字符串S的長度為n，那么S的后綴是suffix[i]=S[i,…,n-1].字符串S=“banana”,那么字符串S的后綴suffix[i]={“banana”,“anana”,“nana”,“ana”,“na”,“a”}.后綴數組SA是字符串S所有后綴按照字典順序排序后，每個后綴對應于S中的位置的數組.S的后綴數組是SA[i]={5,3,1,0,4,2}.通常計算后綴數組SA的效率都比較低.例如樸素暴力窮舉算法的時間復雜度為O(n2logn)，它把字符串所有的后綴全部都計算出來后依次去排序最終得到后綴數組SA，這種方法的效率是十分低效的.倍增法[12]的時間復雜度為O(nlogn)，它是基于基數排序思想去計算后綴數組SA的.雖然倍增法已經極大地縮短了計算后綴數組SA的時間，但是相對于在一個線性時間復雜度O(n)下快速計算后綴數組SA的算法，倍增法就失去了優勢.Sanders等人提供了一個非常有效的skew算法[13].skew算法是根據原始字符串S的所有后綴的位置pos遞歸地將其分成3組:posmodh{1,2,3}，最后合并結果求出后綴數組SA.

2.3 LF映射

LF映射[11]是通過BWT(S)后得到矩陣W中的F列字符串和L列字符串多次反復迭代最終恢復原始字符串S的過程.它等同于在原始字符串S中搜索子字符串T，其中S=T.LF映射如算法2所示.

算法2.LF映射算法.

輸入：矩陣第1列F、矩陣最后1列L;

輸出：原始字符串S.

D=0;

i=0;

執行算法1得到轉換結果矩陣W；

判斷W的第F列和第L行；

在F列中查找排名等于r的L[i]的位置；

whileL[i]≠‘$’ do

D.push(L[i]);

r=rank(L[i]);*L[i]在L列中的排名*

i=find(F[L[i]],r);

end while

whileD≠‘0’ do

S=S+D.POP;

end while

returnS.

然而，實際上方案可以通過SubLF映射來部分恢復原始字符串S從而達到實現子串匹配的目的.它等同于在原始字符串S中搜索子字符串T，其中S≠T.這也是搜索子字符串的重要手段.SubLF映射的具體步驟如算法3所示.

算法3.SubLF映射算法.

輸入：矩陣第1列F、矩陣最后1列L、字符串m；

輸出：字符串m在串S中的位置pos.

l=m.length();

flag=0;

num=rank_max(m[l-1]);*查找m[l-1]的最大排名*

fori=0 tonumdo

forj=0 toldo

ifa≠⊥

a=find(F[m[l-j-1]],i)；

end if

ifa==⊥ orL[a]≠m[l-j-2]

flag=0,pos=null;

end if

returnpos;

end for

end for

flag=1;

r=rank(L[a]);

a=find(F[L[a]],r)；

ifflag==1

pos.append(a);

end if

returnpos.

2.4 FM索引

FM索引是由3列數組組成.FM索引的第1列F列是矩陣W的第1列，第2列L列是矩陣W的最后1列，最后1列是原始字符串S的后綴數組SA.為了支持LF映射，F列和L列中每個字符的唯一排名也都需要存儲在rF和rL中，其中rF和rL均來自于rank〈rF，rL〉二元組.最終通過LF映射利用公式[14]BWT(S)[i]=L[i]=S[SA[i]]，可以計算出后綴數組SA來完成子串查詢.FASSE方案利用文獻[10]中加密的FM索引的方法來構造整個方案.其中FASSE方案中的加密方法包括對稱加密方案SKE={Gen,Enc,Dec}和輕量級加密原語：偽隨機函數PRFFkf(·)，偽隨機置換PRPΠkπ(·).

加密的FM索引結構如圖1所示.其中L列和F列的值為Fkf(cLj)⊕Fkf(rFj‖cFj)‖Fkf(rLj‖cLj)和Fkf(cFj)⊕Fkf(rFj‖cFj).后綴數組SA為SKE.Enc(ke,SA[j])，最后執行PRPΠkπ(FM)打亂整個FM索引的順序.其中kf,kl是偽隨機函數密鑰;kπ是偽隨機置換密鑰;ke是對稱加密密鑰.加密的FM索引執行LF映射算法會比明文FM索引執行LF映射算法要復雜.具體做法是:先生成字符c的搜索令牌Fkf(c)，計算Fkf(c)⊕Fkl(c)，通過查找對應位置的LLset異或解密相應的LL得到字符c對應的二元組lc=〈nptr,addr〉，其中nptr是下一個lc的位置，addr是字符c在F列中的位置.在F[addr]上執行Fkf(c)⊕Fkf(cFj)⊕Fkf(rFj‖cFj)異或運算解密得到Fkf(rFj‖cFj)并且得到的Fkf(rFj‖cFj)可以在L列中執行Fkf(rFj‖cFj)⊕Fkf(cLj)⊕Fkf(rFj‖cFj)異或解密得到Fkf(cLj)，計算Fkf(cLj)⊕Fkf(rLj‖cLj)，繼續比對F列中的Fkf(cFj)⊕Fkf(rFj‖cFj)，經過多輪循環后得到搜索結果，即加密的SA[j].最終使用ke解密得到真正的SA[j].

Fig. 1 Construction of an encrypted AFM圖1 加密的AFM的構建

3 定義FASSE方案

3.1 方案系統模型

如圖2所示，FASSE方案系統模型包含3個實體：云服務器、授權用戶和數據擁有者.數據擁有者使用任意關鍵詞提取算法對文檔集合D提取的關鍵詞KW.數據擁有者為每一個文檔生成唯一文檔標示符id.加密的唯一文檔id得到唯一加密標示符d.數據擁有者加密文檔標題TIT得到ETIT且為每一個文檔構造出安全加密的EAFM索引.最后將加密文檔集ED及EAFM索引上傳至云服務器.云服務器保存ED和EAFM索引返回保存地址給用戶.數據擁有者構建并發送字典Dic到服務器保存.在搜索階段，授權用戶先對搜索的關鍵詞Q={q1;q2;…;qu}構造陷門TQ并上傳.當授權用戶接收到陷門TQ后，云服務器通過字典Dic進行搜索，如果云服務器執行一次命中搜索協議則將結果返回.如果云服務器執行增強搜索協議則通過搜索EAFM索引將結果返回.最后，授權用戶解密密文文檔ED.

3.2 FASSE方案威脅模型

在FASSE方案構建的威脅模型中，服務器被定義為是“半誠實并且好奇”的，敵手和云服務器被視為潛在威脅對象.FASSE方案中云服務器確保會完整正確地執行FASSE方案設計的所有搜索協議，不會惡意刪除用戶文檔和惡意泄露用戶隱私.但是云服務器可能會分析文檔和索引，例如統計分析字符頻率、文檔與關鍵詞匹配的數目、文檔的歷史信息等.在FASSE方案中敵手可能會和云服務器合謀，那么上述的這些隱私信息很可能會被敵手利用去分析攻擊系統，導致系統存在安全隱患.所以在此威脅模型中FASSE方案要確保所有歷史信息、陷門、字典、文檔信息和索引的安全.

3.3 FASSE方案算法描述

FASSE方案是7個多項式時間算法(KeyGen;Encrypt;PreProcess;DicGen;Trapdoor;Search;Decrypt)的集合，定義為：

1)K=KeyGen(1λ).其中，λ是安全參數.該算法用于生成加密密鑰K={k,kf,kl,kπ,ke,kt,kid,kaddr}，其中kf,kl是偽隨機函數密鑰，kπ是偽隨機置換密鑰，ke是對稱加密密鑰，kaddr由服務器生成.這些密鑰都是隨機數，均由系統隨機生成.

2)ED=Encrypt(k,D).D為明文文檔集合，D={D1,D2,…,Dn}.ED為密文文檔集合，ED={ED1,ED2,…,EDn}.使用密鑰k以及對稱加密算法(比如AES)加密生成ED.

3)EAFM=PreProcess({kf,kl,kπ,ke},F‖L‖SA).F是BWT(S)生成矩陣W的第1列，L是W的最后1列.SA是字符串文本S的后綴數組.使用密鑰{kf,kl,kπ,ke}以及對稱加密算法加密F,L,SA生成EAFM索引.

4)Dic=DicGen(Enc({kf,kid,kt,kaddr},KW,id,tit,EAFMaddr,EDaddr)).其中，KW是關鍵詞，id是文檔標示符，tit是文檔標題，EAFMaddr是EAFM的地址，EDaddr是ED的地址.使用密鑰{kf,kid,kt,kaddr}以及對稱加密算法加密KW,id,tit,EAFMaddr和EDaddr生成字典Dic.

5)TKW=SearchToken(kf,KW).其中KW是用戶查詢的關鍵詞.利用密鑰kf加密關鍵詞KW生成對應的搜索令牌TKW.

6)ED(KW)=Search(Dic,EAFM,TKW).利用搜索令牌TKW、字典Dic和EAFM索引進行查找，輸出與KW匹配的加密的文檔集ED(KW).具體的實現細節需要依賴具體的實現算法，將在第4節的4個搜索過程中進行詳細描述.

7)Di(KW)=Decrypt(K,EDi(KW)).使用對稱加密算法以及密鑰k解密包含關鍵詞KW的密文文檔EDi(KW)，生成包含關鍵詞的明文文檔Di(KW).

如果靈活精度可控的對稱加密方案FASSE是正確的，那么對于?λ∈N,n∈Z,D={D1,D2,…,Dn},KeyGen(1λ)和Encrypt(k,D)輸出的k和ED都有：

Search(Dic,EAFM,SearchToken(kf,KW))=EDi(KW)和Decrypt(k,EDi(KW))=Di(KW)成立.

3.4 FASSE方案系統安全性分析

本文設計的FASSE方案假設服務器是“半誠實且好奇”的，所有的數據查詢操作對服務器都是透明的，并且所有的明文數據處理都是由可信客戶端處理后以密文的形式上傳到服務器.服務器僅用于存儲和計算，而并不知道存儲和計算的具體內容.

當存在一個敵手A在不知道密鑰的情況下是無法得知存儲在服務器上加密文檔的任何信息.當敵手A在線攻擊分析時，首先敵手A并不知道搜索令牌tokenm對應的是哪個關鍵詞的令牌，那么敵手A就不可能知道搜索的是哪個關鍵詞.即便敵手得知搜索令牌對應的是哪個關鍵詞，最后也因為無法解密SA所以無法得知本次搜索結果是否有效，這也保護了用戶的隱私信息安全.

敵手A不能通過LLset離線分析字符的頻率去猜測攻擊，因為FASSE方案使用了Fkl(c)加密，Fkf(c)使敵手A無法在不觀察任何搜索令牌的情況下去執行離線頻率攻擊.即便敵手A獲得了搜索關鍵詞令牌也無法執行在線頻率攻擊，因為FASSE方案在LL中進行了填充使得每一個字符的頻率都一樣.

在存儲安全性方面如果存在惡意敵手A想要惡意刪除存在某個關鍵詞k的文檔時，在沒有破解字典之前就無法得知文檔的具體存儲地址、破壞文件，這一定程度上提升了文檔存儲的安全性.當存在一個敵手A試圖去離線分析字典Dic時，他無法得知服務器中存儲了多少文檔和每個關鍵詞對應多少文檔，因為客戶端已經將隨機記錄添加到字典Dic中了.為了提高安全性，字典Dic按字典順序排序.那么字典Dic在歷史上是獨立的，敵手A不能得知任何歷史相關信息.但是，當用戶在線搜索字符串時，服務器將向A暴露有多少個文檔包含字符串m.如果敵手A想要分析EAFM索引，他也不能得知任何與明文有關的內容，因為Leontiadis[10]針對離線頻率攻擊(offline frequency attack)、在線差別攻擊(online difference attack)、離線差別攻擊(offline difference attack)、在線頻率攻擊(online frequency attack)已經做出了相應的對抗手段.

3.5 數據結構圖

1) AFM. AFM是文檔摘要的FM索引.FM索引在文獻[10]中已經有了詳細的描述，它是子字符串搜索的核心部分.客戶端加密AFM后會得到EAFM，EAFM的結構如圖1所示.

2) 字典Dic. FASSE用一個字典Dic代替創建關鍵字集合.字典Dic中每一條記錄的第1個屬性是EKW，它等于F(kf，KW)，表示加密的關鍵詞Fkf(KW).第2個屬性是d，它等于Enc(kid，id)，表示加密文檔的標識符，其中kid是加密文檔標示符id的對稱加密密鑰.這里將加密文檔表示為ED.第3個屬性是Etit，它等于Enc(kf，tit)，表示文檔的加密標題.第4個屬性是EEDaddr，它等于Enc(kaddr，EDaddr)，表示EDaddr的加密地址，其中kaddr是加密EDaddr的對稱加密密鑰，EDaddr是加密文檔的地址.最后一個屬性是EEAFMaddr，等于Enc(kaddr，EAFMaddr)表示EAFMaddr的加密地址，其中EEAFMaddr是加密的AFM的加密地址.通過對EDaddr和EAFMaddr加密盡可能地阻止敵手A在離線分析這些地址的時候可以獲取到任何與明文文檔相關的任何內容或者破壞文檔.同時為了提高安全性，FASSE還將記錄(EKW，d，Etit，EEDaddr，EEAFMaddr)按字典順序添加到字典Dic中.另外，方案還會隨機添加q個記錄到詞典Dic中(q的大小可以手動設置也可以隨機生成)以防敵手A離線分析服務器端的文檔總數以及每個關鍵詞對應的文檔總數.字典Dic的結構如表1所示:

Table 1 Dictionary Dic表1 字典表Dic

3.6 初始化

首先，數據擁有者會將原始的明文文檔D上傳到客戶端同時會生成唯一的加密文檔標識符d.客戶端加密文檔D，生成加密文檔ED、文檔摘要的FM索引AFM、加密的文檔摘要的FM索引EAFM和加密的文檔標示符d，并通過有效地提取關鍵詞算法提取有效關鍵字kwi或者也可以使用預先設定好的關鍵詞kwi.同時使用kf作為密鑰的偽隨機函數PRFF(·)加密有效關鍵字kwi生成Fkf(kwi).客戶端通過計算Enc(kf，tit)來加密文檔的標題得到加密的文檔標題Etit.最后客戶端將這些加密的數據全部都上傳到服務器.服務器保存這些加密數據并且將這些加密文檔的地址EDaddr和加密的文檔摘要的FM索引即EAFM的地址EAFMaddr用kaddr進行加密得到加密文檔的加密地址EEDaddr和EAFM的加密地址EEAFMaddr.最終得到(Ewi，d，Etit，EEDaddr，EEAFMaddr)并生成記錄上傳到字典表Dic中.

4 FASSE加密搜索過程

一次命中搜索、增強搜索和過濾搜索，它們分別對應著用戶只用一次就在字典中找到關鍵詞記錄、沒有在字典中找到關鍵詞記錄而只用一次就在摘要中找到記錄或者多次在字典和摘要中查找到關鍵詞記錄的這3種搜索情況.

一次命中搜索主要適用于關鍵詞提取精度比較高的搜索場景.增強搜索主要適用于關鍵詞提取的比較粗糙的搜索場景.過濾搜索適用于存在關鍵詞重要程度概念的搜索場景.

4.1 一次命中搜索

用戶在輸入搜索字符串m之后服務器會在詞典Dic中依次去查找EKW=Fkf(m)的記錄.如果存在相應的記錄服務器會立即執行一次命中搜索，解密這些EEDaddr得到相應的加密文檔地址EDaddr，并將這些加密文檔標識符d、加密文檔標題Etit和加密文檔地址EDaddr全都發送給客戶端.客戶端會通過計算Dec(kf，Etit)來解密這些文件加密的標題得到明文的標題tit.用戶通過tit選擇對應需要的加密文檔標識符d.客戶端通過這些加密文檔標識符d找到對應的加密文檔地址EDaddr并將這些加密文檔地址EDaddr發送到服務器并請求服務器下載這些加密文檔ED.如圖3所示，一次命中搜索協議的特點是對于搜索關鍵詞已經在字典Dic中的這次搜索服務器會直接檢索字典Dic中的EKW屬性從而最快得到檢索結果，它是整個FASSE搜索過程中耗時最短、精度最高的.但是和傳統的基于關鍵詞集合的SSE一樣，對關鍵詞的提取和關鍵詞集的建立的要求都十分高.綜上可得一次命中搜索主要適用于關鍵詞提取精度比較高的搜索場景.

一次命中搜索協議如下：

客戶端:生成搜索字符串m的搜索令牌tokenm并發送到服務器.

服務器:ifFind(tokenm,Dic)==⊥

返回⊥(空)到客戶端;

else

返回d,Etit,EEDaddr和relativity到客戶端;

其中relativity的每一個元素值都為“Max”.

end if

客戶端:if 從服務器端接收到⊥

請求服務器執行增強搜索or結束退出;

relativity*

設置relativity的每一個元素值都為1.0；

生成新的搜索字符串mi的搜索令牌

tokenmi;

發送tokenmi,d,Etit,EEDaddr和relativity

到服務器請求執行過濾搜索;

or發送EEDaddr后等待接收從服務器發送的ED；

else

解密Etit得到tit;

根據tit選擇需要的d并得到相應的

EEDaddr;

發送EEDaddr到服務器請求服務器進行下載.

end if

end if

服務器:解密EEDaddr下載ED發送到客戶端.

4.2 增強搜索

如果服務器在詞典Dic中未找到任何相應的記錄時，這種情況是經常遇到的，那么增強搜索將起到重要的作用.服務器將通過字典Dic去搜索每個文檔的EAFM，并將與字符串搜索令牌即Fkf(m)相匹配的記錄中的d，Etit和服務器解密后得到的EDaddr發送到客戶端.如果擔心服務器返回大量無效填充位置，那方案也可以使用文獻[10]中的bucke-tization技術并選取適當大小的窗口使填充節點的數量大大減少.通過計算Dec(kf，Etit)來解密得到這些文件的標題tit.用戶通過tit選擇需要的d.最后，客戶端將EDaddr發送到服務器請求下載這些ED.增強搜索結構如圖4所示.如果服務器有足夠的空間資源FASSE也可以采用建立內容的FM索引即CFM(FM index of the content)的方法來進一步提高搜索結果的精確性.增強搜索協議的特點是針對字典Dic中不存在搜索關鍵詞的情況下從而對文檔摘要進行搜索，那么增強搜索相對一次命中搜索速度就會慢上很多，但它也打破了傳統基于關鍵詞集合的SSE因為在關鍵詞集合中未檢索到搜索關鍵詞而無結果的尷尬局面.綜上可見增強搜索主要適用于關鍵詞提取的比較粗糙的搜索場景.

Fig. 4 Reinforcement search圖4 增強搜索

增強搜索協議如下：

服務器:解密整個字典Dic中的EEAFMaddr得到EAFM;

對EAFM執行SubLF映射算法;

計算m在所有摘要中不算填充的有效次數Occur;

ifOccur中的每一元素的值都為0

返回⊥并結束退出;

else

從Occur中選最大的nk項Occurk;

取出Occurk對應字典Dic中nk項的記錄

Temp;

設置relativity的每一個元素值與Temp[Occurk]相對應;*當從過濾搜索執行增強搜索時relativity等于上一次的relativity加上0.2*Temp[Occurk]*

發送Temp[d,Etit,EEDaddr,Occurk]到客戶端.

end if

客戶端:取出Temp[Occurk];

生成新的搜索字符串mi的搜索令牌tokenmi;

發送tokenmi,d,Etit,EEDaddr和relativity到服務器請求執行過濾搜索；

or發送EEDaddr后等待接收從服務器發送的ED；

else

解密Temp[Etit]得到tit;

根據tit從Temp[d]選擇需要的d并得到

相應的EEDaddr;

發送EEDaddr到服務器請求服務器進行下載.

end if

服務器:解密EEDaddr下載ED發送到客戶端.

4.3 過濾搜索

Fig. 5 Filter search圖5 過濾搜索

用戶在經過了一次命中搜索或者增強搜索之后仍然得到了許多難以選擇的tit和d，這是最常見的但也同時是最麻煩的情況.這種情況如果服務器的查詢結果中只有少量的小文件時，那么用戶就可以直接發送請求給服務器請求服務器下載這些文檔到本地來篩選并確定哪些文檔是自己需要的.但是如果服務器的查詢結果中有許多大文檔時，那么巨大的網絡開銷是服務器和客戶端雙方都難以承受的.事實上FASSE中的過濾搜索其實是相當于一個篩子，可以連續地過濾用戶不滿意的文檔.FASSE將成功匹配m1搜索令牌的數量定義為相關性，字符串m1出現在摘要中的頻率越高，那么文檔的相關性越大，反之亦然.服務器會選擇相關度最高的前n%個文件進行下一步處理.n可以通過計算成功匹配了字符串m1摘要的總數的百分比或手動設置合適的數字來確定.服務器將nd，nEtit和解密后的nEDaddr返回給客戶端，客戶端通過計算Dec(kf，Etit)來解密這些tit.最后，用戶通過tit選擇需要的d和EDaddr最終獲得需要的ED.過濾搜索是通過使用不同的字符串mi在這些難以選擇的d上執行重復搜索.用戶將得到n1，n2…直到有確定可以下載的nk個d時，下載這nk個文件，因為重復過濾后文件的相關性達到了最大.過濾搜索結構如圖5所示.因此可得，用戶可以控制搜索的精準性，以便搜索需要的文檔.搜索的準確度越高，用戶獲得預期文檔的可能性就越大，FASSE通過控制用戶獲得預期文檔的可能性就越大.FASSE通過控制過濾搜索的次數來達到精度的控制，從而實現精度可控的搜索.過濾搜索協議的特點是針對在一次關鍵詞搜索字典和文檔摘要后得到太多的結果的局面，對文檔進行反復多次地一次命中搜索或增強搜索，它消耗的時間最多、速度最慢，并且需要用戶手動設置新的關鍵詞.綜上所述過濾搜索適用于存在關鍵詞重要程度概念的搜索場景.

過濾搜索協議如下：

服務器:接收從客戶端發送的d,Etit,EDaddr,relativity;

ifFind(tokenmi,Dic,d)==⊥

返回⊥(空)到客戶端；

else

返回d,Etit,EEDaddr和relativity到客戶端;

其中relativity的每一個元素值都為“Max”.

end if

客戶端:if 從服務器端接收到⊥

請求服務器在d上執行增強搜索;

or發送EEDaddr后等待接收從服務器發送的ED.

relativity*

end if

if 搜索結果相關性低

設置relativity的每一個元素值都為1;

生成新的搜索字符串mi的搜索令牌tokenmi;

發送tokenmi,d,Etit,EEDaddr和relativity

到服務器請求執行過濾搜索;

or發送EEDaddr后等待接收從服務器發送的ED;

else

解密Etit得到tit;

根據tit選擇需要的d并得到相應的EDaddr;

發送EDaddr到服務器請求服務器進行下載.

end if

服務器:解密EDaddr下載ED發送到客戶端.

4.4 基于通配符的模糊增強搜索

模糊增強搜索操作是利用通配符‘*’和‘?’在普通增強搜索的基礎上進行簡單的修改.當服務器在成功匹配到搜索令牌Fkf(T[i])時，如果發現Fkf(T[i])=Fkf(‘?’)，那么直接跳過這次與L列中Fkf(cLj)的比對，利用從F列中得到的Fkf(rFj‖cFj)異或L列中的Fkf(cLj)⊕Fkf(rFj‖cFj)‖Fkf(rLj‖cLj)獲得L列中的Fkf(cLj)‖Fkf(rLj‖cLj)，繼續通過異或運算得到Fkf(cLj)⊕Fkf(rLj‖cLj)Fkf(cLj)‖Fkf(rLj‖cLj)并通過LLset依次在F列中查找與Fkf(cLj)⊕Fkf(rLj‖cLj)相等的Fkf(cFk)⊕Fkf(rFk‖cFk)，經過多次迭代后就可以找到需要搜索的關鍵詞.為了進一步提高方案的靈活性，方案提出了最大容忍錯拼字符數em，并且默認em=0;也可以手動設置em的值，只要em的值合理即可.關于錯拼的搜索本質基本和‘?’一樣，它需要引入一個錯誤程度變量e，當發現Fkf(cLj)不等于Fkf(T[i-1])時直接跳過這次在L列中的比對，同時執行e++一次，只要e不超過設定的最大容忍錯拼字符數em就屬于錯誤可容忍范圍內.關于通配符‘*’，FASSE設置‘*’最大能夠表示r個字符.本文在實現FASSE方案時將r的值設置為2.例如“he*lo”={“helo”,“he?lo”,“he??lo”}.通過觀察發現增強模糊搜索本質上還是對包含‘?’的字符串搜索.關于e,它和“?”一樣相當于在不匹配的位置上加上了“?”.本方案通過對em,r,“?”和“*”的設置來實現靈活的精度可控的模糊搜索.最后可能還會得到一些不相關的結果，可以通過返回結果的相關性來剔除相關性低的結果，從而得到一個相對不錯的結果.

5 實驗驗證

5.1 測試環境搭建

本方案實驗測試使用的計算機操作系統是Windows7，機器配備了Intel?CoreTMi5-4590 CPU @ 3.30 GHz四核處理器，具有8 GB RAM內存.實驗是在本地同時模擬了一臺服務器和一個客戶端，開發環境為Eclipse_4.5.0，使用語言為Java編程語言.對稱加密算法是使用AES密碼算法且實現均調用的是java.security和javax.crypto下工具包.本系統的實現Java代碼已經全部上傳至https:github.comtaoruyuFA-SSE.git上.

5.2 實驗設計

本實驗主要從2個方面測試方案的性能效率.首先測試上傳生成索引的時間效率，研究生成索引的時間與文檔的數量和摘要包含的字符數的相關性；其次對搜索的效率進行進一步的實驗研究.對于搜索的效率研究，本文從增強搜索和模糊增強搜索2個方面進行對比試驗，探索文檔的數量與搜索關鍵詞長度和文檔包含的字符總數對搜索效率的影響.關于本次實驗的所有實驗數據均來自于真實數據集eprint中所有文章的英文摘要.FASSE方案搜索的時間效率主要取決于是否是執行了一次命中搜索.如果搜索過程中的所有操作都是一次命中搜索，這意味著它在搜索過程中所需的時間幾乎等于在字典Dic中搜索全部記錄的時間.這個時間相對于其他搜索過程是可以被忽略不計的.然而，搜索操作不可能都是一次命中搜索，大多數情況下都是增強搜索或過濾搜索，并且搜索過程中的大部分時間也都會消耗在這2種搜索過程中.經過多輪搜索后，增強搜索和過濾搜索的次數將繼續不斷增加，搜索所需的總時間會越來越多，但是每一輪新的搜索所需要的時間也會越來越短同時準確性會越來越高.本實驗中未對過濾搜索的性能進行實驗研究，因為過濾搜索的時間是可以從增強搜索的時間效率圖中計算出來的.過濾搜索本質也是一次命中搜索和增強搜索的不斷循環交替，不同的是過濾搜索的文檔范圍會越來越小.

5.3 實驗結果

Fig. 6 Efficiency of uploading and searching for the FASSE圖6 FASSE方案的上傳和搜索的效率

FASSE方案的上傳和搜索的結果具體參考圖6.其中圖6(a)展示了FASSE方案上傳文件所需的時間效率圖.從中可以計算出當摘要包含500字符以內時，上傳效率平均每個為0.09 s；當摘要包含500～1 000字符時，上傳效率平均每個為0.32 s，當摘要包含1 000～1 500字符時，上傳效率平均每個為0.79 s；當摘要包含1 500～2 000字符時，上傳效率平均每個為1.42 s；當摘要包含2 000～2 500字符時，上傳效率平均每個為2.34 s.圖6(b)表示增強搜索的時間性能圖(固定摘要包含2 000～2 500字符)，可以發現當文檔數逐漸增加時，搜索所需時間越來越不穩定，這是由于不同的搜索關鍵詞在文檔中的頻率不一樣導致的.圖6(c)表示關鍵詞搜索與文檔摘要包含的字符總數的關系圖(固定搜索關鍵詞長度為3).圖6(c)可以發現摘要包含字符總數與搜索時間呈現正相關，且呈現出當文檔數越多這種正相關性越強的趨勢.在圖6(c)中，當摘要包含的字符總數小于500時，對于各個不同文檔數量的平均搜索時間依次為36.425 ms，67.375 ms，109.125 ms，149.125 ms，209.25 ms，故平均搜索時間為114.26 ms.文獻[15]討論了面向多關鍵字的模糊密文搜索，與本文設計的方案相近，同本文具有一定的可比性.該文通過將文件數分為6類進行可搜索對稱加密實驗，該文的平均搜索時間約為120 ms，本文的搜索效率略有提高.

Fig. 7 The efficiency of fuzzy enhanced search with different n圖7 文檔數n不同時模糊增強搜索效率

通過圖6的實驗看到了搜索關鍵詞對實驗結果的影響，圖7將給出模糊增強搜索的搜索效率圖.(由圖6(b)得到結果，設置固定關鍵詞長度為6).

由圖7可以發現通配符‘?’對搜索結果的影響其實并不大，所以方案會在提高實用性的同時也會兼顧搜索的效率.

6 總 結

本文基于Leontiadis[10]可搜索對稱加密方案提出了一種能夠支持靈活的精度可以控制的可搜索對稱加密方案——FASSE方案，它支持靈活精度可控的加密搜索并且節省了大量的存儲開銷.FASSE方案提供了4種基本搜索方式：一次命中搜索、增強搜索、過濾搜索和模糊增強搜索.同時，本文還結合這4種搜索方式設計了一種基于通配符技術的模糊增強搜索，并且通過設置部分參數從而達到靈活可控精度的搜索效果從而進一步增強系統的實用性.最后實驗得出FASSE方案在實驗論文數據集中平均搜索完每一篇論文的時間為114.26 ms.通過實驗可以發現FASSE方案可以輕松應對各種關鍵詞的搜索.但是目前FASSE方案不支持動態更新EAFM索引，所有的EAFM索引都是靜態的，對用戶操作(增、刪、改)都無法做到及時更新，必須重新生成EAFM索引，這會導致時間和空間開銷增加，所以一個可以動態更新EAFM索引的解決方案是我們今后的目標.FASSE將會參考文獻[16]，并且在未來希望它能幫助改進FASSE.此外，FASSE方案的模糊搜索方案中暫時不提供一次命中模糊搜索，所以在今后的工作中希望可以彌補這一點.