一種支持聯(lián)合搜索的多用戶動態(tài)對稱可搜索加密方案

張藍藍 曹衛(wèi)東 王懷超

(中國民航大學(xué)計算機科學(xué)與技術(shù)學(xué)院 天津 300300)

隨著云計算技術(shù)的發(fā)展，越來越多的公司和個人會將自己的數(shù)據(jù)存儲到第三方服務(wù)器.這樣服務(wù)器就具有完全訪問客戶端數(shù)據(jù)的權(quán)限(如數(shù)據(jù)庫查詢)，并且會按照客戶端的指示將數(shù)據(jù)的一部分以明文形式顯示出來.當客戶端的數(shù)據(jù)包含高度敏感的信息(例如生物醫(yī)學(xué)記錄)且服務(wù)器不完全可信時，就會暴露出許多隱私問題.

可搜索加密因其能夠以密文形式查詢數(shù)據(jù)而一直備受關(guān)注.理想情況下，客戶端在查詢加密數(shù)據(jù)時可以不向服務(wù)器透露任何敏感信息.不過目前只有完全同態(tài)加密可能實現(xiàn)這種構(gòu)想，但由于其性能開銷大，不適合實際部署[1-2].對稱可搜索加密(symmetric searchable encryption, SSE)[3]是基于對稱加密算法設(shè)計的一種計算效率高、安全性相對較好的可搜索加密方案，它的目標是在盡可能減少敏感信息泄露的情況下通過查詢關(guān)鍵詞與文檔間的索引來查找加密文檔.

與SSE相關(guān)的早期研究工作主要集中在對靜態(tài)數(shù)據(jù)的安全搜索上.為了支持加密數(shù)據(jù)的更新，Kamara等人[4]提出了動態(tài)對稱可搜索加密(dynamic symmetric searchable encryption, DSSE)技術(shù)，該技術(shù)允許數(shù)據(jù)擁有者對自己的數(shù)據(jù)進行加密存儲，而且之后可以對加密數(shù)據(jù)進行搜索和動態(tài)更新.然而，更新操作可能會導(dǎo)致嚴重的額外信息泄露問題.為了解決更新時出現(xiàn)的額外隱私泄露問題，Stefanov等人[5]提出了前向安全和后向安全的概念，Bost等人[6-7]給出了這2個概念的正式定義.前向安全可確保未來的更新不會與以前的搜索相關(guān)聯(lián)，這有助于抵抗強大的文件注入攻擊；后向安全保證了后續(xù)搜索不會與過去刪除的文檔相關(guān)聯(lián).

目前的研究工作中已經(jīng)存在許多同時滿足前向安全和后向安全的DSSE方案，但大部分僅支持單個關(guān)鍵詞搜索.因此，盡管它們的效率和安全性很高，但支持的查詢在表達能力方面往往受到嚴重限制，例如查詢遠程存儲的大型電子郵件數(shù)據(jù)庫，單個關(guān)鍵詞查詢可能會返回大量匹配記錄，但數(shù)據(jù)使用者想要的最終結(jié)果只占其中的一小部分，這不僅降低了查詢效率，還浪費了許多計算資源[8-9].

為了解決單關(guān)鍵詞搜索效率低的問題，Patranabis等人[10]最近提出了一種支持多關(guān)鍵詞查詢且滿足前后向安全的動態(tài)可搜索加密方案，即不經(jīng)意動態(tài)交叉索引(oblivious dynamic cross tags, ODXT)，該方案通過引入不經(jīng)意交叉索引[11]來存儲每次更新的狀態(tài)信息，在查詢時將交叉索引返回給客戶端作為判斷文檔是否包含所有關(guān)鍵詞的主要依據(jù)，從而實現(xiàn)聯(lián)合查詢.不過，通過大量實驗結(jié)果可以得出，ODXT方案在查詢有刪除的記錄時，在某些情況下存在查詢結(jié)果不準確的問題.這是由于在查詢階段計算交叉索引時，未考慮更新的操作類型，導(dǎo)致算法無法區(qū)分索引是被插入還是被刪除；另外，該方案僅支持單個用戶查詢，這大大限制了數(shù)據(jù)的使用范圍，降低了數(shù)據(jù)的利用率.例如在醫(yī)療系統(tǒng)中，許多部門都需要查詢患者的電子病歷，如果使用僅支持單個用戶查詢的動態(tài)可搜索加密方案來保護電子病歷，則會給患者診斷帶來層層阻礙.

針對這些問題，本文提出了一個滿足前后向安全且支持多關(guān)鍵詞查詢和多用戶查詢的DSSE方案.

本文的主要貢獻包括3個方面：

1)通過將ODXT方案中的查詢令牌改成插入與刪除的查詢令牌對，來區(qū)分交叉索引對應(yīng)的更新操作類型，從而使查詢結(jié)果始終與實際結(jié)果一致，且其查詢的復(fù)雜度僅與更新次數(shù)最低的關(guān)鍵詞的更新次數(shù)有關(guān).

2)提出了一種支持聯(lián)合搜索的多用戶動態(tài)可搜索加密方案，即多用戶不經(jīng)意動態(tài)交叉索引(multi-client oblivious dynamic cross tags, MC-ODXT)，利用有限域內(nèi)元素具有乘法逆元的性質(zhì)，引入了一次性盲因子來生成查詢令牌，并用數(shù)字信封進行授權(quán)驗證，實現(xiàn)用戶授權(quán)與查詢.

3)對所提方案進行了安全性分析與性能分析，結(jié)果表明本文方案滿足前向安全與后向安全，既解決了ODXT方案查詢結(jié)果不準確的問題，又在搜索類型、適用場景等功能方面更加靈活全面，且計算時間復(fù)雜度與ODXT方案相同.

1 相關(guān)工作

1.1 動態(tài)可搜索加密

可搜索加密能夠支持用戶遠程訪問加密數(shù)據(jù)，在工業(yè)界具有廣泛的應(yīng)用前景[9].與公鑰可搜索加密方案相比，使用對稱密碼原語的SSE方案在效率上擁有更突出的優(yōu)勢.

為了使可搜索加密支持更新，Kamara等人[4,10]引入了DSSE方案，不僅可以查詢數(shù)據(jù)，還支持添加和刪除數(shù)據(jù).不過，這些方案在更新過程中會泄露額外的數(shù)據(jù)信息，一旦被惡意敵手濫用將導(dǎo)致嚴重的后果.因此，2013年Stefanov等人[5]提出了前向安全和后向安全的概念；之后Bost等人[6-7]進行了形式化定義，并將后向安全分成3個安全級別，其中BP-I比BP-II更安全，BP-II比BP-III更安全.隨后，人們開始對滿足前后向安全的動態(tài)可搜索加密展開廣泛研究.Sun等人[12]使用一種可穿刺加密原語構(gòu)造動態(tài)可搜索加密方案，不過只實現(xiàn)了BP-III后向安全.Ghareh等人[13]和Sun等人[14]通過茫然映射不經(jīng)意隨機訪問機(oblivious random access machine, ORAM)技術(shù)構(gòu)造索引，實現(xiàn)了BP-I后向安全，但該技術(shù)的計算開銷較大.為了平衡安全性與效率，Ghareh等人[13]將文檔關(guān)鍵詞索引改成關(guān)鍵詞的更新索引，設(shè)計了滿足前向和BP-II后向安全的Mitra方案.Mitra方案通過向數(shù)據(jù)庫增加一條更新條目信息來實現(xiàn)更新操作，并利用本地的更新計數(shù)器來生成搜索令牌，降低了計算的復(fù)雜度.

1.2 支持聯(lián)合查詢的可搜索加密

在實際應(yīng)用中，單關(guān)鍵詞搜索可能會返回大量無用的結(jié)果，降低查詢效率.因此，越來越多的人把目光轉(zhuǎn)移到了支持聯(lián)合查詢的前后向安全動態(tài)可搜索加密上.Zuo等人[15]給出了2個帶有范圍查詢的前向安全和后向安全DSSE方案，名為SchemeA和SchemeB，其中SchemeA方案滿足前向安全，SchemeB滿足后向安全.隨后一系列支持聯(lián)合查詢且滿足前向或后向安全的DSSE方案被相繼提出[16].最近，Patranabis等人[10]介紹了2種基于不經(jīng)意交叉索引(oblivious cross tags, OXT)[11]方案和Mitra方案[13]的聯(lián)合查詢DSSE方案，名為BDXT和ODXT，這2種方案同時實現(xiàn)了前向安全和后向安全.但BDXT方案因查詢時需客戶端與服務(wù)器進行多輪交互，查詢效率較低；而ODXT方案由于使用了延遲刪除技術(shù)，在查詢時只能刪除部分文檔.不過這為我們實現(xiàn)支持聯(lián)合查詢且滿足前后向安全的動態(tài)可搜索加密方案提供了思路.

1.3 多用戶對稱可搜索加密

為了使可搜索加密能夠支持多用戶查詢，Curtmola等人[17]引入了多客戶端對稱可搜索加密(multi-client symmetric searchable encryption, MSSE)的概念.隨后，Jarecki等人[18]提出了一個支持布爾查詢的MSSE方案，他們的方案利用同態(tài)簽名和不經(jīng)意的偽隨機函數(shù)將OXT方案擴展到多客戶端場景，可以抵抗惡意客戶端并實現(xiàn)高效檢索.在他們工作的基礎(chǔ)上，F(xiàn)aber等人[19]提出了一種支持豐富查詢類型的MSSE方案.但是，上述2種方案都只適用于靜態(tài)數(shù)據(jù)集上.盧冰潔等人[20]引入了一個半誠實的代理服務(wù)器實現(xiàn)了DSSE中的多客戶端查詢，但是該方案不能支持多關(guān)鍵詞搜索.Du等人[21]通過改進OXT協(xié)議，提出了一個非交互式且支持多用戶聯(lián)合搜索的DSSE方案，然而該方案僅支持授權(quán)令牌更新，不支持索引更新.受文獻[18,21]的啟發(fā)，本文通過改進ODXT方案中的OXT協(xié)議，將支持聯(lián)合搜索的動態(tài)可搜索加密擴展到多用戶場景，在保證安全性的同時，進一步豐富查詢功能.

2 預(yù)備知識

2.1 偽隨機函數(shù)

定義1.設(shè)Gen(1λ)∈(0,1)λ是一個密鑰生成函數(shù)，G：(0,1)λ×(0,1)l→(0,1)l′是一個偽隨機函數(shù)，GK(x)表示G(K,x).如果對于任意概率多項式時間的敵手A都滿足：|Pr[K←Gen(1λ);AGK(·)(1λ)=1]-Pr[AR(·)(1λ)=1]|≤v(λ)，則稱G是一個安全的偽隨機函數(shù)，其中R：(0,1)λ→(0,1)l′是一個真隨機函數(shù)，v(λ)是一個可忽略函數(shù).

2.2 判定性Diffie-Hellman假設(shè)

如果對于任意多項式時間的敵手A，都滿足：|Pr[A(g,gα,gβ,gα×β)=1]-Pr[A(g,gα,gβ,gγ)=1]|≤v(λ)，則四元組(g,gα,gβ,gα×β)與隨機的四元組(g,gα,gβ,gγ)是計算上不可區(qū)分的，稱為判定性Diffie-Hellman假設(shè)，簡稱DDH假設(shè).

2.3 動態(tài)可搜索加密

一個動態(tài)可搜索加密方案包括索引建立、文檔加密、索引查詢、索引更新及文檔解密5個過程.不過本文僅考慮索引建立、索引查詢與索引更新3個過程，具體過程描述如下.

1)Setup(λ,DB)→(k,st,EDB).索引建立階段.數(shù)據(jù)擁有者輸入安全參數(shù)λ與數(shù)據(jù)庫DB，輸出數(shù)據(jù)擁有者的密鑰k、本地狀態(tài)st及加密數(shù)據(jù)庫EDB.

2)Search(k,w,st;EDB)→DB(w).索引查詢階段.客戶端輸入密鑰k、關(guān)鍵詞w及本地狀態(tài)st，輸出查詢結(jié)果，共有2種結(jié)果：當w∈W時，返回包含w的所有文檔標識符集合DB(w)；當w?W時，返回空.

3)Update(k,op,in,st;EDB).索引更新階段.數(shù)據(jù)擁有者輸入密鑰k、操作類型op、待更新條目in=(id,w)及本地狀態(tài)st，然后在服務(wù)器上對in執(zhí)行插入或刪除操作.其中op的值為add或del，id是文檔標識符，w是關(guān)鍵詞.

動態(tài)可搜索加密的安全性由現(xiàn)實模型Real和理想模型Ideal的不可區(qū)分性來定義.首先定義泄露函數(shù)L=(LSetup,LUpdate,LSearch)來表示敵手A在系統(tǒng)建立階段、更新階段及查詢階段獲取的泄露信息，并假定敵手A獲取的泄露信息只在L表示的范圍內(nèi).

在現(xiàn)實模型Real中，敵手A運行真實方案中的Setup(λ)來初始化系統(tǒng)，隨后A執(zhí)行更新問詢或搜索問詢來獲取信息.在理想模型Ideal中，模擬器S輸入LSetup(λ)，隨后敵手A進行更新問詢或搜索問詢，模擬器S通過相應(yīng)的泄露函數(shù)LUpdate(op,(id,w))或LSearch(w)來回復(fù)敵手A.

定義3.若存在一個模擬器S，使得對于任意概率多項式時間敵手A，都有：|Pr[RealA(λ)=1]-Pr[IdealA,S(λ)=1]|≤v(λ)，則稱該動態(tài)可搜索加密方案是L自適應(yīng)安全的，其中v(λ)是可忽略函數(shù).

2.4 不經(jīng)意交叉索引

不經(jīng)意交叉索引(OXT)協(xié)議最初由Cash等人[11]用在可搜索加密方案中，通過設(shè)計TSet和XSet索引表實現(xiàn)在加密數(shù)據(jù)集上的聯(lián)合搜索.在OXT協(xié)議中，客戶端通過為每個關(guān)鍵詞w定義文檔計數(shù)器Cnt，來記錄包含w的文檔數(shù).給定一個查詢q=(w1,w2,…,wn)，定義其中文檔計數(shù)器值最低的關(guān)鍵詞為w1，其余關(guān)鍵詞為wi(i∈{2,3,…,n})，w1的文檔計數(shù)器值為Cnt[w1]，則OXT協(xié)議包含3個實體和1個過程.其中設(shè)KT是從(0,1)λ上選取的隨機數(shù)，作為對稱加密算法Enc的密鑰；KX，KY，KZ是從上選取的隨機數(shù)，作為偽隨機函數(shù)Fp的密鑰.

1)TSet表.TSet是關(guān)鍵詞索引表，以addr為索引，存儲了包含關(guān)鍵詞w的文檔標識符信息val和致盲因子α.其計算方式為

val=Enc(KT,id)，

(1)

addr=Enc(KT,w‖Cnt[w])，

(2)

α=Fp(KY,id)(Fp(KZ,w‖Cnt[w]))-1，

(3)

其中，id∈DB(w)

2)XSet表.XSet是交叉索引表，存儲了關(guān)鍵詞w與文檔的交叉索引xtag，xtag標記了w與文檔間的包含關(guān)系.系統(tǒng)建立時，根據(jù)文檔標識符id和關(guān)鍵詞w，計算出交叉索引值xtag并存到XSet中.xtag的計算方式為

xtag=gFp(KX,w)×Fp(KY,id)，id∈DB(w).

(4)

3)xtoken變量.xtoken是查詢令牌，在查詢階段由客戶端生成，協(xié)助服務(wù)器端生成xtag以判斷包含w1的文檔是否也包含其他關(guān)鍵詞wi(i∈{2,3,…,n}).其中，

xtoken=gFp(KZ,s‖Cnt[w1])×Fp(KX，wi).

(5)

3 MC-ODXT方案

3.1 系統(tǒng)模型

如圖1所示，本文方案的系統(tǒng)模型包括數(shù)據(jù)擁有者、客戶端、云服務(wù)器3個實體，其中可以有多個客戶端查詢數(shù)據(jù)，但只有數(shù)據(jù)擁有者能更新數(shù)據(jù).本文的研究內(nèi)容包括文檔索引的建立、更新及查詢.以下是各個實體的詳細功能介紹.

1)數(shù)據(jù)擁有者.在系統(tǒng)建立階段，負責(zé)構(gòu)造文檔-關(guān)鍵詞索引，初始化系統(tǒng)，并將加密索引及文檔上傳到云服務(wù)器，如圖1步驟①所示；在查詢階段，為不同客戶端發(fā)來的查詢生成授權(quán)信息及令牌生成因子，如圖1步驟④；在更新階段，負責(zé)生成更新數(shù)據(jù)，發(fā)送給云服務(wù)器，并在本地更新關(guān)鍵詞的更新計數(shù)器，如圖1步驟②.

2)客戶端.在查詢階段，將查詢q發(fā)送給數(shù)據(jù)擁有者，如圖1步驟③；收到數(shù)據(jù)擁有者返回的信息后，客戶端根據(jù)令牌生成因子計算出查詢令牌并發(fā)給云服務(wù)器，如圖1步驟⑤.

3)云服務(wù)器.提供數(shù)據(jù)存儲服務(wù).在系統(tǒng)建立階段，負責(zé)存儲加密文檔及文檔索引；在更新階段，根據(jù)數(shù)據(jù)擁有者發(fā)來的更新信息，更新加密數(shù)據(jù)庫；在查詢階段，驗證授權(quán)信息，之后根據(jù)查詢令牌及授權(quán)信息查找加密索引，將滿足條件的結(jié)果返回給客戶端，如圖1步驟⑥.

3.2 算法定義

MC-ODXT方案的算法思想與ODXT方案相同，即更新時不直接添加或刪除索引，而是將三元組(op,id,w)加密后存儲到云服務(wù)器；查詢時先找到更新次數(shù)最低的關(guān)鍵詞，然后查詢該關(guān)鍵詞的所有更新記錄，判斷每個更新記錄對應(yīng)的文檔是否與所有關(guān)鍵詞都有更新記錄，并將op=del的更新記錄對應(yīng)的文檔過濾掉，得到最終查詢結(jié)果.該方案由系統(tǒng)建立算法、索引更新算法、授權(quán)算法、查詢令牌生成算法和查詢算法5個算法組成，即Σ={Setup,Update,AuthClient,SearchToken,Search}.為方便后續(xù)描述，本文假設(shè)查詢q中更新次數(shù)最低的關(guān)鍵詞為w1，每個算法的具體描述如下.

1)系統(tǒng)建立算法

Setup(λ)→(sk,st,EDB).數(shù)據(jù)擁有者運行該算法，給定安全參數(shù)λ作為輸入，輸出數(shù)據(jù)擁有者的密鑰組sk、本地狀態(tài)st及初始化加密數(shù)據(jù)庫EDB.

2)索引更新算法

Update(sk,st,op,(id,w);EDB)→(st′,EDB′).算法由數(shù)據(jù)擁有者和云服務(wù)器共同執(zhí)行，將數(shù)據(jù)擁有者的密鑰組sk和本地狀態(tài)st、更新操作類型op、文檔標識符與關(guān)鍵詞對(id,w)作為輸入，在EDB上更新索引，輸出更新后的本地狀態(tài)st′和加密數(shù)據(jù)庫EDB′.

3)授權(quán)算法

AuthClient(sk,st,q)→(env,c,strap,btrlist).授權(quán)算法由數(shù)據(jù)擁有者完成，輸入數(shù)據(jù)擁有者密鑰組sk、本地狀態(tài)st及查詢q，輸出授權(quán)信息env、w1的更新次數(shù)c、密鑰派生因子strap及查詢令牌生成因子列表btrlist.

4)查詢令牌生成算法

SearchToken(q,env,c,strap,btrlist)→(env,btklist).客戶端運行該算法，輸入查詢q和授權(quán)算法生成的數(shù)據(jù)，包括授權(quán)信息env、w1的更新計數(shù)器值c、密鑰派生因子strap及查詢令牌生成因子列表btrlist，輸出授權(quán)信息env及查詢令牌列表btklist.

5)查詢算法

Search(env,btklist,KM,PK;EDB)→(Idlist).該算法由客戶端與服務(wù)器共同執(zhí)行.服務(wù)器輸入客戶端發(fā)來的授權(quán)信息env、查詢令牌列表btklist、共享密鑰KM及數(shù)據(jù)擁有者公鑰PK，輸出查詢結(jié)果Idlist.

3.3 改進OXT協(xié)議

OXT協(xié)議中的關(guān)鍵詞索引表TSet和交叉索引表XSet在系統(tǒng)建立階段建立后不再改變，這對于動態(tài)可搜索加密方案并不適用.因此，本節(jié)在ODXT方案的基礎(chǔ)上，對OXT協(xié)議中的關(guān)鍵詞索引表、交叉索引表、查詢令牌的計算方式和查詢過程進行了改進，使其同時支持數(shù)據(jù)庫索引更新和多客戶端準確聯(lián)合搜索.以下是改進協(xié)議的詳細過程描述.

3.3.1 關(guān)鍵詞索引表TSet的構(gòu)建

與OXT協(xié)議相同，TSet中存儲了加密信息val和致盲因子α，即TSet[addr]=(val,α)，addr是本次記錄在TSet中的索引地址.不同的是，式(2)和式(3)中的文檔計數(shù)器被改為更新計數(shù)器UpdtCnt；并將對稱加密算法Enc改為效率更高的偽隨機函數(shù)F；此外，關(guān)鍵詞w的更新記錄(op,(id,w))被加密存儲到val中.其中

addr=F(KT,w‖UpdtCnt[w]‖0)，

(6)

val=(id‖op)⊕F(KT,UpdtCnt[w]‖1)，

(7)

α=Fp(KY,id)×(Fp(KZ,UpdtCnt[w]))-1.

(8)

3.3.2 交叉索引表XSet構(gòu)建

本文在交叉索引的計算公式(式(4))中增加了更新操作類型op，用于區(qū)分本次更新是建立索引還是刪除索引，從而為判斷文檔是否包含所有關(guān)鍵詞提供了依據(jù)，其中

xtag=gFp(KX,w‖op)×Fp(KY,id).

(9)

3.3.3 查詢令牌xtoken的生成

在設(shè)計一個支持多客戶端聯(lián)合查詢的SSE方案時，需要保證數(shù)據(jù)擁有者可以對每次查詢生成不同的查詢令牌，防止客戶端越權(quán)訪問及使用之前的查詢令牌訪問以后的數(shù)據(jù).因此，本文引入了一次性盲因子ρ，每次查詢會產(chǎn)生不同的一次性盲因子ρ，用來計算查詢令牌，以使每次生成的查詢令牌都僅供本次查詢使用.另外，本文引入了bxtrap作為查詢令牌生成因子，為不同的客戶端授權(quán)并協(xié)助客戶端計算查詢令牌.

bxtrap=gFp(KX,w‖op)×ρ，

(10)

bxtoken=bxtrapFp(KZ,UpdtCnt[w]).

(11)

為了使服務(wù)器可以根據(jù)bxtoken和α計算出xtag，之后利用xtag來判斷文檔是否符合聯(lián)合查詢，本文的xtag應(yīng)滿足關(guān)系式

xtag=bxtokenα/ρ.

(12)

3.3.4 聯(lián)合查詢過程

為了詳細描述數(shù)據(jù)擁有者、客戶端與云服務(wù)器之間的交互過程，本文構(gòu)建了一個聯(lián)合查詢用例，如圖2所示.首先，數(shù)據(jù)擁有者收到客戶端發(fā)來的查詢請求q=(w1,w2)，找到更新次數(shù)最低的關(guān)鍵詞(假設(shè)是w1)，按照式(6)計算addrw1；接著對每個關(guān)鍵詞生成查詢令牌生成因子(bxtrapadd,bxtrapdel)和一次性盲因子ρ，分別存儲到btrlist和ρlist；然后用對稱加密算法加密alist和ρlist，并用云服務(wù)器公鑰加密對稱密鑰，形成數(shù)字信封；最后將數(shù)字信封與btrlist一起發(fā)給客戶端.客戶端根據(jù)式(11)計算出bxtoken存儲到btklist，并將btklist與存儲加密alist和ρlist的數(shù)字信封一起發(fā)給云服務(wù)器.云服務(wù)器收到后先驗證數(shù)字信封并解密alist和ρlist，根據(jù)alist中的addr查找TSet表，找到對應(yīng)的(val,α)；接著根據(jù)式(12)，利用α，ρ和bxtoken計算出xtag，然后執(zhí)行圖3所示的判斷過程.

由于不知道每個關(guān)鍵詞與w1每次更新時涉及的文檔之間的包含關(guān)系，所以需將每個關(guān)鍵詞和這些文檔的插入交叉索引xtagadd與刪除交叉索引xtagdel都計算出來，根據(jù)索引是否在XSet中來判斷文檔是否包含該關(guān)鍵詞，共包括3種判斷結(jié)果：

1)當xtagadd?XSet時，文檔與w索引不存在，即文檔不包含w；

2)當xtagadd∈XSet且xtagdel?XSet時，文檔包含w；

3)當xtagadd∈XSet且xtagdel∈XSet時，文檔與w索引已刪除，即文檔不包含w.

3種判斷結(jié)果是對單個文檔包含單個關(guān)鍵詞的判斷結(jié)果.對于單個文檔是否包含聯(lián)合查詢的所有關(guān)鍵詞，其判斷流程如圖3所示：

對于w1的第j個更新記錄，若存在關(guān)鍵詞的xtagadd?XSet，說明該關(guān)鍵詞從未和該文檔建立過索引，即文檔不包含所有關(guān)鍵詞，故返回空值；當所有關(guān)鍵詞的xtagadd∈XSet時，若存在某個關(guān)鍵詞的xtagdel∈XSet，則說明該關(guān)鍵詞與文檔建立索引后又刪除了索引，即文檔不包含所有關(guān)鍵詞，故返回空值；若所有關(guān)鍵詞的xtagadd∈XSet且所有的xtagdel?XSet，則文檔包含所有關(guān)鍵詞，故返回TSet中的索引值給客戶端.

3.4 方案詳細描述

本節(jié)將改進OXT協(xié)議構(gòu)造為具體的動態(tài)可搜索加密方案，主要包括系統(tǒng)建立階段、更新階段和查詢階段.

3.4.1 系統(tǒng)建立階段

系統(tǒng)建立階段由數(shù)據(jù)擁有者生成密鑰組sk=(KS,KX,KY,KM,PK,SK)，并初始化關(guān)鍵詞的更新計數(shù)器表UpdtCnt、關(guān)鍵詞索引表TSet和交叉索引表XSet，得到加密數(shù)據(jù)庫EDB；最終，數(shù)據(jù)擁有者將(KM,PK,EDB)發(fā)給服務(wù)器，然后本地存儲密鑰組sk和本地狀態(tài)st=UpdtCnt.具體過程如算法1所示.

算法1.系統(tǒng)建立算法.

輸入：安全參數(shù)λ；

輸出：密鑰組sk、本地狀態(tài)st、數(shù)據(jù)庫EDB.

數(shù)據(jù)擁有者：

① 用偽隨機函數(shù)F生成密鑰KS；

② 用偽隨機函數(shù)Fp生成密鑰KX，KY和KM；

③ 用密鑰生成算法生成公私鑰對(PK,SK)；

④ 初始化UpdtCnt，TSet和XSet為空表；

⑤ 令sk=(KS,KX,KY,KM,PK,SK)，st=UpdtCnt，EDB=(TSet,XSet)；

⑥ 發(fā)送(KM,PK,EDB)給服務(wù)器.

其中，KM是服務(wù)器與數(shù)據(jù)擁有者之間的共享對稱密鑰；SK和PK被用作數(shù)字簽名，在查詢時實現(xiàn)授權(quán)及權(quán)限驗證.

3.4.2 更新階段

數(shù)據(jù)擁有者運行索引更新算法，查找并更新本地狀態(tài)st中的更新計數(shù)器表；接著計算本次更新記錄在TSet中的存儲地址addr和關(guān)鍵詞索引值(val,α)，其中val是(id,op)的加密值，α是致盲因子；然后計算本次更新的交叉索引值xtag，并將(addr,val,α,xtag)存儲到服務(wù)器上的TSet表和XSet表中.具體的過程如算法2所示.

算法2.索引更新算法.

輸入：密鑰組sk、本地狀態(tài)st、操作類型op、關(guān)鍵詞與文檔標識符對(id,w)、加密數(shù)據(jù)庫EDB；

輸出：更新狀態(tài)st′、更新數(shù)據(jù)庫EDB′.

數(shù)據(jù)擁有者：

① 令sk=(KS,KX,KY,KM,PK,SK)，st=UpdtCnt；

② ifUpdtCnt[w]==null then

③ 令UpdtCnt[w]=0；

④ end if

⑤UpdtCnt[w]=UpdtCnt[w]+1；

⑥ 令strap=F(KS,w)，KZ=F(strap,1)，KT=F(strap,2);/*strap是密鑰派生因子*/

⑦ 令addr=F(KT,w‖UpdtCnt[w]‖0)；

⑧ 令val=(id‖op)⊕F(KT,w‖UpdtCnt[w]‖1)；

⑨ 令α=Fp(KY,id)(Fp(KZ,UpdtCnt[w]))-1；

⑩ 令xtag=gFp(KX,w‖op)×Fp(KY,id)；

服務(wù)器端：

3.4.3 查詢階段

在查詢階段，客戶端會通過接收者公鑰分別與數(shù)據(jù)擁有者、云服務(wù)器端協(xié)商一個會話密鑰，并用會話密鑰加密傳輸數(shù)據(jù)，從而保證數(shù)據(jù)傳輸過程中的安全性.查詢階段包括授權(quán)算法、查詢令牌生成算法和查詢算法.

數(shù)據(jù)擁有者收到客戶端發(fā)送的查詢q后，遍歷q找到更新次數(shù)最低的關(guān)鍵詞w1，并為每個關(guān)鍵詞生成一次性盲因子ρ和查詢令牌生成因子bxtrap，分別存儲到ρlist和btrlist；接著用w1生成密鑰派生因子strap并派生出子密鑰，根據(jù)w1的更新計數(shù)器值計算每次更新的關(guān)鍵詞索引在TSet中的存儲地址addr；然后利用數(shù)字信封技術(shù)和共享密鑰KM來加密ρ和addr，最終得到env.最后用會話密鑰加密(env,UpdtCnt[w1],strap,btrlist)并發(fā)送給客戶端.具體過程如算法3所示.

算法3.授權(quán)算法.

輸入：密鑰組sk、本地狀態(tài)st、查詢列表q=(w1,w2,…,wn)；

輸出：數(shù)字信封env、最低頻關(guān)鍵詞的更新計數(shù)器值UpdtCnt[w1]、密鑰派生因子strap、查詢令牌生成因子列表btrlist.

數(shù)據(jù)擁有者：

① 數(shù)據(jù)擁有者接收客戶端發(fā)來的查詢q；

② 令sk=(KS,KX,KY,KM,PK,SK)，st=UpdtCnt；

③ 找到更新次數(shù)最低的關(guān)鍵詞w1；

④ fori=1 tolen(q)do

⑤ 令ρi=并存入ρlist；

⑥ 令bxtrapadd/del=gFp(KX,wi‖add/del)ρi；

⑦ 將(bxtrapadd,bxtrapdel)存入btrlist；

⑧ end for

⑨ 令strap=F(KS,w1)，KT=F(strap,2)；

⑩ forj=1 toUpdtCnt[w1]do

/*Enc為對稱加密算法*/

/*digest_sign為數(shù)字簽名算法*/

客戶端收到數(shù)據(jù)擁有者發(fā)來的授權(quán)信息并用會話密鑰解密后，先利用密鑰派生因子strap生成子密鑰KZ和KT;然后根據(jù)查詢令牌生成因子bxtrap和子密鑰KZ來生成查詢令牌bxtoken，并存到列表btklist中;最后用會話密鑰將數(shù)據(jù)擁有者發(fā)來的數(shù)字信封env和查詢令牌列表btklist加密發(fā)給服務(wù)器.具體過程如算法4所示.

算法4.查詢令牌生成算法.

輸入：數(shù)字信封env、更新次數(shù)最低關(guān)鍵詞的更新計數(shù)器值UpdtCnt[w1]、密鑰派生因子strap、查詢令牌生成因子列表btrlist；

輸出：數(shù)字信封env、查詢令牌列表btklist.

客戶端：

① 生成密鑰KZ=F(strap,1)，KT=F(strap,2)；

② fori=1 toUpdtCnt[w1]do

③ forj=1 tolen(btrlist)do

④ 取出bxtrapadd/del的值；

⑥ (bxtokenadd,bxtokendel)存入btk[i]；

⑦ end for

⑧ 將btk[i]存入btklist；

⑨ end for

⑩ 發(fā)送(env,btklist)給服務(wù)器.

服務(wù)器收到客戶端發(fā)送的數(shù)字信封env和查詢令牌列表btklist并解密后，首先驗證數(shù)字信封并解密得到一次性盲因子列表ρlist和最低更新次數(shù)的關(guān)鍵詞在TSet中的存儲地址列表alist；然后遍歷alist中的addr，取出對應(yīng)的關(guān)鍵詞索引值(val,α)；接著對于每一個(val,α)，用致盲因子α，ρlist中的ρ和對應(yīng)的(bxtokenadd,bxtokendel)計算每個關(guān)鍵詞的交叉索引對(xtagadd,xtagdel)，判斷每個交叉索引值與XSet的關(guān)系，從而確定val中存儲的文檔是否包含每個關(guān)鍵詞；最終將符合查詢條件的val加入列表EOplist并加密發(fā)送給客戶端.客戶端解密得到EOplist，利用密鑰KT解密得到最終的文檔標識符列表Idlist.具體過程如算法5所示.

算法5.查詢算法.

輸入：數(shù)字信封env、查詢令牌btklist、共享密鑰KM、數(shù)據(jù)擁有者公鑰PK、加密數(shù)據(jù)庫EDB；

輸出：符合聯(lián)合查詢的文檔標識符列表Idlist.

服務(wù)器：

① 令EDB=(TSet,XSet)；

② 用PK和KM驗證并解密env，得到ρlist和alist；

③ fori=1 tolen(alist)do

④ (val,α)=TSet[alist[i]]；

⑤ 設(shè)置b=1;/*標記是否符合聯(lián)合查詢*/

⑥ forj=1 tolen(ρlist)do

⑦ (bxtokenadd,bxtokendel)=btklist[i][j];

⑨ ifxtagadd?XSetthen

⑩b=0；

客戶端：

4 安全性分析與證明

4.1 安全模型

在本文方案的安全模型中，假設(shè)數(shù)據(jù)擁有者與客戶端是完全可信的，服務(wù)器是誠實且好奇的，它會始終正確執(zhí)行給定協(xié)議，但可能會嘗試學(xué)習(xí)關(guān)于存儲數(shù)據(jù)和查詢關(guān)鍵詞的一些其他信息.為了定義本文方案泄露函數(shù)的具體表示形式，本文設(shè)Q是一個包含以下信息的列表：

1)(t,w).表示對關(guān)鍵詞w執(zhí)行的搜索問詢及對應(yīng)時間戳t.

2)(t,op,id,w).對(op,(id,w))執(zhí)行的更新問詢及對應(yīng)時間戳t，其中op∈{add,del}.

對于任意聯(lián)合查詢q=(w1,w2,…,wn)，假設(shè)w1是更新次數(shù)最低的關(guān)鍵詞.本文定義TimeDB(q)返回所有滿足q且未被刪除的文檔標識符及對應(yīng)的插入時間戳，表示為

TimeDB(q)={({ti}i∈[n],id)|(ti,add,id,wi)∈Q

and ?t′:(t′,del,id,wi)?Q}；

(13)

定義Upd(q)返回w1所有更新操作的時間戳，表示為

Upd(q)={t|?(op,id):(t,op,id,w1)∈Q}.

(14)

根據(jù)文獻[10]中泄露函數(shù)的定義，本文方案的泄露函數(shù)L=(LSetup,LUpdate,LSearch)為

LSetup(λ)=⊥，

(15)

LUpdate(op,(id,w))=⊥，

(16)

LSearch(q)=(TimeDB(q),Upd(q)).

(17)

4.2 安全性證明

定理1.給定偽隨機函數(shù)F和Fp是安全的，以g為生成元的群G滿足DDH假設(shè)，如果MC-ODXT方案的泄露函數(shù)L=(LSetup,LUpdate,LSearch)滿足：

LSetup(λ)=⊥，

LUpdate(op,(id,w))=⊥，

LSearch(q)=(TimeDB(q),Upd(q))，

則MC-ODXT方案是L自適應(yīng)安全的.

本文借鑒文獻[10]中的證明方法，通過從Real到Ideal設(shè)置一系列游戲來證明定理1，每個游戲都與上個游戲有所不同，但是在敵手A看來2個相鄰游戲間是不可區(qū)分的，最后使用泄露函數(shù)L模擬Ideal，從而得出敵手A無法區(qū)分現(xiàn)實模型Real與理想模型Ideal.

游戲G0.與Real相同，運行本文真實方案.

游戲G1.與G0不同的是，在每次更新和查詢時，挑戰(zhàn)者將偽隨機函數(shù)F(KS,·)，F(xiàn)(KT,·)，F(xiàn)p(KX,·)，F(xiàn)p(KY,·)，F(xiàn)p(KZ,·)分別替換為GS(·)，GT(·)，GX(·)，GY(·)，GZ(·)，其中GS(·)，GT(·)是(0,1)λ上所有隨機函數(shù)的集合內(nèi)均勻隨機采樣，GX(·)，GY(·)，GZ(·)是上所有隨機函數(shù)的集合內(nèi)均勻隨機采樣.

引理1.如果Fp，F(xiàn)是安全的偽隨機函數(shù)，則在敵手A看來G0與G1是不可區(qū)分的.

證明.假設(shè)存在一個多項式時間敵手B，可以區(qū)分G0與G1，則該敵手可以設(shè)計一個多項式時間算法B′從隨機函數(shù)中區(qū)分出偽隨機函數(shù).顯然，這與偽隨機函數(shù)的偽隨機性相矛盾.

證畢.

游戲G2.與G1不同的是，挑戰(zhàn)者在查詢階段改變了bxtoken的計算方式.對于查詢q，挑戰(zhàn)者通過瀏覽敵手A的更新問詢歷史來獲取w1的更新操作集合{(opj,(idj,w1))|j∈{1,2,…,UpdtCnt[w1]}}.然后，對于每個關(guān)鍵詞wi，計算它們的αi,j和xtagi,j，并將xtagi,j存到數(shù)組A中；接著在上均勻隨機采樣生成ρi，并存到數(shù)組B中.計算bxtokeni,j=xta.對于不可能匹配的bxtoken，挑戰(zhàn)者用bxtoken=gFp(KX,wi‖add/del)ρi×Fp(KZ,j)計算，并且將結(jié)果存到數(shù)組C.從以上步驟可以看出，G2與G1中的bxtoken的分布值是相同，故G2與G1是不可區(qū)分的.

游戲G3.與G2不同的是，挑戰(zhàn)者改變了α在更新階段的生成方式，用上的均勻隨機采樣來代替原來的計算.

引理2.在敵手A看來，G3與G2在統(tǒng)計上是不可區(qū)分的.

證明.游戲G2中的α是由GY(·)與GZ(·)的逆來計算的，其中GY(·)與GZ(·)是上所有隨機函數(shù)的均勻隨機采樣，而在G2中，α的值也是均勻且獨立的隨機分布.故G2與G3中的α值在統(tǒng)計上是不可區(qū)分的.

證畢.

引理3.若在群G上滿足DDH假設(shè)，則在敵手A看來G4與G3是不可區(qū)分的.

證明.假設(shè)存在一個多項式時間敵手B可以從敵手A的視角區(qū)分出G4與G3，則存在一個多項式時間算法B′，可以區(qū)分出gr和gFp(KX,w‖op)×Fp(KY,id).顯然，B′破壞了群G上的DDH假設(shè)，故不存在敵手B可以區(qū)分G3與G4.

證畢.

游戲G5.與G4不同的是，挑戰(zhàn)者改變了addr與val在更新階段的計算方式.具體地，挑戰(zhàn)者將GT(w‖UpdtCnt[w]‖b)(其中b∈{0,1})形式的函數(shù)計算改成了GT(t)形式，其中t是每個更新操作執(zhí)行的時間戳.類似地，挑戰(zhàn)者也改變了查詢階段addr的生成方式，將GT(w‖UpdtCnt[w]‖0)改成了GT(t)，其中t是對應(yīng)的更新操作的時間戳.

引理4.在敵手A看來，G5和G4在計算上是不可區(qū)分的.

證明.由于每一個關(guān)鍵詞的更新計數(shù)器UpdtCnt的值是單調(diào)遞增的，而GT(·)不會在輸入2個不同的時間戳后輸出相同的結(jié)果.所以在敵手A看來G5和G4在計算上是不可區(qū)分的.

證畢.

游戲G6.與G5不同的是，將挑戰(zhàn)者換成了模擬器S，并且S在更新階段和查詢階段只能訪問泄露函數(shù)L=(LUpdate,LSearch).

引理5.在敵手A看來，G5和G6在計算上是不可區(qū)分的.

證明.模擬器S訪問泄露函數(shù)LUpdate(op,(id,w))=⊥和LSearch(q)=(TimeDB(q),Upd(q))，且模擬器S生成的一系列變量與G5中的挑戰(zhàn)者相同.在查詢階段，S可以學(xué)習(xí)更新次數(shù)最低的關(guān)鍵詞的更新次數(shù)和更新時間戳，用Upd(q)表示.S還可以學(xué)習(xí)聯(lián)合查詢的最終結(jié)果，即一系列文檔標識符和相應(yīng)的時間戳，用TimeDB(q)表示.除此之外，S可以推斷出有共同最低更新次數(shù)關(guān)鍵詞的2個聯(lián)合查詢q1和q2，分別用Upd(q1)和Upd(q2)表示.在敵手A看來，由S做出的回應(yīng)與G5中挑戰(zhàn)者做出的回應(yīng)是相同的.故G5與G6是不可區(qū)分的.綜上所述，以上一系列游戲和理論證明都說明了定理1的正確性.

證畢.

由文獻[6]中對前向安全的定義可得，動態(tài)可搜索加密是自適應(yīng)前向安全的，當且僅當泄露函數(shù)LUpdate可以表示為

LUpdate(op,(id,w))=L′(op,id)，

(18)

其中，L′是無狀態(tài)函數(shù)[22],表示服務(wù)器在更新時運行的函數(shù)，op和id表示服務(wù)器在當前更新階段接收到的明文信息，即向服務(wù)器泄露的信息.由式(16)知本文方案在更新階段不會泄露關(guān)鍵詞w、文檔標識符id及更新操作op的任何信息.因此可以得出推論1.

推論1.MC-ODXT的前向安全性.如果F,Fp是安全的偽隨機函數(shù)，群G滿足DDH假設(shè)，則本文方案是自適應(yīng)前向安全的.

由文獻[7]中對后向安全的定義可得，一個支持單關(guān)鍵詞查詢的DSSE方案滿足自適應(yīng)后向安全，

當且僅當更新泄露函數(shù)LUpdate和查詢泄露函數(shù)LSearch可以表示為

LUpdate(op,(id,w))=L″(op,id)，

(19)

LSearch(w)=L?(TimeDB(w),Upd(w))，

(20)

其中，L″和L?是無狀態(tài)函數(shù)[22]，分別表示服務(wù)器在更新和查詢時運行的函數(shù)，op和id表示服務(wù)器在當前更新階段獲取的明文信息，插入時間戳集合TimeDB(w)和更新時間戳集合Upd(w)表示當前查詢階段獲取的明文信息.由式(16)和式(17)可知本文方案的泄露函數(shù)滿足后向安全的定義，故得出推論2.

推論2.MC-ODXT的后向安全性.如果F,Fp是安全的偽隨機函數(shù)，群G滿足DDH假設(shè)，則本文方案是自適應(yīng)后向安全的.

5 性能分析

5.1 理論分析

1)功能方面

① 索引更新.DMSSE方案不支持索引更新，MitraConj,ODXT及本文方案均支持索引動態(tài)更新.

② 多客戶端查詢.MitraConj方案與ODXT方案僅支持數(shù)據(jù)擁有者查詢，而DMSSE方案與本文方案均支持多客戶端查詢.

③ 聯(lián)合查詢.DMSSE方案支持靜態(tài)數(shù)據(jù)集上的聯(lián)合查詢，MitraConj,ODXT及本文方案均支持動態(tài)數(shù)據(jù)集上的聯(lián)合查詢.不過MitraConj方案的查詢效率較低，并且在查詢時會向服務(wù)器泄露每個關(guān)鍵詞的信息；ODXT方案與本文方案在查詢時僅泄露更新次數(shù)最低的關(guān)鍵詞的信息，但ODXT方案在查詢有刪除記錄的關(guān)鍵詞時查詢結(jié)果會與實際結(jié)果有偏差.與其他方案相比，本文方案支持的查詢功能更為豐富、適用范圍更廣.

Table 1 Features Comparison of the Conjunctive-keywords Searchable Encryption Schemes

2)效率方面

① 更新時間.DMSSE方案不支持索引更新，故不考慮更新時間.MitraConj,ODXT與本文方案均通過向數(shù)據(jù)庫中添加更新記錄來實現(xiàn)更新功能，執(zhí)行常數(shù)級運算，故更新時間復(fù)雜度均為O(1).

綜上可知，本文方案與ODXT方案在更新時間、生成查詢時間及查詢時間的復(fù)雜度相同，且查詢時的時間復(fù)雜度僅與更新次數(shù)最低的關(guān)鍵詞的更新次數(shù)有關(guān).

5.2 實驗及結(jié)果分析

本文實驗使用Python語言對算法進行實現(xiàn)，實驗環(huán)境為Windows 10配置在Intel Core i5-1135G7 2.40 GHz 16 GB內(nèi)存中，使用Enron電子郵件數(shù)據(jù)集作為實驗數(shù)據(jù).本文從Enron的150個用戶數(shù)據(jù)中提取了30 109個郵件數(shù)據(jù)，并從中提取了121 380個文檔與關(guān)鍵詞對，參考了文獻[21]中的數(shù)據(jù)預(yù)處理方法來處理數(shù)據(jù)，得到最終實驗數(shù)據(jù)集.

首先，實驗固定更新次數(shù)最低的關(guān)鍵詞的更新次數(shù)為10，通過改變單次查詢中的關(guān)鍵詞數(shù)量n，對方案的查詢耗時進行了測試，結(jié)果如圖4所示.

由圖4可知，當更新次數(shù)最低關(guān)鍵詞的更新次數(shù)不變時，查詢耗時隨著關(guān)鍵詞的個數(shù)增加呈線性增加.這是因為查詢時查詢令牌的計算次數(shù)決定了查詢階段的耗時，而計算次數(shù)會隨關(guān)鍵詞個數(shù)的增加線性增加，所以查詢耗時也線性增加.

接下來通過改變不同關(guān)鍵詞的更新次數(shù)，來測試關(guān)鍵詞的更新次數(shù)與查詢耗時之間的關(guān)系.實驗假設(shè)在查詢q=(w1,w2)中改變關(guān)鍵詞的更新次數(shù)時，始終保持w1的更新次數(shù)比w2低，UpdtCnt[w]表示關(guān)鍵詞w的更新計數(shù)器值.結(jié)果如圖5所示，當固定w1的更新次數(shù)為10時，增加w2的更新次數(shù)，方案的查詢耗時幾乎不變；當固定w2的更新次數(shù)為2 800時，增加w1的更新次數(shù)，查詢耗時呈線性增長.這是由于本文方案先查詢最低更新次數(shù)關(guān)鍵詞對應(yīng)的關(guān)鍵詞索引，再從這些索引中篩選包含所有關(guān)鍵詞的文檔索引，因此查詢耗時僅與更新次數(shù)最低的關(guān)鍵詞的更新次數(shù)有關(guān).

最后，為了測試ODXT方案與本文方案的查詢結(jié)果與實際結(jié)果是否一致，從以上實驗的匹配結(jié)果中隨機選取10%的文檔并刪除了其中一個關(guān)鍵詞與這些文檔的索引，然后改變另一個關(guān)鍵詞從匹配結(jié)果中刪除文檔索引的比例，并統(tǒng)計刪除后查詢結(jié)果占刪除前查詢結(jié)果的百分比.其中，另一個關(guān)鍵詞從匹配結(jié)果中刪除文檔的比例分別設(shè)為0%、5%且與前一個關(guān)鍵詞刪除文檔完全重復(fù)、5%且與前一個關(guān)鍵詞刪除的文檔完全不重復(fù)、10%且有一半與前一個關(guān)鍵詞刪除的文檔重復(fù).為了方便分析實驗結(jié)果，在w1，w2刪除了部分索引后，設(shè)置w1仍然是最低更新次數(shù)的關(guān)鍵詞，實驗結(jié)果如圖6、圖7所示.

圖6展示了從匹配結(jié)果中刪除10%的文檔與w1間的索引后，改變w2刪除比例得出的查詢結(jié)果.由圖6可知，ODXT的查詢結(jié)果始終只比刪除前少了10%.此外，當w2刪除的文檔與w1刪除的文檔不重復(fù)時，相比ODXT方案的結(jié)果會發(fā)生一定偏差，本文方案仍能保證查詢結(jié)果始終與實際結(jié)果一致.

圖7展示了從匹配結(jié)果中刪除10%文檔與w2之間的索引后，改變w1刪除比例得出的查詢結(jié)果.由圖7可知，ODXT的查詢結(jié)果隨著w1刪除比例的增大而減少，且ODXT的減少比例與w1增加的刪除比例一致.而本文方案中的查詢結(jié)果與實際結(jié)果一致，即減少的匹配文檔比例是2個關(guān)鍵詞刪除的文檔比例之和.

對比圖6、圖7可以看出，當w1刪除索引而w2不刪除索引時，ODXT方案與實際查詢結(jié)果一致；當w2刪除索引而w1不刪除索引時，ODXT方案的查詢結(jié)果與刪除前一致；當w1與w2都刪除索引時，ODXT方案的查詢結(jié)果與只刪除w1的查詢結(jié)果是一致的.這是由于ODXT在查詢時只能返回更新次數(shù)最低的關(guān)鍵詞對應(yīng)的每個更新操作類型，無法返回其他關(guān)鍵詞的更新操作類型，故不會過濾掉其他關(guān)鍵詞的已刪除索引.因此，ODXT方案在查詢有刪除記錄的關(guān)鍵詞時，只對更新次數(shù)最低的關(guān)鍵詞執(zhí)行刪除操作，而未對其他關(guān)鍵詞執(zhí)行刪除，所以查詢結(jié)果與實際結(jié)果有一定的偏差.本文方案在查詢有刪除記錄的關(guān)鍵詞時，查詢結(jié)果始終與實際查詢結(jié)果一致，所以本文方案實現(xiàn)了準確的聯(lián)合查詢.

6 結(jié) 論

針對ODXT方案中存在的聯(lián)合查詢結(jié)果不準確的問題，本文通過改進不經(jīng)意交叉索引協(xié)議，實現(xiàn)了準確的聯(lián)合查詢，且查詢的時間復(fù)雜度僅與更新次數(shù)最低的關(guān)鍵詞的更新次數(shù)有關(guān).另外，本文通過引入一次性盲因子和數(shù)字信封技術(shù)，設(shè)計了一個支持聯(lián)合搜索的多用戶動態(tài)可搜索加密方案，保證了授權(quán)多用戶查詢時的安全性.通過方案的安全性分析可以得出，本文所提的MC-ODXT方案滿足前向安全與后向安全.最后我們對方案性能進行了理論和實驗分析，證明了本文方案在保證安全性的同時查詢功能更為豐富，且其時間復(fù)雜度與ODXT方案的時間復(fù)雜度相同.

作者貢獻聲明：張藍藍提出算法思路與實驗方案，完成實驗并撰寫論文；曹衛(wèi)東提供理論指導(dǎo)、研究思路分析及論文修改意見；王懷超提供理論分析和技術(shù)指導(dǎo),提出論文修改意見.