馬昌社， 李曉聰， 陳海龍

(華南師范大學(xué)計(jì)算機(jī)學(xué)院， 廣州 510631)

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

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

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

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

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

1 預(yù)備知識(shí)

1.1 偽隨機(jī)函數(shù)

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

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

1.2 陷門置換

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

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

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

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

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

1.3 多用戶SSE參與者

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

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

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

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

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

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

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

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

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

1.5 安全定義

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

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

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

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

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

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

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

其中idi為第i個(gè)更新的文件的標(biāo)識(shí)符。

2 EMFS方案

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

2.1 EMFS索引結(jié)構(gòu)

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

圖1 EMFS方案的索引結(jié)構(gòu)示意圖Figure 1 The structure of index of EMFS scheme

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

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

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

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

2.2 EMFS方案設(shè)計(jì)

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

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

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

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

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

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

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

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

Client:

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

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

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

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。

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

Server：

EDB′←EDB∪T

c←c+1

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

3 方案評(píng)估

3.1 安全性分析

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

Setup=⊥，

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

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

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

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

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

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

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

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

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

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

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

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

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

因此，結(jié)合上述一系列游戲，有

證畢。

3.2 理論評(píng)估

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

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

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

由結(jié)果(表1)可知：EMFS方案的客戶端存儲(chǔ)開銷是小于其他方案的。究其原因?yàn)椋河捎谛枰卣沟蕉嘤脩舡h(huán)境，EMFS方案將原來由客戶端存儲(chǔ)的搜索關(guān)鍵字狀態(tài)表用全局狀態(tài)代替,從而客戶端存儲(chǔ)開銷縮小為常數(shù)級(jí)別O(1)。搜索前，被授權(quán)用戶需要先與服務(wù)器進(jìn)行一輪交互，獲得當(dāng)前的全局狀態(tài)uc。因?yàn)椴恍枰P(guān)鍵字存儲(chǔ)狀態(tài)表，這使得客戶端存儲(chǔ)開銷減少了，但也以犧牲一定的搜索性能為代價(jià)，即除了至少要對(duì)所有添加進(jìn)數(shù)據(jù)庫的文件檢索(即aw次檢索)外，還需要進(jìn)行額外的uc次陷門函數(shù)計(jì)算。由于EMFS方案支持批量更新，每次更新可以增加不限數(shù)量的文件，這使得uc在實(shí)際使用中可以保持在一個(gè)較小的值，因此這部分額外計(jì)算對(duì)搜索性能的影響有限。

3.3 實(shí)驗(yàn)評(píng)估

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

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

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

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

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

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

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

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

圖5 模擬請(qǐng)求下EMFS方案的搜索性能對(duì)比Figure 5 Comparison of search efficiency of the EMFS scheme by trace simulation

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

實(shí)驗(yàn)結(jié)果(表2)表明：(1)Sophos方案和BESTIE方案的客戶端存儲(chǔ)開銷相似，并且都遠(yuǎn)小于FAST方案的。究其原因?yàn)椋篠ophos方案里的每個(gè)關(guān)鍵字有1個(gè)計(jì)數(shù)器，BESTIE方案里的每個(gè)關(guān)鍵字有2個(gè)計(jì)數(shù)器，而在FAST方案中，每個(gè)關(guān)鍵字除了有1個(gè)計(jì)數(shù)器以外，還對(duì)應(yīng)存放了一個(gè)固定大小的隨機(jī)字符串。(2)EMFS方案的客戶端存儲(chǔ)開銷是最小的，因?yàn)樵摲桨覆恍枰鎯?chǔ)每個(gè)關(guān)鍵字獨(dú)立的狀態(tài)，只需要1個(gè)表示更新次數(shù)的整型變量，約為4個(gè)字節(jié)。

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

4 結(jié)論

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