基于循環(huán)加密鏈的高效動(dòng)態(tài)可搜索對(duì)稱加密方案*

陳海龍, 馬昌社

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

1 引言

目前, 基于云服務(wù)器的數(shù)據(jù)外包技術(shù)是解決用戶本地資源開銷的重要技術(shù). 數(shù)據(jù)外包不僅可以節(jié)省用戶的本地存儲(chǔ)資源開銷, 而且可以讓用戶在任意時(shí)刻和任意地點(diǎn)都能從云服務(wù)器獲取數(shù)據(jù). 然而在大部分情況下云存儲(chǔ)服務(wù)器是不可信的, 用戶普遍的做法是將自己的數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)加密處理后上傳, 但是經(jīng)過標(biāo)準(zhǔn)加密算法處理后的數(shù)據(jù)不支持高效查找. 為了解決加密數(shù)據(jù)的高效查找問題, 可搜索加密(searchable encryption, SE) 應(yīng)運(yùn)而生. 可搜索對(duì)稱加密(searchable symmetric encryption, SSE) 方案一般采用分別加密索引和文檔數(shù)據(jù)的方法實(shí)現(xiàn). SSE 方案的查詢流程如下: 用戶使用查詢令牌從加密索引數(shù)據(jù)表中查詢獲取指向加密文檔數(shù)據(jù)的索引, 然后通過這個(gè)索引查詢加密數(shù)據(jù)表以獲取文檔數(shù)據(jù). SSE 方案不泄露真實(shí)文檔數(shù)據(jù)的內(nèi)容, 且盡可能少地泄露信息, 同時(shí)具有良好的搜索性能. 將大部分早期的靜態(tài)SSE 方案簡單地修改為支持動(dòng)態(tài)更新的方案會(huì)導(dǎo)致額外的信息泄露. 為了減少動(dòng)態(tài)更新帶來的泄露, 前向安全成為動(dòng)態(tài)可搜索對(duì)稱加密(dynamic searchable symmetric encryption, DSSE) 方案必不可少的前提條件之一.

前向安全, 又稱前向隱私, 下文統(tǒng)一稱為前向安全, 是指新增文檔不能泄露它所包含的關(guān)鍵字. 換句話說, 使用舊的查詢令牌無法查詢出在這個(gè)查詢時(shí)間點(diǎn)后更新的所有文檔, 只有用新生成的查詢令牌才能關(guān)聯(lián)最新的文檔. 盡管在密碼學(xué)領(lǐng)域, 前向安全并不是一個(gè)新概念, 但是早期的動(dòng)態(tài)可搜索對(duì)稱加密方案[1]沒有實(shí)現(xiàn)前向安全. Islam 等人[2]和Cash 等人[3]研究了利用SSE 方案泄露的攻擊, 并且他們的研究表明即使是很小的泄露也可以被攻擊者所利用去恢復(fù)用戶的查詢. 他們的攻擊不僅僅只是針對(duì)靜態(tài)SSE 方案, 而且對(duì)DSSE 方案也有效, 在服務(wù)器可以添加新文檔到數(shù)據(jù)庫的情況下, 服務(wù)器能夠獲取更多信息, 使其在攻擊中更具優(yōu)勢(shì). 在2016 年的Usenix 安全會(huì)議上, Zhang 等人[4]提出了文檔注入攻擊, 在可以向數(shù)據(jù)庫注入文檔的場景(如郵件交互) 中, 該攻擊通過利用SSE 方案的訪問模式(access pattern) 泄露和返回的注入文檔, 可以精確地恢復(fù)用戶查詢的關(guān)鍵字. 文獻(xiàn)[4] 指出, 文檔注入攻擊是自適應(yīng)的, 這表明該攻擊對(duì)沒有滿足前向安全的方案非常有效, 只需注入少量文檔(約小于100 個(gè)文檔) 就可以精確恢復(fù)查詢令牌所對(duì)應(yīng)的明文關(guān)鍵字. SSE 方案的前向安全屬性不僅僅能提升安全性, 還能提升初始化效率. 大多數(shù)靜態(tài)SSE 方案需要在初始化階段構(gòu)建加密索引表, 這個(gè)階段占用較多資源且無法提供搜索服務(wù). 因?yàn)闈M足前向安全的DSSE 方案允許實(shí)時(shí)構(gòu)建加密數(shù)據(jù)庫, 從而避免低效率的初始化流程, 實(shí)現(xiàn)動(dòng)態(tài)更新且不中斷搜索服務(wù).

現(xiàn)有的許多滿足前向安全的DSSE 方案仍存在各種各樣的缺陷. Song 等人[5]的方案通過在服務(wù)器緩存查詢關(guān)鍵字在上一次查詢后返回的結(jié)果集, 從而提升方案的搜索性能, 但是以明文形式存儲(chǔ)搜索結(jié)果集可能泄露了更多信息, 比如直接泄露兩個(gè)關(guān)鍵字的文檔交集信息; Etemad 等人[6]的方案使用只含存儲(chǔ)功能的服務(wù)器作為服務(wù)端, 所有的計(jì)算操作都在客戶端處完成, 雖然滿足前向安全, 但是引入較高的通信開銷和客戶端計(jì)算開銷.

本文首先提出了一個(gè)新的密碼學(xué)原語循環(huán)加密鏈, 并基于該原語設(shè)計(jì)了一個(gè)支持前向安全的高效動(dòng)態(tài)可搜索對(duì)稱加密方案ECDSSE (encrypted chain DSSE). 該方案的目標(biāo)為在保證前向安全的前提條件下,提高搜索效率, 同時(shí)盡可能地減少客戶端存儲(chǔ)開銷. 首先給出了循環(huán)加密鏈的形式化定義和通用構(gòu)造方法,然后證明ECDSSE 方案在誠實(shí)且好奇的攻擊模型下具有語義安全. 最后實(shí)現(xiàn)多個(gè)滿足前向安全的DSSE方案并與ECDSSE 方案進(jìn)行性能對(duì)比分析.

各方案的理論性能對(duì)比情況如表1 所示. 其中W表示所有關(guān)鍵字的集合,|W| 表示關(guān)鍵字集合中不重復(fù)關(guān)鍵字的個(gè)數(shù), logM表示搜索令牌的比特長度, 按常見的AES 算法實(shí)現(xiàn)來計(jì)算, 該比特長度一般為128 個(gè)比特. logC和logD分別代表搜索次數(shù)和更新次數(shù)的計(jì)數(shù)器比特長度, 以C++ 的整型為例,在64 位計(jì)算機(jī)中整型大小占32 個(gè)比特.aw代表關(guān)鍵字w的總更新次數(shù),nw代表關(guān)鍵字w的搜索結(jié)果集合中元素的數(shù)量. 雖然更新效率和搜索效率理論性能是總體一致的, 但是在具體算法中, FAST 方案使用了更多的加解密操作或哈希操作, 這導(dǎo)致了搜索和更新性能的下降. BESTIE 方案雖然在搜索效率和更新效率上與本文方案ECDSSE 不相上下, 但是在理論存儲(chǔ)開銷上比ECDSSE 方案多了50%.

表1 三種DSSE 方案的理論性能對(duì)比Table 1 Theoretical performance among three DSSE schemes

2 相關(guān)工作

在2000 年的S&P 安全會(huì)議上, Song 等人[8]首先提出實(shí)用可搜索加密的概念, 該文獻(xiàn)指出可搜索加密方案的目標(biāo)是在搜索效率、擴(kuò)展性以及安全性上取得平衡, 并提出第一個(gè)基于流密碼的可搜索加密方案SWP; 在2006 年的CCS 安全會(huì)議上, Curtmola 等人[9]提出了第一個(gè)基于倒排索引構(gòu)造的SSE 方案的通用安全定義, 并設(shè)計(jì)了滿足自適應(yīng)IND2-CKA (indistinguishability against chosen-keyword attacks)安全定義的SSE 方案; Chase 等人[10]將SSE 方案的索引表結(jié)構(gòu)抽象為一個(gè)多映射(multi-map, MM),并提出了結(jié)構(gòu)化加密的概念; 為了拓展更多特性, Cash 等人[11]提出一個(gè)支持在大規(guī)模數(shù)據(jù)集上進(jìn)行聯(lián)合查詢及布爾查詢的靜態(tài)SSE 方案OXT, 解決了在大規(guī)模數(shù)據(jù)集上進(jìn)行高效多關(guān)鍵字查詢的問題; Ma等人[12]在OXT 方案的基礎(chǔ)上, 提出了子集成員查詢的密碼學(xué)原語及其通用構(gòu)造方法, 并基于該原語來解決多關(guān)鍵字查詢中存在的關(guān)鍵字對(duì)結(jié)果模式(keyword-pair result pattern, KPRP) 泄露問題; Sun 等人[13]根據(jù)RSA 函數(shù)的特點(diǎn)設(shè)計(jì)了一個(gè)支持非交互式和多用戶特性的SSE 方案, 解決了多用戶方案中數(shù)據(jù)擁有者與客戶端用戶交互的隱私泄露問題; 楊旸等人[14,15]使用Simhash 的方法實(shí)現(xiàn)一個(gè)支持模糊查詢功能的可搜索加密方案, 并且將域加權(quán)評(píng)分、語義相似度和相關(guān)度分?jǐn)?shù)三者結(jié)合構(gòu)造更準(zhǔn)確的多關(guān)鍵字語義排序搜索方案; 盧冰潔等人[16]使用名為狀態(tài)鏈的數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)支持多用戶特性的前向安全DSSE 方案; 劉翔宇等人[17]結(jié)合可搜索加密和屬性加密算法, 提出一種多訪問級(jí)別的動(dòng)態(tài)云存儲(chǔ)方案; 孫僖澤等人[18]提出一個(gè)基于可搜索加密機(jī)制的數(shù)據(jù)庫加密方案, 將可搜索加密機(jī)制應(yīng)用到現(xiàn)實(shí)數(shù)據(jù)庫中.

然而, 靜態(tài)SSE 方案不能滿足現(xiàn)實(shí)用戶動(dòng)態(tài)更新數(shù)據(jù)的需求. 為了使SSE 方案更具實(shí)用性, Kamara 等人[1]首先提出了支持動(dòng)態(tài)可搜索對(duì)稱加密的方案, 雖然他們的方案實(shí)現(xiàn)了次線性級(jí)別的搜索效率, 但是刪除和增加操作需要較高的復(fù)雜度; Stefanov 等人[19]首先提出了可搜索加密領(lǐng)域的前向安全的概念, 他們基于層次茫然隨機(jī)訪問內(nèi)存[20](obilivious random acess memory, ORAM) 構(gòu)造設(shè)計(jì)了一個(gè)滿足前向安全的DSSE 方案, 該方案雖然滿足前向安全的定義, 但是同時(shí)引入了較高的通信開銷; 直到2016 年, Bost 等人[21]形式化定義前向安全的概念, 并提出了一個(gè)基于公鑰密碼學(xué)原語構(gòu)造的高效DSSE 方案. 近年來, Bost 等人[22]提出一個(gè)基于受限偽隨機(jī)函數(shù)(constraint pseudorandom function, CPRF) 構(gòu)造的前向安全方案Diana, 使用對(duì)稱密鑰原語替代公鑰密碼學(xué)原語來實(shí)現(xiàn)前向安全;Song 等人[5]提出了基于緩存機(jī)制的前向安全方案FASTIO, 提高了DSSE 方案的I/O 效率; Etemad 等人[6]提出一個(gè)基于只作存儲(chǔ)的服務(wù)器的前向安全方案, 減少了給服務(wù)器的信息泄露; He 等人[23]提出一個(gè)基于魚骨鏈構(gòu)造的前后向安全DSSE 方案, 該方案將客戶端存儲(chǔ)減少至常數(shù)級(jí)別, 但是引入了更新次數(shù)的限制, 實(shí)用性有限; Chen 等人[7]提出一個(gè)滿足前后向安全的基于緩存機(jī)制的DSSE 方案BESTIE, 他們將緩存機(jī)制應(yīng)用在后向安全的方案中, 提升刪除操作的性能. 上述方案存在各種各樣的缺陷, 與這些方案相比, 本文提出的基于循環(huán)加密鏈的ECDSSE 方案在滿足前向安全的前提下, 具有更高的搜索效率.

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

本節(jié)給出DSSE 方案的定義以及本文用到的密碼學(xué)原語, 并對(duì)文中使用的符號(hào)進(jìn)行說明.

3.1 符號(hào)說明

在本節(jié)里, 本文將對(duì)所使用的符號(hào)進(jìn)行說明. 將x$←X看作從一個(gè)集合X均勻隨機(jī)采樣獲得一個(gè)樣本x.x ←D代表從分布D中抽樣出一個(gè)樣本x. 設(shè)P(·) 為概率多項(xiàng)式時(shí)間(probabilistic polynominal time algorithm, PPT) 算法.p ←P(·) 表示算法P(·) 的輸出賦值給變量p. 設(shè)S為集合或字符串,|S| 表示集合S的基數(shù), 笛卡爾積Sn={(s1,s2,··· ,sn)|si ∈S,i= 1,2,··· ,n}. 對(duì)于向量、列表或鏈表v,v[i] 代表v的第i個(gè)分量. 假設(shè)a和b是正整數(shù), 且a ＜b, 令[a,b] ={a,a+1,··· ,b}, [a] = [1,a].對(duì)于兩個(gè)字符串S1和S2,S1||S2代表S1與S2進(jìn)行拼接. 對(duì)于函數(shù)negl(λ) :Z →(0,1), 如果對(duì)于任意的正多項(xiàng)式p(·), 都存在正整數(shù)N0, 使得對(duì)于任意的λ ＞N0, 都有negl(λ)＜1/p(λ) 成立, 那么我們說negl(λ) 是可忽略函數(shù). 令?表示空集或空字符串,⊥表示一個(gè)空值符號(hào), poly(·) 代表一個(gè)多項(xiàng)式函數(shù),代表該函數(shù)能在多項(xiàng)式時(shí)間內(nèi)執(zhí)行.

3.2 IND-CPA 安全的對(duì)稱加密方案

(1) 挑戰(zhàn)者C調(diào)用算法Gen(1λ) 生成一個(gè)隨機(jī)密鑰K.

(2) 敵手A選擇兩個(gè)相同大小的消息對(duì)m0和m1, 發(fā)送給挑戰(zhàn)者C.

(3) 挑戰(zhàn)者C選擇一個(gè)隨機(jī)比特b ←{0,1}, 計(jì)算密文c ←Enc(K,mb) 并將密文c返回給敵手A.(4) 敵手A根據(jù)返回的密文c, 輸出判斷值比特b′.

(5) 實(shí)驗(yàn)的輸出定義為: 當(dāng)b=b′時(shí)實(shí)驗(yàn)輸出1, 否則輸出0.

稱對(duì)稱加密方案Σ 具有IND-CPA 安全, 如果對(duì)任意PPT 敵手A, 存在一個(gè)可忽略函數(shù)negl(λ), 有以下不等式成立:

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

定義2[25]令F:{0,1}λ×{0,1}n →{0,1}n表示一個(gè)函數(shù)族, 其中{0,1}λ表示密鑰空間, 定義域和值域都是{0,1}n. 稱F是一個(gè)偽隨機(jī)函數(shù)(pseudorandom function, PRF), 如果對(duì)于任意PPT 區(qū)分器D, 存在一個(gè)可忽略函數(shù)negl(λ), 有以下不等式成立:

其中, 密鑰k$←{0,1}λ, 函數(shù)f從映射n比特字符串到n字符串的函數(shù)集合中隨機(jī)均勻選擇.

3.4 動(dòng)態(tài)可搜索對(duì)稱加密

一般地, 動(dòng)態(tài)可搜索對(duì)稱加密方案由一個(gè)初始化算法Setup 和兩個(gè)交互式協(xié)議Update、Search 組成.以下是DSSE 方案的形式化定義:

定義3[26]給定安全參數(shù)λ, DSSE 方案Π = (Setup,Update,Search) 由初始化算法Setup、更新協(xié)議Update 和搜索協(xié)議Search 組成. 方案的一般流程如下所示:

(1) ((K,σ);EDB)←Setup((λ,DB);⊥): 系統(tǒng)初始化算法, 該算法主要在客戶端處執(zhí)行. 客戶端輸入一個(gè)明文數(shù)據(jù)庫DB 和一個(gè)安全參數(shù)λ; 服務(wù)器端沒有輸入. 該算法輸出一個(gè)主密鑰K、狀態(tài)σ以及一個(gè)加密后的密文數(shù)據(jù)庫EDB, 其中客戶端存儲(chǔ)主密鑰K和狀態(tài)σ, 服務(wù)器存儲(chǔ)密文數(shù)據(jù)庫EDB.

(2) (σ′;EDB′)←Update((K,σ,op,w,id);EDB): 更新協(xié)議, 該協(xié)議在客戶端和服務(wù)器之間交互進(jìn)行. 客戶端輸入一個(gè)主密鑰K、狀態(tài)σ、一個(gè)文檔id、關(guān)鍵字w以及更新操作符op; 服務(wù)器輸入密文數(shù)據(jù)庫EDB. 其中, 更新操作符op 從集合{add,del}中選擇, 即客戶端只能執(zhí)行增加或刪除(文檔, 關(guān)鍵字) 鍵值對(duì)的操作. 更新協(xié)議結(jié)束后客戶端更新狀態(tài)σ為σ′, 服務(wù)器更新密文數(shù)據(jù)庫EDB 為EDB′.

(3) ((σ′,DB(w));EDB′)←Search((K,σ,w);EDB): 搜索協(xié)議, 該協(xié)議在客戶端和服務(wù)器之間交互進(jìn)行. 客戶端輸入一個(gè)主密鑰K、狀態(tài)σ和要查詢的關(guān)鍵字w; 服務(wù)器輸入一個(gè)密文數(shù)據(jù)庫EDB. 搜索協(xié)議結(jié)束后, 客戶端輸出關(guān)鍵字w的搜索結(jié)果集合DB(w) 并可能更新狀態(tài)σ為σ′, 服務(wù)器可能更新密文數(shù)據(jù)庫EDB 為EDB′.

DSSE 方案的安全性要求敵手盡可能少地了解數(shù)據(jù)庫內(nèi)容和查詢信息, 更準(zhǔn)確地說, 用戶并不希望敵手能夠獲取除了方案允許的泄露之外的任何信息. 為了更好的描述DSSE 方案的安全性, 我們使用理想世界和真實(shí)世界的游戲?qū)ζ溥M(jìn)行形式化的描述.

定義4[26]給定DSSE 方案Π = (Setup,Update,Search),A為任意PPT 敵手,S為以泄露函數(shù)L=(LSetup,LUpdate,LSearch) 作輸入的仿真器. 對(duì)于DSSE 方案Π 的證明通常需要定義兩個(gè)游戲, 一個(gè)游戲RealΠA(λ) 代表協(xié)議的真實(shí)執(zhí)行, 另一個(gè)游戲IdealΠA,S(λ) 由仿真器以泄露函數(shù)L作為輸入模擬生成. 如果敵手無法區(qū)分自己是在哪個(gè)游戲中, 則表明敵手不掌握額外的知識(shí), 即證明方案沒有造成除了泄露函數(shù)描述之外的其他任何泄露, 具體地, 兩個(gè)游戲的定義如圖1 所示:

圖1 DSSE 方案Π 的兩個(gè)安全游戲Figure 1 Two secure games in DSSE scheme Π

其中, stA表示敵手A的狀態(tài), stS表示仿真器S的狀態(tài),K為DSSE 方案的主密鑰,k表示查詢次數(shù), 是關(guān)于λ的多項(xiàng)式poly(λ), (ti)1≤i≤k表示第i次(更新/搜索) 查詢時(shí)客戶端發(fā)送給服務(wù)器的消息(t0=?), (EDBi)0≤i≤k表示第i次查詢時(shí)的加密數(shù)據(jù)庫, (σi)1≤i≤k表示第i次查詢時(shí)客戶端狀態(tài),(typei,idi,wi,DB(wi),opi)1≤i≤k分別表示第i次查詢時(shí)的查詢類型(更新/搜索)、文檔標(biāo)識(shí)符、關(guān)鍵字、關(guān)鍵字wi的查詢結(jié)果和更新操作符,LSetup(DB)、LUpdate(op,w,id) 和LSearch(w) 分別表示Setup 算法、Update 協(xié)議和Search 協(xié)議的泄露函數(shù).

如果對(duì)于任意PPT 敵手A, 存在一個(gè)PPT 仿真器S滿足以下條件:

則稱DSSE 方案Π 具有L-自適應(yīng)安全.

3.5 前向安全

前向安全是指新添加一個(gè)文檔后, 該新添加文檔對(duì)應(yīng)的關(guān)鍵字信息在下一次搜索查詢前不會(huì)被泄露給敵手. 如果更新查詢不會(huì)泄露正在更新的(關(guān)鍵字, 文檔) 對(duì)中的關(guān)鍵字信息, 則DSSE 方案具有前向安全. 形式化定義如下:

定義5 本文使用文獻(xiàn)[21] 的形式化定義. 如果方案Π 的更新泄露函數(shù)LUpdate可以寫為如下形式:

則稱DSSE 方案Π 具有前向安全, 其中input 表示更新操作的輸入, 在方案中通常為(w,id) 鍵值對(duì),op 表示更新操作符, idi代表第i個(gè)更新文檔標(biāo)識(shí)符,|Wid| 表示文檔標(biāo)識(shí)符id 匹配的所有關(guān)鍵字個(gè)數(shù),L′是無狀態(tài)函數(shù).

4 循環(huán)加密鏈

本節(jié)提出循環(huán)加密鏈(circular encrypted chain, CEC) 的定義和安全性分析, 并給出通用的構(gòu)造方法及一個(gè)基于哈希函數(shù)構(gòu)造的CEC 方案的定義及安全性證明.

為了更好地理解循環(huán)加密鏈, 本節(jié)首先描述靜態(tài)SSE 方案的基本流程, 簡單的流程如下:

(1) 初始化算法Setup 主要由客戶端執(zhí)行. 算法輸入數(shù)據(jù)集和安全參數(shù), 輸出加密數(shù)據(jù)集、加密索引集和密鑰. 具體流程為: 客戶端將明文數(shù)據(jù)集拆分成(w,id) 和(id,file) 兩種鍵值對(duì)的形式, 即數(shù)據(jù)庫可以分為索引和文檔數(shù)據(jù)兩部分, 分別加密后上傳到服務(wù)器, 其中w表示關(guān)鍵字, id 表示文檔標(biāo)識(shí)符, file 表示真實(shí)文檔.

(2) 搜索協(xié)議Search 由客戶端和服務(wù)器交互進(jìn)行. 算法輸入關(guān)鍵字和密文數(shù)據(jù)集, 輸出搜索結(jié)果集.具體流程為: 客戶端根據(jù)需要查詢的關(guān)鍵字w生成搜索令牌, 服務(wù)端使用該令牌檢索鍵值對(duì)存儲(chǔ)數(shù)據(jù)庫, 將檢索到的對(duì)應(yīng)的加密文檔標(biāo)識(shí)符結(jié)果集返回給客戶端, 客戶端解密獲得文檔標(biāo)識(shí)符集合, 最后通過文檔標(biāo)識(shí)符從服務(wù)器獲取對(duì)應(yīng)的加密文檔集合.

簡單地改動(dòng)上述常見的靜態(tài)SSE 方案為支持動(dòng)態(tài)更新的SSE 方案會(huì)泄露更多信息, 因?yàn)樵趫?zhí)行了搜索操作后, 服務(wù)器將擁有該查詢關(guān)鍵字的搜索令牌, 如果數(shù)據(jù)擁有者基于該搜索令牌進(jìn)行數(shù)據(jù)更新, 那么服務(wù)器將立刻得知該關(guān)鍵字對(duì)應(yīng)的文檔獲得了更新, 在某些特定場景中服務(wù)器可利用該信息準(zhǔn)確恢復(fù)該令牌對(duì)應(yīng)的關(guān)鍵字. 以中秋節(jié)為例, 許多用戶會(huì)在中秋節(jié)當(dāng)天更新與中秋節(jié)相關(guān)的數(shù)據(jù), 服務(wù)器可以根據(jù)統(tǒng)計(jì)數(shù)據(jù)準(zhǔn)確推斷出中秋節(jié)等關(guān)鍵字對(duì)應(yīng)的搜索令牌和數(shù)據(jù)位置信息. 為了在減輕該類信息泄露影響的同時(shí)保證搜索效率, 前向安全成為DSSE 方案中必不可少的前提條件之一.

文獻(xiàn)[21] 的前向安全定義表明, 查詢之間發(fā)生的更新與前一個(gè)查詢的查詢陷門沒有關(guān)聯(lián)關(guān)系. 因此,滿足前向安全的關(guān)鍵在于找到一個(gè)切斷前后查詢關(guān)聯(lián)的方法, 以此實(shí)現(xiàn)客戶端能根據(jù)舊狀態(tài)生成新狀態(tài),而服務(wù)端無法從舊狀態(tài)生成新狀態(tài)的目標(biāo). 單向陷門置換函數(shù)是一種可以輕易進(jìn)行正向計(jì)算, 但在缺少陷門信息的情況下很難求逆的函數(shù), 這種函數(shù)能夠滿足前向安全的要求. Bost 等人[21]的方案使用基于公鑰的單向陷門置換函數(shù)(如RSA 等) 來實(shí)現(xiàn)前向安全, 雖然該方案滿足前向安全, 但是基于公鑰密碼學(xué)原語構(gòu)造的方案存在計(jì)算開銷較大的問題, 實(shí)用性較差. 隨后Song 等人[5]和Etemad 等人[6]嘗試基于對(duì)稱密碼學(xué)原語構(gòu)造方案, 避免公鑰體系的高計(jì)算開銷, 提升方案搜索性能.

我們實(shí)現(xiàn)前向安全的想法來源于哈希鏈. 在密碼學(xué)中, 哈希鏈?zhǔn)侵钢貜?fù)使用同一個(gè)哈希函數(shù)對(duì)由該函數(shù)生成的哈希值進(jìn)行哈希運(yùn)算, 最終生成的一系列哈希值. 哈希函數(shù)具有單向性, 敵手無法在多項(xiàng)式時(shí)間內(nèi)通過哈希函數(shù)的結(jié)果推導(dǎo)出哈希函數(shù)的原像. 只要DSSE 方案每次更新都從后往前使用前一個(gè)哈希值進(jìn)行哈希運(yùn)算, 由于哈希函數(shù)的單向性, 方案自然滿足前向安全. 具體來說, 客戶端選擇一個(gè)初始化密鑰K0←{0,1}λ, 然后通過安全哈希函數(shù)生成其他密鑰, 即Ki+1←H(Ki),0≤i ＜L. 在客戶端進(jìn)行查詢時(shí), 客戶端通過上傳一個(gè)中間密鑰Ki到服務(wù)器, 服務(wù)器可以從Ki開始一直計(jì)算哈希值Ki+1←H(Ki),直到獲得最終的密鑰Kn. 由于哈希函數(shù)的單向性, 服務(wù)器無法通過Ki計(jì)算出Ki-1, 因此哈希鏈滿足前向安全. 然而, 哈希鏈方案有著致命的缺點(diǎn), 它不僅需要客戶端存儲(chǔ)所有的更新狀態(tài), 還要在一開始就固定更新次數(shù), 這對(duì)于現(xiàn)實(shí)數(shù)據(jù)庫和有存儲(chǔ)空間限制的用戶設(shè)備來說都是不可接受的.

針對(duì)哈希鏈的缺點(diǎn), 本文提出了對(duì)稱循環(huán)加密鏈的新原語. 循環(huán)加密鏈將DSSE 的倒排索引表的每一行抽象成一個(gè)鏈表, 一個(gè)以頭插法進(jìn)行插入的鏈表. 循環(huán)加密鏈的思想可以用帶鑰匙的有鎖盒子來解釋.以Alice 和Bob 的交互進(jìn)行舉例說明, 假設(shè)每一個(gè)帶鎖的盒子都有它對(duì)應(yīng)的一把鑰匙, 最開始Alice 將信息存在第一個(gè)帶鎖的盒子里, 它繼續(xù)添加新信息的時(shí)候, 需要再用一個(gè)新的帶鎖的盒子將新信息裝進(jìn)去,同時(shí)將第一個(gè)盒子的鑰匙也放進(jìn)去一起鎖住, 以此類推, 最后將倒數(shù)第二個(gè)盒子的鑰匙和新添加的信息放入最后一個(gè)盒子中, 使用最后一個(gè)盒子的鑰匙鎖起來, 把所有更新的盒子全交給Bob. 當(dāng)Alice 需要查詢信息時(shí), 將這個(gè)最新的盒子的鑰匙給了Bob, Bob 才能夠依次解開每一個(gè)盒子, 拿出里面的信息給Alice,在此之前, Bob 并不知道每一個(gè)盒子間的關(guān)系, 也無法得知盒子內(nèi)的鑰匙和信息內(nèi)容. 換句話說, 用戶可以通過在客戶端本地即時(shí)計(jì)算一個(gè)新的密鑰Kn, 將這個(gè)密鑰通過IND-KDM 安全的對(duì)稱加密算法恢復(fù)舊的密鑰Kn-1, 但是通過這個(gè)舊的密鑰Kn-1是無法推導(dǎo)出新的密鑰Kn的, 這樣就滿足了前向安全的定義. 如圖2 所示, 循環(huán)加密鏈輸入一系列密鑰的集合K={K0,K1,··· ,Kn}, 使用IND-KDM 安全的對(duì)稱加密方案(KG,E,D), 調(diào)用對(duì)稱加密算法E, 用密鑰K1加密密鑰K0獲得密文e1, 即e1=E(K1,K0),用密鑰K2加密密鑰K1獲得密文e2, 以此類推, 最終獲取一系列密文的集合E={e1,e2,··· ,en}. 對(duì)應(yīng)的解密流程如圖3 所示, 輸入密文集合E, 使用一個(gè)最新的密鑰Kn進(jìn)行循環(huán)解密, 調(diào)用對(duì)稱解密算法D,用密鑰Kn解密密文en獲得密鑰Kn-1, 即Kn-1=D(Kn,en), 以此類推, 獲得一系列解密的密鑰集合K={K0,K1,··· ,Kn}. 同時(shí), 因?yàn)檠h(huán)加密鏈?zhǔn)且粋€(gè)從頭部插入新結(jié)點(diǎn)的鏈表, 通過使用每次更新中本地計(jì)算的新密鑰加密之前的密鑰, 將加密的值插入到鏈表頭部, 通過新密鑰解密該值恢復(fù)之前的密鑰結(jié)點(diǎn). 只要密鑰生成算法由用戶執(zhí)行, 用戶就可以將更新次數(shù)擴(kuò)展為無限次, 從而避免哈希鏈需要固定更新次數(shù)的缺點(diǎn).

圖2 循環(huán)加密鏈加密流程示意圖Figure 2 Presentation of encryption in circular encrypted chain

圖3 循環(huán)加密鏈解密流程示意圖Figure 3 Presentation of decryption in circular encrypted chain

4.1 循環(huán)加密鏈及其安全的形式化定義

定義6 循環(huán)加密鏈方案ΠCEC= (KG,E,D,KGCEC,ECEC,DCEC) 由SKE 密鑰生成算法KG、SKE 對(duì)稱加密算法E、SKE 對(duì)稱解密算法D、循環(huán)密鑰生成算法KGCEC、循環(huán)密鑰加密算法ECEC和循環(huán)密鑰解密算法DCEC組成. 以下是方案的具體內(nèi)容:

(1)K ←KG(λ): 密鑰生成算法. 算法輸入一個(gè)安全參數(shù)λ, 輸出一個(gè)密鑰K.

(2)C ←E(K,M): 對(duì)稱加密算法. 算法輸入一個(gè)密鑰K和一個(gè)明文消息M, 輸出一個(gè)密文C.

(3)M ←D(K,C): 對(duì)稱解密算法. 算法輸入一個(gè)密鑰K和一個(gè)密文C, 輸出一個(gè)明文M.

(4)K ←KGCEC(λ,n): 循環(huán)密鑰生成算法. 算法輸入安全參數(shù)λ和一個(gè)正整數(shù)n, 生成有n+1 個(gè)不同密鑰的集合K={K0,K1,··· ,Kn}.

(5)E ←ECEC(K): 循環(huán)密鑰加密算法. 算法輸入由算法KGCEC生成的有n+1 個(gè)不同密鑰的集合K, 用密鑰K1來加密密鑰K0得到密文e1, 即e1=E(K1,K0), 接著繼續(xù)用密鑰K2來加密密鑰K1得到密文e2, 以此類推, 直到用最后一個(gè)密鑰Kn加密密鑰Kn-1得到密文en, 最終輸出一個(gè)密文集合E={e1,e2,··· ,en}.

(6)K ←DCEC(Kn,E): 循環(huán)密鑰解密算法. 算法輸入密鑰Kn和密文集合E, 用密鑰Kn來解密密文en得到密鑰Kn-1, 即Kn-1=D(Kn,en), 接著繼續(xù)用密鑰Kn-1來解密密文en-1得到密鑰Kn-2, 以此類推, 直到用最后一個(gè)密鑰K1解密密文e1得到密鑰K0, 最終輸出一個(gè)密鑰集合K={K0,K1,··· ,Kn}.

我們說ΠCEC方案具有計(jì)算正確性, 如果對(duì)于任意的安全參數(shù)λ和任意由密鑰生成算法KGCEC生成的一系列密鑰的集合K, 按順序執(zhí)行循環(huán)加密算法E ←ECEC(K), 然后執(zhí)行循環(huán)解密算法K′←DCEC(Kn,E), 有K′=K, 否則K′/=K.

為了分析循環(huán)加密鏈方案的安全性, 對(duì)于方案ΠCEC= (KG,E,D,KGCEC,ECEC,DCEC), 用泄露函數(shù)LΠCEC表示PPT 敵手A能夠從密鑰集K的加密結(jié)果密文鏈集合E中獲取到的信息.

接下來定義循環(huán)加密鏈方案的安全定義.

如果對(duì)于任意PPT 算法A, 存在

則稱循環(huán)加密鏈方案ΠCEC在自適應(yīng)攻擊下具有IND-KDM 安全.

4.2 循環(huán)加密鏈方案

循環(huán)加密鏈?zhǔn)且环N新的密碼學(xué)原語, 它的構(gòu)造方法并不唯一, 可以使用哈希函數(shù)、偽隨機(jī)數(shù)發(fā)生器和偽隨機(jī)函數(shù)等常見構(gòu)造方法來構(gòu)造循環(huán)加密鏈方案. 本節(jié)提出一個(gè)基于哈希函數(shù)構(gòu)造的循環(huán)加密鏈方案(hash-based CEC, HCEC), 詳見算法1, 該方案是循環(huán)加密鏈方案的一個(gè)特例.

為了更好地描述循環(huán)加密鏈方案, 將方案的主要過程抽象為六個(gè)算法. 這六個(gè)算法分別為對(duì)稱密鑰生成算法KG、對(duì)稱加密算法E、對(duì)稱解密算法D、循環(huán)密鑰生成算法KGCEC、循環(huán)加密算法ECEC和循環(huán)解密算法DCEC. 其中, 前面三個(gè)算法滿足IND-KDM 安全, 算法KG 輸入安全參數(shù)λ, 輸出一個(gè)密鑰K; 算法E輸入密鑰K和明文M, 輸出密文C; 算法D輸入密鑰K和密文C, 輸出明文M; 算法KGCEC輸入安全參數(shù)λ和一個(gè)正整數(shù)n, 輸出一系列密鑰的集合K. 具體地, 該算法首先調(diào)用對(duì)稱密鑰生成算法KG 生成一個(gè)密鑰K, 通過安全哈希函數(shù)H和整數(shù)n, 生成一系列密鑰的集合K. 而算法ECEC輸入密鑰集合K={K0,K1,··· ,Kn}, 調(diào)用對(duì)稱加密算法E, 用密鑰K1加密密鑰K0獲得密文e1, 即e1=E(K1,K0), 以此類推, 生成一系列密文的集合E={e1,··· ,en}. 算法DCEC輸入最新的密鑰Kn和一系列密文的集合E={e1,··· ,en}, 調(diào)用對(duì)稱解密算法D, 用密鑰Kn解密密文en獲得密鑰Kn-1, 以此類推, 最終輸出一系列密鑰的集合K={K0,K1,··· ,Kn}.

接下來為了分析HCEC 方案的計(jì)算正確性, 本文將構(gòu)建方案的計(jì)算正確性實(shí)驗(yàn). HCEC 方案的正確性實(shí)驗(yàn)流程如下: 實(shí)驗(yàn)首先執(zhí)行算法KGCEC生成有n+1 個(gè)密鑰的集合K={K0,K1,··· ,Kn}, 然后使用ECEC算法循環(huán)加密這一系列密鑰, 獲得一系列密文的集合E. 解密算法DCEC輸入密鑰Kn和上述一系列密文的集合, 輸出一系列密鑰的集合K′={K′0,K′1,··· ,K′n-1,Kn}. 若解密算法的輸出結(jié)果K′與加密算法的輸入K相等, 那么輸出結(jié)果比特b=1, 否則b=0. 由于加密算法和解密算法都是確定性算法, 因此b=1 出現(xiàn)的可能性是確定的, HCEC 方案的計(jì)算正確性得證.

算法1 HCEC 方案算法KG Input: λ Output: K 1: K ←SKE.Gen(λ)2: Output K算法E Input: K,M Output: C 1: C ←SKE.E(K,M)2: Output C算法D Input: K,C Output: M 1: M ←SKE.D(K,C)2: Output M算法KGCEC Input: λ,n Output: K 1: K ←KG(λ)2: for i = 0 →n do 3: Ki ←H(K,i)4: K ←K ∪{Ki}5: end for 6: Output K算法ECEC Input: K Output: E 1: for i = 1 →n do 2: ei ←E(Ki,Ki-1)3: E ←E ∪{ei}4: end for 5: Output E算法DCEC Input: Kn, E Output: K 1: for i = n →1 do 2: Ki-1 ←D(Ki,ei)3: K ←K ∪{Ki-1}4: end for 5: Output K

下面分析HCEC 方案的安全性, 對(duì)于生成的密鑰集合K, 定義以下泄露函數(shù)LHCEC(K)=(E,N). 其中N,K,E定義如下:

·N=|K| 是密鑰集合的元素個(gè)數(shù).

·K是一系列密鑰的集合.

·E是一系列密文的集合.

定理1 令LHCEC如上所述. 在隨機(jī)預(yù)言機(jī)模型下, 假設(shè)對(duì)稱加密算法SKE 滿足IND-KDM 安全,那么HCEC 方案在自適應(yīng)攻擊下具有IND-KDM 安全.

證明: 接下來使用混合論證的方法來對(duì)HCEC 方案進(jìn)行安全性證明.

因此, HCEC 方案在自適應(yīng)攻擊下具有IND-KDM 安全.

5 ECDSSE 方案

基于循環(huán)加密鏈,本文提出一個(gè)滿足前向安全的高效DSSE 方案ECDSSE(encrypted chain dynamic SSE), 它支持隱藏響應(yīng)結(jié)果(response-hiding). 響應(yīng)結(jié)果的隱藏與否與方案設(shè)計(jì)相關(guān), 如果服務(wù)器返回的查詢響應(yīng)結(jié)果是加密的, 那么稱方案支持隱藏響應(yīng)結(jié)果, 否則稱方案不支持隱藏響應(yīng)結(jié)果. ECDSSE 方案的設(shè)計(jì)思想如下: 用Kn作為滿足IND-KDM 安全的對(duì)稱加密方案的新密鑰, 對(duì)客戶端本地計(jì)算的舊密鑰Kn-1進(jìn)行加密, 以此類推, 循環(huán)加密以前的密鑰, 實(shí)現(xiàn)隱藏新密鑰與舊密鑰的關(guān)聯(lián). 用安全哈希函數(shù)切斷新密鑰和以前的搜索令牌的聯(lián)系, 通過查詢時(shí)發(fā)送最新的密鑰關(guān)聯(lián)更新文檔.

ECDSSE 方案由系統(tǒng)初始化算法Setup、更新協(xié)議Update 和搜索協(xié)議Search 組成. 算法偽代碼如算法2、算法3 和算法4 所示. 以下是Setup 算法、Update 協(xié)議和Search 協(xié)議的具體過程:

(1) Setup(λ,DB;⊥): 系統(tǒng)初始化算法, 該算法主要由客戶端執(zhí)行. 客戶端輸入安全參數(shù)λ和明文初始數(shù)據(jù)庫DB, 從密鑰空間{0,1}λ隨機(jī)均勻抽樣生成主密鑰K并初始化本地緩存映射Σ、索引表T和刪除表DT 為空映射; 服務(wù)器無輸入. 如果初始數(shù)據(jù)庫DB 不為空, 那么進(jìn)行初始數(shù)據(jù)庫的更新, 具體流程如下: 將數(shù)據(jù)庫DB 解析成(w,IDw) 鍵值對(duì)的集合, 其中w代表關(guān)鍵字, IDw代表含有關(guān)鍵字w的文檔標(biāo)識(shí)符集合. 然后, 針對(duì)每一個(gè)關(guān)鍵字w對(duì)應(yīng)的文檔集合IDw調(diào)用循環(huán)密鑰生成算法HCEC.KGCEC生成密鑰集合K, 再調(diào)用循環(huán)密鑰加密算法ECEC, 對(duì)上述生成的一系列密鑰進(jìn)行加密, 獲得相對(duì)應(yīng)的密文集合E, 同時(shí)對(duì)每一個(gè)文檔id 都使用滿足IND-CPA安全的對(duì)稱加密算法進(jìn)行加密, 且通過哈希函數(shù)H獲取每一個(gè)密鑰Ki的哈希鍵值Li, 將鍵值對(duì){Li,(op+ed+ei)}添加到索引表T中. 初始化算法運(yùn)行結(jié)束后, 客戶端存儲(chǔ)主密鑰K和緩

存映射表Σ, 服務(wù)器存儲(chǔ)索引表T和刪除表DT.

算法2 Setup Input: λ,DB Output: K,Σ,T,DT 1: K$←{0,1}λ 2: Σ,T,DT ←empty map 3: while |DB|! = 0 do 4: key ←DB 5: (w,IDw) ←key 6: Σ[w] ←|IDw|7: Kw ←F(K,w)8: K ←HCEC.KGCEC(Kw,|IDw|)9: E ←HCEC.ECEC(K)10: for i = 1 →|IDw| do 11: Li ←H1(Ki)12: ei ←E 13: edi ←Enc(Kw,idi)14: T ←T ∪{Li,(op+edi +ei)}15: end for 16: DB.Remove(key)17: end while 18: Send (T,DT) to the Server

(2) Update(K,Σ,id,w,op;T): 更新協(xié)議, 該協(xié)議在客戶端和服務(wù)器之間交互進(jìn)行. 客戶端輸入主密鑰K、本地狀態(tài)緩存映射表Σ、需要更新的文檔標(biāo)識(shí)符id、文檔中包含的關(guān)鍵字w以及更新操作符op; 服務(wù)器輸入索引表T. 更新協(xié)議的具體流程如下:

(a) 對(duì)于鍵值對(duì)(w,id), 客戶端初始化關(guān)鍵字w對(duì)應(yīng)的狀態(tài)緩存映射表Σ[w] 的更新次數(shù)n為0 或取出最新的更新次數(shù)n, 將該關(guān)鍵字的更新次數(shù)遞增后重新存到狀態(tài)緩存表Σ 中, 并使用偽隨機(jī)函數(shù)計(jì)算對(duì)應(yīng)的關(guān)鍵字密鑰Kw.

(b) 使用這個(gè)關(guān)鍵字密鑰Kw調(diào)用HCEC 方案的密鑰生成算法生成密鑰Kn+1和密鑰Kn, 并對(duì)文檔標(biāo)識(shí)符id 使用IND-CPA 對(duì)稱加密算法進(jìn)行加密獲得密文ed, 其中HCEC 方案的密鑰生成算法中使用了抗碰撞的哈希函數(shù)H,主要目的是利用該函數(shù)的抗碰撞特性生成一系列不同密鑰. 然后調(diào)用循環(huán)加密算法HCEC.E, 用密鑰Kn+1加密密鑰Kn獲得密文en+1.

(c) 用安全哈希函數(shù)H1修飾密鑰Kn+1獲得一個(gè)哈希鍵值Ln+1, 斷開新密鑰與查詢標(biāo)簽的聯(lián)系,將更新操作符op、密文ed 以及加密聯(lián)系密文en+1按順序拼接,獲得新密文En+1. 最后客戶端存儲(chǔ)更新后的本地狀態(tài)緩存Σ, 服務(wù)器存儲(chǔ)更新后的索引表T, 其中T[H1(Kn+1)]=En+1.

算法3 Update Input: (K,Σ,w,id,op);T Output: Σ′,T′Client:1: n ←Σ[w]2: if n == ⊥then 3: n ←0 4: end if 5: Kw ←F(K,w)6: Kn ←H(Kw,n)7: Kn+1 ←H(Kw,n+1)8: en+1 ←HCEC.E(Kn+1,Kn)9: Ln+1 ←H1(Kn+1)10: ed ←Enc(Kw,id)11: En+1 ←(op||ed||en+1)12: Σ[w] ←n+1 13: Send (Ln+1,En+1) to Server Server:14: T[Ln+1] ←En+1

值得注意的是, 客戶端擁有主密鑰K, 它能通過偽隨機(jī)函數(shù)生成關(guān)鍵詞w對(duì)應(yīng)的子密鑰Kw, 再結(jié)合計(jì)數(shù)器作為哈希函數(shù)的輸入, 可生成關(guān)鍵詞w在循環(huán)加密鏈上的一系列不關(guān)聯(lián)的密鑰. 此處偽隨機(jī)函數(shù)的目標(biāo)是為不同關(guān)鍵詞w對(duì)應(yīng)的循環(huán)加密鏈提供不同的隨機(jī)子密鑰Kw, 同時(shí)使得客戶端在更新操作時(shí), 可以利用主密鑰重新計(jì)算出Kw, 免去了子密鑰的存儲(chǔ)開銷. 在Update 協(xié)議步驟6 的密鑰生成算法的選擇取決于循環(huán)加密鏈的具體實(shí)例化, ECDSSE 方案使用了上文基于哈希函數(shù)的HCEC 實(shí)現(xiàn)前向安全, 因此步驟6 使用哈希函數(shù)生成密鑰.

(3) Search(K,Σ,w;(DT,T)): 搜索協(xié)議, 該協(xié)議在客戶端和服務(wù)器之間交互進(jìn)行. 客戶端輸入主密鑰K、本地狀態(tài)緩存Σ 和待查詢的關(guān)鍵字w; 服務(wù)器輸入刪除表DT 和索引表T. 具體流程如下:

(a) 客戶端取出本地狀態(tài)緩存Σ 中關(guān)鍵字w的更新次數(shù)n并使用哈希函數(shù)計(jì)算最新密鑰Kn,發(fā)送密鑰Kn和更新次數(shù)n給服務(wù)器.

(b) 服務(wù)器獲得(Kn,n) 后, 計(jì)算標(biāo)簽H1(Kn) 并用該標(biāo)簽從索引表T中獲取對(duì)應(yīng)的密文En,將密文En按順序分離獲取對(duì)應(yīng)的更新操作符op、結(jié)果標(biāo)識(shí)符密文ed 以及加密鏈值en, 根據(jù)更新操作符op 的類型(增加或刪除), 分別添加到刪除表DT 和加密結(jié)果集ER 中. 其中,服務(wù)器根據(jù)循環(huán)加密鏈方案, 調(diào)用循環(huán)解密算法HCEC.D, 用密鑰Kn解密密文en獲得密鑰Kn-1, 以此類推, 循環(huán)解密直到獲得最后的加密結(jié)果集ER, 服務(wù)器將結(jié)果集ER 發(fā)送給客戶端.

(c) 客戶端獲得服務(wù)器返回的加密結(jié)果集ER 后, 用主密鑰K計(jì)算查詢關(guān)鍵字w對(duì)應(yīng)的子密鑰Kw. 客戶端使用密鑰Kw能夠解密文檔標(biāo)識(shí)符密文集合ER, 獲得明文文檔標(biāo)識(shí)符集合R,至此搜索協(xié)議結(jié)束.

算法4 Search Input: (K,Σ,w);(DT,T)Output: (Σ′,R)Client:1: n ←Σ[w]2: if n = ⊥ then 3: return ? 4: end if 5: Kw ←F(K,w)6: Kn ←H(Kw,n)7: Send (Kn,n) to Server Server:8: ER, DT ←? 9: for i = n →1 do 10: Li ←H1(Ki)11: (op||ed||ei) ←T[Li]12: if op = del then 13: DT←DT ∪{ed}14: else 15: if ed ∈DT then 16: DT←DT-{ed}17: else 18: ER←ER∪{ed}19: end if 20: end if 21: Ki-1 ←HCEC.D(Ki,ei)22: end for 23: Send ER to Client Client:24: Kw ←F(K,w)25: for i = 1 →c do 26: idi ←Dec(Kw,ER[i])27: R ←R ∪{idi}28: end for 29: Output R

下面給出ECDSSE 方案的正確性定理與安全性定理.

定理2 假設(shè)H和H1是安全的抗碰撞哈希函數(shù),F是安全的偽隨機(jī)函數(shù), (Gen,Enc,Dec) 是滿足IND-CPA 安全的SKE 方案, HCEC 方案具有計(jì)算正確性, 如果對(duì)于任意PPT 敵手A, 均有以下不等式成立:

則稱ECDSSE 方案具有計(jì)算正確性.

定理3 設(shè)H和H1是基于隨機(jī)預(yù)言機(jī)建模的安全哈希函數(shù), (Gen,Enc,Dec) 是滿足IND-KDM 安全的SKE 方案,F是安全的偽隨機(jī)函數(shù), HCEC 方案具有計(jì)算正確性并且在自適應(yīng)攻擊下具有INDKDM 安全. 定義泄露函數(shù)L=(LSetup,LUpdate,LSearch), 它記錄一個(gè)包含搜索請(qǐng)求和更新請(qǐng)求的請(qǐng)求列表Q, 如果泄露函數(shù)只泄露如下所示的信息:

也就是說, ECDSSE 方案具有前向安全和L-自適應(yīng)安全, 其中|Widi| 表示更新文檔idi對(duì)應(yīng)的關(guān)鍵字集合的數(shù)量,N表示由初始化算法生成的加密數(shù)據(jù)庫EDB′的鍵值對(duì)個(gè)數(shù), sp(w) 代表關(guān)鍵字w的搜索模式, qp(w) 代表關(guān)鍵字w的查詢模式, 具體細(xì)節(jié)如下:

由于篇幅問題, 定理2 和定理3 的證明在附錄中給出, 此處不再贅述.

6 性能分析

本節(jié)將從更新效率、搜索效率和存儲(chǔ)開銷等方面, 對(duì)ECDSSE 方案、FAST 方案[5]和BESTIE 方案[7]進(jìn)行性能對(duì)比分析. 本文采用C++ 編程語言編寫方案代碼, 使用RocksDB 數(shù)據(jù)庫存儲(chǔ)鍵值對(duì)字典, 基于GRPC 框架實(shí)現(xiàn)客戶端與服務(wù)器的網(wǎng)絡(luò)數(shù)據(jù)傳輸. 此外, 本文使用Cryptopp 密碼學(xué)開源庫實(shí)現(xiàn)安全哈希函數(shù)H和H1、偽隨機(jī)函數(shù)F和對(duì)稱加密方案SKE. 本文修改了FAST 方案和BESTIE 方案的代碼實(shí)現(xiàn), 以便與本文方案進(jìn)行對(duì)比, 其中BESTIE 方案修改為不使用緩存機(jī)制的支持前向安全的方案. 在所有方案中, 標(biāo)識(shí)符長度都設(shè)置為64 位, 所有的關(guān)鍵字均經(jīng)過哈希處理, 以防部分關(guān)鍵字長度過長造成對(duì)稱加密的明文分組長度不同. 在廣域網(wǎng)(wide area network, WAN) 的網(wǎng)絡(luò)環(huán)境下, 服務(wù)端部署在具有4 核CPU、8 GB 內(nèi)存、40 GB 存儲(chǔ)空間的騰訊云服務(wù)器上, 而客戶端部署在位于筆記本電腦上, 該電腦具有4 核CPU (英特爾酷睿i5-11300H, 3.10 Ghz)、16 GB 內(nèi)存和500 GB 固態(tài)硬盤. 在本地局域網(wǎng)(local area network, LAN) 的網(wǎng)絡(luò)環(huán)境下, 服務(wù)端和客戶端同時(shí)部署在同一臺(tái)筆記本電腦上, 筆記本電腦的配置同上.

6.1 更新效率

首先展示三個(gè)方案在更新操作上的性能情況. FAST、BESTIE 和ECDSSE 都是基于對(duì)稱密碼學(xué)原語構(gòu)造的方案, 但是各方案更新協(xié)議中的操作有所區(qū)別. 更新實(shí)驗(yàn)測量的參數(shù)包括吞吐量和單個(gè)鍵值對(duì)更新時(shí)間, 其中吞吐量表示單位時(shí)間內(nèi)方案執(zhí)行鍵值對(duì)更新操作的數(shù)量, 單個(gè)鍵值對(duì)更新時(shí)間表示執(zhí)行單個(gè)鍵值對(duì)更新操作所需的時(shí)間. 每個(gè)文檔包含關(guān)鍵字個(gè)數(shù)范圍有1000、5000、10 000 三種, 這是因?yàn)樵趯?shí)際的數(shù)據(jù)庫中, 一個(gè)文檔對(duì)應(yīng)關(guān)鍵字個(gè)數(shù)普遍落在這三個(gè)數(shù)的范圍內(nèi), 選擇這三個(gè)數(shù)有利于分析在不同關(guān)鍵字個(gè)數(shù)的情況下方案的更新效率的情況. 實(shí)驗(yàn)首先測量了更新FAST、BESTIE 和ECDSSE 方案在LAN 中的更新效率, 即在同一計(jì)算機(jī)上運(yùn)行客戶端程序和服務(wù)端程序. 在LAN 環(huán)境中, 實(shí)驗(yàn)結(jié)果不包括網(wǎng)絡(luò)傳輸導(dǎo)致的延遲誤差, 更能體現(xiàn)方案本身的執(zhí)行效率. 然后實(shí)驗(yàn)測量在WAN 環(huán)境中的方案更新效率, 其中服務(wù)器部署在騰訊云服務(wù)器, 客戶端部署在筆記本電腦. 每個(gè)實(shí)驗(yàn)重復(fù)30 次, 取平均值, 避免偶然誤差. 更新性能測試的結(jié)果如表2 所示, 在兩種網(wǎng)絡(luò)環(huán)境中, ECDSSE 方案的吞吐量都是FAST 方案的1.3 倍, 并且與BESTIE 方案的吞吐量幾乎一致. 結(jié)果證實(shí), ECDSSE 方案在更新效率方面比FAST 方案更勝一籌, 這是由于FAST 方案在更新過程中需要不斷生成偽隨機(jī)數(shù), 而ECDSSE 方案的子密鑰是通過安全哈希函數(shù)生成的, 更新效率的差距來源于哈希函數(shù)和偽隨機(jī)數(shù)生成器的效率差. ECDSSE 方案與BESTIE 方案更新效率的差距不大的實(shí)驗(yàn)結(jié)果源于兩者的客戶端計(jì)算復(fù)雜度相當(dāng), 兩者均執(zhí)行相同數(shù)量的哈希操作或加解密操作.

表2 FAST、BESTIE 和ECDSSE 方案的更新效率Table 2 Update efficiency among FAST、BESTIE and ECDSSE

6.2 搜索效率

對(duì)于FAST、BESTIE 和ECDSSE 方案, 服務(wù)器端的搜索操作需要處理加密索引條目列表以查找匹配的文檔. 因此, 搜索效率關(guān)鍵取決于處理索引的效率. 圖4 和圖5 展示了三種方案在不同網(wǎng)絡(luò)環(huán)境中的搜索效率情況. 使用三個(gè)不同數(shù)量級(jí)大小的數(shù)據(jù)庫106、107和108進(jìn)行了實(shí)驗(yàn). 每個(gè)實(shí)驗(yàn)測量了服務(wù)器端搜索具有10—105個(gè)匹配文檔的關(guān)鍵字的總時(shí)間(即不計(jì)算客戶端的網(wǎng)絡(luò)延遲和令牌生成時(shí)間). 實(shí)驗(yàn)重復(fù)了1000 次, 取平均值, 然后除以匹配文檔的數(shù)量, 得到搜索單個(gè)條目的時(shí)間. 從圖中可以看到, 隨著更新文檔數(shù)量的增加, 處理單個(gè)更新文檔的時(shí)間會(huì)減少. 這是因?yàn)槌跏蓟阉饔幸粋€(gè)固定的成本, 它被分?jǐn)偟矫總€(gè)更新文檔的處理時(shí)間中. 隨著條目數(shù)量的增加, 攤銷的初始化成本變得不那么重要.

圖4 LAN 環(huán)境下106、107、108 的數(shù)據(jù)集的方案搜索性能對(duì)比Figure 4 Search performance comparison in 106、107 and 108 size dataset at LAN

圖5 WAN 環(huán)境下106、107、108 的數(shù)據(jù)集的方案搜索性能對(duì)比Figure 5 Search performance comparison in 106、107 and 108 size dataset at WAN

根據(jù)圖4 和圖5 的實(shí)驗(yàn)數(shù)據(jù)可以發(fā)現(xiàn), 隨著數(shù)據(jù)庫的容量增大, 對(duì)應(yīng)的DSSE 方案的搜索效率都有一定程度的下降, 但整體的搜索效率趨勢(shì)是大體一致的. 無論是在WAN 還是在LAN 的網(wǎng)絡(luò)環(huán)境下,ECDSSE 方案的搜索效率都穩(wěn)定優(yōu)于FAST 方案. 根據(jù)具體的實(shí)驗(yàn)數(shù)據(jù)對(duì)比, 除了搜索匹配文檔數(shù)量級(jí)為10 的關(guān)鍵字的搜索效率提升約為10%, 針對(duì)其他數(shù)量級(jí)的關(guān)鍵字的搜索效率提升均超過20%. 方案間的搜索效率差是由于本文算法在服務(wù)器端進(jìn)行搜索時(shí)進(jìn)行更少的加解密以及哈希操作. 在WAN 環(huán)境下,ECDSSE 方案和BESTIE 方案依然比FAST 方案的搜索效率更高, 但是由于存在網(wǎng)絡(luò)延遲等其他原因,實(shí)際的性能表現(xiàn)比在LAN 環(huán)境中稍差. 在WAN 和LAN 環(huán)境中, ECDSSE 方案與BESTIE 方案的搜索效率差距均不大, 原因在于兩個(gè)方案的服務(wù)端計(jì)算復(fù)雜度是一樣的, 兩者都有相同數(shù)量的耗時(shí)操作, 比如加解密操作以及哈希操作.

6.3 存儲(chǔ)開銷

表1 展示了ECDSSE、FAST 和BESTIE 方案的理論存儲(chǔ)性能, 本小節(jié)將用實(shí)驗(yàn)數(shù)據(jù)展示并分析三者的存儲(chǔ)開銷.

在實(shí)驗(yàn)中, 我們采用RocksDB 鍵值對(duì)數(shù)據(jù)庫來存儲(chǔ)客戶端的狀態(tài)表, 即在本地以RocksDB 數(shù)據(jù)庫的數(shù)據(jù)文件格式存儲(chǔ)狀態(tài)表. 實(shí)驗(yàn)選擇的數(shù)據(jù)庫有不同的數(shù)量級(jí): 106、107和108, 它們分別包含約10 萬個(gè)關(guān)鍵字、50 萬個(gè)關(guān)鍵字和200 萬個(gè)關(guān)鍵字. 實(shí)驗(yàn)數(shù)據(jù)如表3 所示, 在106級(jí)別的數(shù)據(jù)庫中,ECDSSE 方案的存儲(chǔ)開銷相對(duì)于BESTIE 和FAST 方案分別減少12.5% 和61.1%; 在107級(jí)別的數(shù)據(jù)庫中, ECDSSE 方案的存儲(chǔ)開銷相對(duì)于BESTIE 和FAST 方案分別減少16.1% 和54.0%; 在108級(jí)別的數(shù)據(jù)庫中, ECDSSE 方案的存儲(chǔ)開銷相對(duì)于BESTIE 和FAST 方案分別減少13.0% 和60.4%. 由上述數(shù)據(jù)可知, BESTIE 方案的存儲(chǔ)開銷并沒有比ECDSSE 少多少, 這是因?yàn)樵诰幊虒?shí)現(xiàn)中, 計(jì)數(shù)器按整型變量計(jì)算, 存儲(chǔ)一個(gè)數(shù)需要4 個(gè)字節(jié)的存儲(chǔ)空間, 但是在存入文件時(shí)可以轉(zhuǎn)換為字符串, 在更新次數(shù)較少的情況下, 所需客戶端存儲(chǔ)空間小于4 個(gè)字節(jié), 比如計(jì)數(shù)器的值為1, 按整型計(jì)算需要4 個(gè)字節(jié), 轉(zhuǎn)換為字符串存儲(chǔ)只需要1 個(gè)字節(jié), 因而在數(shù)據(jù)量不大的情況下, 差距不明顯. 理論上, ECDSSE 方案相比BESTIE 方案在客戶端存儲(chǔ)開銷上最多可以減少50%, 這是因?yàn)锽ESTIE 方案有2 個(gè)計(jì)數(shù)器, 而ECDSSE 方案只有1 個(gè)計(jì)數(shù)器, 在關(guān)鍵字個(gè)數(shù)一樣的情況下, 存儲(chǔ)開銷由計(jì)數(shù)器的數(shù)量決定. 而FAST 方案的客戶端存儲(chǔ)開銷比ECDSSE 方案高, 因?yàn)樗嗽诒镜卮嬗幸粋€(gè)關(guān)鍵字更新次數(shù)的計(jì)數(shù)器之外, 還存有一個(gè)固定大小的隨機(jī)字符串, 這導(dǎo)致了FAST 方案比ECDSSE 方案多(關(guān)鍵字個(gè)數(shù)* 隨機(jī)字符串) 的數(shù)值大小的客戶端存儲(chǔ)開銷.

表3 三種DSSE 方案的實(shí)際存儲(chǔ)開銷對(duì)比Table 3 Realistic storage cost among three DSSE schemes

7 結(jié)論與展望

本文提出了一種新的密碼學(xué)原語循環(huán)加密鏈, 并基于該密碼學(xué)原語及其通用構(gòu)造提出了一種滿足前向安全的高效DSSE 方案ECDSSE. 與FAST[5]方案相比較, ECDSSE 方案在保證安全性的情況下, 使用哈希函數(shù)實(shí)現(xiàn)密鑰的生成, 避免了不必要的生成偽隨機(jī)密鑰的計(jì)算, 提高了更新效率, 并且通過提前加密文檔標(biāo)識(shí)符, 減少了不必要的異或加密操作, 提升了搜索效率, 并且將客戶端的存儲(chǔ)開銷明顯降低, 同時(shí)相對(duì)于FAST 方案將更新效率和搜索效率提高了約35% 和20%. 與BESTIE[7]方案相比, ECDSSE 方案在減少客戶端存儲(chǔ)開銷上取得優(yōu)勢(shì), 相比于BESTIE 方案可減少至少12.5% 的客戶端存儲(chǔ)開銷.

滿足前向安全的DSSE 方案具有實(shí)用性, 但是此類方案仍然不足以應(yīng)對(duì)未來可能出現(xiàn)的因刪除文檔導(dǎo)致的信息泄露攻擊. 為了應(yīng)對(duì)這種挑戰(zhàn), 需要進(jìn)一步研究后向安全的概念. 目前已有一些研究著力于實(shí)現(xiàn)滿足后向安全的方案[22,23,29,30], 如何實(shí)現(xiàn)滿足后向安全的DSSE 方案可作為進(jìn)一步的研究方向.