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

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

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

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

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

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

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

1 相關(guān)知識(shí)

1.1 Goldwasser-Micalli公鑰加密方案

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

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

(1)

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

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

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

1)Gen.密鑰生成算法.給定一個(gè)安全參數(shù)l.首先選擇2個(gè)l-bit的奇素?cái)?shù)q1,q2，計(jì)算N=q1×q2∈.生成N階雙線性群G，令g,u為G的2個(gè)生成元，然后計(jì)算h=uq2為G的q1階子群的隨機(jī)生成元.最后輸出私鑰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的密文可以被計(jì)算.同時(shí)，方案中的解密時(shí)間是消息空間m大小的多項(xiàng)式時(shí)間，因此，2DNF密碼方案顯然可以有效地適用于短消息.

1.3 逆向文本頻率TF-IDF

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

1.4 布爾搜索與集合論

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

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

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

對(duì)于3個(gè)集合的并集操作來說，推導(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個(gè)實(shí)體，分別是數(shù)據(jù)擁有者、云服務(wù)器和安全協(xié)處理器(secure coprocessor, SCP)如圖2所示：

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

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

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

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

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

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

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

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

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

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

2.2 形式化定義

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

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

每個(gè)算法的具體描述為：

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

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

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

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

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

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

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

2.3 安全威脅

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

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

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

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

3.1 密鑰生成算法

密鑰生成算法KSY,KDN,KGM←KeyGen(λ)在數(shù)據(jù)擁有者端實(shí)現(xiàn).TBSE方案在加密文件時(shí)利用傳統(tǒng)對(duì)稱加密方式(如AES)的方式加密文件，輸入安全參數(shù)λ，生成文件加密密鑰KSY.本方案在構(gòu)造加密索引與搜索令牌的過程依賴于GM加密與2DNF加密，輸入安全參數(shù)λ，生成2個(gè)加密方案的公私鑰KDN=(skDN,pkDN),KGM=(skGM,pkGM).根據(jù)相關(guān)知識(shí)，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)實(shí)現(xiàn)于數(shù)據(jù)擁有者端.為了實(shí)現(xiàn)布爾搜索，利用預(yù)備知識(shí)中集合論的相關(guān)知識(shí)，本方案所構(gòu)建的關(guān)鍵字加密索引包含2個(gè)部分：對(duì)單關(guān)鍵字的加密索引SEID與關(guān)鍵字之間交集的加密索引inEID.

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

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

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

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

(3)

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

根據(jù)集合論相關(guān)知識(shí)，數(shù)據(jù)擁有者首先為每一個(gè)關(guān)鍵字wi∈W與其后面的關(guān)鍵字wj∈W做交集，生成(|W||D|)個(gè)交集倒排索引inIDi.與單關(guān)鍵字加密索引生成類似，根據(jù)每一個(gè)關(guān)鍵字的交集倒排索引生成長度為|D|的二進(jìn)制索引串inbIDi，并將其依次存放于一個(gè)字典中.將每一個(gè)字典放入一個(gè)Multi-map結(jié)構(gòu)MMb(wi)中.對(duì)MMb(wi)的每一個(gè)元素，采用與生成單關(guān)鍵字加密索引類似的方法生成加密索引.使用GM加密生成inGi∩inGj=EncGM(pkGM,inbIDi).對(duì)進(jìn)行交集操作的關(guān)鍵字之間做“⊕”異或操作，使用2DNF加密生成inDi∩inDj=EncDN(pkDN,wi⊕wj).其余操作與生成單關(guān)鍵字加密索引類似.數(shù)據(jù)擁有者將每一個(gè)關(guān)鍵字對(duì)應(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)實(shí)現(xiàn)于數(shù)據(jù)擁有者端.分?jǐn)?shù)索引為正向索引，即每一個(gè)文件dj對(duì)應(yīng)一串索引，這與關(guān)鍵字索引不同.數(shù)據(jù)擁有者首先計(jì)算關(guān)鍵字wi在文件中的“詞頻”(TF)與“逆向文本頻率”(IDF)對(duì)dj構(gòu)建分?jǐn)?shù)索引，以方便之后對(duì)文件進(jìn)行top-k排序,記關(guān)鍵字wi在文件dj中的個(gè)數(shù)為c.計(jì)算文件的TF-IDF值后，存放在字典sD(dj)中.其算法為

(5)

(6)

3.4 令牌生成算法

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

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

(7)

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

(8)

將每一個(gè)inτbiwq∩biwi整合在一起，生成wq所對(duì)應(yīng)的交集搜索令牌inτwq.對(duì)于最后一個(gè)關(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時(shí)，云服務(wù)器得到的參數(shù)s?wq即為wq所對(duì)應(yīng)的GM加密的二進(jìn)制索引串Gwq.將搜索到的每一個(gè)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對(duì)inEID進(jìn)行搜索，分別從字典inD(wi)中取出每個(gè)關(guān)鍵字對(duì)應(yīng)的索引向量，其方法同對(duì)SEID的搜索方法類似，得到的參數(shù)in?wq∩in?wi為對(duì)wq與其后面關(guān)鍵字wi所對(duì)應(yīng)的GM加密的二進(jìn)制索引串inGq∩inGi.將搜索到的每一個(gè)參數(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)

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

3.6 top-k算法

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

(10)

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

(11)

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

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

3.7 索引更新算法

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

(12)

4 安全性與性能分析

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

4.1 安全性分析

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

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

(13)

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

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

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

4.2 性能分析與方案對(duì)比

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

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

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

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

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

4.3 效率測試

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

首先對(duì)索引存儲(chǔ)空間效率進(jìn)行測試.實(shí)驗(yàn)結(jié)果如圖6所示，橫坐標(biāo)為關(guān)鍵字個(gè)數(shù)，縱坐標(biāo)為內(nèi)存大小.可以發(fā)現(xiàn)，索引內(nèi)存大小隨著關(guān)鍵字個(gè)數(shù)的增加不會(huì)有非常明顯的變化，這是因?yàn)槲覀兝孟蛄康募臃ǎ瑢⑺饕鎯?chǔ)到一個(gè)向量中.

Fig. 6 Index storage efficiency圖6 索引存儲(chǔ)效率

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

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

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

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

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

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

5 總 結(jié)

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