一種具有多級安全目標(biāo)的動態(tài)對稱可搜索加密方案

關(guān)鍵詞：動態(tài)對稱可搜索加密；多用戶；搜索模式隱藏；訪問模式隱藏；前后向安全；多級安全目標(biāo)中圖分類號：TP309 文獻標(biāo)志碼：A 文章編號：1001-3695（2025）07-033-2168-08doi：10.19734/j.issn.1001-3695.2024.10.0434

Abstract：Searchable encryption encryptsdata files before storingthemin the cloudand enables retrievaldirectlyover the ciphertext.Dynamic searchableencryptionfacilitates dynamic updates to cloud-storedfiles.Existing dynamic searchable encryptionschemesprimarilyfocusonaddressingforwardandbackwardsecurity，buttheytypicallysupportonlysingle-usersearches andfail to simultaneouslyprotect searchandaccesspaterns.Inresponse tothese limitations，this paper proposed adynamic symmetric searchable encryption scheme，TS-MDSSE，basedonoblivious key-value store （OKVS）technology.The scheme achieved forward security while hiding both search andaccesspatterns，meeting three security goals.Building on this，it enhanced theupdatealgorithm byemploying randomvaluesubstitution，achieving backward securityandintroducing FSMDSSE，which metfoursecuritygoals.Securityanalysisand experiments demonstrate thatthe proposed schemes fulfillmultilevel security requirements，support multi-user queries，and complete a single search in only O.O22 ms.

Key words：dynamic symmetric searchable encryption；multi-user;search patern privacy；access pattern privacy；forward andbackward security；multilevel securityobjective

0 引言

隨著云計算技術(shù)的廣泛應(yīng)用，個人和企業(yè)為了減輕存儲壓力，將大量的數(shù)據(jù)通過數(shù)據(jù)外包服務(wù)存儲到云服務(wù)器上[1]。但是，由于一些領(lǐng)域（如電子醫(yī)療系統(tǒng)、位置實時上傳記錄系統(tǒng)）的數(shù)據(jù)涉及隱私敏感信息，所以要將數(shù)據(jù)進行加密后上傳，但加密后導(dǎo)致數(shù)據(jù)使用者很難通過搜索查詢到符合要求的文檔（例如返回所有包含關(guān)鍵詞 w 的文檔）。因此，如何對加密數(shù)據(jù)進行搜索成為一個亟待決解的問題。

2000年，Song等人[2提出了第一個對稱可搜索加密方案（symmetricsearchableencryption，SSE）。該方案既能實現(xiàn)對用戶數(shù)據(jù)的隱私保護，又能對密文外包數(shù)據(jù)進行關(guān)鍵詞搜索。Curtmola等人[3]提出了一種更高效的SSE方案，實現(xiàn)固定計算量的同時實現(xiàn)了多用戶搜索。2012年，Kamara等人[4提出了動態(tài)對稱可搜索加密（dynamic symmetric searchable encryption，DSSE），允許數(shù)據(jù)擁有者對服務(wù)器上的加密數(shù)據(jù)進行搜索和動態(tài)更新。其沒有考慮到更新操作會出現(xiàn)的信息泄露問題，于是Stefanov等人首次提出了前向安全和后向安全。前向安全可以確保未來的更新不會與以前的搜索相關(guān)聯(lián)，即使用舊的搜索陷門也不能獲取新更新的相關(guān)信息；后向安全保證后續(xù)的搜索不會與過去刪除的文檔相關(guān)聯(lián)，即刪除更新操作之后的搜索請求不會獲取已經(jīng)刪除的文檔信息。

Bost等人[通過穿刺加密提出了第一個非交互的后向安全可搜索加密方案Janus，但是該方案計算和通信開銷較大。Sun等人使用對稱穿刺加密的變體實現(xiàn)具有Ⅲ型后向安全的非交互DSSE方案。該方案能夠在客戶進行刪除操作時將部分穿刺密鑰外包給服務(wù)器，實現(xiàn)以低存儲需求且不變的情況下逐步刪除數(shù)據(jù)。Song等人[8基于緩存機制提出了具有前向安全的Fastio方案，使用單鏈表數(shù)據(jù)結(jié)構(gòu)，通過臨時密鑰加密生成新的狀態(tài)，給定當(dāng)前密鑰和當(dāng)前狀態(tài)，服務(wù)器可以通過解密計算之前的狀態(tài)，從而實現(xiàn)了前向安全。He等人[基于魚骨鏈構(gòu)造前向和后向安全的DSSE方案。該方案將客戶端存儲減少至常數(shù)級別，但是引入了更新次數(shù)的限制，實用性有限。Zuo 等人[10]提出并實現(xiàn)前向和I-型后向安全的FB-DSSE，通過位圖索引的同態(tài)運算實現(xiàn)動態(tài)更新。Chen等人[1]基于緩存機制提出具有前向和后向安全的DSSE方案Bestie，將緩存機制應(yīng)用在后向安全的方案中，提升刪除操作的性能。

可以注意到，以上DSSE方案都是為單用戶搜索設(shè)計的，即上傳數(shù)據(jù)的用戶和搜索數(shù)據(jù)的用戶是同一個，但在實踐應(yīng)用中，支持多用戶搜索的DSSE是一個重要的研究方向。具體來說，數(shù)據(jù)擁有者將數(shù)據(jù)外包給云服務(wù)器，然后將密鑰信息授權(quán)給數(shù)據(jù)使用者，這樣授權(quán)用戶可以通過云服務(wù)器執(zhí)行所需的搜索操作。本文的兩個方案均可以滿足多用戶搜索，這與目前動態(tài)可搜索加密方案中主要關(guān)注單用戶搜索的工作形成對比。

現(xiàn)有的DSSE在實現(xiàn)前向和后向安全上已經(jīng)有了很大進展，但大多忽略了搜索模式和訪問模式的安全屬性，以搜索模式和訪問模式泄露為代價來提高搜索效率。通過利用搜索模式，云服務(wù)器可以從用戶的搜索習(xí)慣中推斷出關(guān)鍵詞[12]。利用訪問模式的信息泄露，敵手可以利用少量的文檔先驗知識獲取大量的敏感信息[13]

針對可搜索加密方案中的搜索模式和訪問模式泄露問題，孫曉玲等人[14]利用哈希鏈表構(gòu)建三個索引表構(gòu)造了高效的動態(tài)可搜索加密方案，提高了更新效率且不會泄露訪問模式外的其他信息。鄭東等人[15]提出了一個支持用戶檢索權(quán)限撤銷的公鑰動態(tài)可搜索加密方案。該方案將系統(tǒng)的生命周期進行劃分，保證了前向安全性，但忽略了搜索模式和訪問模式問題。Zheng等人[16利用 k -匿名加密設(shè)計了一種模糊處理技術(shù)支持單關(guān)鍵詞查詢，實現(xiàn)搜索模式隱藏和前后向安全的DSSE方案。此DSSE方案未實現(xiàn)訪問模式隱藏，仍存在安全問題，且每次操作之后都需要重建索引表，通信開銷較大。Wang等人[17]利用加性同態(tài)加密技術(shù)，提出了具有搜索模式和訪問模式安全的SSE方案。但該方案搜索令牌的大小與總關(guān)鍵詞的數(shù)量成線性關(guān)系，計算開銷較大、搜索效率較低。Yang等人[18]提出了第一個基于安全多方計算技術(shù)實現(xiàn)搜索模式和訪問模式隱藏的可搜索加密方案IXT。文獻[17，18]雖均可以同時保護搜索模式和訪問模式，但都不支持?jǐn)?shù)據(jù)擁有者動態(tài)更新加密數(shù)據(jù)庫。以上搜索方案均未同時滿足搜索模式和訪問模式安全，以及前向和后向安全。針對上述問題，本文定義了多級安全目標(biāo)結(jié)構(gòu)，提出了一個具有多級安全目標(biāo)的多用戶動態(tài)可搜索加密方案，主要貢獻如下：

a）設(shè)計了一個滿足三級安全目標(biāo)的多用戶動態(tài)對稱可搜索加密方案TS-MDSSE。采用不經(jīng)意鍵值對編碼技術(shù)和偽隨機函數(shù)，對服務(wù)器端的加密反向索引進行編碼，在搜索階段由數(shù)據(jù)使用者進行解碼獲得匹配文檔標(biāo)識符信息，從而同時實現(xiàn)前向安全、保護搜索模式和訪問模式，完成對關(guān)鍵詞信息的隱藏。

b）提出了第一個滿足四級安全目標(biāo)的FS-MDSSE方案。在TS-MDSSE的基礎(chǔ)上，對需要更新的關(guān)鍵詞索引密文采用隨機值覆蓋技術(shù)，從而使搜索查詢無法鏈接到更新前的文檔，進一步使方案具有后向安全性。

c）對所提方案進行了安全分析與性能分析，結(jié)果表明TS-MDSSE滿足搜索模式與訪問模式隱藏，以及前向安全，達到了三級安全目標(biāo)；FS-MDSSE滿足前向和后向安全，以及搜索模式與訪問模式隱藏，達到了四級安全目標(biāo)，且FS-MDSSE在總搜索時間方面優(yōu)于文獻[10，16，17，19，20]。

1預(yù)備知識

本章使用的符號如表1所示。

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

動態(tài)對稱可搜索加密方案由一個初始化算法setup與兩個交互式協(xié)議search和update組成，以下是DSSE方案的形式化定義。

setup（λ，DB）?（k，σ，EDB） ：索引建立階段。數(shù)據(jù)擁有者輸入一個明文數(shù)據(jù)庫 DB 和一個安全參數(shù) λ ，輸出數(shù)據(jù)擁有者的加密密鑰 k 、本地狀態(tài) σ 以及加密數(shù)據(jù)庫 EDB_?（ 0

search（w，k，σ;EDB）?DB（w） ：搜索協(xié)議。數(shù)據(jù)使用者輸入密鑰 k 關(guān)鍵詞 w 以及本地狀態(tài) σ ；服務(wù)器輸入密文數(shù)據(jù)庫EDB 。搜索協(xié)議結(jié)束后，數(shù)據(jù)使用者輸出關(guān)鍵詞 w 的搜索結(jié)果集合 DB（w） 。

updat te（w，k，op，id，σ;EDB）?（EDB^′，σ^′） ：更新協(xié)議。數(shù)據(jù)擁有者輸入關(guān)鍵詞 w 、密鑰 k 、更新操作符 op 、一個文檔標(biāo)識符 id 以及本地狀態(tài) σ ;服務(wù)器輸入密文數(shù)據(jù)庫 EDB 。其中，更新操作符 op 從集合 {add，del} 中選擇，即數(shù)據(jù)擁有者執(zhí)行增加或刪除鍵值對的操作。更新協(xié)議之后，數(shù)據(jù)擁有者更新狀態(tài) σ 為 σ^′ ，云服務(wù)器更新密文數(shù)據(jù)庫 EDB 為 EDB^′ 。

1.2 偽隨機函數(shù)

偽隨機函數(shù)（pseudorandomfunction，PRF）是一種隨機加密函數(shù) 是一個偽隨機函數(shù)，它產(chǎn)生的隨機數(shù)與真正隨機生成的序列是無法區(qū)分的，即 f 是 {0，1}^l {0，1}^l′ 的一個真隨機函數(shù)， ε 是可忽略的概率，對于任意概率多項式時間的敵手 A 都滿足： 1]∣?ε 。

1.3偽隨機生成器

定義1讓 G：X?Y 表示為一個偽隨機生成器（pseudoran-domgenerator，PRG），使用一個隨機種子 x∈X，G 能生成一個長隨機數(shù) G（x）∈Y 對于任意概率多項式時間敵手 A ，很難將G（x） 從一個隨機數(shù) x^′ 區(qū)分開來， x^′ 具有與 G（x） 相同的長度，即 I是可以忽略的。

1.4不經(jīng)意鍵值對存儲

不經(jīng)意鍵值對存儲（obliviouskey-valuestore，OKVS）[21]由encode和decode兩個算法組成，encode是將一列鍵值對（ k_i ，v_i. ）作為輸入，并返回一個抽象的數(shù)據(jù)結(jié)構(gòu) P 。解碼時decode以 P 和密鑰 k_i 作為輸人，則輸出對應(yīng)的 v_i ，否則輸出隨機值。

鍵值對存儲（KVS）可以形式化為由一組 k_i 組成的集合 K_? 一組 v_i 組成的集合 V 和一組函數(shù) H ，并由兩種算法組成。

encode_H（K，V）?P ：輸入由集合 K 和 V 組成的鍵值對集（k_i，v_i） ，輸出一個數(shù)據(jù)結(jié)構(gòu) P 。在統(tǒng)計上很小概率的情況下，輸出指示符“ ⊥ ”，即編碼失敗。

decode_H（P，k）?v ：輸入是一個數(shù)據(jù)結(jié)構(gòu) P 和一個鍵值 k 如果 k∈K ，則輸出對應(yīng)的 v∈V ，否則是一個隨機的值 。

本文采用文獻[22]的方法來實例化OKVS。輸人一組鍵值對 {（k₁，v₁），…，（k_n，v_n）} ，算法首先基于 k₁，…，k_n 構(gòu)造出一個矩陣 ^T，T 的第 i 行與 k_i 對應(yīng)。然后解出一個數(shù)據(jù)結(jié)構(gòu) P ，使得 TP=（v₁，…，v_n） ，通過將 T 轉(zhuǎn)換為下三角形式求解 P ，然后使用標(biāo)準(zhǔn)的反向傳播算法來計算 P ，最終獲得編碼結(jié)果 P 。對矩陣 T 轉(zhuǎn)換方法，文中進行了優(yōu)化，關(guān)于OKVS的更多細節(jié)可以參考文獻[20]中的第2節(jié)。

2 系統(tǒng)目標(biāo)和模型

2.1 安全目標(biāo)

現(xiàn)有的數(shù)據(jù)庫模型分為靜態(tài)數(shù)據(jù)庫和動態(tài)數(shù)據(jù)庫，區(qū)別在于使用過程中是否對數(shù)據(jù)庫進行修改。在可搜索加密中，靜態(tài)數(shù)據(jù)庫每個關(guān)鍵詞的搜索陷門固定，敵手可以通過分析搜索請求的模式和頻率，進而造成搜索模式和訪問模式的泄露；而對于動態(tài)數(shù)據(jù)庫，不僅存在相同問題，而且如果不及時更新搜索陷門，將會導(dǎo)致用戶使用舊的搜索陷門獲取新的匹配信息，或者解密之前的密文，這將導(dǎo)致前向安全和后向安全問題。

針對動態(tài)可搜索加密中的安全問題，按照方案可以保證的安全由弱到強程度，定義了四個級別的安全目標(biāo)結(jié)構(gòu)。隨著安全目標(biāo)等級的提高，包含的安全問題逐級增多，如圖1所示。

一級安全目標(biāo)：動態(tài)可搜索加密方案僅滿足前向安全。

定義2前向安全即更新請求不可以和以前的檢索請求產(chǎn)生關(guān)聯(lián)，表示云服務(wù)器不能利用已有的搜索陷門搜索到新更新的文件[5]。前向安全的形式化定義如下：

若一個方案具有前向安全性，則方案中更新操作的泄露函數(shù)滿足

L_update（w_i）=L^′（op，id_j）

其中： L^′ 為無狀態(tài)函數(shù)。

二級安全目標(biāo)：在一級安全目標(biāo)的基礎(chǔ)上，實現(xiàn)搜索模式或者訪問模式安全。

定義3搜索模式是云服務(wù)器獲取到當(dāng)前搜索操作與之前的搜索操作是否相同，即云服務(wù)器可以通過了解到哪些查詢是針對同一關(guān)鍵詞而推斷出的任何信息[18]。

設(shè)QList為查詢列表，列表元素形式為 （t，w_i） ，表示在時間t 查詢了關(guān)鍵詞 w_i，rid 表示與關(guān)鍵詞 w_i 匹配的所有文檔標(biāo)識符，則關(guān)鍵詞 w_i 的搜索模式為

sp（w_i）={t|（t，w_i）∈QList}

定義4訪問模式是每次搜索查詢的結(jié)果，即云服務(wù)器通過獲取文檔與搜索的匹配關(guān)系而推斷出的任何信息[21]]

則關(guān)鍵詞 w_i 的訪問模式為

若一個可搜索加密方案不具有訪問模式安全，則在搜索階段將會泄露與搜索關(guān)鍵詞匹配的密文 rid 集合信息。

三級安全目標(biāo)：即動態(tài)可搜索加密方案可以同時保護前向安全、搜索模式和訪問模式。

四級安全目標(biāo)：包含四個安全問題，即在三級安全目標(biāo)的基礎(chǔ)上增加任意強度的后向安全，使服務(wù)器無法訪問已經(jīng)刪除的密文信息。

定義5后向安全是被刪除的密文不可以和未來可能的檢索請求產(chǎn)生關(guān)聯(lián)，指對關(guān)鍵詞 w_i 的搜索查詢不能鏈接到包含 w_i 且之前已經(jīng)刪除的文檔[

Bost等人[進一步正式定義了三種強度的后向安全，若一個方案具有后向安全性，則方案中更新操作的泄露函數(shù)L_update 和搜索操作的泄露函數(shù) L_search 需要滿足

I型插入模式的后向安全：泄露與 w_i 匹配的文件和匹配文件的插入時間，以及 w_i 總的更新次數(shù)；

L_update（op，w_i，id）=L^′（op）

L_search（w_i）=L^′′（TimeDB（w_i），N）

I 型更新模式的后向安全：泄露與 w_i 匹配的文件和插入時間，以及 w_i 所有的更新發(fā)生時間；

Ⅲ型弱后向安全：泄露與 w_i 匹配的文件和插入時間，以及 w_i 所有的更新發(fā)生時間，和某個刪除更新取消了某個插入更新。

L_update（op，w_i，id）=L^′（op，w_i）

L_search（w_i）=L^′′（TimeDB（w_i），DelHist（w_i））

其中： L^′?L^′′ 為無狀態(tài)函數(shù)； 表示所有當(dāng)前在數(shù)據(jù)集中的含有關(guān)鍵詞 w_i 的文檔及其插入時間； update（w_i） 表示所有與 w_i 有關(guān)的更新操作的時間戳； DelHist（w_i） 表示關(guān)于 w_i 的插入/刪除對。

I型后向安全：泄露與 w_i 匹配文件 ?_?w_i 的更新總數(shù)和每次更新的時間。 I^- 型泄露的強度介于I和 I 型之間，是由Zuo 等人[10]在2019年進行的定義。

基于上述對安全目標(biāo)等級的定義，設(shè)計一個可以保護搜索模式和訪問模式，以及前向和后向安全的多用戶動態(tài)對稱可搜索加密方案是本文的主要工作。其中，本文FS-MDSSE方案滿足Ⅱ型后向安全。

2.2 系統(tǒng)模型

本文方案的系統(tǒng)模型由數(shù)據(jù)擁有者DO、云服務(wù)器CS和數(shù)據(jù)使用者DU三方組成，如圖2所示。

a）數(shù)據(jù)擁有者。DO使用反向索引結(jié)構(gòu)將每個關(guān)鍵詞 w_i 與對應(yīng)的文檔標(biāo)識符 id_j 匹配，如表2所示。例如關(guān)鍵詞 w₁ 、w₂、w₃ ，反向索引為 DB（w₁）={id₂，id 3， DB（w₂）={id₁，id₃ {d₄，id₅} ， DB（w₃）={id₁，id₅，id₆} 。然后，DO將 w_i 和 id_j 分別進行加密，生成密文反向索引并與加密的文件一起上傳到云服務(wù)器。此外，在支持動態(tài)更新的方案中，DO還負責(zé)給新添加的文件選取關(guān)鍵詞，DO是完全可信的。

b）云服務(wù)器。CS負責(zé)接收DO的加密反向索引表并進行OKVS編碼并存儲。在查詢階段，接收DU的搜索請求，將編碼生成的OKVS數(shù)據(jù)結(jié)構(gòu)發(fā)送給DU；在更新階段，根據(jù)DO發(fā)來的更新信息，更新密文反向索引表并重新編碼。在這個過程中，CS是誠實且好奇的，可能會利用自身的計算能力來分析用戶的隱私信息。

c）數(shù)據(jù)使用者。經(jīng)過授權(quán)的DU向DO發(fā)送要查詢的關(guān)鍵詞，DO會向其發(fā)送相應(yīng)關(guān)鍵詞的計數(shù)器，DU根據(jù)計數(shù)器和關(guān)鍵詞生成搜索陷門，解碼CS發(fā)來的數(shù)據(jù)結(jié)構(gòu)，得到與查詢關(guān)鍵詞匹配的文檔標(biāo)識符，DU是完全可信的。

2.3 安全模型

DSSE的安全性要求敵手盡可能少地了解數(shù)據(jù)庫內(nèi)容和查詢信息。首先定義泄露函數(shù)來表示敵手 A 在系統(tǒng)建立階段、搜索階段及更新階段獲取的泄露信息 L=（L_setup，L_search，L_update） ，并假定敵手 A 獲取的泄露信息只在 L 表示的范圍內(nèi)。

DSSE的安全性由現(xiàn)實模型real和理想模型ideal的不可區(qū)分來定義。在現(xiàn)實模型real中，敵手 A 運行真實方案中的setup（λ） 來初始化系統(tǒng)，隨后 setup（λ） 執(zhí)行更新問詢或搜索問詢來獲取信息。在理想模型ideal中，模擬器S輸入setup（入），隨后敵手 A 進行更新問詢或搜索問詢，模擬器S通過相應(yīng)的泄露函數(shù) L_update（op，w_i，id_j） 或 L_search（w_i） 來回復(fù)敵手 A 。

定義6若存在一個模擬器S，使得對于任意概率多項式時間敵手 A ，都有

IPr[real_A（λ）=1]-Pr[ideal_A，S（λ）=1]∣?v（λ）

則稱該動態(tài)對稱可搜索加密方案是 L 自適應(yīng)安全的，其中 v（λ） 是可忽略函數(shù)。

3方案設(shè)計

本章給出了滿足前向安全、搜索模式和訪問模式隱藏的TS-MDSSE方案的具體構(gòu)造，并在此基礎(chǔ)上實現(xiàn)后向安全，提出具有四級安全目標(biāo)的FS-MDSSE方案。

在TS-MDSSE和FS-MDSSE中，服務(wù)器利用OKVS數(shù)據(jù)結(jié)構(gòu)對存儲的鍵值對進行編碼，將編碼之后生成的數(shù)據(jù)結(jié)構(gòu) P 發(fā)給數(shù)據(jù)使用者，數(shù)據(jù)使用者計算搜索陷門，使用陷門對 P 解碼，得到搜索關(guān)鍵詞對應(yīng)的文檔標(biāo)識符。利用OKVS編碼，可以將關(guān)鍵詞和對應(yīng)文檔標(biāo)識符的對應(yīng)關(guān)系隱藏，同時每次搜索都只發(fā)送 P 給數(shù)據(jù)使用者，并不泄露搜索陷門信息，服務(wù)器從未獲得過搜索陷門，從而解決DSSE中搜索和訪問模式的泄露問題，以及前向安全。但這一方案并未解決后向安全中泄露已刪除的文檔標(biāo)識符信息的問題，于是改進TS-MDSSE中的更新算法，加入隨機值替換技術(shù)，將刪除信息用隨機值覆蓋，實現(xiàn)具有四級安全目標(biāo)的FS-MDSSE。

3.1 TS-MDSSE方案設(shè)計

3.1.1 系統(tǒng)初始化

setup（λ，DB） ，由DO運行setup 算法。具體地，DO將加密的反向索引表 T 和關(guān)鍵詞對應(yīng)的更新計數(shù)器CountT初始化為空。對于每個關(guān)鍵詞 w_i 都隨機生成一個計數(shù)器 c_wi^update ，用以生成關(guān)鍵詞的加密密鑰，即 。對于每一條數(shù)據(jù)記錄 （w_i，DB（w_i） ），DO將 DB（w_i） 中所有的文檔標(biāo)識符映射為一個 N 比特位長的字符串 B_i 。設(shè)每個文檔標(biāo)識符 id_j 為 χ_t 比特位長，與 w_i 相關(guān)的文檔數(shù)量為 n ，則 χ_t 與 n 滿足關(guān)系：t×n=N， 。如果 w_i 對應(yīng)的 id 較多，即 n 值較大時，與該關(guān)鍵詞匹配的 N 會很大。這種情況下，可以采用切片技術(shù)，將其分解為多個等長的串分別進行存儲。然后，DO 加密 （w_i，B_i） ， addr_wi= 生成映射地址和 B_i 生成文檔標(biāo)識符密文，其中 G 是偽隨機生成器，生成長為 N 的二進制串。按照 T[addr_wi]=val_wi 進行存儲，最后DO將加密數(shù)據(jù)庫 T 發(fā)送給CS，自己本地存儲CountT表。

算法1系統(tǒng)初始化算法 setup（λ，DB） （2號輸入：安全參數(shù) λ 和需要加密的數(shù)據(jù)庫 DB 。

輸出：各關(guān)鍵詞更新計數(shù)器 c_wi^update ，加密數(shù)據(jù)庫 EDB

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

初始化 T 和CountT為空映射表//設(shè)置需要的存儲空間

for w_i∈W do//對于系統(tǒng)中的所有關(guān)鍵詞均勻隨機采樣 c_?i^update //作為關(guān)鍵詞 w_i 的更新計數(shù)器初始值 （204號 （2號 //關(guān)鍵詞 w_i 匹配的文檔標(biāo)識符串（20號 //映射地址（204號 //對 B_i 進行加密T[addr_wi]=val_wi //對應(yīng)在表 T 的存儲關(guān)系CountT[ wi] =c\"pdate //記錄關(guān)鍵詞的更新計數(shù)器

endfor//循環(huán)結(jié)束

將表 T 作為 EDB 發(fā)送至云服務(wù)器//上傳密文信息

3.1.2 編碼階段

encode（ （addr_wi，val_wi）：P） ，由CS運行encode算法。在CS收到由DO發(fā)來的加密數(shù)據(jù)庫之后，不僅要對 （addr_wi，val_wi） 進行存儲，還要對其進行編碼，即 P= encode（ {addr_wi，val_wi} ），其中 P= encode（ {addr_wi，val_wi} ）作為OKVS編碼中的 作為其中的 v_i ，編碼輸出為一個數(shù)據(jù)結(jié)構(gòu) P 。當(dāng)DU發(fā)來搜索請求時，CS即可將 P 作為返回值發(fā)給該DU，然后DU使用搜索陷門對 P 進行解碼，獲得關(guān)鍵詞匹配的文檔標(biāo)識符。

CS通過不經(jīng)意鍵值對編碼，將關(guān)鍵詞和文檔標(biāo)識符匹配關(guān)系 （addr_wi，val_wi） 隱藏于數(shù)據(jù)結(jié)構(gòu) P 中，即使敵手截獲了 P 也無法通過重構(gòu) P 獲得真實編碼信息，因為OKVS編碼的值在隨機的情況下，與其他的隨機值編碼結(jié)果在計算上是不可區(qū)分的，同時DU也不能正確解碼獲得非查詢關(guān)鍵詞的文檔匹配信息。

由CS對反向索引 （addr_wi，val_wi） 進行OKVS編碼，只要未發(fā)生更新操作都可以繼續(xù)使用當(dāng)前的 P 作為搜索請求的返回值，從而可以避免多次搜索時的冗余計算。

3.1.3搜索階段

。數(shù)據(jù)使用者DU要搜索關(guān)鍵詞w_i 時，需要和云服務(wù)器CS交互獲得該關(guān)鍵詞對應(yīng)的文檔 id ，如算法2所示。DU要搜索包含關(guān)鍵詞 w_i 的所有文檔，且搜索中CS無法獲得搜索陷門，從而保護搜索模式和訪問模式。具體步驟如下：DU與CS交互獲得反向索引數(shù)據(jù)的OKVS編碼P，DU 與DO交互獲得要搜索關(guān)鍵詞 w_i 的更新計數(shù)器 c_wi^update 5然后，DU計算 作為搜索陷門，帶入結(jié)構(gòu) P 解碼 ，并計算 $B _ { i } = C v a l ＼oplus G （ F （ { ＼mathfrak { c } } _ { w _ { i } } ^ { ＼mathrm { u p d a t e } } ＼parallel 1 ＼$ $w _ { i } ＼big ，$ ），最后從 B_i 中恢復(fù)與 w_i 對應(yīng)的 id_j 。

由CS對DO上傳的加密反向索引存儲并進行OKVS編碼，對于有搜索請求的DU，CS將編碼得到的數(shù)據(jù)結(jié)構(gòu)發(fā)送給DU，在整個過程中CS未獲得任何搜索陷門，從而隱藏了搜索模式和訪問模式，而且不會出現(xiàn)CS利用陷門信息檢索或解密任何內(nèi)容，因此也滿足前向安全。針對多關(guān)鍵詞查詢，由于de-code可以在任何鍵上調(diào)用，所以DU可以通過向DO一次性申請多個關(guān)鍵詞計數(shù)器值來獲取多個關(guān)鍵詞搜索陷門，并利用數(shù)據(jù)結(jié)構(gòu) P 對所有陷門進行解碼，從而實現(xiàn)多關(guān)鍵詞查詢的功能。

算法2搜索算法

輸入：數(shù)據(jù)使用者輸入搜素關(guān)鍵詞 w_i 和關(guān)鍵詞計數(shù)器 c_wi^update ；云服務(wù)器輸入為密文索引數(shù)據(jù)庫 EDB 。

輸出：匹配的文檔索引字符串 B_i 。

云服務(wù)器：

將 P 發(fā)送至當(dāng)前有搜索請求的數(shù)據(jù)使用者//使授權(quán)用戶進行查詢

數(shù)據(jù)使用者：

DU 從 DO獲取搜索關(guān)鍵詞的計數(shù)器 c_wi^update //DU 使用計數(shù)器計算陷門

//計算搜索陷門

Cval=decode（P，y） //解碼獲得標(biāo)識符密文

）//解密得標(biāo)識符串

從 B_i 中恢復(fù)文檔標(biāo)識符 //DU完成搜索查詢

3.1.4更新階段

update（ c_wi^update （w_i，B_i）;EDB） 。在 DSSE 方案中，由于 DO的數(shù)據(jù)可能會動態(tài)變化，所以需要對CS端的索引表進行更新。更新階段是由DO運行update算法，對加密索引表進行更新，并將更新信息發(fā)送至云服務(wù)器，如算法3所示。

當(dāng)更新了 w_i 和 B_i ，首先對關(guān)鍵詞 w_i 的更新計數(shù)器 c_wi^update 執(zhí)行加1操作，然后按照 setup 中的方法計算一對（addrw，val_wi. ），這是更新關(guān)鍵詞的新映射地址和標(biāo)識符密文，最后僅需要將 （addr_wi，val_wi） 發(fā)給CS，自己本地存儲 w_i 最新的計數(shù)器 c_wi^update O算法3更新算法 update（c_wi^update，（w_i，B_i）;EDB）

輸入：數(shù)據(jù)擁有者輸人關(guān)鍵詞文檔對 （w_i，B_i） 和關(guān)鍵詞計數(shù)器cupdate;；云服務(wù)器輸入為密文索引數(shù)據(jù)庫EDB。

輸出：更新后的密文索引數(shù)據(jù)庫 EDB 。

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

cupdate =cupdate+1//更新關(guān)鍵詞計數(shù)器（20 //更新 w_i 的映射地址（20 //對 B_i 進行異或加密CountT[ wi] =cupdate //更新表中的計數(shù)器發(fā)送 （addr_wi，val_wi） 至云服務(wù)器//完成更新

在TS-MDSSE方案中，DO僅計算一對更新關(guān)鍵詞的映射地址和存儲密文，CS對更新后的加密反向索引表進行OKVS編碼，并將編碼結(jié)果 P 作為搜索請求的返回值發(fā)送給DU，從而使CS在搜索和更新過程中始終沒有獲得搜索關(guān)鍵詞的陷門，所以CS無法與之前的搜索操作聯(lián)系起來，進而保證方案的搜索模式及訪問模式隱藏和前向安全，實現(xiàn)三級安全目標(biāo)。

3.2 FS-MDSSE方案設(shè)計

TS-MDSSE方案可以隱藏搜索模式和訪問模式，并在動態(tài)更新時實現(xiàn)前向安全，滿足了三級安全目標(biāo)。但是當(dāng)數(shù)據(jù)使用者在搜索時，搜索結(jié)果中可能會包含已刪除的文檔標(biāo)識符，從而造成信息泄露。因此，在TS-MDSSE方案的基礎(chǔ)上，設(shè)計了滿足四級安全目標(biāo)的FS-MDSSE方案，即不僅可以實現(xiàn)搜索模式和訪問模式隱藏，還具備前向安全和后向安全。FS-MDSSE方案中的系統(tǒng)初始化、編碼和搜索與TS-MDSSE方案一致，不同的是update操作，更新過程具體如算法4所示。在每次對關(guān)鍵詞 w_i 進行更新時，都用一個變量ustore記下先前關(guān)鍵詞 w_i 的映射地址，然后更新計數(shù)器 c_wi^update 的值，使用更新后計數(shù)器的值計算關(guān)鍵詞 w_i 新的映射地址和 B_i 密文，之后存儲一個 N 位長的隨機值到wstore，并與新生成的 （addr_wi，val_wi） 一起發(fā)送給CS，保證CS上的密文具有時效性。因為使用隨機值對關(guān)鍵詞更新前的 B_i 進行了覆蓋，所以DU就無法用舊的搜索陷門解碼獲得之前的文檔匹配信息，從而實現(xiàn)了后向安全。

算法4更新算法 update（c_wi^update，（w_i，B_i）;EDB） （20

輸入：數(shù)據(jù)擁有者輸入關(guān)鍵詞文檔對 （w_i，B_i） 和關(guān)鍵詞計數(shù)器c_wi^update ;云服務(wù)器輸人為密文索引數(shù)據(jù)庫 EDB 。

輸出：更新后的密文索引數(shù)據(jù)庫 EDB 。

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

（204號 //記下更新索引映射地址

cupdate=cupdate+1//更新關(guān)鍵詞計數(shù)器

（20 //更新 w_i 的映射地址

//對 B_i 進行異或加密

均勻隨機采樣一個隨機數(shù) R₁ //用來覆蓋舊密文

（204號 //更新表中的計數(shù)器

發(fā)送 （wstore，R₁） 和 （addr_wi，val_wi） 至云服務(wù)器//完成更新

FS-MDSSE方案在TS-MDSSE方案的基礎(chǔ)上對更新算法進行優(yōu)化，加入隨機值替換技術(shù)更新CS端的索引信息，使CS端都是最新時效的密文信息，解決了在關(guān)鍵詞搜索和更新中會出現(xiàn)的后向安全問題，這也是第一個實現(xiàn)四級安全目標(biāo)，即同時具有搜索模式和訪問模式隱藏，以及前向安全和后向安全的多用戶動態(tài)對稱可搜索加密方案。對比兩個方案的更新算法，因為FS-MDSSE中增加了計算更新關(guān)鍵詞的原映射地址和覆蓋所用的隨機值，同時要上傳至云服務(wù)器的信息增加至原來的兩倍，所以FS-MDSSE的計算開銷和通信開銷會比TS-MDSSE略高。因此，綜合考慮性能和安全需求，TS-MDSSE方案適用于插入更新頻繁的場景，例如醫(yī)院的電子醫(yī)療保健系統(tǒng)；FS-MDSSE方案更適用于刪除更新頻繁且不泄露任何刪除信息的場景。

4方案分析與比較

本章分析了TS-MDSSE和FS-MDSSE方案的安全性。具體而言，F(xiàn)S-MDSSE實現(xiàn)了2.1節(jié)描述的四級安全目標(biāo)，即前向安全、搜索模式、訪問模式和后向安全。

4.1 TS-MDSSE的安全性分析

a）前向安全。前向安全是確保更新關(guān)鍵詞不能鏈接到之前搜索的關(guān)鍵詞。在設(shè)置階段，CS接收密文反向索引和加密文件；在更新階段，DO將更新關(guān)鍵詞的文檔標(biāo)識符信息重新計算一個新的地址存儲，對CS來說，這個操作與設(shè)置階段的上傳無異；在搜索階段，CS不接收搜索陷門，只對有搜索請求的DU發(fā)送信息。因此，CS不能通過推導(dǎo)當(dāng)前的更新操作和先前搜索查詢中的真實關(guān)鍵詞來打破前向安全。

b）搜索模式安全。搜索模式是關(guān)于哪些查詢是對應(yīng)查詢相同關(guān)鍵詞的信息。TS-MDSSE方案在搜索階段，CS將編碼反向索引生成的數(shù)據(jù)結(jié)構(gòu) P 發(fā)給DU，CS僅僅知道該DU有過搜索請求，并未獲得有關(guān)搜索關(guān)鍵詞的信息，CS沒有獲得任何搜索陷門信息。因此，本文方案可以隱藏搜索模式。

c）訪問模式安全。通過知道哪個文檔與查詢匹配而推斷出的任何信息。TS-MDSSE方案能夠保證訪問模式安全與搜索模式安全的原因相同，方案設(shè)計使CS始終不知道DU使用哪些搜索陷門進行搜索查詢，因此無法獲得文檔與查詢匹配的信息。

TS-MDSSE方案中的更新操作只泄露更新操作類型 op 更新文檔的標(biāo)識符 id_j 和所有關(guān)鍵詞上次更新時間戳 LastTime（?W） 。其中， op 和 的泄露是來自真實文檔的更新。更新泄露函數(shù)為 L_update（op，w_i，id_j）=L^′（op，id_j，LastTime（W）） 。具體來說，真實的文檔更新及其長度的變化分別泄露了更新文檔標(biāo)識符和更新操作。

4.2FS-MDSSE的安全性分析

后向安全：FS-MDSSE滿足 I 型后向安全，在更新階段只泄露與 w_i 匹配的文件和插入時間，以及 w_i 所有的更新發(fā)生時間，確保對關(guān)鍵詞 w_i 的搜索查詢不能鏈接到包含 w_i 但已經(jīng)刪除的文檔標(biāo)識符。此操作的更新泄露函數(shù)是 L_update（op，w_i，id_j）= L^′（op，id_j，LastTime（W）） 。明確泄露已刪除的文檔標(biāo)識符的方式只有兩種：a） B_i 中包含相關(guān)文檔的記錄，但在方案設(shè)計中，這種方式是不可能發(fā)生的。因為當(dāng)文檔刪除 w_i 時，DO會立即更改對應(yīng)的 B_i ，所以 B_i 中不可能包含已經(jīng)刪除文檔的標(biāo)識符。b）DU使用舊的搜索陷門繼續(xù)進行搜索查詢，如果是TS-MDSSE的更新操作方式，DU將會獲得額外信息。在本文方案中，采用隨機值覆蓋技術(shù)將原地址的密文用隨機值在CS端覆蓋，同時更改關(guān)鍵詞的搜索陷門，使DU無法在接下來的搜索查詢中鏈接到已經(jīng)刪除的文檔。因此，基于后向安全的定義，F(xiàn)S-MDSSE滿足Ⅱ型后向安全。

搜索查詢只泄露了與搜索關(guān)鍵詞匹配的文檔標(biāo)識符，即L_search（w_i）=L^′（id_j） 。實際上，泄露的文檔標(biāo)識符來自對真實文檔的搜索。例如，當(dāng)DU恢復(fù) id_j 時，需要向云服務(wù)器發(fā)送關(guān)于 id_j 的請求來獲得真實文檔，這樣會將 id_j 泄露給云服務(wù)器。

定理1假設(shè)函數(shù) F 和 G 是安全的偽隨機函數(shù)和偽隨機生成器，F(xiàn)S-MDSSE是具有自適應(yīng)安全的MDSSE方案，則泄露函數(shù) L_seup?L_search 和 L_update 滿足

L_setup（λ）=λ

L_search（w_i）=L^′（id_j）

L_update（Φop，w_i，id_j）=L^′（op，id_j，LastTime（ΦW））

通過從real到ideal設(shè)置一系列游戲來證明定理1，得出敵手 A 無法區(qū)分現(xiàn)實模型 real 與理想模型ideal。證明FS-MDSSE是具有搜索模式和訪問模式安全的，以及前向和 I 型后向安全性。每個游戲都與上個游戲有所不同，但是在敵手 A 看來兩個相鄰游戲間是不可區(qū)分的，最后使用泄露函數(shù) L 模擬ideal，從而證明FS-MDSSE的安全性。

游戲 G₀ 與real相同，運行真實的FS-MDSSE方案。

游戲 G₁ 與 G₀ 不同的是，在每次搜索和更新時，敵手將偽隨機函數(shù) F 和偽隨機生成器 G 分別替換為 G_x 和 G_y ，它們分別是 （0，1）^l′ 和 （0，1）^N 上所有隨機函數(shù)集合內(nèi)的均勻隨機采樣。

引理1如果 F 和 G 是安全的偽隨機函數(shù)和偽隨機生成器，則在敵手 A 看來 G₀ 和 G₁ 是不可區(qū)分的。

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

游戲 G₂ 與 G₁ 不同的是，敵手在搜索階段向云服務(wù)器發(fā)送搜索請求，云服務(wù)器響應(yīng)并返回密文編碼之后的數(shù)據(jù)結(jié)構(gòu)P 。然后，敵手使用 G_x 均勻隨機采樣生成的陷門 y^′ 計算解碼，得到 N 位長的隨機字符串 B_i^′ 。從上面的步驟看， G₁ 和 G₂ 得到的 N 位長隨機字符串是不可區(qū)分的。

游戲 G₃ 與 G₂ 不同的是，敵手改變了關(guān)鍵詞更新計數(shù)器c\"pdae 的更新方式，采用均勻隨機采樣代替原來的計算。

引理2在敵手 A 看來， G₃ 和 G₂ 在統(tǒng)計上是不可區(qū)分的。

證明游戲 G₂ 中的 y^′ 是由 G_x 均勻隨機采樣計算得到的，其中 G_x 使用的密鑰是更新計數(shù)器 c_wi^update ，而在 G₃ 中 c_??i^update 的值也是均勻且獨立的隨機分布。故 G₂ 和 G₃ 中的 c_wi^update 值在統(tǒng)計上是不可區(qū)分的，所以將更新計數(shù)器 c_wi^update 作為計算陷門的密鑰之一是安全的。

游戲 G₄ 與 G₃ 不同的是，敵手改變了 addr_wi 和 val_wi 在更新階段的計算方式。具體地，敵手將 形式的函數(shù)計算改成 G_x（t） 形式，其中 χ_t 是每個更新操作執(zhí)行的時間戳。類似地，敵手也改變搜索階段 addr_wi 的生成方式。

游戲 G₅ 與 G₄ 不同的是，將敵手換成了模擬器S，并且S在查詢階段和更新階段只能訪問泄露函數(shù) L_update 。

引理3在敵手 A 看來， G₄ 和 G₅ 在計算上是不可區(qū)分的。

證明模擬器 S訪問泄露函數(shù) L_search（w_i） L_update（op，w_i id_j ），且模擬器S生成的一系列變量與 G₄ 中的敵手相同。在查詢階段，S可以學(xué)習(xí)到數(shù)據(jù)使用者查詢的結(jié)果，即一系列的文檔標(biāo)識符 id_j ，這個泄露對于所有DSSE來說是可以忽略的。在更新階段，S可以學(xué)習(xí)到更新關(guān)鍵詞和其更新時間戳。在敵手 A 看來，由S作出的回應(yīng)與 G₅ 中敵手作出的回應(yīng)是相同的。故 G₄ 和 G₅ 是不可區(qū)分的。

綜上所述，以上一系列游戲和引理證明都說明了定理1的正確性。對于搜索和更新協(xié)議，理想世界游戲中與查詢的關(guān)鍵詞匹配位置的時間戳與現(xiàn)實世界游戲中的時間戳相同，理想世界游戲中與搜索和更新的關(guān)鍵詞 w_i 匹配的文檔標(biāo)識符與現(xiàn)實世界游戲中的標(biāo)識符相同?？傊?，存在一個模擬器S來模擬具有給定泄漏函數(shù)的FS-MDSSE，并且該模擬與真實的FS-MDSSE無法區(qū)分。因此，TS-MDSSE 和FS-MDSSE 都是在 L_seup?L_search 和L_update 下自適應(yīng)安全的。

4.3方案比較

本節(jié)介紹了TS-MDSSE和FS-MDSSE的通信開銷和功能分析。兩個方案中的四個算法只有系統(tǒng)初始化算法的時間復(fù)雜度為 O（n） ，其中 n 為系統(tǒng)中關(guān)鍵詞的個數(shù)，其他三個算法均為 O（1） 。表3是本文兩個方案與其他可搜索加密方案在搜索和更新中客戶端與服務(wù)器之間的通信開銷對比。其中： N 是系統(tǒng)中關(guān)鍵詞/文檔標(biāo)識符對的個數(shù)； n 是搜索或更新中的關(guān)鍵詞個數(shù);k是文獻[16]中混淆技術(shù)的安全參數(shù)； P 是服務(wù)器對加密數(shù)據(jù)庫進行編碼后得到的數(shù)據(jù)結(jié)構(gòu)；“一”表示沒有該項功能。

表4功能對比

如前文所述，與之前的方案相比，F(xiàn)S-MDSSE可以提供更高的安全保證，同時支持多關(guān)鍵詞搜索。表4是本文方案與其他方案在滿足安全性上的比較。易看出，F(xiàn)B-DSSE使用位圖索引來表示所有可能文件的標(biāo)識符，只可以實現(xiàn)前向和后向安全。Chen等人[1]提出的具有前向和后向安全的Bestie方案，實現(xiàn)了非交互式真實刪除的動態(tài)搜索功能。文獻[20]基于穿刺偽隨機函數(shù)設(shè)計了一個提高搜索效率的動態(tài)可搜索加密方案。然而這些方案都沒有考慮訪問模式和搜索模式。文獻[16，19]實現(xiàn)了前向安全和后向安全，同時隱藏搜索模式，雖然可以實現(xiàn)多關(guān)鍵詞查詢，但是都沒有考慮訪問模式的泄露問題。文獻[17，18]可以隱藏搜索模式和訪問模式，支持聯(lián)合關(guān)鍵詞搜索，但都不支持動態(tài)更新數(shù)據(jù)庫。FS-MDSSE實現(xiàn)了四級安全目標(biāo)，即能夠隱藏搜索模式和訪問模式，同時保證動態(tài)更新搜索中的前向安全和后向安全。

5實驗

本章對FS-MDSSE進行了評估測試，并將其性能與文獻[10，16，17，19，20]進行了比較。文獻[17]是支持多關(guān)鍵詞連接查詢的可搜索加密方案，同時具備訪問模式和搜索模式安全。文獻[16，19]是支持前后向安全和搜索模式隱藏的動態(tài)對稱可搜索加密方案。Zuo等人[10]的FB-DSSE是滿足前向和后向安全的DSSE方案。該方案與文獻[16]都使用了基于位圖的索引，與本文構(gòu)建索引的方法一致。文獻[20]僅需一次交互就完成了數(shù)據(jù)搜索，提升了搜索效率，但其僅具備前向和后向安全。FS-MDSSE實現(xiàn)了四級安全目標(biāo)，具有最高的安全保障，同時是這些方案中搜索效率最優(yōu)的。

5.1實驗設(shè)置

本文設(shè)計的協(xié)議通過 C++ 實現(xiàn)，調(diào)用GMP、NTL、LIBOTE和 CRYPTO++ 庫，并在LinuxUbuntu20.04系統(tǒng)上進行演示實驗，其中CPU為AMDRyzen 76800H@3.20GHz ，安全參數(shù)為128，運行內(nèi)存為 32GB 。為保證對比實驗的準(zhǔn)確性，本文與對比方案均在同一網(wǎng)絡(luò)帶寬環(huán)境下運行。使用Enron電子郵件數(shù)據(jù)集作為實驗數(shù)據(jù)，預(yù)處理提取了79880個關(guān)鍵詞和文檔標(biāo)識符對作為實驗數(shù)據(jù)集。實驗用了兩個數(shù)據(jù)集，數(shù)據(jù)集Ⅰ包含14 331個文件，23500對 （w_i，id_j） ，數(shù)據(jù)集Ⅱ包含32651個文件，79880對 （w_i，id_j） 。此外，參考文獻[18]中的性能評估方法，搜索實驗中不考慮服務(wù)器和客戶端傳輸數(shù)據(jù)的時間消耗。

5.2 實驗結(jié)果

本節(jié)展示了FS-MDSSE的一些性能指標(biāo)，包括存儲在云服務(wù)器上的加密數(shù)據(jù)庫的存儲開銷、搜索帶寬和搜索時間成本，其中搜索時間成本分為數(shù)據(jù)使用者陷門生成時間和服務(wù)器搜索時間。本文方案不對更新性能進行評估，因為在實踐中更關(guān)注的是搜索性能，尤其是對大型數(shù)據(jù)庫進行管理時。

a）存儲開銷。在設(shè)置階段，主要測量存儲在云服務(wù)器中的加密索引表的大小，并將FS-MDSSE與同樣用位圖構(gòu)建索引的方案進行比較。該實驗在數(shù)據(jù)集I上進行，結(jié)果表明，文獻[17]雖然使用的是同態(tài)加密，但由于其上傳到云服務(wù)器的是加密多項式的系數(shù)，所以在同一數(shù)據(jù)集下，存儲開銷較小，為6758KB 。文獻[10，16]都是基于位圖構(gòu)建的索引，因此具有相近的存儲開銷，分別為 9628KB 和 9713KB 。FS-MDSSE在同樣的設(shè)置下，其關(guān)鍵詞對應(yīng)的文檔標(biāo)識符以一個 B_i 的值進行存儲，其存儲開銷最小，為 1434KB 。

b）搜索帶寬成本。其為客戶端與服務(wù)器執(zhí)行搜索協(xié)議時交換的數(shù)據(jù)總大小，表5列出了評估方案的搜索帶寬成本。文獻[17]、FB-DSSE和FS-MDSSE實現(xiàn)了最優(yōu)搜索往返，只需要一次往返數(shù)據(jù)，而文獻[16]多引入了一個搜索往返。FB-DSSE的帶寬消耗最少，為 285B 。文獻[16]的帶寬消耗第二低為35KB，這是因為它的帶寬與搜索條目數(shù)量成正比。對于FS-MDSSE而言，它的搜索帶寬是云服務(wù)器編碼的數(shù)據(jù)結(jié)構(gòu) P 的大小，雖不是這些方案中最低的，但其搜索帶寬也在數(shù)據(jù)使用者可以接受的范圍內(nèi)，而且只需要一個搜索往返。

索時間較長為 13.260s 。在數(shù)據(jù)集Ⅱ上進行單關(guān)鍵詞搜索時間成本測量，數(shù)值結(jié)果表明，F(xiàn)S-MDSSE用時最少，需要0.022ms 就能完成搜索，而文獻[16］和FB-DSSE分別需要0.348ms 和 0.572ms 。文獻［19]已經(jīng)具有很高的安全性能，它需要對搜索到的關(guān)鍵詞密文進行全部的比對，在搜索耗時上需要0.179s，比本文方案稍慢。穿刺偽隨機函數(shù)這一密碼原語在搜索階段耗時較少，文獻［20]基于該原語設(shè)計的方案搜索用時為 0.043ms 。由此可見，本文利用不經(jīng)意鍵值對編碼技術(shù)對云服務(wù)器的密文信息進行處理，不僅可以實現(xiàn)多級安全目標(biāo)，而且具有較好的搜索效率，具有更廣泛的應(yīng)用場景。下面對FB-DSSE和FS-MDSSE展開多關(guān)鍵詞搜索中不同階段的評估。

d）陷門生成階段的計算消耗。 x 軸表示搜索關(guān)鍵詞的個數(shù)， y 軸表示搜索不同數(shù)量關(guān)鍵詞下的消耗時間，本實驗測試的最多以50個關(guān)鍵詞作為搜索關(guān)鍵詞集。該實驗在數(shù)據(jù)集Ⅱ上進行，結(jié)果如圖3所示。文獻[16]是基于混淆技術(shù)構(gòu)建的，每次搜索一個關(guān)鍵詞時，實際要計算 k 個關(guān)鍵詞陷門信息，因此時間消耗會是最大的，本文不再做評估。文獻［19]的搜索陷門生成使用了 m 次乘法運算，當(dāng)加密關(guān)鍵詞個數(shù)為50時，需要的時間為 0.691ms 。文獻[20]的搜索陷門包括密鑰表中的密鑰和計算搜索關(guān)鍵詞的偽隨機函數(shù)值，該方案的陷門生成階段耗時很短，與本文方案時間重合度極高，將不在圖中重復(fù)給出。FB-DSSE搜索時對要查詢的關(guān)鍵詞進行查表、計算關(guān)鍵詞密鑰，而且密鑰是用偽隨機函數(shù)生成的，所以陷門生成時間消耗很小。本文方案計算陷門是通過偽隨機函數(shù)循環(huán)生成的，時間消耗最小。

c）總搜索時間成本消耗。包括生成搜索陷門、計算操作和解密最終結(jié)果，表6報告了在數(shù)據(jù)集Ⅱ上的時間消耗結(jié)果。文獻[17]是基于加性同態(tài)進行搜索操作，在收到返回結(jié)果后還需要解多個多項式獲得最終的匹配文檔標(biāo)識符，因此它的搜

e）云服務(wù)器搜索階段計算消耗。 x 軸表示搜索關(guān)鍵詞的個數(shù)， y 軸表示搜索不同數(shù)量關(guān)鍵詞下的消耗時間，本實驗是在陷門生成階段之后進行的，最多以50個關(guān)鍵詞作為搜索關(guān)鍵詞集。該實驗在數(shù)據(jù)集Ⅱ上進行，結(jié)果如圖4所示。文獻[16]的搜索條目與生成的陷門數(shù)量是對應(yīng)的，即是要搜索關(guān)鍵詞數(shù)量的 k 倍，為了安全性保證， k 值越大越好，所以其消耗時間較大，這里同樣不進行評估。FB-DSSE的搜索時間與搜索關(guān)鍵詞更新次數(shù)有關(guān)，更新次數(shù)越大，消耗時間越大，在進行評估時統(tǒng)一將更新次數(shù)設(shè)置為20。文獻[19]的搜索時間復(fù)雜度與搜索關(guān)鍵詞匹配的文件數(shù)量 N 相關(guān)，時間復(fù)雜度為 O（N） 0文獻[20]搜索的主要時間消耗是在服務(wù)器端依次執(zhí)行增加和刪除搜索操作，得到密鑰標(biāo)記序?qū)χ笠来斡嬎銈坞S機函數(shù)值循環(huán)得到文檔標(biāo)識符集合。該方案僅支持單關(guān)鍵詞搜索，所以對比本文方案的多關(guān)鍵詞，其計算消耗不具有優(yōu)勢。FS-MDSSE的搜索不是在服務(wù)器上完成的，而是由DU使用陷門進行解碼直接獲得搜索結(jié)果值，使用OKVS解碼時間消耗非常小。

在解密階段，F(xiàn)B-DSSE需要使用循環(huán)語句對多個密文進行恢復(fù)，本文測試了解密十個搜索關(guān)鍵詞的時間為1.48s，而本文FS-MDSSE只對解碼得到的密文進行異或解密即可，所以解密階段FS-MDSSE的時間開銷遠小于FB-DSSE。

本文方案采用不經(jīng)意鍵值對存儲技術(shù)對云服務(wù)器上的加密反向索引進行編碼，編碼的時間并不計人數(shù)據(jù)使用者的搜索時間，因為在使用者發(fā)出搜索請求前，云服務(wù)器就已經(jīng)完成了對索引的編碼操作。表7報告了使用OKVS對不同數(shù)量的關(guān)鍵詞/文檔標(biāo)識符對編碼所用的時間，以及解碼不同數(shù)量的關(guān)鍵詞所用的時間，兩者時間都是毫秒級。本文DSSE搜索時，使用OKVS對查詢關(guān)鍵詞解碼，以獲得匹配的文檔標(biāo)識符，因此TS-MDSSE和FS-MDSSE的搜索效率都很高。

同時，實驗評估了FS-MDSSE在數(shù)據(jù)集I和 I 上的多關(guān)鍵詞查詢的總搜索時間消耗，如圖5所示。實驗結(jié)果表明，客戶端的總搜索時間成本會隨著搜索關(guān)鍵詞的數(shù)量增加而增加，但相比其他方案的搜索成本，可以說FS-MDSSE具有比較好的多關(guān)鍵詞搜索性能。

6結(jié)束語

針對動態(tài)對稱可搜索加密存在的四個安全性問題，以及無法有效支持多用戶搜索，本文定義了多級安全目標(biāo)結(jié)構(gòu)，并設(shè)計一個具有三級安全目標(biāo)的多用戶動態(tài)對稱可搜索加密方案TS-MDSSE，實現(xiàn)在更新查詢時滿足前向安全，在搜索時隱藏搜索模式和訪問模式。并在TS-MDSSE的更新算法中加入隨機值替換技術(shù)，從而使方案增加了后向安全性，得到了具備四級安全目標(biāo)的FS-MDSSE方案。通過安全性分析得出，TS-MDSSE和FS-MDSSE方案均能滿足設(shè)定的安全目標(biāo)。最后進行了實驗評估，與其他同樣使用位圖索引的方案相比，本文方案在保證安全性的同時，搜索性能更佳，在密文搜索領(lǐng)域具有廣泛的應(yīng)用前景。未來工作將聚焦于多數(shù)據(jù)源、多用戶搜索的動態(tài)可搜索加密方案的研究，同時保障搜索模式和訪問模式安全，進一步降低方案的計算開銷，提升安全性能。

參考文獻：

[1]ZhengYandong，Lu Rongxing，Li Beibei，et al.Efficient privacypreserving data mergingand skyline computation over multi-source encrypted data[J]. InformationSciences，2019，498：91-105.

[2]SongD X，WagnerD，Perrig A.Practical techniques for searches on encrypted data[C]//Procof IEEE SymposiumonSecurityand Privacy.Piscataway，NJ：IEEEPress，2OOO：44-55.

[3]CurtmolaR，GarayJ，Kamara S，etal.Searchable symmetric encryption：improved definitions and efficient constructions[J].Journal of ComputerSecurity，2011，19（5）：895-934.

[4] Kamara S，Papamanthou C，RoederT.Dynamic searchable symmetricencryption[C]//Proc ofACMSIGSACConference on Computer and Communications Security.New York：ACM Press，2012：965-976.

[5]Stefanov E，Papamanthou C， Shi Runting. Practical dynamic searchable encryption with smalleakage[EB/OL].（2013-12-16）. htps：//ia.cr/ 2013/832

[6]Bost R，Minaud B，Ohrimenko O. Forward and backward private searchableencryptionfromconstrained cryptographicprimitives [C]// Proc of ACM SIGSAC Conference on Computer and Communications Security. New York：ACM Press，2017： 1465-1482.

[7]Sun Shifeng，Yuan Xingliang，Liao Qirui，et al. Practical backwardsecure searchable encryption from symmetricpuncturable encryption [C]// Proc of ACM SIGSAC Conf on Computer and Communications Security.NewYork：ACMPress，2018：763-780.

[8]Song Xiangfu， Dong Changyu， Yuan Dandan，et al. Forward private searchable symmetric encryption with optimized I/O eficiency[J]. IEEETrans on Dependable and Secure Computing，2020，17 （5）： 912-927.

[9]He Kun，Chen Jing，Zhou Qinxi，et al. Secure dynamic searchable symmetric encryptionwith constant client storage cost[J].IEEE Trans on Information Forensics and Security，2020，16：1538-1549.

[10] Zuo Cong，Sun Shifeng，Liu JK，et al.Dynamic searchable symmetric encryption with forward and stronger backward privacy [M]// Sako K，Schneider S，Ryan P.Computer Security-ESORICS 2019. Cham： Springer， 2019： 283-303.

[11]Chen Tianyang，Xu Peng，Wang Wei，et al.Bestie：very practical searchable encryption with forward and backward security_[M]// Bertino E，Shulman H，Waidner M. Computer Security-ESORICS 2021.Cham： Springer，2021： 3-23.

[12]Liu Chang，Zhu Liehuang，Wang Mingzhong，et al. Search pattern leakage in searchable encryption： attacks and new construction [J]. Information Sciences，2014， 265：176-188.

[13]Cash D，Grubbs P，Perry J，et al.Leakage-abuse atacks against searchable encryption[C]//Proc of ACM SIGSAC Conf on Computer and Communications Security.New York：ACM Press，2015：668-679.

[14］孫曉玲，楊秋格，沈焱萍，等．改進的高效動態(tài)可搜索加密方案 [J].計算機應(yīng)用研究，2020，37（8）：2472-2476.（SunXiaoling，Yang Qiuge，Shen Yanping，etal.Improved efficient dynamic searchable encryption [J]. Application Research of Computers， 2020，37（8）： 2472-2476.）

[15］鄭東，何俊杰，秦寶東，等．可撤銷的多關(guān)鍵字公鑰可搜索加密 方案［J].計算機應(yīng)用研究，2023，40（7）：2179-2183，2191. （Zheng Dong，He Junjie， Qin Baodong，et al.Multi-keyword public key searchable encryption schemewith keyword revocation[J].ApplicationResearch of Computers，2023，40（7）：2179-2183，2191.）

[16] Zheng Yandong，Lu Rongxing，Shao Jun，etal.Achieving practical symmetric searchable encryption with search patern privacy over cloud [J]. IEEE Trans on Services Computing，2022，15（3）：1358- 1370.

[17]Wang Yunling，Sun Shifeng，Wang Jianfeng，etal.Achieving searchable encryption scheme with search pattern hidden [J]. IEEE Trans on Services Computing，2020，15（2）：1012-1025.

[18]Yang Yunbo，Dong Xiaolei，Cao Zhenfu，et al. IXT：improved searchable encryption for multi-word queries based_onPSI[J]. Frontiers of Computer Science，2023，17（5）：175811.

[19］宋翔飛，王化群．一個具有前向安全和后向安全的可驗證多關(guān)鍵 字可搜索加密方案［J]．計算機學(xué)報，2023，46（4）：727-742. （Song Xiangfei，Wang Huaqun. Verifiable multi-keyword searchable encryption with forward and backward security[J]. Chinese Journal of Computers，2023，46（4）： 727-742.）

[20]劉運東，汪學(xué)明，基于穿刺偽隨機函數(shù)的動態(tài)可搜索加密方案 [J/OL].計算機應(yīng)用.（2024-10-16）．https：//doi.org/10. 11772/j. isn.1001-9081. 2024071011.（Liu Yundong，Wang Xueming. Dynamic searchable encryption scheme based on puncture pseudorandom function[J/OL].Journal of Computer Applications.（2024- 10-16）.https：//doi.org/10.1172/j.issn.1001-9081.2024071011.）

[21] Garimell G，Pinkas B，Rosulek M，et al. Oblivious key-value storesand amplification forprivatesetintersection[M]//MalkinT，Peikert C，AdvancesinCryptology-CRYTO221.Cham：Springer，2021：395-425.

[22]Raghuraman S， Rindal P. Blazing fast PSIfrom improved OKVS and subfield VOLE[C]// Proc of ACM SIGSAC Conference on Computer and Communications Security.New York ： ACM Press，2022： 2505-2517.