基于雙向索引的高效連接關鍵字查詢動態可搜索加密方案

杜瑞忠，張玉晴，李明月

（1.河北大學網絡空間安全與計算機學院，河北 保定 071000；2.河北省高可信信息系統重點實驗室，河北 保定 071000；3.南開大學計算機學院，天津 300071）

0 引言

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

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

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

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

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

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

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

1 相關工作

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

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

2 DSSE 定義及其安全模型

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

2.1 符號定義

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

表1 主要參數

2.2 DSSE 方案的定義

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

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

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

(Γ,⊥)←Search(s,σ;EDB)。對于狀態σ，客戶端發出搜索請求s，與擁有加密數據庫的服務器進行交互。執行協議結束后，客戶端輸出一個匹配搜索請求s的文件標識符的集合Γ，服務器不輸出任何內容。

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

2.3 DSSE 方案安全模型

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

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

2.4 前向安全

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

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

其中，{(fi, μi)}是與更新文件fi的修改關鍵字數量μi配對的修改文件集。

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

2.5 后向安全

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

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

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

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

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

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

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

3 BPC-DSSE 方案

本節給出了BPC-DSSE 的方案設計。首先介紹了方案的設計理念，然后給出了方案涉及的詳細步驟。

3.1 設計理念

BPC-DSSE 方案是具有前向安全和Type-I-后向安全的連接關鍵字DSSE 方案，主要思想是基于位圖索引[16]構建雙向索引結構，利用基于同態加法的對稱加密[17]對索引進行加密，并通過基于內積的匹配算法[23]實現連接關鍵字查詢。

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

圖1 索引結構及其運算規則

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

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

3.2 方案涉及的詳細步驟

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

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

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

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

同態加法Add(c1,c2,N)。其輸入為2 個密文c1和c2以及公共參數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 個協議Update 和Search 組成。

Setup 算法如算法1 所示。客戶端首先初始化2 個空映射Mw和Mf，分別存儲關鍵字w對應的bsw和文件f對應的bsf，然后初始化2 個空的映射CTw用來存儲當前搜索令牌STcw以及每個關鍵字更新次數cw，CTf用來存儲當前搜索令牌STcf以及每個關鍵字更新次數cf。最后計算EDB←{Mw,Mf}，將EDB 以及狀態σ發送給服務器。

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

輸入安全參數λ，數據庫DB

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

圖2 方案主要步驟

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

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

輸入關鍵字w和文件f，對應的更新位串bsw和bsf，狀態σ

輸出更新后的加密數據庫EDB′

客戶端

Search 算法如算法3 所示。客戶端首先根據頻率最低的w1生成搜索令牌并發送給服務器。服務器訪問Mw得到加密位串bsw，并返回客戶端。客戶端解密得到對應文件id，并發送給服務器。服務器訪問Mf得到對應的位串，將其逐一與查詢位串內積，并將內積結果和查詢關鍵字的個數相同的文件id加入結果集合。

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

輸入查詢連接關鍵字q=w1∧w2∧…∧wk，狀態σ

輸出結果集合result

客戶端

4 安全性分析

本節給出BPC-DSSE 的安全分析。

4.1 前向安全

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

4.2 后向安全

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

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

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

GameG0。G0和現實博弈完全一樣。

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

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

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

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

5 仿真分析

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

5.1 計算開銷

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

5.2 存儲開銷

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

5.3 性能對比

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

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

表3 不同方案的性能對比

圖3 更新時間受更新次數的影響

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

圖4 查詢時間受w1 的更新次數的影響

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

圖5 查詢時間受查詢關鍵字個數的影響

6 結束語

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