趙梓婷 徐 銀 宋祥福 蔣 瀚,3

1(山東大學(xué)軟件學(xué)院 濟(jì)南 250101) 2(山東大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 濟(jì)南 250101) 3(山東省軟件工程重點(diǎn)實(shí)驗(yàn)室(山東大學(xué)) 濟(jì)南 250101)

云計(jì)算的流行使得外包數(shù)據(jù)存儲(chǔ)技術(shù)得到了廣泛的關(guān)注和應(yīng)用，越來(lái)越多的用戶(hù)將數(shù)據(jù)存儲(chǔ)在遠(yuǎn)程云服務(wù)器中.這種方式降低了用戶(hù)的存儲(chǔ)和計(jì)算成本，但也帶來(lái)了一系列隱私問(wèn)題.將隱私信息明文保存在云數(shù)據(jù)庫(kù)中，會(huì)讓云存儲(chǔ)提供商輕而易舉獲得用戶(hù)信息；將數(shù)據(jù)加密后存入服務(wù)器中，雖然對(duì)內(nèi)容進(jìn)行了保護(hù)，但用戶(hù)無(wú)法直接對(duì)遠(yuǎn)程數(shù)據(jù)進(jìn)行檢索；同時(shí)，即使數(shù)據(jù)進(jìn)行了加密，云服務(wù)提供商也可以通過(guò)對(duì)查詢(xún)進(jìn)行分析，得知用戶(hù)最近的搜索偏好，構(gòu)建人物模型；或者得知公司最近的營(yíng)業(yè)方向、業(yè)務(wù)的增長(zhǎng)趨勢(shì)，判斷公司的發(fā)展情況.毫無(wú)疑問(wèn)，對(duì)大數(shù)據(jù)毫無(wú)防護(hù)的存儲(chǔ)會(huì)使隱私泄露，從而極大地影響到人身安全.

對(duì)稱(chēng)可搜索加密技術(shù)(symmetric searchable encryption, SSE)正是解決這一隱私問(wèn)題的極好方法.它允許客戶(hù)端將加密文檔存儲(chǔ)在不受信任的服務(wù)器上，使用對(duì)關(guān)鍵字加密編碼得到的令牌(token)檢索包含某個(gè)關(guān)鍵字的所有文檔.自Song等人[1]提出首個(gè)SSE方案以來(lái)，SSE已經(jīng)在許多領(lǐng)域得到了廣泛的應(yīng)用[2].初期方案基于靜態(tài)設(shè)置下，即用戶(hù)只能對(duì)關(guān)鍵字進(jìn)行檢索；Kamara等人[3]提出了首個(gè)動(dòng)態(tài)方案，允許用戶(hù)更新關(guān)鍵字信息，但仍只能提供抵御被動(dòng)敵手攻擊的安全性.Zhang等人[4]提出的文件注入攻擊使人們開(kāi)始重視對(duì)動(dòng)態(tài)可搜索加密方案及其應(yīng)滿(mǎn)足的安全特性的研究.

動(dòng)態(tài)對(duì)稱(chēng)可搜索加密(DSSE)不僅可以在數(shù)據(jù)保密的情況下進(jìn)行搜索，而且還能夠?qū)?shù)據(jù)提供更新(添加和刪除)后對(duì)增量進(jìn)行查詢(xún)，并且能夠破除添加操作的關(guān)聯(lián)性(前向安全)，甚至刪除操作的關(guān)聯(lián)性(后向安全).

然而仍然存在大量泄漏使得敵手能夠利用它來(lái)獲取用戶(hù)的私人信息，例如搜索模式(標(biāo)識(shí)序列中哪些查詢(xún)對(duì)應(yīng)同一個(gè)關(guān)鍵字)、訪問(wèn)模式(與查詢(xún)匹配的文檔的標(biāo)識(shí)符)、更新模式(更新歷史記錄)、容量模式(響應(yīng)查詢(xún)返回的文檔個(gè)數(shù))等.

近年來(lái)，動(dòng)態(tài)對(duì)稱(chēng)可搜索加密方案在提高效率，功能和安全性方面取得了許多進(jìn)展[5-7].然而，他們專(zhuān)注于搜索和訪問(wèn)模式，而忽略了容量這一嚴(yán)重的威脅，該威脅會(huì)泄漏關(guān)鍵字查詢(xún)結(jié)果的個(gè)數(shù)，被敵手利用執(zhí)行特定攻擊，獲取用戶(hù)隱私，針對(duì)這一泄露的最有效防御方法是設(shè)計(jì)一個(gè)容量隱藏方案.

對(duì)于動(dòng)態(tài)對(duì)稱(chēng)可搜索加密，另一個(gè)研究目標(biāo)是利用泄露設(shè)計(jì)攻擊，還原查詢(xún)的原始信息，或者是數(shù)據(jù)存儲(chǔ)的原始內(nèi)容，就近年來(lái)已經(jīng)提出了很多攻擊方案[8-10]，給可搜索加密研究的安全性提出了嚴(yán)峻的挑戰(zhàn).這些攻擊方案使用可搜索加密中的固有泄露，包括搜索模式、訪問(wèn)模式、更新模式以及容量模式，但在目前所設(shè)計(jì)的方案中，都是專(zhuān)注于一種訪問(wèn)模式進(jìn)行保護(hù)，因此難以抵抗使用其他泄露構(gòu)造的攻擊，因此，設(shè)計(jì)一個(gè)能夠隱藏多種泄露模式的安全方案是目前的難點(diǎn)，也是研究正在追求的方向.

針對(duì)這些問(wèn)題，我們?cè)O(shè)計(jì)了一個(gè)基于差分隱私[11]的高效存儲(chǔ)填充方案，并研究如何將其應(yīng)用到多服務(wù)器框架下的動(dòng)態(tài)對(duì)稱(chēng)可搜索加密方案中.具體來(lái)說(shuō)，我們希望在實(shí)現(xiàn)動(dòng)態(tài)更新的同時(shí)減少搜索模式、訪問(wèn)模式、更新模式和容量模式，實(shí)現(xiàn)多模式隱藏的動(dòng)態(tài)可搜索加密方案.

總而言之，本文的貢獻(xiàn)有3個(gè)方面：

1) 引入差分隱私這一安全概念，提出了新的填充方式-差分隱私填充(differential privacy padding,DPP)，并且給出了它在方案中的動(dòng)態(tài)使用機(jī)制.它可以根據(jù)隱私保護(hù)要求程度對(duì)噪音量進(jìn)行調(diào)節(jié)，不僅可以提供存儲(chǔ)量更少的安全填充方案，還可以通過(guò)其隱私保護(hù)屬性來(lái)保護(hù)關(guān)鍵字的容量信息.

2) 提出了一個(gè)基于多服務(wù)器框架的動(dòng)態(tài)對(duì)稱(chēng)可搜索加密方案MDSSE(multi dynamic searchable symmetric encryption)，使用第三方服務(wù)器存儲(chǔ)更新，并且使用DPP進(jìn)行填充，定義了新的安全泄露DP-Update，證明了我們的方案的容量泄露在查詢(xún)和更新過(guò)程中滿(mǎn)足差分隱私安全，并且方案同時(shí)滿(mǎn)足前向安全和后向安全性.

3) 對(duì)方案進(jìn)行了攻擊實(shí)驗(yàn)，證明方案可以抵抗容量泄露攻擊，并且擁有良好的表現(xiàn).

4) 對(duì)目前提出的容量泄露的保護(hù)方法進(jìn)行了研究梳理，并將算法與其進(jìn)行比較.結(jié)果證明我們的填充算法擁有更低的填充率.

1 相關(guān)工作

1.1 可搜索加密

可搜索加密能夠使用戶(hù)遠(yuǎn)程對(duì)加密數(shù)據(jù)進(jìn)行檢索，得到了來(lái)自學(xué)術(shù)界和工業(yè)界的廣泛關(guān)注[12-15].數(shù)據(jù)所有者可以將私有數(shù)據(jù)外包給不受信任的服務(wù)器，同時(shí)有選擇地檢索與查詢(xún)匹配的數(shù)據(jù)元素，而無(wú)需向服務(wù)器透露數(shù)據(jù)內(nèi)容或搜索關(guān)鍵字.相比于使用公鑰原語(yǔ)的非對(duì)稱(chēng)可搜索加密方案，能夠提供更高效率的對(duì)稱(chēng)可搜索加密方案成為了我們的研究目標(biāo).

對(duì)稱(chēng)可搜索加密最基本的構(gòu)造是對(duì)文件生成索引，將加密文件和索引外包給服務(wù)器.在查詢(xún)時(shí)客戶(hù)端生成關(guān)鍵字令牌上傳給服務(wù)器，服務(wù)器通過(guò)令牌使用密碼工具生成索引位置，通過(guò)索引找到與查詢(xún)匹配的文件列表.在此之上，開(kāi)展了一系列對(duì)于安全性、功能性以及性能方面的優(yōu)化[16-17].

Kamara等人[3]提出了首個(gè)動(dòng)態(tài)可搜索加密方案，除了常規(guī)的查詢(xún)操作，DSSE允許在數(shù)據(jù)集中進(jìn)行添加和刪除.之后人們嘗試使用紅黑樹(shù)[7]、茫然存儲(chǔ)[18]、陷門(mén)置換[19]等進(jìn)行實(shí)現(xiàn).DSSE的出現(xiàn)豐富了SSE的研究，但是也引入了新的泄露，敵手通過(guò)利用泄露進(jìn)行攻擊破壞數(shù)據(jù)隱私性.為了準(zhǔn)確刻畫(huà)方案中出現(xiàn)的泄露以及方案能夠達(dá)到的安全性，對(duì)前向安全與后向安全的形式化定義進(jìn)行了深入研究.

1.2 前向與后向安全

前向安全與后向安全的概念，首先由Stefanov等人[20]提出，之后由Bost等人[21]將概念形式化.自此，人們開(kāi)始對(duì)具有這2種性質(zhì)的方案展開(kāi)了廣泛的研究[22-27].

前向安全(forward privacy, FP)能夠保證服務(wù)器不會(huì)得知新添加進(jìn)數(shù)據(jù)庫(kù)的文檔是否包含之前查詢(xún)過(guò)的關(guān)鍵字.Mohammad等人[6]使用ORAM將查詢(xún)索引進(jìn)行外包；Bost等人[19]使用單向陷門(mén)置換生成搜索令牌鏈?zhǔn)沟脹](méi)有私鑰的服務(wù)器無(wú)法正向計(jì)算出新的搜索令牌.Song等人[27]將其方案中冗余的公鑰原語(yǔ)替換成偽隨機(jī)置換，使用對(duì)稱(chēng)密碼原語(yǔ)實(shí)現(xiàn)了更優(yōu)的計(jì)算和通信效率.

后向安全(backward privacy, BP)是指更新和接下來(lái)的查詢(xún)都無(wú)法泄露關(guān)于刪除文檔的信息.后向安全根據(jù)安全強(qiáng)度分為3類(lèi):1)后向安全(BP-Ⅰ)泄露最近匹配關(guān)鍵字的文檔、插入文檔的時(shí)間以及關(guān)鍵字的更新個(gè)數(shù)；2)BP-Ⅱ在前面的基礎(chǔ)上泄露關(guān)于關(guān)鍵字更新的時(shí)間和類(lèi)型；3)BP-Ⅲ又泄露對(duì)于每一個(gè)刪除操作對(duì)應(yīng)的插入操作.Bost等人[21]首先提出了一系列構(gòu)造：基于Sophos的BP-Ⅱ安全方案Fides,使用TWORAM的BP-Ⅰ方案Moneta；以及基于可穿刺加密的BP-Ⅲ方案Janus.Demertzis等人[28]提出了3個(gè)客戶(hù)端存儲(chǔ)的方案SDa和SDd以及QOS，將茫然映射作為數(shù)據(jù)結(jié)構(gòu)的同時(shí)減少客戶(hù)端存儲(chǔ).

1.3 泄露與攻擊

即使在可搜索加密協(xié)議中數(shù)據(jù)庫(kù)和檢索請(qǐng)求都是保密的，服務(wù)器仍然能得到某些泄露信息.首先，如果對(duì)于相同關(guān)鍵字每次生成的令牌是確定性的，那么服務(wù)器會(huì)發(fā)現(xiàn)多次搜索可能對(duì)應(yīng)同一個(gè)關(guān)鍵字.這就是所謂的搜索模式(search pattern, SP)[29]泄漏.有些方案會(huì)在查詢(xún)時(shí)泄露關(guān)鍵字所匹配的文檔列表，這就是所謂的訪問(wèn)模式(access pattern, AP)泄漏.更新時(shí)間、長(zhǎng)度甚至是更新內(nèi)容的泄露對(duì)應(yīng)的就是更新模式(update pattern, UP)泄露.對(duì)于泄露的研究表明可以利用這些泄露函數(shù)對(duì)查詢(xún)和文件信息進(jìn)行攻擊.

計(jì)數(shù)攻擊(count attack)[30]的提出使容量泄露(volume pattern, VP)成為研究關(guān)注的焦點(diǎn)，關(guān)鍵字容量是指關(guān)鍵字搜索返回的結(jié)果數(shù)量，計(jì)數(shù)攻擊可以通過(guò)每次查詢(xún)返回的文檔數(shù)量推測(cè)是否請(qǐng)求了相同的關(guān)鍵字.對(duì)于他的防御方式，最樸素的想法就是通過(guò)使用填充.將所有關(guān)鍵字都填充到最大的容量，這樣無(wú)疑是最安全的做法，但是消耗了大量的存儲(chǔ)和通信.Demertzis等人[31]提出了一種特殊的群填充方案，將每個(gè)關(guān)鍵字的長(zhǎng)度都填充到與當(dāng)前容量最近的x的指數(shù)次方.Kamara等人[32]首先使用偽隨機(jī)置換為關(guān)鍵字生成新長(zhǎng)度，這減少了存儲(chǔ)負(fù)載但是產(chǎn)生了截?cái)?；之后使用稠密子圖置換重新排列關(guān)鍵字進(jìn)行填充，這個(gè)方案消滅了截?cái)?，但需要額外存儲(chǔ)映射表和字典以保證搜索的正確性.Patel等人[33]中使用差分隱私生成拉普拉斯噪音對(duì)容量進(jìn)行填充，但是僅應(yīng)用于靜態(tài)設(shè)置下.方案受此啟發(fā)，設(shè)計(jì)了能夠適應(yīng)動(dòng)態(tài)設(shè)置下的查詢(xún)與更新操作的填充方法DPP，能夠在保證安全效果的前提下提供更好的存儲(chǔ)效率.

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

2.1 動(dòng)態(tài)可搜索加密技術(shù)

動(dòng)態(tài)可搜索加密方案由3個(gè)協(xié)議構(gòu)成：

1) (K,σ,ED)←Setup(λ,D).初始化階段用于生成密鑰、構(gòu)造加密數(shù)據(jù)集.用戶(hù)輸入安全參數(shù)λ和數(shù)據(jù)集D，輸出密鑰K，關(guān)鍵字狀態(tài)σ、以及加密數(shù)據(jù)集ED，將ED發(fā)送到服務(wù)器端存儲(chǔ).

2) (σ′,D(w),ED′)←Search(K,σ,w,ED).查詢(xún)階段用于搜索關(guān)鍵字對(duì)應(yīng)的數(shù)據(jù)集，這里我們的查詢(xún)是單關(guān)鍵字查詢(xún).用戶(hù)輸入密鑰K、查詢(xún)的關(guān)鍵字w及其狀態(tài)σ，服務(wù)器輸入加密數(shù)據(jù)集ED，輸出關(guān)鍵字對(duì)應(yīng)的數(shù)據(jù)集D(w).在查詢(xún)過(guò)后關(guān)鍵字的狀態(tài)和加密數(shù)據(jù)集有可能會(huì)發(fā)生改變，用σ′和ED′表示.

3) (σ′,ED′)←Update(K,σ,ind,w,op,ED).更新階段用于對(duì)數(shù)據(jù)集進(jìn)行插入/刪除操作.用戶(hù)輸入密鑰K，關(guān)鍵字狀態(tài)σ、關(guān)鍵字w、加密數(shù)據(jù)集ED及其對(duì)應(yīng)的文檔標(biāo)識(shí)符(w,ind)，以及進(jìn)行的操作op=添加/刪除.更新后關(guān)鍵字狀態(tài)和數(shù)據(jù)集會(huì)發(fā)生改變，用σ′和ED′表示.

2.2 差分隱私

Pr[M(D)∈T]≤e∈[M(D′)∈T],

則稱(chēng)算法M滿(mǎn)足ε-差分隱私.其中ε是隱私預(yù)算，表示算法隱私保護(hù)的程度，參數(shù)越小，隱私保護(hù)的程度越高.

方案使用拉普拉斯機(jī)制實(shí)現(xiàn)算法的差分隱私保護(hù).在介紹拉普拉斯機(jī)制之前，首先介紹函數(shù)敏感度概念以及拉普拉斯分布的密度函數(shù)：

對(duì)于位置與規(guī)模參數(shù)分別為μ與q的拉普拉斯分布，定義其密度函數(shù)：

基于定義2，給出拉普拉斯機(jī)制的定義：

定義3.拉普拉斯機(jī)制.設(shè)函數(shù)f:Nn→Rk則拉普拉斯機(jī)制滿(mǎn)足M(X)=f(X)+(Y1,Y2,…,Yk)，其中Yi是滿(mǎn)足拉普拉斯分布為L(zhǎng)aplace(Δ/ε)的隨機(jī)變量.

2.3 泄露函數(shù)與前后向安全

針對(duì)方案所涉及的泄露函數(shù)，我們給出其形式化定義4：

定義4.泄露模式安全定義.泄露函數(shù)為查詢(xún)列表保持查詢(xún)時(shí)的狀態(tài)，定義了用戶(hù)在進(jìn)行關(guān)鍵字查詢(xún)時(shí)可以被服務(wù)器獲取的信息，包括搜索模式、更新模式、容量模式，分別表示為sp(w),up(w),vp(w)，定義為：

sp(w)={i:(i,w)∈Q},up(w)={i:(i,op,in)∈Qandwappearsininw},vp(w)={|i|:(i,w)∈Q},

其中,i為時(shí)間戳，初始時(shí)設(shè)置為0，在每次查詢(xún)時(shí)自增，Q為查詢(xún)集合，op為更新操作、in為更新時(shí)的輸入.

其中ind為文檔標(biāo)識(shí)符，μ為文檔中所更改的關(guān)鍵字個(gè)數(shù).

我們提出的DSSE方案滿(mǎn)足BP-Ⅱ后向安全，在BP-Ⅱ后向安全方案中，搜索和更新操作中的泄露可被定義為：

其中,TimeDB(w)表示目前所有匹配關(guān)鍵字w的文檔標(biāo)識(shí)符集合以及它們被插入的時(shí)間點(diǎn)，不包含被刪除的標(biāo)識(shí)符；Updates(w)是關(guān)于關(guān)鍵字w的一系列更新時(shí)間戳.

2.4 可搜索加密安全定義

方案使用理想/真實(shí)世界模擬定義可搜索加密方案的安全性.Real實(shí)驗(yàn)中敵手攻擊的是真實(shí)方案，Ideal實(shí)驗(yàn)中敵手攻擊的是模擬器通過(guò)泄露模擬的環(huán)境，如果敵手無(wú)法區(qū)別真實(shí)世界與模擬世界，那么說(shuō)明無(wú)法獲得除了定義以外的其他泄露.我們將DSSE方案中的泄露函數(shù)定義為L(zhǎng)setup,Lsearch以及Lupdate，分別表示方案在初始化、查詢(xún)及更新時(shí)產(chǎn)生的泄露，敵手輸出1表示判斷自己與真實(shí)世界交互.具體游戲的定義為：

Real.敵手產(chǎn)生數(shù)據(jù)集D，將其發(fā)送給挑戰(zhàn)者.挑戰(zhàn)者執(zhí)行初始化操作后生成加密數(shù)據(jù)集ED返回給敵手.敵手可以自適應(yīng)的選擇多項(xiàng)式個(gè)請(qǐng)求對(duì)挑戰(zhàn)者進(jìn)行挑戰(zhàn).如果是查詢(xún)請(qǐng)求，挑戰(zhàn)者調(diào)用產(chǎn)生返回結(jié)果；如果是更新請(qǐng)求，挑戰(zhàn)者調(diào)用產(chǎn)生返回結(jié)果.最后敵手輸出字符b∈{0,1}.

Ideal.敵手產(chǎn)生數(shù)據(jù)集D，將其發(fā)送給模擬器.模擬器根據(jù)Lsetup生成加密數(shù)據(jù)集ED返回給敵手.敵手可以自適應(yīng)的選擇多項(xiàng)式個(gè)請(qǐng)求對(duì)模擬器進(jìn)行挑戰(zhàn).如果是查詢(xún)請(qǐng)求，模擬器根據(jù)Lsearch生成查詢(xún)結(jié)果，如果是更新請(qǐng)求，模擬器根據(jù)Lupdate進(jìn)行更新.最后敵手輸出字符b∈{0,1}.

2.5 差分隱私的容量泄露

本文使用文獻(xiàn)[32]中基于游戲的定義，來(lái)定義泄露函數(shù)的容量隱藏性，便于后面理解，我們將游戲所需概念和定義進(jìn)行介紹：

首先將2個(gè)相鄰數(shù)據(jù)庫(kù)D0，D1抽象成(關(guān)鍵字，關(guān)鍵字容量)對(duì)，作為2個(gè)數(shù)據(jù)庫(kù)的標(biāo)識(shí)Sign：

Sign0=(key,l0(key))key∈K,Sign1=(key,l1(key))key∈K,

其中,l0(key)表示關(guān)鍵字key在D0中的容量，l1(key)表示關(guān)鍵字key在D1中的容量.

對(duì)于所有key?{key0,key1}，l0(key)=l1(key)，

l0(key0)=l1(key1)+d,l0(key1)=l1(key0)-d,

相鄰數(shù)據(jù)庫(kù)僅有一個(gè)關(guān)鍵字不同，D0中獨(dú)有的關(guān)鍵字為key0，D1中獨(dú)有的關(guān)鍵字為key1,他們?cè)诓樵?xún)時(shí)的容量相差為d.

接下來(lái)定義游戲DPGAME0和DPGAME1，其中η∈{0,1}.

定義7.DPGAME(η)：

1) 敵手按照定義，生成2個(gè)數(shù)據(jù)庫(kù)標(biāo)識(shí)Sign0和Sign1，發(fā)送給挑戰(zhàn)者.

2) 挑戰(zhàn)者接收到2個(gè)標(biāo)識(shí)，選取其中一個(gè)Signη進(jìn)行差分隱私處理，將處理過(guò)后的標(biāo)識(shí)記作San(η)

3) 挑戰(zhàn)者根據(jù)San(η)為關(guān)鍵字生成對(duì)應(yīng)數(shù)量的文檔標(biāo)識(shí)符，然后將初始化時(shí)產(chǎn)生的泄露發(fā)送給敵手.

4) 敵手適應(yīng)性選擇關(guān)鍵字進(jìn)行詢(xún)問(wèn)，對(duì)于每個(gè)關(guān)鍵字，挑戰(zhàn)者將對(duì)應(yīng)的查詢(xún)泄露發(fā)送給敵手.

5) 敵手輸出b，判斷查詢(xún)來(lái)自哪個(gè)數(shù)據(jù)庫(kù).

將敵手在游戲中猜測(cè)成功的概率記為Pr，由此可以得到安全性定義8：

3 本文提出的方案表示

3.1 參數(shù)表示與安全定義

為了便于描述算法，我們?cè)诒?中給出所使用符號(hào)的整體說(shuō)明.

Table 1 System Parameter Symbol表1 系統(tǒng)參數(shù)符號(hào)

續(xù)表1

3.2 方案框架

本文方案的系統(tǒng)框架由2種實(shí)體組成，分別是可信的客戶(hù)端以及不可信的服務(wù)器端，服務(wù)器端包括用于初始化存儲(chǔ)的存儲(chǔ)服務(wù)器S0,S1以及用于隔離更新的更新服務(wù)器Sup，目的是將存儲(chǔ)和更新隔離放置，阻斷針對(duì)同一個(gè)關(guān)鍵字搜索和更新請(qǐng)求的關(guān)聯(lián)關(guān)系，同時(shí)在2個(gè)服務(wù)器之間挪移數(shù)據(jù)隱藏搜索模式.

客戶(hù)端首先在本地將數(shù)據(jù)集分割成2部分，分別放置到S0和S1上，并將關(guān)鍵字的存儲(chǔ)位置b∈{0,1}保存在本地關(guān)鍵字的狀態(tài)集σ中.當(dāng)客戶(hù)端對(duì)數(shù)據(jù)進(jìn)行更新時(shí)，先在本地將更新進(jìn)行差分隱私填充，之后上傳到更新服務(wù)器Sup.進(jìn)行查詢(xún)時(shí)，客戶(hù)端在本地生成關(guān)鍵字陷門(mén)，同時(shí)向存儲(chǔ)服務(wù)器Sb和更新服務(wù)器Sup發(fā)送查詢(xún)陷門(mén)和文檔個(gè)數(shù)，服務(wù)器端根據(jù)接收參數(shù)生成索引位置，返回索引處存放的數(shù)據(jù).

客戶(hù)端接收到查詢(xún)返回的數(shù)據(jù)后，在本地進(jìn)行解密，丟棄填充的虛擬標(biāo)識(shí)符后將有效標(biāo)識(shí)符進(jìn)行聚合.將聚合后的數(shù)據(jù)進(jìn)行差分隱私填充后放置到存儲(chǔ)服務(wù)器Sb⊕1上.

我們使用2種方式用于切斷不同請(qǐng)求之間的關(guān)聯(lián)關(guān)系，首先是使用DPP填充關(guān)鍵字容量，每次搜索請(qǐng)求返回時(shí)都使用隨機(jī)生成的噪音填充.由于噪音的生成與關(guān)鍵字容量獨(dú)立，提供的隨機(jī)性能夠隱藏關(guān)鍵字的真實(shí)容量，敵手無(wú)法通過(guò)返回的關(guān)鍵字?jǐn)?shù)量對(duì)查詢(xún)進(jìn)行匹配，保護(hù)了關(guān)鍵字的容量模式.其次是在令牌生成時(shí)，我們?yōu)殛P(guān)鍵字維護(hù)一個(gè)搜索次數(shù)狀態(tài)sw，每次搜索完成后數(shù)量加以保存，使用新的sw為關(guān)鍵字生成新的搜索令牌.這樣做可以保證每次搜索時(shí)關(guān)鍵字對(duì)應(yīng)的令牌不同，切斷了令牌鏈接性，減少了搜索模式產(chǎn)生的泄露.

3.3 Differential Privacy Padding(DPP)算法

在處理生成加密數(shù)據(jù)庫(kù)之前，客戶(hù)端將首先對(duì)原始數(shù)據(jù)執(zhí)行差分隱私填充算法，為原始容量生成服從拉普拉斯分布的噪音，具體DPP算法如下：

算法1.DPP算法.

輸入：隱私預(yù)算ε1、均值μ、敏感度d、關(guān)鍵字集合W;

輸出：填充后的數(shù)據(jù)集DPDB.

①ε=ε1,Δf=d,q=Δf/ε;

② for each keywordwinWin parallel:

③noise(w)=Lap(q);

④dlw=lw+Ceiling(noise(w));

⑤ end for

首先，客戶(hù)選擇隱私預(yù)算ε，為每個(gè)關(guān)鍵字添加符合拉普拉斯分布的噪音，然后使用Ceiling函數(shù)返回一個(gè)整數(shù)噪音值，填充到原始數(shù)據(jù)中.這里的填充是對(duì)關(guān)鍵字返回的文檔個(gè)數(shù)添加噪音，舉例來(lái)說(shuō)，關(guān)鍵字w1所對(duì)應(yīng)的文檔個(gè)數(shù)為10，添加數(shù)值型噪音后長(zhǎng)度變?yōu)?2，w1相對(duì)應(yīng)需要各自增加2個(gè)虛擬標(biāo)識(shí)符和無(wú)效文檔.為了區(qū)分虛擬標(biāo)識(shí)符與有效標(biāo)識(shí)符，使得客戶(hù)端在獲取搜索結(jié)果時(shí)過(guò)濾虛擬標(biāo)識(shí)符，我們將所有文檔標(biāo)識(shí)符的第1位設(shè)置為標(biāo)志位，無(wú)效文檔內(nèi)容為全0.

3.4 方案詳細(xì)描述

方案的主要思想是利用三臺(tái)服務(wù)器與差分隱私填充方案相結(jié)合，以提供可調(diào)節(jié)的SSE泄漏.在將可搜索索引外包給服務(wù)器之前，客戶(hù)端將在數(shù)據(jù)庫(kù)DB上應(yīng)用DPP算法以獲取其填充版本DPDB.然后，客戶(hù)端像普通的SSE方案一樣對(duì)填充的索引進(jìn)行加密，并外包給服務(wù)器.

在以下偽代碼中，我們使用偽隨機(jī)函數(shù)F，帶密鑰的哈希函數(shù)H生成協(xié)議期間所需的令牌，哈希函數(shù)h和MDSSE.Enc和MDSSE.Dec表示語(yǔ)義安全對(duì)稱(chēng)加密方案的加密和解密算法.

首先初始化需要遠(yuǎn)程存儲(chǔ)的數(shù)據(jù)集，之后描述服務(wù)器上執(zhí)行的查詢(xún)與更新操作.為了簡(jiǎn)化操作，我們將文檔使用文檔標(biāo)識(shí)符進(jìn)行代替，即加密數(shù)據(jù)集存儲(chǔ)文檔標(biāo)識(shí)符.

算法2.MDSSE.Setup().

輸入：安全參數(shù)λ，數(shù)據(jù)集DB;

輸出：密鑰K、關(guān)鍵字狀態(tài)σ、加密數(shù)據(jù)集DPDB.

①ks,ku←{0,1}λ,Σ,EDB0,EDB1初始化為空的映射表;

②DPDBb←DPP(ε1,μ,d,DB);

③ forwinWdo

④dlw,sw,dpw←0,b←{0,1};

⑤tw←F(ks,h(w)‖sw‖b);

⑥ forind∈DPDBb(w) do

⑦e←H(kw‖sw);

⑧v←MDSSE.Enc(ku,ind);

⑨dlw←dlw+1,DPDBb[e]←v;

⑩ end for

初始化算法的具體描述為：

首先客戶(hù)端產(chǎn)生2個(gè)密鑰ks,ku.ks從PRF的密鑰空間中選擇，ku用于加密文檔標(biāo)識(shí)符.選取隱私預(yù)算ε，使用DPP算法對(duì)原始數(shù)據(jù)進(jìn)行填充，得到填充數(shù)據(jù)庫(kù)DPDB.對(duì)于每個(gè)關(guān)鍵字w，隨機(jī)選取存放的服務(wù)器位置b，查詢(xún)次數(shù)sw初始置為0.我們將ks與h(w)‖sw作為偽隨機(jī)函數(shù)F的輸入，生成關(guān)鍵字w的令牌tw，使用令牌為關(guān)鍵字w的每一個(gè)標(biāo)識(shí)符生成索引e，指示標(biāo)識(shí)符的存放位置，然后加密文檔標(biāo)識(shí)符，存放入存儲(chǔ)服務(wù)器Sb中.

算法3.MDSSE.Update().

輸入：關(guān)鍵字w、更新列表UDB(w)；

輸出：填充后的加密數(shù)據(jù)集DPDBup(w).

①DPDBup(w)←DPP(ε2,μ,d,UDB(w))

/*隨機(jī)選擇隱私預(yù)算*/

② forwinDPDBupdo

③ 從映射表中取出w的狀態(tài)信息(sw,dpw);

④tp←F(ks,h(w)‖sw‖2);

⑤e←H(kp,dpw);

⑥v←MDSSE.Enc(ku,op‖ind);

⑦dpw←dpw+1;

⑧DPDBup[e]←v;

⑨ end for

更新算法的具體描述為：

當(dāng)需要對(duì)關(guān)鍵字進(jìn)行更新時(shí)，隨機(jī)選擇隱私預(yù)算生成噪音添加到原始數(shù)據(jù)中.接下來(lái)為填充后的標(biāo)識(shí)符生成索引位置e.從關(guān)鍵字的狀態(tài)表中取出狀態(tài)信息sw,dpw，其中dpw表示關(guān)鍵字2次搜索間的更新個(gè)數(shù)，每更新1次加1，在每次查詢(xún)后置0.使用狀態(tài)信息為關(guān)鍵字產(chǎn)生更新令牌tp，為更新標(biāo)識(shí)符生成索引、進(jìn)行加密.加密關(guān)鍵字的同時(shí)需要綁定對(duì)關(guān)鍵字進(jìn)行的操作(增加或者刪除).最后將關(guān)鍵字的更新DPDBup(w)存入更新服務(wù)器.

需要注意的是，在生成更新令牌時(shí)使用sw而不是dpw，因?yàn)閐pw在每次查詢(xún)后都會(huì)被置零，所以每次對(duì)于同一個(gè)關(guān)鍵字的更新會(huì)被放到相同位置上，泄露關(guān)鍵字的更新次數(shù).在生成索引時(shí)使用的是dpw，因?yàn)樵陉P(guān)鍵字的2次搜索之間，sw并沒(méi)有改變從而會(huì)產(chǎn)生位置沖突.因此在2次搜索間的所有更新，我們都可以使用相同的更新令牌進(jìn)行查詢(xún)，2次查詢(xún)之間的更新個(gè)數(shù)由dpw維持.

算法4.MDSSE.Search().

輸入：查詢(xún)令牌kw、kp，關(guān)鍵字長(zhǎng)度dlw、dpw，查詢(xún)列表SDB(w);

輸出：查詢(xún)結(jié)果EM.

步驟1)客戶(hù)端發(fā)送查詢(xún)令牌

客戶(hù)端：

① 從映射表中取出w的狀態(tài)(b,sw,dlw,dpw)

② forwinSDB(w) do

③tw←F(ks,h(w)‖sw‖b)；

④tp←F(ks,h(w)‖sw‖2)；

⑤ end for

⑥ 將(tw,dlw)發(fā)送到Sb，(tp,dpw)發(fā)送到Sup

步驟2)服務(wù)器進(jìn)行檢索

服務(wù)器Sb端：

① fori←0 todlwdo

②e←H(kw,i)；

③R←R∪{EDBb[e]}；/*R為存儲(chǔ)服務(wù)器端存放查詢(xún)結(jié)果的集合*/

④ end for

⑤ 將R發(fā)送回客戶(hù)端，從服務(wù)器端刪掉R

服務(wù)器Sup端：

① fori←0 todpwdo

②e←H(tp,i)；

③P←P∪{EDBup[e]}；

④ end for

⑤ 將P發(fā)送回客戶(hù)端，從服務(wù)器端刪掉P

步驟3)客戶(hù)端篩選并重新加密數(shù)據(jù)

客戶(hù)端：

①D,EM←{}/*存放下載的關(guān)鍵字文檔*/

② forC∈R∪Pdo：

③ (op,ind)←MDSSE.Dec(ku,c)；

④ ifop=“add” ∧ ind is valid then

⑤D←D∪{ind}；

⑥ elseD←D-{ind}；

⑦ end if

⑧ end for

⑨DPDBb⊕1←DPP(ε1,μ,d,D)；

⑩ forind∈DPDBb⊕1do

搜索算法描述為：

給定一個(gè)關(guān)鍵字w,去關(guān)鍵字狀態(tài)表中拿出參數(shù)b,sw,dlw，使用sw級(jí)聯(lián)與h(w)作為輸入，嵌入帶密鑰的PRF中生成查詢(xún)令牌kw，將生成的查詢(xún)令牌tw和差分長(zhǎng)度dlw一起送往Sb.更新服務(wù)器同理.

2個(gè)服務(wù)器各自根據(jù)傳遞過(guò)來(lái)的參數(shù)生成查詢(xún)的索引e，去對(duì)應(yīng)的位置取出密文放入P/R，其中P/R分別為存儲(chǔ)/更新服務(wù)器存放文檔標(biāo)識(shí)符的集合，之后將集合返回，將存儲(chǔ)在服務(wù)器端的密文刪除.

客戶(hù)端接收加密數(shù)據(jù)集后開(kāi)始解密，根據(jù)解密后操作符op對(duì)應(yīng)的是增加還是刪除判斷是否將其放入新的數(shù)據(jù)集EM中還是刪除，同時(shí)丟棄填充的虛擬標(biāo)識(shí)符.將解密后的數(shù)據(jù)進(jìn)行匯總再次使用DPP算法進(jìn)行填充得到新的DPDBb⊕1(w)，將其存入Sb+1中.

4 本文提出的方案分析

4.1 復(fù)雜度分析

在我們的方案中，客戶(hù)端需要存儲(chǔ)關(guān)鍵字的狀態(tài)信息，因此其客戶(hù)端存儲(chǔ)開(kāi)銷(xiāo)為O(|w|)，其中|w|表示關(guān)鍵字的數(shù)量.

服務(wù)器存儲(chǔ)開(kāi)銷(xiāo)為O(n×l+nw×μ)，其中n表示關(guān)鍵字的個(gè)數(shù)，l表示所有關(guān)鍵字對(duì)應(yīng)的平均文檔個(gè)數(shù)，nw表示關(guān)鍵字的數(shù)量，μ表示噪音的期望值.

在搜索和更新過(guò)程中，計(jì)算復(fù)雜度分別為O(dpnw)和O(1)，其中O(dpnw)是差分隱私保護(hù)了匹配關(guān)鍵字w之后搜索結(jié)果集的大小.通信復(fù)雜度分別為O(dpnw)和O(1).

4.2 容量泄露分析

首先證明方案的查詢(xún)更新操作同時(shí)滿(mǎn)足了差分隱私容量隱藏安全(下文簡(jiǎn)稱(chēng)差分隱藏).

關(guān)于查詢(xún)，假設(shè)第k個(gè)查詢(xún)開(kāi)始查詢(xún)到2個(gè)數(shù)據(jù)庫(kù)中不一樣的關(guān)鍵字.

關(guān)于搜索模式，方案也進(jìn)行了差分隱藏.搜索模式一般用于對(duì)2次查詢(xún)進(jìn)行匹配，在令牌層面，隨著查詢(xún)次數(shù)與服務(wù)器位置的變化，關(guān)鍵字查詢(xún)令牌也隨之改變，切斷了令牌之間的關(guān)聯(lián)性，此時(shí)唯一可能泄露搜索模式的信息來(lái)自查詢(xún)結(jié)果長(zhǎng)度.由于關(guān)鍵字的長(zhǎng)度使用DPP算法進(jìn)行填充，并且在每次搜索后為關(guān)鍵字賦予一個(gè)新噪聲，這使得服務(wù)器也無(wú)法通過(guò)2次查詢(xún)返回的長(zhǎng)度判斷是否是同一個(gè)關(guān)鍵字，實(shí)現(xiàn)了差分隱私的容量隱藏.因此本方案搜索模式的泄露也是差分隱私的，并且只額外泄露了關(guān)鍵字存放的服務(wù)器位置b.

4.3 安全性分析

MDSSE不僅提供了動(dòng)態(tài)可搜索加密方案滿(mǎn)足的前向安全與后向安全性，而且消除了更新泄露，提供了差分隱私安全的容量泄露，實(shí)現(xiàn)了搜索泄露的差分隱私隱藏，具有更加強(qiáng)大的安全特性.

在對(duì)方案的安全性進(jìn)行證明之前，需要對(duì)之前的更新歷史定義進(jìn)行改造，使其適應(yīng)提出的方案.基于此，我們引入了一個(gè)新的安全定義，稱(chēng)為差分隱私部分更新(Differential Privacy Partial Update,DP-Update).假設(shè)現(xiàn)在產(chǎn)生了一系列更新：(add,w1,ind1),(del,w1,ind1),(add,w1,ind3),(search,w1),(add,w1,ind4),(add,w1,dummy),search(w1)，其中dummy為差分隱私后對(duì)文檔標(biāo)識(shí)符進(jìn)行的補(bǔ)充.在時(shí)刻4和時(shí)刻7之間的差分更新歷史泄露為DP-Update(w1)={5，6}，并且更新長(zhǎng)度是經(jīng)過(guò)差分之后的，并不代表準(zhǔn)確的更新次數(shù).

定理1證明了MDSSE的自適應(yīng)安全性.

證明.

G0.我們將G0定義為真實(shí)世界中的實(shí)驗(yàn)Real.

G1.G1中不再使用偽隨機(jī)函數(shù)F生成令牌，而是使用隨機(jī)數(shù)代替，并將生成的隨機(jī)數(shù)與關(guān)鍵字存放在定義為T(mén)oken的數(shù)組中.由于偽隨機(jī)函數(shù)和真隨機(jī)函數(shù)的不可區(qū)分性，可知2個(gè)實(shí)驗(yàn)是不可區(qū)分的.

G2.G2中使用隨機(jī)字符串而不是調(diào)用哈希函數(shù)為關(guān)鍵字生成標(biāo)識(shí)符，并將其存在映射表H中.

G3.G3中將原先使用語(yǔ)義安全對(duì)稱(chēng)密鑰加密方案生成的密文替換為相同長(zhǎng)度的隨機(jī)字符串.由于加密方案的語(yǔ)義安全性，我們無(wú)法區(qū)分G2和G3.

G4.G4中不再保存關(guān)鍵字的狀態(tài)，而是將其輸入隨機(jī)預(yù)言機(jī)得到輸出，而是在搜索時(shí)隨機(jī)生成；在更新時(shí)使用數(shù)組U保存上次查詢(xún)之后的更新請(qǐng)求.由于更新時(shí)真隨機(jī)串與偽隨機(jī)串的不可區(qū)分性，無(wú)法區(qū)分G3和G4.

Simulator.在理想世界中，模擬器需要通過(guò)泄露函數(shù)來(lái)生成敵手所需要的視圖.初始化時(shí)，模擬器根據(jù)泄露長(zhǎng)度隨機(jī)生成DPNDb對(duì)隨機(jī)字符串上傳到服務(wù)器Sb.在搜索時(shí)，由于涉及2個(gè)服務(wù)器，需要各自為他們分配模擬器Simb以及Simb⊕1，用來(lái)模擬的各自視圖，由于2個(gè)服務(wù)器是非共謀的，他們可以獨(dú)立完成模擬而不進(jìn)行協(xié)同.

Simb⊕1生成|DPDB(w)|個(gè)隨機(jī)對(duì)上傳至服務(wù)器.對(duì)于Simb，客戶(hù)端使用泄露函數(shù)獲取關(guān)鍵字長(zhǎng)度，隨機(jī)生成kw后一起發(fā)送給服務(wù)器端.在進(jìn)行返回時(shí)，模擬器從泄露中取出DP-Update(w)，如果內(nèi)容為空，說(shuō)明之前從未被搜索過(guò)，那么隨機(jī)選擇|DPDB(w)|個(gè)隨機(jī)對(duì)；如果之前搜索過(guò)，根據(jù)泄露中的時(shí)間戳確定返回結(jié)果，對(duì)隨機(jī)語(yǔ)言機(jī)進(jìn)行編程，使未來(lái)的搜索結(jié)果相匹配.

算法5.模擬算法.

步驟1)初始化模擬算法：

① 初始化映射表EDB將其置為空;

③ fori←0 toDPNDb-1 do

④e←{0,1}l,v←{0,1}|v|;

⑤EDBb[e]←v;

⑥ end for

步驟2)查詢(xún)模擬算法：

客戶(hù)端：

②kw←{0,1}l,uw←|DPDB(w)|;

③ 將kw，uw發(fā)送到服務(wù)器端

服務(wù)器Sb端：

① (sp(w),TimeDB(w),DP-Update(w))

②e←{0,1}l,v←{0,1}|v|;

③EDB2[e]←v;

④ ifDP-Update(w) is null then

⑤ 從EDBb中隨機(jī)選取|DPDB(w)|項(xiàng)，將其放入數(shù)組E中;

⑥ else從數(shù)組E中取出DP-Update(w)時(shí)產(chǎn)生的更新;

⑦ end if

⑧ fori←0 toH(kw,i)←E[i] do

⑨ 使用編程RO：H(kw,i)←E[i] ;

⑩ end for

服務(wù)器Sb⊕1端：

接受從客戶(hù)端發(fā)來(lái)的EDB并保存.其中EDB是|DPDB(w)|對(duì)隨機(jī)字符串.

步驟3)更新模擬算法：

② fori←0 to {ind}i| do

③e←{0,1}l,v←{0,1}|v|;

④EDBb[e]←v;

⑤ end for

證畢.

5 實(shí)驗(yàn)分析

本節(jié)首先列舉出目前常用的3種填充方案，之后在相同的攻擊效果下將3種填充方式所需要的額外存儲(chǔ)進(jìn)行對(duì)比，實(shí)驗(yàn)證明我們的填充方式能夠在相同的安全效果下使用更少的存儲(chǔ).之后將我們的方案與其他使用差分隱私但實(shí)現(xiàn)方法不同的方案進(jìn)行性能上的比較.最后我們從采取另一種方法的方案中選擇了在各方面表現(xiàn)效果良好的CLRZ[34]方案進(jìn)行對(duì)比.

我們選用的3種填充方式分別為普通填充(將每個(gè)關(guān)鍵字長(zhǎng)度都填充到最大長(zhǎng)度)、可調(diào)節(jié)填充(每個(gè)關(guān)鍵字長(zhǎng)度都填充到離他最近的指數(shù)的冪)以及差分隱私填充(為關(guān)鍵字生成服從拉普拉斯分布的噪音).在可調(diào)節(jié)填充中我們將所有關(guān)鍵字填充到2的冪次，差分隱私填充中選擇的隱私預(yù)算和均值分別為1與3.實(shí)驗(yàn)結(jié)果如表2所示：

Table 2 Comparison of the Padding Rate of Three Padding Algorithms表2 3種填充算法的填充率對(duì)比

我們將這3種填充方式在不同數(shù)據(jù)規(guī)模下的全部數(shù)據(jù)與真實(shí)數(shù)據(jù)之比進(jìn)行計(jì)算.比率越大，說(shuō)明填充方法所需要的虛擬標(biāo)識(shí)越多.表格顯示，普通的填充雖然最安全，但是所需要的存儲(chǔ)與數(shù)據(jù)規(guī)模呈線(xiàn)性增長(zhǎng).可調(diào)節(jié)填充與差分隱私填充各有優(yōu)勢(shì)，可調(diào)節(jié)填充根據(jù)底數(shù)的選取將關(guān)鍵字分組，保護(hù)組內(nèi)關(guān)鍵字的安全性，因此保護(hù)效果更好，所需要的填充也更多.差分隱私保護(hù)關(guān)鍵字查詢(xún)敏感度內(nèi)相鄰的關(guān)鍵字，因此填充的數(shù)量更少.可以注意到DPP也可以通過(guò)對(duì)參數(shù)進(jìn)行修改達(dá)到可調(diào)節(jié)的目的.

截至目前，使用差分隱私實(shí)現(xiàn)容量隱藏的方案可分為2種：1)使用拉普拉斯機(jī)制為關(guān)鍵字生成噪音補(bǔ)充道原始的容量中，文獻(xiàn)[32]和本方案使用了這一方法.2)將訪問(wèn)模式表示成關(guān)于查詢(xún)與文檔標(biāo)識(shí)的矩陣，元素為1表示文檔與查詢(xún)相匹配.通過(guò)對(duì)矩陣中元素的隨機(jī)反轉(zhuǎn)生成混淆的訪問(wèn)模式進(jìn)行保護(hù)，文獻(xiàn)[34-35]均使用這一方法.我們將這4種方案的性能與安全性方面進(jìn)行對(duì)比，結(jié)果如表3所示，我們的方案能夠在動(dòng)態(tài)更新的同時(shí)提供更高的安全保障.

Table 3 Comparison of Four SSEschems Based on Dp表3 4種基于差分隱私的可搜索加密算法對(duì)比

下面將方案與CLRZ進(jìn)行比較：首先從功能性上進(jìn)行分析.CLRZ基于靜態(tài)設(shè)置，使用比特翻轉(zhuǎn)制造混淆訪問(wèn)模式，但他在使用的過(guò)程中引入了p(將包含關(guān)鍵字的文檔判斷為不包含的比率)與r(將不包含關(guān)鍵字的文檔判斷為包含的比率)，而p將會(huì)導(dǎo)致本應(yīng)該返回的文檔標(biāo)識(shí)符被過(guò)濾，降低了搜索的完整性與準(zhǔn)確性.我們?yōu)樵奸L(zhǎng)度添加噪音，增加了不包含關(guān)鍵字但仍然能被返回的幾率，并且我們的方案支持動(dòng)態(tài)的更新操作.

接下來(lái)對(duì)性能進(jìn)行分析.我們使用Python語(yǔ)言對(duì)算法進(jìn)行實(shí)現(xiàn)，運(yùn)行環(huán)境為Ubuntu18.04配置在Intel?CoreTMi7-10700 CPU@2.90 GHz,16 GB內(nèi)存中.使用Enron email dataset作為數(shù)據(jù)集，使用文獻(xiàn)[35]中的技巧對(duì)關(guān)鍵字進(jìn)行提取處理.每個(gè)實(shí)驗(yàn)結(jié)果均為實(shí)驗(yàn)重復(fù)100次后取平均值得到.

Fig. 1 Comparison of defensive capabilities for the two solutions圖1 2個(gè)方案的防御能力對(duì)比

我們將本方案(MDSSE)與CLRZ同時(shí)進(jìn)行計(jì)數(shù)攻擊，測(cè)試方案在攻擊下的防御程度.測(cè)試結(jié)果如圖1所示，實(shí)驗(yàn)表明在引入噪音后，MDSSE對(duì)攻擊的防御性能有了明顯的提升，這里的噪音量是對(duì)整個(gè)數(shù)據(jù)庫(kù)添加，原始數(shù)據(jù)長(zhǎng)度為1 378 473.由于CLRZ使用r添加噪音，因此我們將r換算成噪音量繪制了此圖.實(shí)驗(yàn)證明在添加的噪音增大時(shí)，我們的方案攻擊準(zhǔn)確率下降顯著.

在對(duì)不同容量的關(guān)鍵字進(jìn)行搜索時(shí)間統(tǒng)計(jì)后，結(jié)果如圖2所示.為了簡(jiǎn)化實(shí)驗(yàn)操作，減少實(shí)際文件檢索帶來(lái)的干擾，我們使用文件標(biāo)識(shí)符來(lái)代替文件進(jìn)行搜索.隨著搜索數(shù)量的增加，初始化生成索引的時(shí)間被平攤到后面每一個(gè)搜索結(jié)果中，因此，搜索結(jié)果數(shù)量越多，單個(gè)文檔的平均搜索時(shí)間越少，有利于搜索效率的提升.

Fig. 2 The serach time of MDSSE圖2 MDSSE的搜索時(shí)間

6 總結(jié)與未來(lái)展望

本文針對(duì)可搜索加密中一個(gè)重要的泄露模式-容量泄露進(jìn)行了討論，并提出了改進(jìn)的填充模式，在節(jié)約內(nèi)存的情況下保證了安全性，之后將其部署在動(dòng)態(tài)環(huán)境中，提出了一個(gè)新的DSSE方案MDSSE.我們的方案在提供更新的同時(shí)保證了前向安全和后向安全.最后我們給出了方案的安全性證明，并對(duì)其進(jìn)行了性能評(píng)估，證明我們的方案能夠在保證安全性的情況下具有更好的存儲(chǔ)和效率.

需要注意的是，MDSSE支持單用戶(hù)的對(duì)稱(chēng)加密搜索與更新操作，下一步我們打算將其推廣到多用戶(hù)搜索模式下，并且壓縮由此產(chǎn)生的額外的查詢(xún)泄露，應(yīng)用到更加廣泛的場(chǎng)景之中的同時(shí)保證安全性.