馬昌社， 李曉聰， 陳海龍

(華南師范大學計算機學院， 廣州 510631)

隨著大數(shù)據(jù)時代的到來，數(shù)據(jù)量的高速增長使不少個人用戶和企業(yè)選擇將數(shù)據(jù)外包存儲到云服務器上。云服務器一般被視為誠實且好奇的：誠實地執(zhí)行程序，卻存在窺探用戶數(shù)據(jù)的可能。因此，一般將數(shù)據(jù)加密后再存儲。但是，經(jīng)過加密算法處理后的數(shù)據(jù)不支持快速檢索，為了滿足數(shù)據(jù)加密后的高效搜索需求，學術界開始研究可搜索對稱加密(Searchable Symmetric Encryption，SSE)技術。

2000年，SONG等[1]提出了實用對稱可搜索加密的概念，并給出了第1個SSE方案。此后，學者們提出了一系列在搜索性能、功能、安全性之間權衡的靜態(tài)SSE方案[2-6]。如：為了提高搜索性能，GOH[2]構建了基于正排索引的SSE方案，CURTMOLA等[3]給出了基于倒排索引的SSE方案；為了拓展更多功能特性，CASH等[4]提出了支持大數(shù)據(jù)集上聯(lián)合查詢的可搜索加密方案(OXT)，SUN等[5]將OXT方案拓展到了多用戶場景，孫僖澤等[6]提出了一個密態(tài)數(shù)據(jù)庫查詢框架，將可搜索加密技術應用到了現(xiàn)有的主流數(shù)據(jù)庫中。然而，已有的靜態(tài)SSE方案無法滿足現(xiàn)實中對文件進行動態(tài)更新的需求。2012年，KAMARA等[7]提出了首個動態(tài)SSE方案(Dynamic SSE，DSSE)，該方案實現(xiàn)了次線性級別的搜索效率，但因引入數(shù)據(jù)更新機制而導致易泄露更多信息；ZHANG等[8]針對DSSE方案的攻擊指出，只需要注入不多于100個文件，就可恢復全部的關鍵字信息。為了減緩動態(tài)SSE方案中的文件注入攻擊，STEFANOV等[9]給出了DSSE方案中的前向安全定義，指出前向安全為DSSE方案的必備要求，并設計了一個基于茫然隨機訪問內存[10](Obilivious Random Access Memory，ORAM)的前向安全DSSE方案。

支持前向安全的方案避免了舊的搜索令牌與新加入的密文文件產(chǎn)生關聯(lián)，從而減緩隱私泄露。從技術角度概括，除了基于開銷巨大的ORAM的方案外，實現(xiàn)前向安全的方式主要可以分為以下3種：(1)通過單向函數(shù)構建索引。如BOST[11]首次基于公鑰密碼學原語設計了高效DSSE方案；HE等[12]通過原像不可逆的哈希函數(shù)構建索引，減少了客戶端本地存儲，但引入了更新次數(shù)的限制。(2)通過多次更換密鑰重構索引。如ETEMAD等[13]提出了基于重構索引的方案，該方案雖然不要求服務器有計算功能，但要求客戶端為查詢結果重新構造索引，因此在搜索時的通信開銷和客戶端的計算開銷巨大。(3)通過對稱加密函數(shù)構建索引。如SONG等[14]針對文獻[11]中公鑰密碼學原語帶來的性能瓶頸，構造了基于對稱密碼學原語的前向安全方案，為目前理論搜索性能最優(yōu)的前向安全DSSE方案。

然而，在現(xiàn)有的前向安全DSSE方案中，大部分方案僅支持單用戶環(huán)境，這是由于為了生成最新的搜索令牌，這些方案在客戶端本地維護了一個存儲了所有關鍵字狀態(tài)信息的狀態(tài)表，而關鍵字狀態(tài)存儲在本地使得方案難以支持多用戶檢索[15]。目前僅有的2種支持多用戶檢索的前向安全方案[16-17]增設了一個可信中間件來記錄關鍵字狀態(tài)，數(shù)據(jù)擁有者在動態(tài)更新后，將狀態(tài)表保存在可信中間件中，其他用戶發(fā)起查詢時，首先將搜索請求發(fā)送到可信中間件，再由可信中間件根據(jù)當時的狀態(tài)表計算出最新的搜索令牌發(fā)送給服務器。盡管支持多用戶檢索的前向安全方案[16-17]為設計多用戶前向安全DSSE方案提供了思路，但在資源受限的情況下，增設可信服務器的方法并不實用。

針對上述問題，本文提出了一個基于雙鏈索引結構的支持多用戶的高效前向安全可搜索加密方案(Efficient Multi-user Forward Secure SSE，EMFS)。該方案無需增設可信中間件，基于陷門單向函數(shù)構建主鏈索引，基于流密碼尋址式結構構建從鏈索引，利用陷門函數(shù)在無密鑰時的單向計算性，以及主索引鏈的長度不依賴于各關鍵詞狀態(tài)，實現(xiàn)了前向安全和多用戶；利用從鏈高效遍歷的特性以及對主鏈檢索長度的緩存優(yōu)化，達到了搜索的高效性。最后，將EMFS方案與Sophos[11]、FAST[14]、BESTIE[18]方案進行對比實驗。

1 預備知識

1.1 偽隨機函數(shù)

令F:{0,1}λ×{0,1}n→{0,1}n是一個多項式時間可計算函數(shù)，如果對于任何敵手,都有

成立，則稱F是一個偽隨機函數(shù)，其中第1個概率依賴于K{0,1}n的均勻隨機性，第2個概率依賴于從n比特字符串映射到n比特字符串的函數(shù)集合中抽樣出f的隨機性。

1.2 陷門置換

陷門置換(Trapdoor Permutation,TDP)是定義域與值域相同的陷門單向函數(shù)。對于給定的運行在置換域D的一個陷門置換π，使用公鑰pk可以快速地進行正向計算，使用私鑰sk可以反向計算置換π-1。陷門置換是一個算法三元組(KeyGen,π,π-1)，其中：

(1)(pk,sk)←KeyGen(λ)是一個隨機生成算法。其輸入是安全參數(shù)λ，輸出是公鑰pk和私鑰sk。

(2)y←π(pk,x)是一個確定性算法。其輸入是公鑰pk和原像xD，輸出是置換下的像yD。

(3)x←π(sk,y)是一個確定性算法。其輸入是私鑰sk和像yD，輸出是原像xD。

陷門置換還應滿足以下安全性質：在沒有私鑰的情形下，反向計算置換π-1十分困難。任何一個PPT敵手在沒有私鑰的情況下成功求解反向置換的概率λ)≤negl(λ)。

1.3 多用戶SSE參與者

一般來講，多用戶SSE系統(tǒng)的參與者由三方組成：

(1)數(shù)據(jù)擁有者：數(shù)據(jù)擁有者將數(shù)據(jù)加密后存放到云服務器，并為密文數(shù)據(jù)生成檢索索引，為被授權用戶生成授權信息。此外，在支持動態(tài)更新的SSE方案中，數(shù)據(jù)擁有者負責給新添加的文件選取關鍵字，發(fā)送相應數(shù)據(jù)以幫助服務器添加密文文件和更新檢索索引。

(2)云服務器：服務器根據(jù)存放的加密文件、對應的索引以及用戶發(fā)送過來的搜索令牌完成搜索，并將正確查詢結果發(fā)送給用戶，同時可以利用自身的計算能力來分析用戶的隱私信息。

(3)數(shù)據(jù)使用者(其他用戶)：在搜索時，根據(jù)數(shù)據(jù)擁有者提供的授權信息為需要搜索的關鍵字生成搜索令牌，然后將搜索令牌提交給云服務器，并接收返回來的結果。

1.4 動態(tài)SSE形式化定義

根據(jù)文獻[11]給出的通用動態(tài)對稱可搜索加密方案的定義，給定安全參數(shù)λ, 一個動態(tài)對稱可搜索加密方案DSSE包含了1個初始化算法和2個客戶端與服務器之間的兩方協(xié)議：

(1)((K,σ);EDB)←Setup((λ,DB);⊥)：系統(tǒng)初始化算法?？蛻舳溯斎氚踩珔?shù)λ、明文數(shù)據(jù)集DB，服務器無需輸入。該算法輸出主密鑰K、狀態(tài)值σ和加密數(shù)據(jù)庫EDB，其中主密鑰K和狀態(tài)值σ由客戶端存儲，加密數(shù)據(jù)庫EDB由服務器存儲。

(2)(σ′;EDB′)←Update(K,σ,op,input,EDB):更新協(xié)議?？蛻舳溯斎朊荑€K、當前狀態(tài)值σ、更新操作符op和要更新的數(shù)據(jù)input，服務端輸入加密數(shù)據(jù)庫EDB，其中op{add,del}用于指示本次更新為添加操作或刪除操作，新數(shù)據(jù)是形如的文件標識符和關鍵字組成的對。更新協(xié)議結束后客戶端保存新的狀態(tài)值σ′，服務器保存更新后的密文數(shù)據(jù)庫EDB′。

(3)((σ′,DB(w);EDB′))←Search((K,σ,w),EDB)：搜索協(xié)議。客戶端輸入密鑰K、前狀態(tài)值σ、要搜索的關鍵字w，服務端輸入密文數(shù)據(jù)庫EDB。搜索結束后客戶端獲得搜索結果集合DB(w)，此外客戶端輸出一個可能更新過的狀態(tài)值σ′，服務端輸出一個可能更新過的密文數(shù)據(jù)庫EDB′。

1.5 安全定義

CURTMOLA等[3]首次給出了SSE方案的安全性的正式定義，通過泄露函數(shù)來刻畫SSE方案的安全泄露，由2個以上的游戲證明SSE方案的安全性，一個游戲代表真實的協(xié)議執(zhí)行，一個游戲由仿真器根據(jù)泄露函數(shù)模擬生成。如果敵手無法區(qū)分自己是在哪個游戲中，則表明敵手不掌握除了泄露函數(shù)之外的任何知識，稱這樣的方案為-自適應語義安全的。泄露函數(shù)維護了一個請求列表q，其中qiq代表第i次請求。常見的泄露函數(shù)有搜索模式sp(x)、查詢模式qp(x)：

sp(x)={i|(i,x)q} (qi為搜索請求)，

qp(x)={i|(i,x)qor (i,op,input)qandx

input} (qi為搜索請求或更新請求)。

前向安全是針對動態(tài)可搜索加密方案的強安全屬性，要求服務器無法將新添加的文件與已存在的文件相關聯(lián)。換言之，在新添加了一個文檔后，該文檔包含的關鍵字信息在下一次搜索查詢前不會被泄露給敵手，更新請求不會泄露新添加的文件是否包含之前搜索過的關鍵字。形式化定義如下：

定義1[11](前向安全)一個-自適應安全的動態(tài)對稱可搜索加密方案是前向安全的，如果它的更新泄露函數(shù)為如下形式：

Update(op,input)=′(op,{idi,|Widi|})，

其中idi為第i個更新的文件的標識符。

2 EMFS方案

本文提出了一個支持多用戶的高效前向安全可搜索加密方案(EMFS)，該方案在文件更新和搜索時都不需要額外的可信中間件參與。本章首先介紹該方案的索引結構，再介紹協(xié)議的具體步驟。

2.1 EMFS索引結構

EMFS方案基于雙鏈索引結構,該結構由兩部分組成：陷門單向函數(shù)組成的主鏈和解密后可直接尋址的側鏈(圖1)。

圖1 EMFS方案的索引結構示意圖Figure 1 The structure of index of EMFS scheme

通過主鏈上的陷門單向函數(shù)，可以實現(xiàn)新加入的文件與以往存在的文件的不可鏈接性，直到客戶端搜索時將最新的搜索令牌發(fā)送給服務器。搜索時，被授權用戶根據(jù)當前的更新次數(shù)c計算出最新的搜索令牌STc(w)，并將其發(fā)送給服務器。由于服務器不擁有私鑰，因而只能單向計算陷門單向函數(shù)，對于任何的i>c，服務器不能計算出STi(w)。假設下次更新加入的文件包含關鍵字w，由于新文件存放的地址將由STc+1(w)通過哈希計算得到，因此，直到服務器收到能搜索到新文件的搜索令牌STc+1(w)前，都不能將新文件與以往的關鍵字關聯(lián)，從而保證了前向安全。

服務器拿到當前最新的搜索令牌STc(w)之后，可以利用公鑰計算出所有STi(w)，其中i

EMFS方案的主鏈索引結構與Sophos方案相似，但又略有不同。在Sophos方案中，每個搜索令牌下僅包含一個文件，由于搜索令牌在服務端需要通過公鑰密碼學原語計算得到，開銷較大，因此，EMFS方案通過加入側鏈結構，使得同一批加入的數(shù)據(jù)能夠共享一個搜索令牌，從而減少主鏈長度。側鏈結構中，鏈的遍歷不包含公鑰計算，而是將下一個節(jié)點的位置用類似流密碼的方式異或保護。收到最新令牌后，可以通過令牌計算出側鏈上第一個位置的流密碼，通過解密側鏈上的第一個位置，可以得到下一個節(jié)點的位置。因此，相較于主鏈的遍歷，在側鏈中的遍歷速度極高。

另外，在Sophos方案中，每個關鍵字對應的陷門單向函數(shù)鏈長度不同，分別是各個關鍵字所包含的文件數(shù)。 EMFS方案中所有關鍵字對應的主索引鏈長度均與更新次數(shù)相同，也正是這個設計，使得EMFS方案可以在不需要第三方可信服務器的前提下拓展到多用戶的場景。

2.2 EMFS方案設計

EMFS方案的系統(tǒng)模型(圖2)由數(shù)據(jù)擁有者、被授權用戶、服務器三方以及它們之間的交互協(xié)議構成。

圖2 EMFS方案的系統(tǒng)模型圖Figure 2 The system model of EMFS scheme

在初始化階段，數(shù)據(jù)擁有者將外包文件加密并生成密文索引，將加密文件和密文索引上傳到外包服務器；針對各個被授權用戶允許搜索的關鍵字，生成不同的授權信息集合，將授權信息集合發(fā)送給對應的用戶，由用戶在本地保存自己的授權信息表。

在更新階段，數(shù)據(jù)擁有者對新增的文件加密，并生成一系列更新令牌，然后將更新令牌和加密文件上傳到外包服務器；外包服務器根據(jù)更新令牌對文件進行插入。更新完成后，數(shù)據(jù)擁有者和服務器都更新當前系統(tǒng)狀態(tài)值。

在搜索階段，被授權用戶首先發(fā)起搜索請求，服務器將當前狀態(tài)值發(fā)送給用戶，被授權用戶利用本地保存的授權信息表的信息，根據(jù)服務器返回的當前狀態(tài)值生成最新的搜索令牌。服務器根據(jù)搜索令牌搜索索引表得到查詢結果，并將結果返回給用戶。搜索階段不需要數(shù)據(jù)擁有者或代理服務器的參與，被授權用戶和服務器兩方交互即可完成。

初始化算法的執(zhí)行步驟如算法1所示。算法的偽代碼中，F(xiàn)為偽隨機函數(shù)，用于生成關鍵字的初始搜索令牌以及會話密鑰；W為存放授權關鍵字到搜索令牌和會話密鑰的映射，由數(shù)據(jù)擁有者生成后，傳給被授權用戶存儲在本地，同時存放在本地的還有陷門函數(shù)的私鑰。服務器存放索引表以及陷門函數(shù)的公鑰。初始化算法還會輸出狀態(tài)值，初始時該狀態(tài)值為0，該狀態(tài)值隨著更新次數(shù)增加而增長。

算法1 初始化算法Setup(λ,keywordSet;⊥)

DataOwner:

(sk,pk)←KeyGen(1λ)

W,T←empty map

forwin keywordSet do

W[w]←F(ks,w)| |F(kw,w)

end for

return ((T,pk),(W,sk),c)

搜索算法的執(zhí)行步驟如算法2所示。當被授權用戶需要搜索關鍵字時，從W表中取出初始搜索令牌ST0(w)，然后根據(jù)服務端獲取到的當前狀態(tài)值c，利用陷門函數(shù)的私鑰即可生成最新的搜索令牌STc(w)。服務器利用STc(w)和陷門單向函數(shù)的公鑰pk，可以恢復其他的搜索令牌STi(w) (i=[0,c-1])。每一個搜索令牌STi(w)代表雙鏈索引結構中主鏈上的一個節(jié)點，利用該搜索令牌可以計算出該位置上的側鏈的頭節(jié)點位置。側鏈的遍歷不包含公鑰計算，而是利用流密碼的方式進行保護。以位于主鏈i位置上的側鏈為例，服務器先根據(jù)收到的STc(w)計算STi(w)(i

算法2 搜索算法Search(w,W;EDB)

Client:

發(fā)起查詢請求，從服務器獲得最新全局狀態(tài)值c

(ST0(w),Kw)←W[w]

將STc(w),Kw發(fā)送給服務器

Server:

ST(w)←STc(w)

ID←empty map

ID.add(C2[Kw])

fori=cto 0 do

if (ST(w)=C1[Kw]) then

C1[Kw]←ST(w),C2[Kw]←ID

return ID

end if

ui←H1(ST(w)| |Kw)

if (T[ui]=⊥) then

ST(w)←πpk(ST(w))

i←i-1

else

r←ST(w)

whiler≠⊥ do

ui←H(r| |Kw)

(id,r)←T[ui]⊕H2(r| |Kw)

ID.add(id)

ST(w)←πpk(ST(w))

i←i-1

end if

end for

把ID發(fā)送給客戶端

f←dcmod (p-1)(q-1)，

STc(w)←ST0(w)fmodN。

服務器端則需通過STc(w)進行c次公鑰計算，對于主索引鏈上i[0,c]的位置，檢查其側鏈上是否包含數(shù)據(jù)。算法2通過將查詢過的結果緩存，從而進一步提高后續(xù)搜索效率，搜索結果由C2表和T表中取出的兩部分組成，并在搜索結束后，將搜索結果加入C2表，將該關鍵字對應的最新搜索令牌加入C1表,從而避免在將來的搜索中重復計算。如果對于某關鍵字的搜索與上次搜索而言，2次搜索期間發(fā)生了次更新，服務器搜索過程的公鑰計算次數(shù)從首次搜索的c次降為次。

算法3 更新算法Update(Doc,σ;EDB)

DataOwner:

T←empty map

parse doc as (id,Wid)

forwWiddo

ST0(w)←F(ks,w),Kw←F(kw,w)

u←H1(STc(w)||Kw)

if (T[u]=⊥) then

T[u]←H2(STc(w)| |Kw)⊕(ind| |⊥)

else

tmp←T[u]⊕H2(STc(w)| |Kw)

T[u]←H2(STc(w)||Kw)⊕(ind||r)

T[H1(r||Kw)]←H2(r||Kw)⊕tmp

end if

end for

end for

c←c+1

把T發(fā)送給服務器

Server：

EDB′←EDB∪T

c←c+1

簡而言之，EMFS方案的核心思想是將擁有確定性計算結果的陷門函數(shù)主鏈與引入隨機性的側鏈相結合，從而使得被授權用戶與服務器交互獲取到當前系統(tǒng)狀態(tài)值c后，即可計算出確定性的搜索令牌。盡管數(shù)據(jù)擁有者在計算更新令牌時，通過抽取隨機數(shù)來生成流密碼，引入了隨機性，但由于側鏈的入口是固定的，故不需要額外增設代理服務器記錄更新時引入的隨機狀態(tài)。主鏈遍歷的公鑰計算速度是慢于側鏈的，因此，EMFS方案通過加入2個緩存表，減少了主鏈上的遍歷長度，通過避免重復計算，進一步提升了后續(xù)搜索性能。

3 方案評估

3.1 安全性分析

定理1設H1和H2是基于隨機預言機建模的安全哈希函數(shù)，π是陷門單向置換，F(xiàn)是安全的偽隨機函數(shù)，那么EMFS方案是滿足前向安全的-自適應安全動態(tài)可搜索加密方案。EMFS方案的-自適應安全定義如下：

Setup=⊥，

Search(w)=(sp(w),qp(w))，

Update(op,docid)=′(op,|Wid|})。

證明通過構造一系列的游戲來進行證明，其中，第一個游戲執(zhí)行真實世界的協(xié)議，最后一個游戲是由仿真器模擬運行的。在這一系列游戲中，相鄰的游戲之間只有微小的差異，根據(jù)不可區(qū)分性的傳遞性，只要證明任意相鄰的2個游戲是不可區(qū)分的，則證明了第一個游戲和最后一個游戲是不可區(qū)分的。

游戲G2：游戲G2與游戲G1基本相同，除了游戲G2在更新時使用隨機字符串表示H1(ST(w)| |Kw)。具體來講，游戲G2維護一個映射表L,在執(zhí)行搜索時隨機選擇一個字符串u保存在L[ST(w)| |Kw]中，用L[ST(w)| |Kw]中的數(shù)據(jù)為哈希函數(shù)H1的隨機預言機H1編碼。若敵手在搜索前不使用ST(w)||Kw問詢隨機預言機，則敵手無法區(qū)分自己是處于游戲G2或是處于游戲G1中。但敵手如果在搜索前就已經(jīng)使用ST(w)||Kw問詢隨機預言機，那么隨機預言機會選擇隨機字符串為H1(STw| |Kw)編碼，而這個隨機字符串極大概率會與L[ST(w)| |Kw]中的數(shù)據(jù)不一致，敵手觀察到這種不一致的現(xiàn)象時就會知道自己不是與真實世界交互。稱這不一致的情形為Bad事件，因此

|Pr[G2=1]-Pr[G1=1]|≤Pr[Bad]。

由于只有敵手在搜索前使用ST(w)| |Kw問詢隨機預言機，Bad事件才會發(fā)生。而如果敵手有提前猜測到ST(w)的能力，則可以利用該能力構建一個陷門單向函數(shù)π的敵手，因此

游戲G3： 游戲G3與游戲G2基本相同，除了游戲G3在更新時使用隨機字符串來表示H2(ST(w)| |Kw)，并保存該隨機字符串，搜索時使用該隨機字符串為哈希函數(shù)H2的隨機預言機H2編碼。同理，有

游戲G4：游戲G4與游戲G3基本相同，除了游戲G4在更新時使用隨機字符串來表示H1(r| |Kw)，并保存該隨機字符串，搜索時使用該隨機字符串為哈希函數(shù)H1的隨機預言機H1編碼。由于r的長度為λ，在游戲G4中發(fā)生Bad事件的概率Pr[Bad]≤poly(λ)·(2-λ)，因此

|Pr[G4=1]-Pr[G3=1]|≤poly(λ)·(2-λ)。

游戲G5：游戲G5與游戲G4基本相同，除了游戲G5在更新時使用隨機字符串來表示H2(r| |Kw)。同理，有

|Pr[G5=1]-Pr[G4=1]|≤poly(λ)·(2-λ)。

游戲G6：游戲G6與游戲G5的主要區(qū)別是：在游戲G6中，不是使用已有的搜索令牌，而是隨機生成搜索令牌。為了獲得搜索結果與更新操作的一致性，使用Updates表記錄所有的更新請求。在執(zhí)行搜索協(xié)議時，如果是關鍵詞w的第一次查詢，則游戲G6先隨機產(chǎn)生ST0(w)，再迭代生成STi(w) (i[1,c])，同時根據(jù)Updates表的數(shù)據(jù)更新隨機預言機的狀態(tài)。敵手不能區(qū)分這種變化，因為從敵手的視角來看，游戲G6和游戲G5的行為完全相同：更新協(xié)議均是輸出一個隨機字符串，而搜索協(xié)議的搜索令牌也具有相同的分布。因此，游戲G6和游戲G5是不可區(qū)分的，有

Pr[G6=1]=Pr[G5=1]。

因此，結合上述一系列游戲，有

證畢。

3.2 理論評估

如表1所示，分別以W代表關鍵字的集合，|W|表示關鍵字集合中不同關鍵字的數(shù)量，nw代表搜索關鍵字w的結果集合的元素個數(shù)，aw代表被添加到數(shù)據(jù)庫中包含關鍵字w的元素個數(shù)；logM表示搜索令牌的長度，在FAST的方案中搜索令牌由分組密碼實現(xiàn)，按AES算法計算，該比特長度一般為128比特;logC和logD分別表示查詢次數(shù)和更新次數(shù)的計數(shù)器長度，具體實現(xiàn)時一般為對應程序設計語言的整型變量長度;對于總更新次數(shù)，則以uc表示。表1中的客戶端存儲指的是數(shù)據(jù)擁有者的本地存儲開銷。

表1 4種DSSE 方案的性能對比表Table 1 Table of performance among the four DSSE schemes

從計算復雜度、通信復雜度以及客戶端存儲開銷幾個方面進行理論評估。3個對比方案均為具有理論最優(yōu)搜索時間復雜度的方案。其中：Sophos方案[11]包含公鑰密碼學操作；FAST方案[14]的實現(xiàn)完全基于非對稱密碼學原語；BESTIE方案[18]進一步減少了FAST方案中不必要的異或操作，為目前實際搜索性能最優(yōu)的前向安全方案。

由結果(表1)可知：EMFS方案的客戶端存儲開銷是小于其他方案的。究其原因為：由于需要拓展到多用戶環(huán)境，EMFS方案將原來由客戶端存儲的搜索關鍵字狀態(tài)表用全局狀態(tài)代替,從而客戶端存儲開銷縮小為常數(shù)級別O(1)。搜索前，被授權用戶需要先與服務器進行一輪交互，獲得當前的全局狀態(tài)uc。因為不需要關鍵字存儲狀態(tài)表，這使得客戶端存儲開銷減少了，但也以犧牲一定的搜索性能為代價，即除了至少要對所有添加進數(shù)據(jù)庫的文件檢索(即aw次檢索)外，還需要進行額外的uc次陷門函數(shù)計算。由于EMFS方案支持批量更新，每次更新可以增加不限數(shù)量的文件，這使得uc在實際使用中可以保持在一個較小的值，因此這部分額外計算對搜索性能的影響有限。

3.3 實驗評估

在測試中，所用環(huán)境為6核6線程的CPU AMD3600、32 GB的內存、500 GB的固態(tài)硬盤。實驗采用C++編寫方案代碼，使用Cryptopp開源庫實現(xiàn)RSA陷門函數(shù)、抗碰撞的哈希函數(shù)以及偽隨機函數(shù)，使用Rocksdb數(shù)據(jù)庫存儲文件標識符和關鍵字組成的對，服務器和客戶端間采用gRPC框架來實現(xiàn)網(wǎng)絡數(shù)據(jù)傳輸。

3.3.1 服務端搜索性能 實驗通過測量EMFS、Sophos、FAST、BESTIE方案的服務端搜索耗時來對比搜索性能。選取文件數(shù)大小為106的數(shù)據(jù)庫，測量服務端搜索10～105個匹配文件的總時間，再將總時間除以對應匹配文件的個數(shù)，得到檢索出各條目的平均時間(單位：ms)。由于EMFS方案支持批量更新，在構建數(shù)據(jù)庫時將數(shù)據(jù)分10次更新進數(shù)據(jù)庫。此外，圖3中所有方案匹配每個文件的平均時間均與匹配文件數(shù)呈反比，這是由于初始化搜索有著一些固定的開銷，這些固定開銷被分攤到各個匹配條目后，對平均搜索時間的影響可忽略不計，導致平均搜索效率有所提升。

圖3 4種DSSE方案的搜索性能對比Figure 3 Comparison of search performance among the four DSSE schemes

平均搜索時間測量結果(圖3)表明：(1)在匹配文件數(shù)較少時，EMFS方案與基于公鑰密碼學原語構建索引的Sophos方案相差無幾。這是由于EMFS方案有一個與更新次數(shù)成正比的陷門函數(shù)計算開銷，但是當匹配文件數(shù)量增大時，該方案的檢索效率與目前現(xiàn)有前向安全方案中搜索性能最優(yōu)的FAST方案和BESTIE方案相似，搜索每個文件的時間均在0.01 ms以下。這是因為當搜索結果較大時，EMFS方案的搜索開銷主要在遍歷支鏈上，而支鏈上的操作和FAST、BESTIE方案一樣只涉及非對稱密碼學原語操作，效率極高。(2)所有方案的平均搜索效率都隨著數(shù)據(jù)集的增大而提升，其中EMFS方案的提升效率尤其明顯。EMFS方案是以合理的搜索性能為代價換取支持多用戶的拓展，而隨著匹配文件集越大，這項代價的開銷在EMFS方案總開銷的占比越小，因此EMFS方案尤其適合匹配結果較多的大數(shù)據(jù)集。

實驗進一步探究了不同的總更新次數(shù)uc對EMFS方案搜索效率的影響。顯然，隨著匹配條目數(shù)的增大，總的搜索時間也會增大。由結果(圖4)可知：(1)uc分別為10、100、1 000時，搜索時間隨匹配文件數(shù)量的增大而增長的幅度都是相似的，搜索時間的差異主要還是源于不同的初始固定開銷。(2)uc為一個較大的值(uc=1 000)時，對應了系統(tǒng)在批量更新的場景下，每天批量更新一次，運行約3年，EMFS方案匹配十萬個結果的時間僅比系統(tǒng)初始運行化時匹配相同數(shù)目的結果所耗的時間增加約0.3 s，不會影響用戶的實際搜索體驗。

圖4 不同更新次數(shù)下EMFS方案的搜索性能對比Figure 4 Comparison of search performance of the EMFS scheme at different updates

事實上，上述實驗并沒有完全反映EMFS方案的搜索性能，反映的僅是“最壞情況”下的搜索結果?；仡橢MFS方案的搜索算法，方案通過利用舊的搜索進行了效率優(yōu)化，只遍歷上一次查詢到最新更新這段時間沒有遍歷過的節(jié)點，從而得到部分搜索結果，結合舊的搜索結果得到最終結果，避免了在搜索時重復遍歷節(jié)點，并且不會帶來超出搜索模式sp(w)以外的新的泄露。在相鄰的幾次查詢中，僅首次查詢會消耗較多時間，后續(xù)的搜索查詢可以利用上一次的查詢結果。因此，上述實驗僅代表了初次搜索的效率。同理，在多用戶的環(huán)境下，任一用戶搜索過某關鍵詞后，其他用戶再次搜索時效率也會顯著提升。

為了顯示再次搜索時效率的顯著提升，動態(tài)模擬了更新請求和搜索請求交替執(zhí)行的情況：令搜索請求和更新請求的比值為a，即請求序列為搜索請求的概率為a，為更新請求的概率為1-a，實驗測量了不同比例下的服務端的搜索時間。實驗結果(圖5)表明：與初次搜索相比，后續(xù)的搜索效率提升幅度較大，并且執(zhí)行搜索的頻率越高，對搜索性能的提升越大。這表明引入緩存機制后，頻繁的更新對EMFS方案實際性能的影響進一步降低，EMFS方案具有很強的拓展性和實用性。

圖5 模擬請求下EMFS方案的搜索性能對比Figure 5 Comparison of search efficiency of the EMFS scheme by trace simulation

3.3.2 客戶端存儲開銷 實驗測量EMFS、Sophos、FAST、BESTIE方案的客戶端實際存儲開銷。實驗選取文件數(shù)大小為106的數(shù)據(jù)庫，該數(shù)據(jù)庫包含105個關鍵字。實驗數(shù)據(jù)來源于存放了客戶端本地狀態(tài)的Rocksdb數(shù)據(jù)庫文件。

實驗結果(表2)表明：(1)Sophos方案和BESTIE方案的客戶端存儲開銷相似，并且都遠小于FAST方案的。究其原因為：Sophos方案里的每個關鍵字有1個計數(shù)器，BESTIE方案里的每個關鍵字有2個計數(shù)器，而在FAST方案中，每個關鍵字除了有1個計數(shù)器以外，還對應存放了一個固定大小的隨機字符串。(2)EMFS方案的客戶端存儲開銷是最小的，因為該方案不需要存儲每個關鍵字獨立的狀態(tài)，只需要1個表示更新次數(shù)的整型變量，約為4個字節(jié)。

表2 4種DSSE方案的客戶端存儲對比表Table 2 Table of client-side storage among the four DSSE schemes

4 結論

本文提出了一個不需要代理服務器的高效多用戶前向安全可搜索加密方案(EMFS)，該方案通過陷門單向函數(shù)構建主鏈索引來實現(xiàn)前向安全，被授權用戶僅與服務器交互即可獲取當前全局統(tǒng)一的系統(tǒng)狀態(tài)值，然后計算搜索陷門，從而實現(xiàn)前向安全SSE方案向多用戶的拓展。實驗結果表明：以合理的搜索性能為代價，EMFS方案實現(xiàn)了支持多用戶搜索的拓展；在數(shù)據(jù)集較大時，EMFS方案的搜索效率趨近于目前搜索效率最優(yōu)的前向安全方案(BESTIE)的，并且EMFS方案的客戶端存儲開銷小于Sophos、FAST、BESTIE方案的。