一種支持聯合搜索的多用戶動態對稱可搜索加密方案

張藍藍 曹衛東 王懷超

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

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

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

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

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

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

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

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

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

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

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

1 相關工作

1.1 動態可搜索加密

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

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

1.2 支持聯合查詢的可搜索加密

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

1.3 多用戶對稱可搜索加密

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

2 預備知識

2.1 偽隨機函數

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

2.2 判定性Diffie-Hellman假設

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

2.3 動態可搜索加密

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

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

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

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

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

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

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

2.4 不經意交叉索引

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

1)TSet表.TSet是關鍵詞索引表，以addr為索引，存儲了包含關鍵詞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是交叉索引表，存儲了關鍵詞w與文檔的交叉索引xtag，xtag標記了w與文檔間的包含關系.系統建立時，根據文檔標識符id和關鍵詞w，計算出交叉索引值xtag并存到XSet中.xtag的計算方式為

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

(4)

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

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

(5)

3 MC-ODXT方案

3.1 系統模型

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

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

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

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

3.2 算法定義

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

1)系統建立算法

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

2)索引更新算法

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

3)授權算法

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

4)查詢令牌生成算法

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

5)查詢算法

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

3.3 改進OXT協議

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

3.3.1 關鍵詞索引表TSet的構建

與OXT協議相同，TSet中存儲了加密信息val和致盲因子α，即TSet[addr]=(val,α)，addr是本次記錄在TSet中的索引地址.不同的是，式(2)和式(3)中的文檔計數器被改為更新計數器UpdtCnt；并將對稱加密算法Enc改為效率更高的偽隨機函數F；此外，關鍵詞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構建

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

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

(9)

3.3.3 查詢令牌xtoken的生成

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

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

(10)

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

(11)

為了使服務器可以根據bxtoken和α計算出xtag，之后利用xtag來判斷文檔是否符合聯合查詢，本文的xtag應滿足關系式

xtag=bxtokenα/ρ.

(12)

3.3.4 聯合查詢過程

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

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

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

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

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

3種判斷結果是對單個文檔包含單個關鍵詞的判斷結果.對于單個文檔是否包含聯合查詢的所有關鍵詞，其判斷流程如圖3所示：

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

3.4 方案詳細描述

本節將改進OXT協議構造為具體的動態可搜索加密方案，主要包括系統建立階段、更新階段和查詢階段.

3.4.1 系統建立階段

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

算法1.系統建立算法.

輸入：安全參數λ；

輸出：密鑰組sk、本地狀態st、數據庫EDB.

數據擁有者：

① 用偽隨機函數F生成密鑰KS；

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

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

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

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

⑥ 發送(KM,PK,EDB)給服務器.

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

3.4.2 更新階段

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

算法2.索引更新算法.

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

輸出：更新狀態st′、更新數據庫EDB′.

數據擁有者：

① 令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)；

服務器端：

3.4.3 查詢階段

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

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

算法3.授權算法.

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

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

數據擁有者：

① 數據擁有者接收客戶端發來的查詢q；

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

③ 找到更新次數最低的關鍵詞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為數字簽名算法*/

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

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

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

輸出：數字信封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

⑩ 發送(env,btklist)給服務器.

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

算法5.查詢算法.

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

輸出：符合聯合查詢的文檔標識符列表Idlist.

服務器：

① 令EDB=(TSet,XSet)；

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

③ fori=1 tolen(alist)do

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

⑤ 設置b=1;/*標記是否符合聯合查詢*/

⑥ forj=1 tolen(ρlist)do

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

⑨ ifxtagadd?XSetthen

⑩b=0；

客戶端：

4 安全性分析與證明

4.1 安全模型

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

1)(t,w).表示對關鍵詞w執行的搜索問詢及對應時間戳t.

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

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

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)

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

LSetup(λ)=⊥，

(15)

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

(16)

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

(17)

4.2 安全性證明

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

LSetup(λ)=⊥，

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

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

則MC-ODXT方案是L自適應安全的.

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

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

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

引理1.如果Fp，F是安全的偽隨機函數，則在敵手A看來G0與G1是不可區分的.

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

證畢.

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

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

引理2.在敵手A看來，G3與G2在統計上是不可區分的.

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

證畢.

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

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

證畢.

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

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

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

證畢.

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

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

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

證畢.

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

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

(18)

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

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

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

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

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

(19)

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

(20)

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

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

5 性能分析

5.1 理論分析

1)功能方面

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

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

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

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

2)效率方面

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

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

5.2 實驗及結果分析

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

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

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

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

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

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

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

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

6 結 論

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

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