基于多關鍵字的Top-k布爾可搜索加密方案

郭斯栩 何 申 粟 栗 張 星 周福才 張鑫月

1(中國移動通信有限公司研究院安全技術研究所 北京 100053)2(東北大學軟件學院 沈陽 110819)

現階段，越來越多的用戶和企業選擇將自己的數據存儲及業務計算外包到云服務器中，并由其代為存儲和計算，以節省數據存儲開銷和系統維護開支.為了保證云端數據的機密性，人們首先考慮到對數據進行加密.然而，加密之后的數據，也喪失了數據原有的特性.經過大量的研究之后，可搜索加密(searchable encrypion)[1-5]技術應運而生.可搜索加密是指對于諸如文件、數據表等信息，在加密之后通過使用關鍵詞的手段對密文進行搜索.最早的可搜索加密[1]這一概念是由Goldreich和Ostrovsky提出的.傳統的可搜索加密方案包含客戶端與服務器2個實體以及2個階段：數據初始化階段和搜索階段.在數據初始化階段，客戶端對每一個關鍵字生成倒排索引，同時對索引加密生成加密索引，并將加密后的文件集合與加密索引上傳至服務器；在搜索階段，當用戶發起搜索請求時，客戶端向服務器發送待搜索關鍵字的搜索令牌.該令牌利用密碼學知識將關鍵字封裝，且無法泄露任何關鍵信息.當服務器獲得令牌后，利用數學運算等方式將加密索引解開，返回符合搜索條件的文件.現如今，可搜索加密的重要性從其廣泛的應用領域中顯而易見，其中許多工作正在進行中.文獻[6]中提出可搜索加密正在探索物聯網設備和智能電表；文獻[7]中提出可搜索加密技術被應用于云環境中的電子醫療保健系統中；文獻[8]中討論：當與區塊鏈技術結合使用時，可搜索加密也會對安全交易產生深遠的影響.隨著同態加密的出現，在基因組分析中也正在探索使用可搜索加密來安全地分析和搜索人類DNA序列[9].

同時，為了保證從大數據中高效安全地提取重要信息，滿足用戶需求，我們考慮針對一些特殊的關鍵字對每一個文件進行排名，top-k排名搜索[10-15](top-kranking search)技術應運而生.Fagin[10]首先提出了top-k排名搜索這一概念，目的是解決針對大數據的文件檢索.由于很多場景對文件等數據的排名有特定的要求，top-k排名搜索一經提出便備受關注，在搜索引擎、電子商務、移動App等諸多領域得到了廣泛的研究與應用.用戶通過對關鍵字不同屬性的權值設定來反映其自身偏好，而云服務器則根據用戶提供的權值信息作為排名依據進行計算，并返回符合用戶需求的前top-k個數據.top-k排名搜索能夠幫助用戶從大量數據中精確找到自己所關心的信息，因此研究top-k排名搜索具有非常實際和廣泛的應用價值.

然而，當前的top-k排名算法大多針對明文數據，這無法確保在云服務器上保證數據的安全性，因此top-k排名與可搜索加密機制的結合也勢在必行.但現存的可搜索加密方案大多不支持top-k排名搜索；在構建可搜索加密方案時，通常需要考慮隱私性、效率與查詢有效性[16]這3個因素，盡管這些因素同等重要，但大多數現有方案無法在它們之間保持平衡；同樣地，現階段的可搜索加密方案大多只支持對單關鍵字的搜索，無法對多關鍵字進行高效的布爾搜索.因此，這些方案缺乏可用性，無法部署到真正的云服務器上.

針對上述所提到的問題，本文提出一種基于多關鍵字的top-k布爾可搜索加密方案(top-kboolean searchable encryption scheme based on multiple keywords, TBSE).其能夠滿足用戶的日常需求，在對多關鍵字進行安全高效的布爾搜索的同時，對文件進行高效的top-k排序.TBSE首先利用數學中集合論的知識，對多關鍵字進行高效的布爾搜索；然后構建正向文件索引，利用安全協處理器對搜索后的文件進行top-k排名.另外，現存的可搜索加密方案所使用的倒排索引大多不支持動態更新，在增加或刪除關鍵字時，倒排索引需要重新構建.這不僅僅降低了關鍵字更新的效率，每次重構索引也會泄露更多文件信息.TBSE利用Goldwasser-Micalli與2DNF這2種加密算法構建關鍵字索引，能夠對索引進行動態的更新，同時利用搜索令牌的巧妙構造，大大提高了搜索效率與top-k排名效率.通過安全性分析，證明該方案滿足自適應安全.

本文的優勢在于，從功能性的角度考慮，相比于傳統可搜索加密方案，TBSE方案能夠在支持布爾搜索的同時，對搜索后的文件進行top-k排名；相比于文獻[17]中的方案，該方案支持對多關鍵字進行布爾搜索；相比于文獻[17-19]中的方案，本方案支持對索引的動態更新.從性能的角度考慮，首先考慮到對關鍵字的搜索效率，由于TBSE方案獨特的索引構造，其搜索效率與索引長度無關，只與關鍵字個數成線性關系，因此相比于文獻[18-19]中的方案，本方案提升了布爾搜索的效率.關于索引存儲效率，文獻[18]中方案的索引存儲空間與關鍵字個數成線性關系，文獻[19]中方案在此基礎上做出了改進，其索引存儲空間與關鍵字個數成亞線性關系，而本方案由于索引結構為向量形式，其索引存儲空間只與向量長度有關，而與關鍵字個數無關.因此，本方案的索引存儲效率為一個常數級，當關鍵字個數較多時，其索引存儲效率將會大大提升.

1 相關知識

1.1 Goldwasser-Micalli公鑰加密方案

Goldwasser-Micalli(GM)公鑰加密方案是第1個在標準密碼假設下可證明安全的概率公鑰加密方案，由Gen,Enc,Dec三個算法組成.

3)Dec.解密算法.對于密文ci∈C，利用私鑰sk，對密文中的每一個比特ci解密，得到明文xi：

(1)

由于GM加密是使用概率算法執行的，所以給定的明文在每次加密時可能產生非常不同的密文，這具有顯著的優點.

1.2 2DNF同態加密方案

2DNF加密方案[20]滿足同態機制，其具有加法同態性質，這與Paillier[21]加密方案相似.具體地說，2DNF加密方案由Gen,Enc,Dec三個算法組成.

1)Gen.密鑰生成算法.給定一個安全參數l.首先選擇2個l-bit的奇素數q1,q2，計算N=q1×q2∈.生成N階雙線性群G，令g,u為G的2個生成元，然后計算h=uq2為G的q1階子群的隨機生成元.最后輸出私鑰sk=q1和公鑰pk=(N,G,GT,g,h).

2)Enc.加密算法.假設消息空間由集合{0,1,…,T}中的整數組成且T

2DNF加密方案有加法同態的特性，即：給定密文E(a1),E(a2)，那么a1+a2的密文可以被計算.同時，方案中的解密時間是消息空間m大小的多項式時間，因此，2DNF密碼方案顯然可以有效地適用于短消息.

1.3 逆向文本頻率TF-IDF

TF-IDF[22]是一種信息檢索的常用技術，主要用于對文件中常用關鍵字進行加權.在信息檢索領域常用 TF-IDF作為統計方法，用以評估一個字詞對于一個文件集或一個語料庫中的其中一份文件的重要程度，因此用這項技術進行top-k排名搜索來說再合適不過了.在該技術中，不僅僅只關注字詞出現的頻率，因為例如“的”、“the”這些詞匯在文章中經常出現，但意義卻并不大.因此，TF-IDF 技術的字詞的重要性不僅僅隨著它在文件中出現的次數成正比增加，同時會隨著它在語料庫中出現的頻率成反比下降.

1.4 布爾搜索與集合論

在進行布爾搜索的過程中，首先要對生成的邏輯檢索式進行析取操作，得到一個標準的關鍵字連接式δ1∨δ2∨…∨δ，其中，對于任意一個δi來說，δi=ωi,1∧ωi,2∧…∧ωi,q，對于集合的交集來說，只需要將二者包含的相同內容找到即可，對于集合的并集來說，需要找到集合的交集，并用二者的和減掉交集，這樣做，無疑浪費了大量的時間用在求和與減法操作上.

在集合論知識體系中，有一種將并集操作轉化為交集操作的內容，例如，有3個集合DB(ω1),DB(ω2),DB(ω3)，關系如圖1所示：

Fig. 1 Collection relationship diagram圖1 集合關系示意圖

對于3個集合的并集操作來說，推導過程[19]：

DB(ω1)∪DB(ω2)∪DB(ω3)=
(id1,id2,id3,id4)?(id1)+(id3)+(id2,id4)=
DB(ω1)-(DB(ω1)∩DB(ω2))-(DB(ω1)∩
DB(ω3))+DB(ω2)-(DB(ω2)∩
DB(ω3))+DB(ω3)=(id1,id3,id4)-
(id3)-(id4)+(id3)-?+(id2,id4).

(2)

至此，就完成了用交集操作替換并集操作的推導過程.

2 TBSE方案

本節將描述TBSE方案的模型、形式化定義以及存在的安全威脅.

2.1 方案模型

TBSE方案包括3個實體，分別是數據擁有者、云服務器和安全協處理器(secure coprocessor, SCP)如圖2所示：

Fig. 2 The architecture of TBSE scheme圖2 TBSE方案的體系架構

對于圖2所示的方案模型而言，TBSE方案首先執行圖2中虛線所表示的離線傳輸階段.數據擁有者將加密文件及加密關鍵字索引傳送至云服務器，并將加密分數索引及top-k排名中的k值傳送至SCP.接下來方案執行在線傳輸階段，包括4個步驟：

1) 數據擁有者將搜索令牌傳送至云服務器，發出搜索請求;

2) 云服務器執行搜索后，將搜索后的結果與搜索令牌傳送至SCP;

3) SCP對搜索結果執行top-k排名后，將前k個加密文件傳送至云服務器;

4) 云服務器將排名后的前k個加密文件傳送至數據擁有者，整個TBSE方案執行完畢.

在TBSE方案中，安全協處理器被認為是一個代理的小型服務器，它駐留在云服務器提供的隔離執行環境中，被認為是可信的.數據擁有者首先將文件加密，并上傳到服務器.云服務器被認為是誠實且好奇(curious but honest)的.下面對3個實體在本方案中的功能進行詳細介紹：

1) 數據擁有者.負責生成整個搜索方法中要使用到的密鑰及利用對稱加密算法生成加密文件，即負責初始化的部分；他要對自己的文件集合生成對應的關鍵字集合，并根據二者生成倒排索引；他要對已經生成的倒排索引進行處理，加密后上傳至云服務器，即要負責關鍵字索引生成；由于要實現布爾搜索，該索引包括單關鍵字索引及交集索引2部分；為了實現top-k排名，他需要為每一個文件生成正向的分數索引；同時對于每一個待搜索的關鍵字，數據擁有者需要為其生成關鍵字所對應的令牌，并將其傳送給數據擁有者；同時，當搜索結果返回時，他需要對數據進行解密，并得到搜索到的文件.

2) 云服務器.主要接收數據擁有者傳送的加密索引；接受可信賴用戶的搜索請求及相應的搜索令牌，并進行搜索操作；同時它還接受數據擁有者發出的搜索請求，并接收安全協處理器排名好的top-k個文件集.

3) 安全協處理器.主要負責接收加密的分數索引，同時接收云服務器傳遞的加密的字符串，對關鍵字進行搜索及 top-k排名，并返回相應文檔標簽至云服務器.

2.2 形式化定義

TBSE方案共包含7個算法，分別是密鑰生成算法、關鍵字索引生成算法、加密分數索引生成算法、令牌生成算法、搜索算法、top-k算法以及索引更新算法，TBSE方案所示：

(KeyGen,IndexGen,ScoreIndexGen,
TrapdoorGen,Search,Top_k,IndexUpdate).

每個算法的具體描述為：

1) 密鑰生成算法KSY,KDN,KGM←KeyGen(λ)為概率性算法，運行于數據擁有者.輸入安全參數λ，輸出對稱加密密鑰KSY，2DNF加密密鑰KDN=(pkDN,skDN)以及GM加密密鑰KGM=(pkGM,skGM).

2) 關鍵字索引生成算法EID←IndexGen(pkDN,pkGM,V,W,R)為概率性算法，運行于數據擁有者.輸入密鑰pkDN,pkGM，隨機正交向量集V，關鍵字集合W以及隨機數集合R，輸出關鍵字加密索引EID.

3) 加密分數索引生成算法EIDScore←ScoreIndexGen(pkDN,D,V,W,R)為概率性算法，運行于數據擁有者.輸入密鑰pkDN，隨機正交向量集V，文檔集合D，關鍵字集合W以及隨機數集合R，輸出加密分數索引EIDScore，用于對搜索后的文件進行top-k排名.

4) 令牌生成算法τwq←TrapdoorGen(KDN,W,V)為確定性算法，運行于數據擁有者.輸入密鑰pkDN，隨機正交向量集V以及關鍵字集合W，輸出關鍵字的搜索令牌τwq.

5) 搜索算法?wq←Search(EID,τwq)為確定性算法，運行于云服務器.輸入加密的安全索引EID，搜索令牌τwq，輸出每一個搜索關鍵字所對應的加密字符串?wq.

6) top-k算法Dk←Top_k(?wq,skGM,k,EIDScore,τwq)為確定性算法，運行于SCP.輸入加密字符串?wq，密鑰skGM，搜索令牌τwq，加密分數索引EIDScore與可選數字k，輸出top-k個文檔集合Dk.

7) 索引更新算法EID′←IndexUpdate(EID,w′)為概率性算法，運行于數據擁有者.輸入為加密索引EID與待更新的關鍵字w′，輸出為新的加密索引EID′.

2.3 安全威脅

根據文獻[17，22]，本文方案考慮2種模型安全威脅，即已知明文模型和已知背景模型.本方案認為數據擁有者和SCP是完全可信的實體，而云服務器是“誠實且好奇的”，它會“誠實地”根據算法的指定協議存儲數據擁有者全部的數據文檔，但對存儲的數據“感到好奇”，即云服務器想通過推斷或分析加密數據和搜索令牌來獲取數據擁有者的數據信息.

2) 已知背景模型.在已知背景模型中，云服務器能夠獲取比已知密文模型更多的數據信息，比如關鍵字索引之間、搜索令牌之間相關的信息或者數據集之間的統計信息等.因此，云服務器具有更強的攻擊能力.云服務器可以根據已知的令牌信息，并借助一些統計信息來推斷，分析上傳的加密索引，搜索令牌和搜索結果等來確定搜索中的某些關鍵詞的明文信息.

3 TBSE方案詳細設計

本節主要介紹TBSE方案的詳細設計.TBSE方案需要解決3個問題：1)能夠高效地實現對多關鍵字的布爾搜索；2)能夠對搜索后的文件進行有效的top-k排序；3)能夠對構建的關鍵字安全索引進行動態更新.根據第2節形式化定義，下面對TBSE方案的7個算法分別進行詳細描述.

3.1 密鑰生成算法

密鑰生成算法KSY,KDN,KGM←KeyGen(λ)在數據擁有者端實現.TBSE方案在加密文件時利用傳統對稱加密方式(如AES)的方式加密文件，輸入安全參數λ，生成文件加密密鑰KSY.本方案在構造加密索引與搜索令牌的過程依賴于GM加密與2DNF加密，輸入安全參數λ，生成2個加密方案的公私鑰KDN=(skDN,pkDN),KGM=(skGM,pkGM).根據相關知識，pkDN=(N,G,GT,g,h),skDN=q1;pkGM=(n,m),skGM=p.

3.2 關鍵字索引生成算法

關鍵字索引生成算法EID←IndexGen(pkDN,pkGM,V,W,R)實現于數據擁有者端.為了實現布爾搜索，利用預備知識中集合論的相關知識，本方案所構建的關鍵字加密索引包含2個部分：對單關鍵字的加密索引SEID與關鍵字之間交集的加密索引inEID.

3.2.1 單關鍵字加密索引生成

首先，數據擁有者為每一個關鍵字wi∈W生成一個長度為|D|的二進制索引串biwi，即當文件dj∈D中包含關鍵字wi，biwi的第j位記為1，否則記為0.每一條biwi被存放在一個字典的數據結構中，記為biD(wi)，大小為|W|，biD(wi)構造如圖3所示：

Fig. 3 Construction of binary dictionary圖3 二進制字典構造結構

對字典中的每一個元素，使用GM加密生成Gi=EncGM(pkGM,bID(wi)).定義V是一個互相正交的向量集,vi∈V為每一個關鍵字所對應的隨機向量，r∈R為一個隨機數，vr∈V為一個隨機向量.對每一個關鍵字wi使用2DNF加密生成Di=EncDN(pkDN,wi).利用上述步驟，生成關鍵字集W所對應的單關鍵字加密索引向量SEID，其構造：

(3)

3.2.2 關鍵字交集加密索引生成

根據集合論相關知識，數據擁有者首先為每一個關鍵字wi∈W與其后面的關鍵字wj∈W做交集，生成(|W||D|)個交集倒排索引inIDi.與單關鍵字加密索引生成類似，根據每一個關鍵字的交集倒排索引生成長度為|D|的二進制索引串inbIDi，并將其依次存放于一個字典中.將每一個字典放入一個Multi-map結構MMb(wi)中.對MMb(wi)的每一個元素，采用與生成單關鍵字加密索引類似的方法生成加密索引.使用GM加密生成inGi∩inGj=EncGM(pkGM,inbIDi).對進行交集操作的關鍵字之間做“⊕”異或操作，使用2DNF加密生成inDi∩inDj=EncDN(pkDN,wi⊕wj).其余操作與生成單關鍵字加密索引類似.數據擁有者將每一個關鍵字對應的交集加密索引向量放入字典inD(wi)中，其構造：

(4)

綜上所述，關鍵字交集索引inEID生成完畢.

3.3 加密分數索引生成算法

加密分數索引生成算法EIDScore←ScoreIndex-Gen(pkDN,D,V,W,R)實現于數據擁有者端.分數索引為正向索引，即每一個文件dj對應一串索引，這與關鍵字索引不同.數據擁有者首先計算關鍵字wi在文件中的“詞頻”(TF)與“逆向文本頻率”(IDF)對dj構建分數索引，以方便之后對文件進行top-k排序,記關鍵字wi在文件dj中的個數為c.計算文件的TF-IDF值后，存放在字典sD(dj)中.其算法為

(5)

(6)

3.4 令牌生成算法

令牌生成算法τwq←TrapdoorGen(KDN,W,V)實現于數據擁有者端，以便于實現搜索與top-k排序操作.TBSE方案為實現布爾搜索，每一個關鍵字wq對應的令牌τwq=(sτwq,inτwq)包含2個部分：單關鍵字令牌sτwq與關鍵字之間交集令牌inτwq.

3.4.1 單關鍵字令牌生成

(7)

3.4.2 關鍵字交集令牌生成

(8)

將每一個inτbiwq∩biwi整合在一起，生成wq所對應的交集搜索令牌inτwq.對于最后一個關鍵字wq，無需與其他關鍵字做交集，只需要得到其單關鍵字搜索令牌sτwq即可.將2部分令牌合并得到τwq，其結構：

τw1=(sτw1,inτbiw1∩biw2，…，inτbiw1∩biwq),
τw2=(sτw2,inτbiw2∩biw3，…，inτbiw2∩biwq),
?
τwq-1=(sτwq-1,inτbiwq-1∩biwq),
τwq=sτwq.

3.5 搜索算法

(9)

當wq∈W時，云服務器得到的參數s?wq即為wq所對應的GM加密的二進制索引串Gwq.將搜索到的每一個s?wq放入字典Ds ?(wq)中，其結構如圖4所示：

Fig. 4 Construction of single keyword search result圖4 單關鍵字搜索結果構造結構

云服務器取出inτwq對inEID進行搜索，分別從字典inD(wi)中取出每個關鍵字對應的索引向量，其方法同對SEID的搜索方法類似，得到的參數in?wq∩in?wi為對wq與其后面關鍵字wi所對應的GM加密的二進制索引串inGq∩inGi.將搜索到的每一個參數in?wq∩in?wi放入MultimapMMin?(wq)中.其結構如圖5所示：

Fig. 5 Construction of multi-keywords search result圖5 關鍵字交集搜索結果構造結構

對于最后一個關鍵字wq，只需要取出其單關鍵字令牌sτwq對SEID進行搜索，得到s?wq=Gwq.將s?wq放入字典Ds ?(wq)中，搜索過程執行完畢.

3.6 top-k算法

top-k算法Dk←Top_k(?wq,skGM,k,EIDScore,sτwq)實現于安全協處理器(SCP)端，用于對文檔進行排序并返回top-k個文件集Dk.云服務器在搜索算法執行完畢后，發送?wq至SCP.SCP首先用skGM分別對s?wq與inτwq解密，得到每一個關鍵字wq的二進制索引串biwq，以及wq與其后面的每一個關鍵字wi的交集二進制索引串inbiwq∩inbiwi.對于執行布爾搜索的全部關鍵字W′，首先對執行“并”操作的全部關鍵字andW進行操作：

(10)

得到andbi.這里的“∑”表示逐比特相加.將andbi與執行“交”操作全部關鍵字inW的inbiwq∩inbiwi進行操作：

(11)

得到對執行布爾搜索得到的全部文件集的二進制索引串biD′，進而得到搜索到的全部文件集D′.

SCP利用分數索引實現top-k排序操作，使用單關鍵字搜索令牌sτwq對EIDScore解密.得到存儲dj的排名分數字典sD(dj).SCP根據數據擁有者提供的可選數字k對sD(dj)中的所有文件的分數進行排序，返回前k個文檔集Dk至云服務器，整個top-k算法執行完畢.

3.7 索引更新算法

索引更新算法EID′←IndexUpdate(EID,w′)實現于數據擁有者端.TBSE方案實現了對關鍵字集合W更新的同時，對關鍵字加密索引EID進行動態更新，大大提升了關鍵字索引更新的效率.索引更新算法包括對單關鍵字加密索引SEID與關鍵字交集加密索引inEID的更新.

(12)

4 安全性與性能分析

本節首先對TBSE方案進行安全性分析及性能分析，再從性能和功能2個角度與之前已有方案進行對比，最后對搜索效率及索引存儲效率進行效率測試.

4.1 安全性分析

1) 已知密文模型中的安全性

在已知密文模型中，攻擊者可以通過已知的密文建立線性方程，來計算加密索引和搜索令牌的真實值.考慮到加密索引，云服務器對于加密索引EID中的2部分SEID與inEID均為已知的，但對其中每一個關鍵字對應的子索引的值未知.使用隨機向量vi∈V，隨機數r∈R與GM，2DNF這2種加密算法分別對SEID與inEID加密，從而構成一個線性方程組：

(13)

其中，考慮到vi,vr,r均為隨機的，則方程式左側有(|W||D|)個未知數，方程式右側有|D|個未知數.根據式(13)所示，此方程組包含|W|個方程式.根據行列式的性質可知，當未知數的數量大于行列式的數量時，此方程組無解，則根據方程組無法得到通過GM以及2DNF加密后的數據，也就無法獲得加密索引的真實值.同理，通過搜索令牌也得不到有關關鍵字數據和加密后數據的真實值，本方案對索引及令牌采用的加密機制能夠保證數據的隱私性.

2) 已知背景模型中的安全性

根據文獻[17]中的證明可知，在已知背景模型中，云服務器能夠通過分析詞頻分布圖，尋求加密索引與搜索令牌之間的內在聯系來挖掘泄露文檔的隱私，進而推斷關鍵字信息.本方案在索引構建的過程中，對于單關鍵字索引SEID，將對每一個加密后的子索引向量相加，使其成為單個向量的形式，并引入隨機數與隨機向量，確保了加密后的單關鍵字索引與關鍵字所對應的倒排索引是毫無關聯的.同樣地，對于關鍵字交集索引inEID中的每一個向量，其每一條索引都采用2種加密方式，并將加密的數據相乘，同樣引入了隨機數與隨機向量，因此無法得到多條關鍵字交集索引之間的關聯.同理，攻擊者也無法通過分析搜索令牌之間的關系得到搜索結果.同時，由于2DNF與GM加密中均引入了隨機數，也就是說，即使多次重復一樣的搜索，云服務器收到的索引和令牌也是不一樣的，這有效地抵抗了統計分析攻擊，防止了搜索模式泄露.因此，本文方案在已知背景模型中是安全的.

4.2 性能分析與方案對比

本節對TBSE方案與之前的相關可搜索加密方案進行對比，并對方案功能及性能2方面進行分析.

TBSE方案同其他方案的對比數據如表1所示,其中M表示MRSE方案[17]與OXT方案[19]生成的倒排索引的最長索引的長度.#DB(w)表示MRSE，OXT，IBE方案[18]生成的倒排索引的長度，strg表示索引的存儲空間.其中，從方案實現功能的角度，相比于IBE，TBSE方案支持對多關鍵字的布爾搜索.與MRSE方案和OXT方案相比，TBSE方案可以對搜索后得到的文件進行top-k排序.相比于MRSE，OXT，IBE，TBSE方案支持對關鍵字索引的動態更新.

Table 1 Function and Performance Comparison Between TBSE and Other Schemes表1 TBSE同各方案的功能對比及性能對比

從方案性能的角度，首先分析方案的時間復雜度.假定待搜索的關鍵字集合為W={w1,w2,…,wq}.首先取出每一個關鍵字的單關鍵字搜索令牌與單關鍵字索引做乘法及冪運算，其搜索效率為O(|W|).接下來依次取出關鍵字w1,w2,…,wq-1的交集搜索令牌inτwq并與交集索引inEID做乘法及冪運算，其搜索效率為O(|W|2).則TBSE搜索算法的時間效率為O(|W|2).相比于同樣支持布爾搜索的MRSE與OXT，TBSE提高了搜索算法的效率.其搜索算法時間復雜度低于IBE，主要是因為該算法只支持對單關鍵字的搜索.

分析索引的存儲效率.對于MRSE方案，其關鍵字索引的存儲效率隨關鍵字個數呈線性提升.OXT方案對MRSE方案進行了改進，主要表現在存儲交集索引時，其存儲效率與關鍵字數量呈亞線性提升.TBSE方案進一步提升了索引存儲效率，由于其單關鍵字索引SEID為一個向量元素，其存儲效率為O(strg(#SEID)).交集索引inEID為存儲(|W|-1)個向量元素的字典，其存儲效率為O(strg(|W-1|#inEID)).因此，TBSE的單關鍵字索引存儲效率只與向量的長度有關，因此單關鍵字存儲效率不會隨著關鍵字個數的增加而增加，同時在存儲交集索引時也會減少存儲空間.當|W|很大時，這大大提高了索引的存儲效率，其效率優于MRSE方案和OXT方案.對于IBE方案，由于其不支持布爾搜索，在這里不參與對索引存儲效率的比較.

4.3 效率測試

通過實驗的形式分別對方案中的索引存儲大小，搜索效率及top-k排名效率進行測試，本文設計了一個C/S架構的TBSE方案原型系統，在Win10操作系統下通過Java語言實現.

首先對索引存儲空間效率進行測試.實驗結果如圖6所示，橫坐標為關鍵字個數，縱坐標為內存大小.可以發現，索引內存大小隨著關鍵字個數的增加不會有非常明顯的變化，這是因為我們利用向量的加法，將索引存儲到一個向量中.

Fig. 6 Index storage efficiency圖6 索引存儲效率

對關鍵字的搜索效率進行測試.首先對單關鍵字的搜索效率進行測試并與MRSE方案對比，如圖7所示，其中橫坐標為待搜索文件集的個數，縱坐標為搜索時間.通過實驗我們可以清晰地得出結論，該方案在對單關鍵字進行搜索時，其時間復雜度不會隨著文件集個數的增加而增加，永遠保持一個常數，即O(|W|)的時間復雜度.當文件集個數越來越多時，TBSE在對單關鍵字的搜索效率的提升顯著.

Fig. 7 Single keyword search efficiency圖7 單關鍵字搜索效率

對多關鍵字的布爾搜索效率測試，如圖8所示.假定布爾搜索全部為求“交”操作，橫坐標為待搜索的關鍵字個數，縱坐標為搜索耗時.通過實驗結果我們可以得出結論，在對多關鍵字進行布爾搜索時，其搜索算法的時間復雜度為O(|W|2).相比于同樣支持布爾搜索的OXT方案，本文方案提高了搜索算法的效率.而相比于MRSE方案，由于其不支持布爾搜索，只考慮對多關鍵字搜索時，其搜索效率為常數，不隨搜索關鍵字個數增加而改變，因此只有當搜索關鍵字很少時，本方案相比MRSE方案在多關鍵字搜索上有優勢.

Fig. 8 Multi-keywords boolean search efficiency圖8 多關鍵字布爾搜索效率

最后，對方案的top-k排名效率進行測試，如圖9所示.盡管MRSE方案支持top-k，由于其搜索階段包含top-k排名，因此不與其作比較.

Fig. 9 top-k rank efficiency圖9 top-k排名效率

5 總 結

針對先有的可搜索加密方案大多不支持對多關鍵字進行布爾搜索這一問題，本文提出了一種基于多關鍵字的top-k布爾可搜索加密方法，簡稱TBSE.該方案在傳統的可搜索加密方案的基礎上，通過GM加密算法及2DNF加密算法，生成了具有高搜索效率、高存儲率的加密安全索引.在此基礎上，利用集合論的相關性質，分別構建了單關鍵字加密索引及交集加密索引，從而實現了對多關鍵字的布爾搜索；利用TF-IDF技術構建正向分數索引，借助第三方實體SCP實現了對搜索后文件的top-k排名；同時，該方法能夠對多關鍵字進行動態更新，提升了更新效率.之后通過安全性分析，證明了該算法能夠對抗2種不同的安全威脅.最后對該方法進行了功能分析及性能分析，通過與其他可搜索加密方案進行對比，證明了TBSE方案的優越性.