基于多關(guān)鍵字的Top-k布爾可搜索加密方案

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

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

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

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

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

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

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

1 相關(guān)知識

1.1 Goldwasser-Micalli公鑰加密方案

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

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

(1)

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

1.2 2DNF同態(tài)加密方案

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

1)Gen.密鑰生成算法.給定一個安全參數(shù)l.首先選擇2個l-bit的奇素數(shù)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.加密算法.假設(shè)消息空間由集合{0,1,…,T}中的整數(shù)組成且T

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

1.3 逆向文本頻率TF-IDF

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

1.4 布爾搜索與集合論

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

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

Fig. 1 Collection relationship diagram圖1 集合關(guān)系示意圖

對于3個集合的并集操作來說，推導(dǎo)過程[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)

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

2 TBSE方案

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

2.1 方案模型

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

Fig. 2 The architecture of TBSE scheme圖2 TBSE方案的體系架構(gòu)

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

1) 數(shù)據(jù)擁有者將搜索令牌傳送至云服務(wù)器，發(fā)出搜索請求;

2) 云服務(wù)器執(zhí)行搜索后，將搜索后的結(jié)果與搜索令牌傳送至SCP;

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

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

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

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

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

3) 安全協(xié)處理器.主要負(fù)責(zé)接收加密的分?jǐn)?shù)索引，同時接收云服務(wù)器傳遞的加密的字符串，對關(guān)鍵字進行搜索及 top-k排名，并返回相應(yīng)文檔標(biāo)簽至云服務(wù)器.

2.2 形式化定義

TBSE方案共包含7個算法，分別是密鑰生成算法、關(guān)鍵字索引生成算法、加密分?jǐn)?shù)索引生成算法、令牌生成算法、搜索算法、top-k算法以及索引更新算法，TBSE方案所示：

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

每個算法的具體描述為：

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

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

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

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

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

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

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

2.3 安全威脅

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

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

3 TBSE方案詳細(xì)設(shè)計

本節(jié)主要介紹TBSE方案的詳細(xì)設(shè)計.TBSE方案需要解決3個問題：1)能夠高效地實現(xiàn)對多關(guān)鍵字的布爾搜索；2)能夠?qū)λ阉骱蟮奈募M行有效的top-k排序；3)能夠?qū)?gòu)建的關(guān)鍵字安全索引進行動態(tài)更新.根據(jù)第2節(jié)形式化定義，下面對TBSE方案的7個算法分別進行詳細(xì)描述.

3.1 密鑰生成算法

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

3.2 關(guān)鍵字索引生成算法

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

3.2.1 單關(guān)鍵字加密索引生成

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

Fig. 3 Construction of binary dictionary圖3 二進制字典構(gòu)造結(jié)構(gòu)

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

(3)

3.2.2 關(guān)鍵字交集加密索引生成

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

(4)

綜上所述，關(guān)鍵字交集索引inEID生成完畢.

3.3 加密分?jǐn)?shù)索引生成算法

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

(5)

(6)

3.4 令牌生成算法

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

3.4.1 單關(guān)鍵字令牌生成

(7)

3.4.2 關(guān)鍵字交集令牌生成

(8)

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

τ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)

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

Fig. 4 Construction of single keyword search result圖4 單關(guān)鍵字搜索結(jié)果構(gòu)造結(jié)構(gòu)

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

Fig. 5 Construction of multi-keywords search result圖5 關(guān)鍵字交集搜索結(jié)果構(gòu)造結(jié)構(gòu)

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

3.6 top-k算法

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

(10)

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

(11)

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

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

3.7 索引更新算法

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

(12)

4 安全性與性能分析

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

4.1 安全性分析

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

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

(13)

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

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

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

4.2 性能分析與方案對比

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

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

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

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

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

4.3 效率測試

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

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

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

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

Fig. 7 Single keyword search efficiency圖7 單關(guān)鍵字搜索效率

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

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

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

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

5 總 結(jié)

針對先有的可搜索加密方案大多不支持對多關(guān)鍵字進行布爾搜索這一問題，本文提出了一種基于多關(guān)鍵字的top-k布爾可搜索加密方法，簡稱TBSE.該方案在傳統(tǒng)的可搜索加密方案的基礎(chǔ)上，通過GM加密算法及2DNF加密算法，生成了具有高搜索效率、高存儲率的加密安全索引.在此基礎(chǔ)上，利用集合論的相關(guān)性質(zhì)，分別構(gòu)建了單關(guān)鍵字加密索引及交集加密索引，從而實現(xiàn)了對多關(guān)鍵字的布爾搜索；利用TF-IDF技術(shù)構(gòu)建正向分?jǐn)?shù)索引，借助第三方實體SCP實現(xiàn)了對搜索后文件的top-k排名；同時，該方法能夠?qū)Χ嚓P(guān)鍵字進行動態(tài)更新，提升了更新效率.之后通過安全性分析，證明了該算法能夠?qū)?種不同的安全威脅.最后對該方法進行了功能分析及性能分析，通過與其他可搜索加密方案進行對比，證明了TBSE方案的優(yōu)越性.