基于雙向索引的高效連接關(guān)鍵字查詢動態(tài)可搜索加密方案

杜瑞忠，張玉晴，李明月

（1.河北大學(xué)網(wǎng)絡(luò)空間安全與計算機學(xué)院，河北 保定 071000；2.河北省高可信信息系統(tǒng)重點實驗室，河北 保定 071000；3.南開大學(xué)計算機學(xué)院，天津 300071）

0 引言

云計算的出現(xiàn)允許個人和組織將大量數(shù)據(jù)的存儲和處理外包給第三方服務(wù)器。然而，這導(dǎo)致了隱私問題，用戶通常不相信服務(wù)提供者會尊重其數(shù)據(jù)的機密性[1]。這種信任的缺乏往往會受到來自內(nèi)部惡意用戶和外部攻擊者的威脅。為了解決這個問題，Song 等[2]首次提出了可搜索加密（SE,searchable encryption）技術(shù)?？伤阉骷用芊譃閷ΨQ可搜索加密（SSE,searchable symmetric encryption）[3]和公鑰可搜索加密（PEKS,public-key encryption with keyword search）[4]，SSE 算法簡單并且更加高效，所以得到更廣泛的應(yīng)用。然而，早期的SSE 方案都是靜態(tài)的。

動態(tài)對稱可搜索加密（DSSE,dynamic searchable symmetric encryption）技術(shù)[5]的提出擴展了SSE的應(yīng)用，其不僅支持?jǐn)?shù)據(jù)檢索，還支持?jǐn)?shù)據(jù)動態(tài)更新。然而，DSSE 方案在動態(tài)更新的過程中，服務(wù)器可能會學(xué)習(xí)到一些信息，即導(dǎo)致信息泄露，泄露的信息包括數(shù)據(jù)庫大小、查詢模式和訪問模式。為提出更安全的方案，前向安全和后向安全[6]的概念被提出。前向安全是指無法確認(rèn)新添加的文件是否包含已搜索的關(guān)鍵字。后向安全是指如果一個關(guān)鍵字/文件對(w,f )被添加到數(shù)據(jù)庫中，然后被刪除，則對w的后續(xù)搜索查詢不會顯示文件f。Bost 等[7]根據(jù)泄露程度的不同定義了3 種后向安全：對于關(guān)鍵字w，Type-I 泄露了當(dāng)前匹配關(guān)鍵字w的文件和文件的插入時間，以及w更新的總次數(shù)；Type-II額外泄露了更新發(fā)生的時間；Type-III 額外泄露了已刪除文件被添加的時間，以及被哪次更新刪除。

大多數(shù)前向安全和后向安全的DSSE 方案都是利用茫然隨機訪問機（ORAM,oblivious random access machine）避免訪問模式的泄露。然而，ORAM結(jié)構(gòu)檢索和更新效率低，通信開銷和計算開銷大，并且不支持包含大量文件的數(shù)據(jù)庫，所以需要采用新的索引結(jié)構(gòu)去提升檢索和更新效率，并且保證方案的前向安全和后向安全。同時，現(xiàn)有的同時滿足前向安全和后向安全的DSSE 方案只支持單關(guān)鍵字查詢，表達(dá)能力受到嚴(yán)重限制且不滿足實際應(yīng)用的需求。因此，任何SSE 方案要真正實用，至少應(yīng)該支持連接關(guān)鍵字查詢，即給定一組關(guān)鍵字(w1,...,wn)，該方案能夠找到并返回包含所有這些關(guān)鍵字的文檔集。

為了解決上述問題，本文主要研究工作如下。

1) 采用正排索引和倒排索引結(jié)合的思想，利用位圖索引設(shè)計雙向索引結(jié)構(gòu)，添加和刪除操作僅需要一個模加法運算，不僅簡化了更新過程的操作，而且防止了訪問模式的泄露。

2) 利用雙向索引設(shè)計了連接關(guān)鍵字查詢方案BPC-DSSE。該方案使用內(nèi)積匹配算法計算連接關(guān)鍵字查詢結(jié)果，查詢過程只需要兩輪交互，提高了查詢效率，同時實現(xiàn)了Type-I-后向安全。

3) 理論分析和仿真實驗結(jié)果表明，BPC-DSSE方案與使用ORAM 結(jié)構(gòu)和其他結(jié)構(gòu)實現(xiàn)前向安全和后向安全的連接關(guān)鍵字方案相比，具有更好的查詢與更新性能，并且保證了更新過程的安全性。

1 相關(guān)工作

SSE 首先由Song 等[2]提出，對于長度為n的文件，該方案加密和搜索算法需要流密碼和分組密碼，操作時間復(fù)雜度為O(n)。為了支持動態(tài)更新，DSSE[5]被提出。早期的DSSE 方案很容易受到潛在攻擊的威脅[8]，如文件注入攻擊[9]。為了減輕這種攻擊造成的威脅，前向安全和后向安全的概念被提出[6]。2016 年，Bost[10]給出了前向安全的正式定義，并給出了一種前向安全的DSSE 方案Σoφo?，該方案使用簡單的密碼工具（只有偽隨機函數(shù)和陷門原語），不依賴ORAM 結(jié)構(gòu)，效率和安全性都有一定的提升。2017 年，Bost 等[7]根據(jù)泄露的不同程度從高到低定義了3 種后向安全類型，并給出了4 種前向安全和后向安全的方案。第一種方案Fides 實現(xiàn)了Type-II的后向安全。第二種方案Diana非常高效，但只實現(xiàn)了Type-III 的后向安全，Diana 被修改成只需要2 種往返的后向安全方案Dianadel。第三種方案Janus 是具有單次往返的后向安全方案，但該方案也只實現(xiàn)了Type-III 的后向安全。第四種方案Moneta 實現(xiàn)了Type-I 的后向安全，但此方案是基于TWORAM（ORAM in two rounds）結(jié)構(gòu)的，因此計算開銷和通信開銷都非常大。自此，一系列前向安全和后向安全的方案被提出[11-17]。

Cash 等[18]提出基于茫然交叉標(biāo)簽（OXT,oblivious cross tag）協(xié)議設(shè)計有效的SSE 協(xié)議，支持單作者閱讀框架中的連接關(guān)鍵字查詢。雖然OXT 協(xié)議通過許多專門的數(shù)據(jù)結(jié)構(gòu)來提供高性能，但它向服務(wù)器泄露“部分”數(shù)據(jù)庫信息。同時，該方案需要三輪交互，增加了通信開銷。2018 年，Lai 等[19]提出了一種新的SSE 協(xié)議，稱為隱藏交叉標(biāo)簽（HXT,hidden cross tag），它消除了連接關(guān)鍵字查詢的關(guān)鍵字對結(jié)果模式（KPRP,keyword pair result pattern）泄露。2019 年，Wu 等[20]提出以自上而下的方式存儲索引元素到虛擬二叉樹（VBTree,virtual binary tree）結(jié)構(gòu)中，而不存儲任何樹枝和樹節(jié)點，該樹只存在于邏輯視圖中，并且所有的元素實際上都存儲在一個哈希表中，但是該方案只實現(xiàn)了前向安全。2020 年，Zuo 等[21]提出了一個擴展位圖索引結(jié)構(gòu)，比VBTree 更高效地實現(xiàn)了連接關(guān)鍵字查詢，并且實現(xiàn)了前向安全和后向安全。2021 年，Patranabis等[22]提出了茫然動態(tài)交叉標(biāo)簽（ODXT,oblivious dynamic cross tag），ODXT 通過有效地支持在大型數(shù)據(jù)庫上的快速更新和連接關(guān)鍵字查詢，在性能和安全性之間提供了現(xiàn)實的折中，同時根據(jù)現(xiàn)有的前后隱私概念，只對服務(wù)器造成適度的訪問模式泄露。

2 DSSE 定義及其安全模型

本節(jié)給出了必要的背景知識，包括符號定義、DSSE 方案的定義及其安全模型、前向安全和后向安全。

2.1 符號定義

本文中使用的主要參數(shù)如表1 所示。

表1 主要參數(shù)

2.2 DSSE 方案的定義

數(shù)據(jù)庫DB 為關(guān)鍵字/文件標(biāo)識符對的列表；fi為文檔標(biāo)識符；wi為fi中包含的所有關(guān)鍵字集合，wi?{0,1}*；n 為數(shù)據(jù)庫DB 中所有文件的數(shù)量。那么數(shù)據(jù)庫DB 可以表示為|DB|為關(guān)鍵字/文件標(biāo)識符對的總數(shù)量。W 為數(shù)據(jù)庫DB 中所有關(guān)鍵字的集合

DSSE 方案包括算法Setup 以及運行在客戶端和服務(wù)器的協(xié)議Search 和Update，即DSSE=(Setup,Search,Update)，具體描述如下。

(EDB,σ)←Setup(1λ,DB)。輸入安全參數(shù)λ、數(shù)據(jù)庫DB，輸出當(dāng)前的狀態(tài)σ以及加密數(shù)據(jù)庫EDB，其中，σ存儲在客戶端，EDB 上傳到云服務(wù)器。

(Γ,⊥)←Search(s,σ;EDB)。對于狀態(tài)σ，客戶端發(fā)出搜索請求s，與擁有加密數(shù)據(jù)庫的服務(wù)器進(jìn)行交互。執(zhí)行協(xié)議結(jié)束后，客戶端輸出一個匹配搜索請求s的文件標(biāo)識符的集合Γ，服務(wù)器不輸出任何內(nèi)容。

(σ′,EDB′)←Update(σ,op,in;EDB)。對于狀態(tài)σ，操作op∈{add,del}，集合in=(f,w)是文件/關(guān)鍵字對，客戶端向擁有加密數(shù)據(jù)庫的服務(wù)器發(fā)出添加或刪除in 中文件/關(guān)鍵字對的請求。協(xié)議結(jié)束后，返回給客戶端新的狀態(tài)σ′，并更新服務(wù)器的加密數(shù)據(jù)庫為EDB′。

2.3 DSSE 方案安全模型

給定一個2.2 節(jié)定義的DSSE 方案，本文將定義現(xiàn)實博弈REAL 和理想博弈IDEAL 并給出其安全模型，REAL 反映了原始的DSSE 方案的行為，IDEAL反映了模擬器S的行為，該模擬器將原始的DSSE的泄露作為輸入。對于敵手A，泄露函數(shù)定義為L=(Lstup,Lsrch,Lupdt)，Lstup是在執(zhí)行Setup 算法時A可以學(xué)到的信息，Lsrch是在執(zhí)行Search 協(xié)議時A可以學(xué)到的信息，Lupdt是在執(zhí)行Update 協(xié)議時A可以學(xué)到的信息。概率博弈REAL 和IDEAL 定義如下。首先運行Setup(λ,DB)，得到加密數(shù)據(jù)庫EDB，A發(fā)起一系列搜索查詢q或者是更新查詢(op,in)，最后，A返回實驗結(jié)果b,b∈{0,1}。模擬器S首先執(zhí)行泄露函數(shù)Lstup(λ,DB)，針對A發(fā)起一系列搜索查詢或更新查詢的不同(op,in)，模擬器S分別輸入Lsrch和Lupdt，并將輸出結(jié)果返回給A。最后，A返回實驗結(jié)果b,b∈{0,1}。

定義1機密性。給定一個動態(tài)可搜索加密方案DSSE 和以上規(guī)則，如果對于任意概率多項式的敵手A，存在高效的模擬器 S 和輸入 L 滿足則這種DSSE 方案是L-適應(yīng)性安全的。

2.4 前向安全

前向安全由Stefanov 等[6]提出。前向安全保證了DSSE 方案在更新期間不會泄露新插入的文件與之前的搜索查詢匹配的信息，前向安全的正式定義[7]如下。

定義2前向安全。如果一種L-適應(yīng)安全的DSSE方案是前向安全的，那么存在一個無狀態(tài)的函數(shù)L′，其更新的泄露函數(shù)Lupdt為

其中，{(fi, μi)}是與更新文件fi的修改關(guān)鍵字?jǐn)?shù)量μi配對的修改文件集。

本文中，泄露函數(shù)為Lupdt(op,{(W,bsw),(f,bsf)})=L′(op, bsw,bsf), 其中，W和f是更新操作關(guān)鍵字和文件集合，bsw和bsf是對應(yīng)的更新索引。

2.5 后向安全

后向安全由Stefanov 等[6]提出。對同一關(guān)鍵字的兩次查詢期間，后向安全保證不會泄露之前插入且之后刪除的文件的信息。Bost[10]定義了3 種不同泄露程度的后向安全：Type-I、Type-II 和Type-III。Zuo 等[16]定義了Type-I-級別的后向安全。后向安全泄露信息對比如表2 所示，其中，√表示泄露相應(yīng)信息，—表示不泄露相應(yīng)信息。

表2 后向安全泄露信息對比

例如，發(fā)生以下一組操作序列，順序為{1,search,w},{2,add,(w,f1)},{3,add,(w,f2)},{4,add,(w,f3)},{5,delete,(w,f1)},{6,search,w}，Type-I 后向安全會泄露當(dāng)前匹配關(guān)鍵字w的文檔有f2和f3，分別在時間3 和時間4 插入，以及發(fā)生在w上的更新一共有4 次；Type-II 額外泄露w的更新發(fā)生在時間2～時間5；Type-III 額外泄露w在時間2 的插入在時間5 被刪除。而Type-I-后向安全僅泄露一共有4 次更新，分別發(fā)生在時間2～時間5。

本文中基于動態(tài)填充算法的BPC-DSSE方案采用基于位圖索引的技術(shù)，添加和刪除使用同一個模塊，所以不會泄露文件插入時間；并且查詢結(jié)果返回位串，隱藏了訪問模式。綜上，BPC-DSSE 方案僅泄露更新次數(shù)以及更新時間，實現(xiàn)了Type-I-后向安全。

為了正式定義Type-I-，對于搜索查詢列表Q，本文定義了搜索模式sp(w)={t:(t,w)∈Q}，其中t為時間戳。該搜索模式會泄露對關(guān)鍵字w的搜索查詢重復(fù)的次數(shù)。本文還定義了新的泄露函數(shù)TimePDB，對于一個關(guān)鍵字w，TimePDB(w)存儲了關(guān)鍵字w所有更新時間t的列表。對于更新查詢Q＇，有

定義3后向安全。對于一個L-適應(yīng)性安全的DSSE 方案，如果存在2 個無狀態(tài)的函數(shù)L′和L′′，使搜索和更新的泄露函數(shù)可以寫為

則稱這種DSSE 方案是Type-I-后向安全的。

3 BPC-DSSE 方案

本節(jié)給出了BPC-DSSE 的方案設(shè)計。首先介紹了方案的設(shè)計理念，然后給出了方案涉及的詳細(xì)步驟。

3.1 設(shè)計理念

BPC-DSSE 方案是具有前向安全和Type-I-后向安全的連接關(guān)鍵字DSSE 方案，主要思想是基于位圖索引[16]構(gòu)建雙向索引結(jié)構(gòu)，利用基于同態(tài)加法的對稱加密[17]對索引進(jìn)行加密，并通過基于內(nèi)積的匹配算法[23]實現(xiàn)連接關(guān)鍵字查詢。

更新操作。構(gòu)建索引采用位圖索引，索引結(jié)構(gòu)及其運算規(guī)則如圖1 所示。假設(shè)數(shù)據(jù)庫文件數(shù)量最大為n，關(guān)鍵字空間W的每個關(guān)鍵字都維持一個n位的比特串，用來表示文件是否包含此關(guān)鍵字，如果包含則將相應(yīng)位置設(shè)置為1，否則設(shè)置為0。對倒排索引以相同的方式進(jìn)行處理，為每個文件維持一個|W|大小的比特串。如圖1(a)所示，數(shù)據(jù)庫的文件最大數(shù)量為6，關(guān)鍵字空間大小為4，即n=6，|W|=4，對應(yīng)的比特串(000100)2以及(0010)2表示(w1,f2)存在。下面以關(guān)鍵字索引演示位圖索引的計算規(guī)則，文件索引計算規(guī)則相同。如圖1(b)所示，如果添加文件f3，需要生成比特串(001000)2，并將其加到初始比特串(000100)2上，得到結(jié)果(001100)2。如圖1(c)所示，如果刪除文件f2，需要生成比特串-(000100)2=(111100)2mod26并加到初始比特串(000100)2上，得到結(jié)果(000000)2。

圖1 索引結(jié)構(gòu)及其運算規(guī)則

連接關(guān)鍵字查詢實現(xiàn)。其主要思想是采用正排索引和倒排索引結(jié)合，利用位圖索引實現(xiàn)高效的連接關(guān)鍵字查詢。首先，搜索頻率最低的關(guān)鍵字w1得到相應(yīng)倒排索引的位串，將其解密后得到與w1匹配的文件標(biāo)識符。然后，根據(jù)文件標(biāo)識符獲取相應(yīng)的正排索引對應(yīng)的位串。最后，利用基于內(nèi)積的匹配思想將位串解密并計算與查詢位串的內(nèi)積，通過內(nèi)積結(jié)果過濾得到最終的結(jié)果集合。

方案主要步驟如圖2 所示，以明文形式進(jìn)行說明。此時的索引結(jié)構(gòu)如左上角位圖索引所示，關(guān)鍵字空間大小為6，文件數(shù)量為8。查詢關(guān)鍵字w0、w1和w5，即q=(100011)2。首先，訪問倒排索引得到頻率最低的關(guān)鍵字w0對應(yīng)的位串為(10101010)2，解密后得到包含關(guān)鍵字w0的文件標(biāo)識符集合為f={f1,f3,f5,f7}，訪問正排索引獲取f中文件對應(yīng)的位串分別為(100111)2、(111010)2、(100111)2、(101011)2，將其分別與查詢位串q內(nèi)積，并將內(nèi)積結(jié)果與查詢關(guān)鍵字的個數(shù)（此例為3）進(jìn)行比較，將比較結(jié)果相同的文件標(biāo)識符加入結(jié)果集合，得到最終結(jié)果集合result={f1,f5,f7}。

3.2 方案涉及的詳細(xì)步驟

在詳細(xì)介紹算法之前，首先給出具有加法同態(tài)性質(zhì)的對稱加密算法[14]，主要由以下4 種算法組成。

初始化Setup(1λ)。其輸入為安全參數(shù)λ，輸出為公共參數(shù)消息空間N。如果一種方案可以支持的最大文件數(shù)量為n，那么消息空間N=2n。

加密算法Enc(m,sk,N)。其輸入為明文消息m、隨機的安全密鑰sk 以及公共參數(shù)N，輸出為加密后的密文c。其中，0≤m＜N，0≤sk＜N，密文c=sk+m (mod N)。

解密算法Dec(c,sk,N)。其輸入為密文c、隨機的安全密鑰sk 以及公共參數(shù)N，輸出為解密后的明文m。其中，明文m=c-sk (mod N)。

同態(tài)加法Add(c1,c2,N)。其輸入為2 個密文c1和c2以及公共參數(shù)N，輸出為2 個密文c1和c2之和c。對于密文c1=Enc(m1,sk1,N)，c2=Enc(m2,sk2,N)，c=c1+c2=Enc(m1+m2,sk1+ sk2,N)。

BPC-DSSE 方案由一種算法 Setup 和2 個協(xié)議Update 和Search 組成。

Setup 算法如算法1 所示?？蛻舳耸紫瘸跏蓟? 個空映射Mw和Mf，分別存儲關(guān)鍵字w對應(yīng)的bsw和文件f對應(yīng)的bsf，然后初始化2 個空的映射CTw用來存儲當(dāng)前搜索令牌STcw以及每個關(guān)鍵字更新次數(shù)cw，CTf用來存儲當(dāng)前搜索令牌STcf以及每個關(guān)鍵字更新次數(shù)cf。最后計算EDB←{Mw,Mf}，將EDB 以及狀態(tài)σ發(fā)送給服務(wù)器。

算法1BPC-DSSE Setup(1λ,DB)

輸入安全參數(shù)λ，數(shù)據(jù)庫DB

輸出EDB，狀態(tài)σ=(nw,nf, K, CTw, CTf)

圖2 方案主要步驟

Update 算法如算法2 所示?？蛻舳烁鶕?jù)更新的(w,id)生成對應(yīng)的位串bsw和bsf，將其加密后得到加密位串Ew 和Ef。首先訪問CTw得到關(guān)鍵字w對應(yīng)的搜索令牌STcw和更新次數(shù)cw，并訪問CTf得到文件f對應(yīng)的搜索令牌STcf和更新次數(shù)cf，接下來生成密鑰。如果數(shù)據(jù)庫為空，則初始化搜索令牌STcw、STcf和更新次數(shù)cw、cf。用哈希函數(shù)H1生成更新令牌UW 和UF 來更新服務(wù)器端的EDB，并用H2混淆之前的搜索令牌，用哈希函數(shù)H3生成一次密鑰skcw和skcf。將UW、UF、Ew、Ef 和混淆后的搜索令牌C發(fā)送給服務(wù)器，并且更新CT 得到新的狀態(tài)σ′。服務(wù)器更新映射對應(yīng)的位串，并加到原始位串上。

算法2BPC-DSSE Update(w,f,bsw,bsf,σ;EDB)

輸入關(guān)鍵字w和文件f，對應(yīng)的更新位串bsw和bsf，狀態(tài)σ

輸出更新后的加密數(shù)據(jù)庫EDB′

客戶端

Search 算法如算法3 所示?？蛻舳耸紫雀鶕?jù)頻率最低的w1生成搜索令牌并發(fā)送給服務(wù)器。服務(wù)器訪問Mw得到加密位串bsw，并返回客戶端。客戶端解密得到對應(yīng)文件id，并發(fā)送給服務(wù)器。服務(wù)器訪問Mf得到對應(yīng)的位串，將其逐一與查詢位串內(nèi)積，并將內(nèi)積結(jié)果和查詢關(guān)鍵字的個數(shù)相同的文件id加入結(jié)果集合。

算法3BPC-DSSE Search(q,σ;EDB)

輸入查詢連接關(guān)鍵字q=w1∧w2∧…∧wk，狀態(tài)σ

輸出結(jié)果集合result

客戶端

4 安全性分析

本節(jié)給出BPC-DSSE 的安全分析。

4.1 前向安全

BPC-DSSE 是前向安全的。在更新期間，使用3 個哈希函數(shù)，H1通過隨機選取的密鑰來生成更新令牌UW 和UF，由于加上計數(shù)c，每個更新令牌都是不相同的；H2通過新生成的搜索令牌和密鑰將之前的搜索令牌進(jìn)行更新，如果擁有之前的搜索令牌，就可以通過哈希函數(shù)計算得到之后的搜索令牌，而擁有最新的搜索令牌卻無法得知之前的搜索令牌，保證了前向安全性；H3用來生成一次性密鑰。綜上所述，BPC-DSSE 是前向安全的。

4.2 后向安全

BPC-DSSE 是Type-I-后向安全的。由于使用位圖索引，并且添加和刪除操作只需要一個模加法運算，因此不會泄露插入時間以及文件被插入后刪除對應(yīng)的插入和刪除時間；同時由于F的偽隨機性，每次更新時都包含了不同的輸入，對于兩次查詢期間添加隨后又刪除的文件，服務(wù)器是無法學(xué)習(xí)到其相關(guān)信息的。綜上所述，BPC-DSSE 是Type-I-后向安全的。

定理1BPC-DSSE 的前向安全和Type-I-后向安全。F 是安全的偽隨機函數(shù)，RO1、RO2和RO3是隨機預(yù)言機。定義泄露函數(shù)LBPC-DSSE=(Lsrch,Lupdt)，如果泄露函數(shù)Lsrch(w)=(sp(w),rp(w),Time(w))，Lupdt(op,(w,bsw),(f,bsf))=⊥，那么BPC-DSSE 是LBPC-DSSE-適應(yīng)前向安全和Type-I-后向安全的。

證明與Chamani 等[12]類似，從現(xiàn)實博弈REAL和理想博弈IDEAL 之間構(gòu)造了一系列博弈Game，連續(xù)2 個Game 之間存在細(xì)微的不同，但不可區(qū)分，從而得到REAL 與IDEAL 不可區(qū)分的結(jié)論。最后，用定理1 中定義的泄露函數(shù)模擬了IDEAL。

GameG0。G0和現(xiàn)實博弈完全一樣。

GameG1。G1與G0相同，除了不使用F生成關(guān)鍵字w的密鑰，而是以相同的概率隨機選擇密鑰，并將密鑰存儲在表Key 中。如果從來沒有搜索過w，則生成w的密鑰并存儲在表中；如果搜索過w，則返回表中關(guān)鍵字w的密鑰。由于偽隨機函數(shù)的安全性，G1與G0是不可區(qū)分的。

GameG2。G2與G1相同，除了在更新過程中，使用隨機預(yù)言機RO1代替H1進(jìn)行運算。對于更新協(xié)議，更新令牌是隨機生成的并被存儲在表UT 中。當(dāng)搜索協(xié)議被調(diào)用時，通過計算RO1(K,ST)生成更新令牌并存儲在表R1中，若(K,ST)已經(jīng)在R1中，則可以直接搜索R1得到結(jié)果。對于同樣的哈希函數(shù)H2和H3，也同樣使用隨機預(yù)言機逐個替換，由于搜索令牌是隨機選取的，并且每次輸入的令牌都是不同的，G2與G1是不可區(qū)分的。

GameG3。G3與G2相同，除了使用長度為n的全0 的位串代替bs。由于具有加法同態(tài)性質(zhì)對稱加密的安全性，G3與G2是不可區(qū)分的。

模擬器。模擬器與G3相同，只是用搜索模式sp(w)代替搜索關(guān)鍵字w來模擬理想博弈。對于更新，在G3中為每次更新選擇了新的隨機字符串。對于搜索，模擬器從當(dāng)前搜索標(biāo)記STc開始，并為之前的搜索標(biāo)記選擇一個隨機字符串。對于關(guān)鍵字w，模擬器使用新的時間戳t′←minsp(w)，然后通過RO2將其嵌入密文C中。此外，模擬器通過RO3將bs 嵌入STc并將所有0 嵌入剩余的搜索標(biāo)記中。因此，G3和模擬器是不可區(qū)分的。另外，模擬器中描述的本質(zhì)上是2.3 節(jié)定義的理想博弈因此是不可區(qū)分的。綜上與G0是不可區(qū)分的，即是不可區(qū)分的。

5 仿真分析

本節(jié)主要對BPC-DSSE 方案的查詢、更新復(fù)雜度和存儲開銷進(jìn)行分析，并給出仿真結(jié)果。BPC-DSSE 方案與已有前向安全和后向安全的動態(tài)可搜索加密方案（包含單關(guān)鍵字查詢以及連接關(guān)鍵字查詢）的性能對比如表3 所示，其中，N為關(guān)鍵字/文件標(biāo)識符對數(shù)，nw為包含關(guān)鍵字w的文檔數(shù)量，dw為關(guān)鍵字w被刪除的條目數(shù)，aw為關(guān)鍵字w的更新次數(shù)，|w|為關(guān)鍵字的總數(shù)，|D|為文件總數(shù)，? 符號隱藏了多對數(shù)因子。連接關(guān)鍵字中，n為連接關(guān)鍵字查詢的關(guān)鍵字個數(shù)，w1為其中頻率最小的關(guān)鍵字，|Upd(w1)|為包含w1的文件的數(shù)量更新操作，HT 為樹的高度。經(jīng)對比分析可以發(fā)現(xiàn)，實現(xiàn)連接關(guān)鍵字的方案中，VBTree[20]沒有實現(xiàn)后向安全性，F(xiàn)BDSSE-CQ[21]實現(xiàn)了Type-C 的后向安全性，ODXT[22]只實現(xiàn)了Type-II 的后向安全性，因此，BPC-DSSE 方案實現(xiàn)了更強的后向安全性。

5.1 計算開銷

在查詢階段，第一次交互服務(wù)器需要計算關(guān)鍵字w1對應(yīng)的位串并返回，時間復(fù)雜度為O(|Upt(w1)|)，客戶端需要計算出文件對應(yīng)的更新令牌，復(fù)雜度相同；接下來服務(wù)器通過文件更新令牌返回文件對應(yīng)的加密位串，時間復(fù)雜度為O(|Upt(w1)|)，客戶端解密出文件的位串，并與查詢位串進(jìn)行內(nèi)積，時間復(fù)雜度為O(|Upt(w1)|)，綜上，查詢過程時間復(fù)雜度為O(|Upt(w1)|)。在更新階段，客戶端服務(wù)器只需要固定地進(jìn)行搜索令牌更新以及更新令牌生成操作，時間復(fù)雜度為O(1)。

5.2 存儲開銷

在客戶端，存放狀態(tài)σ，由于需要找到最小頻率的關(guān)鍵字，因此造成的客戶端的存儲開銷為O(1)。在服務(wù)器端，由于需要存儲雙向映射Mw和Mf，因此服務(wù)器端存儲開銷為O(max(|w|,|D|))，其中max(|w|,|D|)為文件數(shù)量和關(guān)鍵字?jǐn)?shù)量中的最大值。

5.3 性能對比

本節(jié)給出BPC-DSSE方案經(jīng)過一系列測試后的性能評估。本文方案采用擁有AMD Ryzen 7 4800U with Radeon Graphics 1.8 GHz 的處理器配置了Windows 10(64 位)系統(tǒng)的機器，支持16 GB RAM，使用Java 語言編程實現(xiàn)。實驗采用的是安然電子郵件（Enron）數(shù)據(jù)集，包括50 萬個不同的文件，將其解析為本文設(shè)計的雙向索引結(jié)構(gòu)，在索引中提取190 萬個不同的關(guān)鍵字。對于本文方案，將文件的最大數(shù)量設(shè)置為50 萬。在實驗過程中，多次調(diào)整文件更新次數(shù)以及查詢連接關(guān)鍵字的個數(shù)進(jìn)行實驗，以此模擬不同的情境下本文方案的性能。

首先，測試更新性能。選用實現(xiàn)連接關(guān)鍵字的方案中效率較高的VBTree 方案[20]以及同樣使用位圖索引實現(xiàn)連接關(guān)鍵字的FBDSSE-CQ 方案[21]來進(jìn)行對比。通過變換更新次數(shù)來測試更新時間受更新次數(shù)的影響，根據(jù)現(xiàn)有論文對比實驗的設(shè)計，將更新次數(shù)設(shè)置為10～50 次，測試結(jié)果如圖3 所示。由于位圖索引簡化了更新操作并且方案基于雙向索引結(jié)構(gòu)，因此BPC-DSSE 的更新時間比VBTree 以及FBDSSE-CQ更短。由此可見，BPC-DSSE 實現(xiàn)了更好的更新性能。

表3 不同方案的性能對比

圖3 更新時間受更新次數(shù)的影響

接下來，測試查詢性能。查詢性能主要從兩方面來考察：一方面是關(guān)鍵字頻率最低的w1的更新次數(shù)對查詢時間的影響；另一方面是查詢關(guān)鍵字個數(shù)對查詢時間的影響。

圖4 查詢時間受w1 的更新次數(shù)的影響

對于第二方面，對比方案 VBTree[20]和FBDSSE-CQ[21]分別測試了3 個和5 個關(guān)鍵字的實驗結(jié)果，由于5 個關(guān)鍵字已滿足實際應(yīng)用的需求，因此本文將查詢的連接關(guān)鍵字個數(shù)設(shè)置為1～5，測試結(jié)果如圖5 所示。當(dāng)查詢關(guān)鍵字個數(shù)為1 時，與FBDSSE-CQ 相比，BPC-DSSE 的搜索時間大約是相比，BPC-DSSE的查詢時間大約是通過表3 的查詢時間復(fù)雜度分析可以看出，F(xiàn)BDSSE-CQ 和VBTree 的查詢時間復(fù)雜度與查詢關(guān)鍵字個數(shù)呈線性相關(guān)，而BPC-DSSE 的查詢時間不受查詢關(guān)鍵字個數(shù)的影響。所以隨著查詢關(guān)鍵字個數(shù)從1 增加到5，F(xiàn)BDSSE-CQ 的查詢時間增長了5 倍，VBTree的查詢時間增加了2 倍，而BPC-DSSE 的查詢時間幾乎不受影響。由此可見，BPC-DSSE 實現(xiàn)了更好的查詢性能。

圖5 查詢時間受查詢關(guān)鍵字個數(shù)的影響

6 結(jié)束語

本文構(gòu)造了一種前向安全和后向安全的連接關(guān)鍵字查詢方案。基于位圖索引設(shè)計了雙向索引，簡化了更新過程，同時防止了訪問模式的泄露，提高了方案的安全性。此外，利用基于內(nèi)積的匹配思想計算連接關(guān)鍵字的查詢結(jié)果，具有更好的查詢性能。安全分析表明，本文方案具有前向安全以及Type-I-的后向安全。仿真結(jié)果表明，本文方案具有更好的更新性能以及查詢性能。