黃一才 郁 濱 李森森

（信息工程大學(xué) 鄭州 450001）（huangyicai3698@163.com）

可搜索加密無需解密就能實現(xiàn)數(shù)據(jù)搜索.依據(jù)搜索時所采用的加密算法加密方案可分為公鑰可搜索加密（public key encryption with keyword search, PEKS）和對稱可搜索加密（searchable symmetric encryption,SSE）這2 類.其中SSE 方案因采用對稱算法，在數(shù)據(jù)量較大的云存儲環(huán)境下往往具有更高的搜索效率.

1 相關(guān)工作

2000 年，Song 等人[1]提出了可搜索加密的基本概念，并基于對稱密碼算法，構(gòu)造對稱可搜索加密方案.文獻(xiàn)[2-6]分別構(gòu)造了正排索引、倒排索引、雙向索引和樹形索引結(jié)構(gòu)的對稱可搜索加密方案，提高了方案的搜索效率.

相比靜態(tài)方案，支持密文數(shù)據(jù)更新，如添加、刪除等操作的動態(tài)方案具有更好的實用性.文獻(xiàn)[6]利用OMAP 結(jié)構(gòu)隱藏服務(wù)器密文字典的訪問地址，實現(xiàn)了一種安全且支持動態(tài)更新的對稱可搜索加密方案，但OMAP 結(jié)構(gòu)較高的通信開銷降低了方案的實用性[7].文獻(xiàn)[8-10]分別采用并行計算和優(yōu)化I/O 效率的方式進(jìn)一步提高了方案的搜索效率.文獻(xiàn)[11]設(shè)計2 級索引鏈結(jié)構(gòu)，實現(xiàn)了固定大小的客戶端存儲空間開銷.

安全性一直是動態(tài)方案構(gòu)造中研究的熱點(diǎn)問題.為方便對動態(tài)方案的安全性進(jìn)行分析，Curtmola 等人[4]通過泄露函數(shù)給出了自適應(yīng)安全對稱可搜索加密方案的定義.文獻(xiàn)[12]給出了方案動態(tài)更新時前向及后向隱私的正式定義.文獻(xiàn)[13]構(gòu)造了一種前向隱私的可搜索加密方案，但方案需要進(jìn)行大量的指數(shù)運(yùn)算，搜索效率不高.文獻(xiàn)[14-16]提出了執(zhí)行效率更高的前向隱私方案.文獻(xiàn)[17-18]提出了同時滿足前向和后向隱私的對稱可搜索加密方案，文獻(xiàn)[19]提出了利用SGX 技術(shù)實現(xiàn)的后向隱私，但方案的安全性需要基于特殊軟件平臺，一定程度上降低了方案的通用性.

方案的構(gòu)造過程通常需要結(jié)合應(yīng)用場景在搜索效率、存儲和通信開銷、安全性、功能性等方面進(jìn)行多種妥協(xié).其中利用可穿刺加密技術(shù)構(gòu)造的前向/后向隱私方案，具有交互少、安全性高的特點(diǎn)，近年來越來越受到人們的重視.文獻(xiàn)[20]基于可穿刺加密技術(shù)，在Janus 方案[12]基礎(chǔ)上，采用可穿刺偽隨機(jī)函數(shù)[21]代替公鑰算法，設(shè)計了對稱可穿刺可搜索加密方案Janus++，提高了方案在增加和刪除密文索引時的效率，且方案在實現(xiàn)后向隱私的同時，具有更小的通信開銷.

Sun 等人[22]指出Janus++方案中使用的對稱可穿刺加密（symmetric puncturable encryption，SPE）無法抵抗共謀攻擊，為此定義了基于可穿刺偽隨機(jī)函數(shù)的對稱可撤消加密（symmetric revokable encryption，SRE）密碼學(xué)原語，并利用對稱可撤消加密構(gòu)造一種單輪交互的后向安全對稱可搜索加密方案Aura.Aura 方案使用GGM 樹實現(xiàn)可穿刺偽隨機(jī)函數(shù)，并在此基礎(chǔ)上引入Bloom Filter 記錄刪除索引，實現(xiàn)了TypeII 級后向隱私.實驗證明，該方案能夠進(jìn)一步提高搜索響應(yīng)速度.然而該方案存在2 個方面的不足：1）由于Bloom Filter 存在假陽性[23]，會導(dǎo)致索引誤刪除.2）服務(wù)器在每次搜索前需要生成所有密鑰序列，增加了服務(wù)器計算開銷，降低了搜索效率，且使非可信服務(wù)器提前掌握了所有密鑰信息，存在一定的安全隱患.

本文基于Aura 方案[22]提出了一種改進(jìn)的可穿刺對稱可搜索加密方案，具有3 個方面的優(yōu)勢：

1） 搜索效率高.通過在客戶端增加存儲節(jié)點(diǎn)使用標(biāo)志，解密時僅傳輸已使用節(jié)點(diǎn)密鑰，減少服務(wù)器端計算開銷，提高搜索效率，且節(jié)點(diǎn)平均搜索時間不受節(jié)點(diǎn)規(guī)模影響.

2） 避免誤刪除.結(jié)合Bloom Filter 設(shè)計思想，計算可穿刺密鑰節(jié)點(diǎn)位置選擇算法，在提高節(jié)點(diǎn)利用率的同時，防止因哈希碰撞而誤刪索引.

3） 服務(wù)器密文存儲規(guī)模小.Aura 方案中密文規(guī)模與Bloom Filter 中哈希函數(shù)個數(shù)相關(guān)，通過設(shè)計插入位置選擇算法為每個索引選擇唯一的節(jié)點(diǎn)位置，避免密文規(guī)模擴(kuò)大，減少服務(wù)器密文存儲開銷.

2 預(yù)備知識

首先簡要介紹方案設(shè)計中用到的相關(guān)密碼學(xué)基礎(chǔ)知識，包括多點(diǎn)可穿刺偽隨機(jī)函數(shù)、對稱加密算法及前向與后向隱私等.

2.1 多點(diǎn)可穿刺偽隨機(jī)函數(shù)

定義1.多點(diǎn)可穿刺偽隨機(jī)函數(shù)[21-22].設(shè)t(·)表示一個確定的多項式，密鑰空間為 K的偽隨機(jī)函數(shù)MF：K×X →Y ， 若集合S滿 足 |S|≤t，存在另外一個密鑰空間Kp以及3個多項式時間算法 （Setup,Punc,Eval）：

1）k←Setup(1λ).輸入安全參數(shù)λ，輸出偽隨機(jī)函數(shù)密鑰k∈K.

2）kS←Punc(k,S).輸 入 密 鑰k∈K ， 集 合S?X s.t.|S|≤t(λ)， 輸出可穿刺密鑰kS∈Kp.

3）y←Eval(kS,x).輸入可穿刺密鑰kS∈Kp，x∈X，輸出y∈Y 或 ⊥.

則稱MF為多點(diǎn)可穿刺偽隨機(jī)函數(shù)t-Punc-PRF（tpuncturable pseudorandom function）.

定義2.MF正確性[22].對所有S?Xs.t.|S|≤t(λ)，x∈XS，k←Setup(1λ)，kS←Punc(k,S)， 對 所 有k∈K使

成立，其中 ν (λ)為 可忽略函數(shù)，則稱函數(shù)MF滿足正確性條件.

2.2 對稱加密算法

定義3.對稱加密算法[22].設(shè)明文空間 M、密鑰空間 K 和密文空間 C，則對稱加密（symmetric encryption，SE）算法可用3 個多項式時間算法的三元組表示，記為S E=(Gen,Enc,Dec)，其中：

1）k←Gen(1λ).輸入秘密參數(shù) λ ，輸出密鑰k∈K.

2）ct←Enc(k,m).輸入密鑰k、明文消息m，輸出密文ct∈C.

3）m←Dec(k,ct).輸入密鑰k、密文ct，成功解密輸出ct對應(yīng)明文m， 否則輸出 ⊥.

定義4.SE正確性[22].若算法對任意明文m∈M，k←Gen(1λ)且ct←Enc(k,m)，滿足

則稱算法SE滿足正確性條件.

2.3 前向隱私與后向隱私

可搜索加密方案前向隱私是指更新查詢不會泄露正在更新的關(guān)鍵字或文檔對中所涉及的關(guān)鍵字信息，主要針對文檔添加操作，確保新添加文檔不會包含在以前查詢令牌的檢索結(jié)果中.文獻(xiàn)[24]指出針對不具備前向隱私的方案可有效實施文件注入攻擊，快速恢復(fù)用戶檢索信息.

后向隱私要求搜索和更新操作僅泄露數(shù)據(jù)庫中的當(dāng)前文檔（不包括已刪除的文檔），主要針對文檔刪除操作，確保當(dāng)前查詢不會包含過去已刪除的文檔索引.文獻(xiàn)[4]根據(jù)泄露信息不同，將安全強(qiáng)度由高到低分為TypeⅠ，TypeⅡ，TypeⅢ.TypeⅠ后向隱私允許泄露當(dāng)前關(guān)鍵詞所匹配的文檔索引、插入時間及更新關(guān)鍵詞的更新總數(shù)；TypeⅡ在TypeⅠ基礎(chǔ)上，增加了泄露關(guān)鍵詞的操作類型和時間；TypeⅢ相對于TypeⅡ，增加了泄露刪除操作對應(yīng)的那個添加操作.

3 搜索模型

本文方案中各主要符號定義如表1 所示.為簡化方案構(gòu)造，假定：

Table 1 Symbol Definition表1 符號定義

1）服務(wù)器為“誠實且好奇（honest but curious）”的.即服務(wù)器能忠實運(yùn)行用戶發(fā)出的請求，但也會盡可能地窺探用戶個人隱私.

2）只有數(shù)據(jù)擁有者（data owner，DO）是完全可信的，且能夠訪問系統(tǒng)中所有的明文信息；各實體之間以及云存儲服務(wù)器內(nèi)部各通信信道均不可信，且存在各種可能的網(wǎng)絡(luò)攻擊行為.

3）數(shù)據(jù)擁有者能夠?qū)ξ臋n進(jìn)行解密，但在訪問服務(wù)器前并不確定云服務(wù)器中存有哪些文件，以及是否包含其想要的文件.

4）不考慮多客戶端應(yīng)用場景.僅對方案搜索效率優(yōu)化與避免誤刪除進(jìn)行設(shè)計，對多客戶端場景下的特殊性不做專門研究.

3.1 場景描述

對稱可搜索加密應(yīng)用場景由安全存儲服務(wù)器和數(shù)據(jù)擁有者2 部分組成，其中安全存儲服務(wù)器包括1個存儲用戶密文文件的存儲服務(wù)器和1 個實現(xiàn)數(shù)據(jù)密文搜索的密文索引搜索服務(wù)器.DO 既能夠向安全存儲服務(wù)器中添加新的密文文件，又可以實現(xiàn)對數(shù)據(jù)密文查詢.應(yīng)用場景如圖1 所示.

Fig.1 Application scenario of dynamic searchable symmetric encryption圖1 動態(tài)對稱可搜索加密應(yīng)用場景

方案的工作過程包括數(shù)據(jù)動態(tài)更新和數(shù)據(jù)查詢2 個階段，其中數(shù)據(jù)動態(tài)更新通常包括數(shù)據(jù)添加、刪除和更新3 種操作，為簡化描述過程，這里以數(shù)據(jù)添加為例，具體描述方案的工作過程.

1）數(shù)據(jù)添加.用于向密文索引數(shù)據(jù)庫中加入新的數(shù)據(jù)文件索引.DO 先將數(shù)據(jù)文件加密后存儲在文件存儲服務(wù)器，并返回訪問入口信息；然后DO 通過對明文數(shù)據(jù)進(jìn)行處理，生成文件訪問入口信息與關(guān)鍵詞對應(yīng)關(guān)系，并按照一定索引結(jié)構(gòu)生成密文索引，將密文索引存儲于密文索引服務(wù)器.

2）數(shù)據(jù)查詢.要求密文服務(wù)器不用解密具體密文文件，便能從所有密文文件中返回符合用戶查詢需求的文件信息，這也是可搜索加密方案的核心.此過程一般是DO 通過關(guān)鍵詞生成查詢令牌，然后通過密文索引服務(wù)器獲取密文文件的入口地址信息，最終從密文文件服務(wù)器獲取密文文件.

3.2 方案形式化描述

動態(tài)對稱可搜索加密（dynamic searchable symmetric encryption, DSSE）的形式化定義通常由一組多項式時間算法組成.

定義5.DSSE 方案.設(shè)數(shù)據(jù)庫由DB=文檔地址或關(guān)鍵詞集構(gòu)成，其中idi為第i文 檔，Wi為文檔i包含的關(guān)鍵詞集合，d為數(shù)據(jù)庫中文檔的數(shù)量，則動態(tài)對稱可搜索加密方案可用一個三元組多項式時間算法(Setup,Search,Update)表示，其中：

1）初始化算法：(K,σ,EDB)←S etup(1λ,DB).算法輸入安全參數(shù) λ和明文索引數(shù)據(jù)庫DB， 輸出密鑰K、關(guān)鍵詞狀態(tài) σ和密文索引數(shù)據(jù)庫EDB.在DSSE 方案中，通常設(shè)EDB=?.

2）查 詢 算 法：(DB(w),σ′,EDB′)←S earch(K, σ,w;EDB).輸入密鑰K、關(guān)鍵詞狀態(tài) σ和檢索關(guān)鍵詞w，輸出包含檢索關(guān)鍵詞w的所有文檔標(biāo)識DB(w)，以及搜索操作后關(guān)鍵詞狀態(tài) σ′和密文索引數(shù)據(jù)庫EDB′.通常算法包含客戶端生成查詢令牌和服務(wù)器根據(jù)令牌搜索查詢結(jié)果2 部分.

3）更新算法：(σ′,EDB′)←Update(K,σ,w,ind,op;EDB).輸入密鑰K、關(guān)鍵詞狀態(tài) σ、更新關(guān)鍵詞w及對應(yīng)索引ind，更新操作類 型op，其中op∈{add,del}，輸出更新后的密文索引數(shù)據(jù)庫EDB′、 關(guān)鍵詞狀態(tài) σ′.

定義6.DSSE 正確性[25].對于所有的DB和W，若任意的w∈W，滿足

則稱DSSE 方案滿足正確性條件.

3.3 SRE 語法定義

定義7.SRE 算法定義[21].設(shè) MSK表示密鑰空間，T表示標(biāo)簽空間，則一個SRE 算法可用4 個多項式時間算法表示，記為SRE=(KGen,Enc,KRev,Dec)，其中：

1）msk←KGen(1λ).輸入安全參數(shù) λ，輸出系統(tǒng)密鑰msk∈MSK.

2）ct←Enc(msk,m,T).輸入系統(tǒng)密鑰msk，消息m∈M 及 標(biāo)簽列表T?T ，輸出消息m標(biāo) 簽T下的密文ct.

3）skR←KRev(msk,R).輸入系統(tǒng)密鑰msk及撤消列表R?T ，輸出撤消后的密鑰skR，僅能解密不屬于標(biāo)簽R對應(yīng)的密文.

4）m←Dec(skR,ct,T).輸入撤消后的密鑰skR、密文ct及對應(yīng)標(biāo)簽T，輸出消息m（ 解密失敗輸出 ⊥）.

定義8.SRE正確性.對所有安全參數(shù) λ ∈N+，消息m∈M 及 對應(yīng)標(biāo)簽T?T 、撤消列表R?Ts.t.R∩T=?，算法SRE正確解密的概率Pr[SRE.Dec(skR,ctm,t)=m]=即對于未撤消加密節(jié)點(diǎn)均可正確解密，則稱算法S RE滿足正確性條件.

相比文獻(xiàn)[21]給出的正確性定義中，解密發(fā)生錯誤的概率以一個不可忽略函數(shù) ν (λ)為上界，定義8要求能夠?qū)∈T 且t?R的 所有密文ctm及對應(yīng)標(biāo)簽T，均可正確解密.

定義9.撤消操作.對所有安全參數(shù) λ ∈N+， 消息m對應(yīng)標(biāo)簽t∈Ts.t.T?T 和撤銷列表R?T ，消息m∈M，撤消加密操作定義為R=R∪{t}.

性質(zhì)1.撤消操作的有效性.對所有安全參數(shù)λ ∈N+， 消 息m對 應(yīng) 標(biāo) 簽t∈Ts.t.T?T 和撤 銷 列 表R?T ，消 息m∈M 撤 消 加 密，則Pr[S RE.Dec(skR,ctm,t)=m]=0 ， 即撤消加密后無法通過撤消后的密鑰skR、密文ctm和對應(yīng)標(biāo)簽t完成解密.

證明.令消息m撤消前的撤消列表為R′，根據(jù)定義9，撤消后撤消列表R=R′∪{t}， 則有t∈T 且t∈R.

根據(jù)正確性定義，Pr[S RE.Dec(skR,ctm,t)=m]=0.

證畢.

性質(zhì)2.撤消操作的正確性.對所有安全參數(shù)λ ∈N+， 已 插 入 消 息 M={m1,m2,···,mn}，對 應(yīng) 標(biāo) 簽T={t1,t2,···,tn} 和 撤銷列表R?T ，其中n為已插入消息 數(shù).?mi,mj∈M ， 對 應(yīng) 標(biāo) 簽 分 別 為ti,tj∈Ts.t.i≠j,ti≠tj.當(dāng)ti∈R,tj?R，則

Pr[SRE.Dec(skR,ctmi,ti)=mi]=0且Pr[SRE.Dec(skR,ctmj,tj)=mj]=1，即撤消解密后不會破壞其他已加密密文解密的正確性.

證明.因為ti∈R，由性質(zhì)1 可知，Pr[S RE.Dec(skR,ctmi,ti)=mi]=0成立.

因為tj∈T且tj?R， 則由定義8 可知，Pr[S RE.Dec(skR,ctmj,tj)=mj]=1成立.證畢.

撤消消息m∈M 對 應(yīng)密文ctm的 解密操作，將ctm對應(yīng)標(biāo)簽tm加入撤消列表，即進(jìn)行消息刪除操作.

定理1.誤刪除條件.若方案滿足正確性條件，發(fā)生誤刪除的充要條件是 ?j≠i,且ti=tj.

證 明.設(shè) ?mi,mj∈M ，對 應(yīng) 標(biāo) 簽 分 別 為ti,tj∈Ts.t.i≠j，mi撤 消前撤消列表為R*.

1） 充分性

設(shè)消息mi撤 消后，mj也 被撤消，其中j≠i,ti≠tj.撤消前，ti,tj∈T 且ti,tj?R*.當(dāng)mi撤消后，依據(jù)性質(zhì)2，撤消列表R=R*∪{ti}.

因 為j≠i且ti≠tj，tj?R*，所 以tj?R*∪{ti}=R, 則Pr[SRE.Dec(skR,ctmj,tj)=mj]=1.

因為mi撤 消時，mj也被撤消，所以依據(jù)性質(zhì)1，有Pr[SRE.Dec(skR,ctmj,tj)=mj]=0.

矛盾，即假設(shè)不成立.

2） 必要性

由定義9 得到，刪除mi后 ，撤消列表R=R*∪{ti}，即ti∈R.因為ti=tj， 所以tj∈R.

根據(jù)正確性定義，可得

則由定義9 可知，消息mj也已刪除.證畢.

可以看出，防止選擇相同標(biāo)簽加密是避免誤刪除的有效手段.

4 方案構(gòu)造

插入位置選擇算法為每個插入文件索引尋找唯一的節(jié)點(diǎn)位置.在此基礎(chǔ)上，構(gòu)造基于SRE 的對稱可搜索加密方案.

4.1 插入位置選擇算法

插入位置選擇算法用于在給定范圍內(nèi)，為消息m隨機(jī)選擇一個未使用的節(jié)點(diǎn)位置pm.

設(shè)hp(x)，hf p(x)分 別表示2 個 哈希函數(shù)，Lb表示長度為b的狀態(tài)列表，Lb[i]=(fi,f pi).其中，fi為占用標(biāo)志，寬度為1 b，用于記錄列表Lb中位置i的占用情況，占用時標(biāo)志置為 t rue， 否則置為false；f pi為 位置i上存儲的消息指紋，一般為消息m的哈希值低n比特（n為預(yù)設(shè)指紋寬度）.圖2 所示為消息m選擇插入位置過程示意圖.

Fig.2 Design idea of insertion position selection algorithm圖2 插入位置選擇算法設(shè)計思想

算法記為InsPos（b,dmax,n）， 其中b表示列表規(guī)模，dmax表示最大搜索深度，n表示消息指紋寬度，且b,dmax,n∈N+，dmax＜b，則 算 法 可 以 用 一 個 三 元 組InsPos=(S etup,Insert,Test)表示.

1）初始化：Lb←S etup(b,n,Lbinit).輸入列表規(guī)模b、初始狀態(tài)Lbinit， 輸出狀態(tài)列表Lb.工作過程為：

① 分配位長為b+nb的 比特狀態(tài)列表Lb.

②若Lbinit=⊥， 令Lb[i]=(false,⊥)， 否則Lb[i]=Lbinit[i]，其中0 ≤i≤b-1.

③ 返回比特列表Lb.

2）插入點(diǎn)位置選擇：(Rst,pm,Lb′)←Insert(m,dmax,Lb).輸入待插入消息m、 最大搜索深度dmax、狀態(tài)列表Lb；輸出為插入結(jié)果Rst、 插入位置pm、插入后狀態(tài)列表Lb′.工作過程為：

① 計算消息m的插入位置pm=hp(m)modb，f pm=hf p(m).

②令Rst=false ，若fpm=false， 則Rst=true，運(yùn) 行③，否則 ? ≤i≤dmax，使fpm=false 成 立（其中pm=(pm+i)modb） ，則pm=(pm+i)modb，Rst=true.

③ 若Rst=true ，則 修 改Lb列 表fpm=true，f ppm=f pm.

④ 返回插入結(jié)果Rst、 插入位置pm、最新狀態(tài)列表Lb′=Lb， 即 (Rst,pm,Lb′).

當(dāng)Rst=true時表示在列表中找到唯一的節(jié)點(diǎn)位置pm， 否則表示在搜索深度d=dmax下未能找到空閑節(jié)點(diǎn)，返回pm為第1 哈希的節(jié)點(diǎn)位置.此時若選擇此節(jié)點(diǎn)位置偽隨機(jī)數(shù)作為加密密鑰，將導(dǎo)致密鑰重用，并在刪除該節(jié)點(diǎn)時因同時刪除多個文件加密密鑰而造成誤刪除.

3）插入位置測試：(rstPos,f pm)←Test(m,dmax,Lb).通過對消息指紋對比獲取消息m在 列表Lb中的位置.輸入為消息m、最大搜索深度dmax、 狀態(tài)列表Lb；輸出為消息m插入位置rstPos，消息指紋f pm.工作過程為：

① 計算消息m的插入位置pm=hp(m)modb和消息指紋f pm=hfp(m).

②令rstPos=-1， 若 ?0≤i≤dmax，Lb[(pm+i)modb]=(rstPos,f pm)， 則rstPos=(pm+i)modb.

③ 返回 (rstPos,f pm).當(dāng)rstPos≥0時，表示找到消息m的插入位置.

在可搜索加密方案構(gòu)造中，Test算法主要用于從列表刪除索引時查找索引準(zhǔn)確位置.搜索時服務(wù)器通過存儲密文對應(yīng)標(biāo)簽，直接獲取節(jié)點(diǎn)在列表中的位置，因此不需要重新通過Test算法計算.Test算法的性能僅影響節(jié)點(diǎn)刪除時的執(zhí)行速度，不影響添加和搜索效率.

插入指紋生成時使用的哈希函數(shù)、位置選擇以及位置深度搜索時使用的哈希函數(shù)可以設(shè)為相同也可以設(shè)為不同，列表占用標(biāo)志fi可以通過判斷指紋位置是否為0 判斷該位置是否已被占用.然而指紋生成時采用哈希函數(shù)的質(zhì)量將直接影響方案指紋大小設(shè)定，選擇優(yōu)秀的哈希函數(shù)作為消息指紋生成算法能有效降低指紋占用空間的大小.同時方案中，由于fi僅需1 b，占用空間較小，且能夠方便對指定位置占用情況進(jìn)行判斷，提高算法執(zhí)行效率.

4.2 SRE的一般構(gòu)造

設(shè)S E=(Gen,Enc,Dec)為標(biāo)準(zhǔn)對稱加密算法，其密鑰空間為 Y，MF：K×X →Y為多點(diǎn)穿刺偽隨機(jī)函數(shù)，記 為MF=（S etup,Punc,Eval）[20-21]，InsPos（b,dmax,n）=(S etup,Insert,Test)表示插入位置選擇算法，則對稱可撤消加密算法S RE=(KGen,Enc,KRev,Dec)的具體描述為4 個步驟.

1）msk←KGen(1λ,b,n,Lbinit)： 輸入安全參數(shù) λ和整 數(shù)b,n∈N+，Lbinit[i]=(false,⊥)， 其中0 ≤i≤b-1，系統(tǒng)主密鑰msk的生成過程有2 步：

①生成Lb←InsPos.Setup(b,n,Lbinit).

②生 成sk←MF.Setup(1λ)， 輸 出msk=(sk,Lb).

2） (ctm,t)←Enc(dmax,msk,m,t).輸入msk=(sk,Lb)和消息m∈M對 應(yīng)標(biāo)簽t∈T，通過2 個步驟生成密文ctm：

① (Rst,t)←InsPos.Insert(m,dmax,Lb)和skt=MF(sk,t).

② 生 成ctm=S E.Enc(skt,m)， 返 回 密 文ctm和 對 應(yīng)標(biāo)簽t.

3）skR←KRev(msk,R).輸入msk=(sk,Lb)和撤消標(biāo) 簽 列 表R={t1,t2,…,tτ}， 滿 足 τ ≤NL，NL為Lb中 已使用節(jié)點(diǎn)數(shù).通過2 個步驟生成R下撤消的密鑰skR：

① 計算Lb所 有置1 的索引節(jié)點(diǎn)位置集合IR={t:t∈[b]且t?R}.

② 計算集合skIR←MF.Punc(sk,IR)， 返回skR=(skIR,IR).

4）m←Dec(skR,ctm,t).輸入密文ctm、 對應(yīng)標(biāo)簽t，以及R下撤消后的密鑰skR，按2 個步驟恢復(fù)消息：

① 若t?IR，解密失敗，運(yùn)行②.

② 若t∈IR， 計 算skt=MF.Eval(skI,t) ， 計 算m=S E.Dec(skt,ctm).

4.3 方案描述

設(shè)Σadd=(S etup,S earch,Update)為一個前向安全的對稱可搜索加密方案，用于動態(tài)增加密文索引，并保證前向數(shù)據(jù)隱私，SRE=(KGen,Enc,KRev,Dec)為對稱可撤消加密算法（構(gòu)造方法詳見4.2 節(jié)）.算法1詳細(xì)描述 基于SRE和 Σadd的可搜索 加密方 案Σadd=(S etup,S earch,Update)的工作過程.

算法1.初始化Σ.Setup(1λ).

輸入：安全參數(shù) λ；

輸出：密鑰集K，關(guān)鍵詞狀態(tài) σ，密文索引數(shù)據(jù)庫EDB.

客戶端：

①(EDBadd,Kadd,σadd)←Σadd.S etup(1λ)；

③return((Kadd,Ks,Kt),(σadd,MS K,C,A,D),(EDBadd,EDBcache)).

初始化完成后，客戶端存儲密鑰K=(Kadd,Ks,Kt)、關(guān)鍵詞狀態(tài) σ =(σadd,MS K,C,A,D)，服務(wù)器存儲密文索引數(shù)據(jù)庫EDB=(EDBadd,EDBcache).

算法2.查詢 Σ.S earch(K,w,σ;EDB).

輸入：客戶端輸入密鑰集K，關(guān)鍵詞狀態(tài) σ，查詢關(guān)鍵詞w，服務(wù)器輸入密文索引數(shù)據(jù)庫EDB；

輸出：匹配結(jié)果集DB(w)及 更新后關(guān)鍵詞狀態(tài) σ′.

Step 1.生成查詢令牌 Σ.S earch(K,w,σ;EDB).

客戶端：

①c←C[w],mskw←MS K[w],D←D[w],

A←A[w]；

② ifc=⊥ then

③ return ?；

④ end if

⑤ 計算skR=(skA,A)←S RE.KRev((mskw,A),D)；

/*A來自A[w]，D來自D[w]*/

⑥發(fā)送skR和tkn=h(Ks,w)至服務(wù)器；

⑦←S RE.KGen(1λ,A)；

/*搜索后更新w對應(yīng)的msk*/

⑧MS K[w]←，C[w]←c+1.

Step 2.Σ.S earch(K,w,σ;EDB)結(jié)果搜索.

客戶端 & 服務(wù)器：

① 運(yùn)行 Σadd.S earch(Kadd,w||i,σadd;EDBadd)，服務(wù)器得到關(guān)于密文和標(biāo)簽對的列表((ct1,t1),(ct2,t2),···,(ct?,t?)).

服務(wù)器：

② 服務(wù)器使用skR按如下步驟解密所有密文{(cti,ti)}；

③ fori∈[1,?] do

④indi=S RE.Dec(skR,cti,ti)；

⑤ ifindi≠⊥ then

⑥NewInd←NewInd∪{indi,ti}；

⑦ else

⑧DelInd←DelInd∪{ti}；

⑨ end if

⑩ end for

?OldInd←EDBcache[tkn]；

?OldInd←OldInd{(ind,t):

?ti∈DelInds.t.t=ti}；

?Res←NewInd∪OldInd,

EDBcache[tkn]←Res；

? returnRes.

查詢算法用于實現(xiàn)對關(guān)鍵詞w的搜索操作，主要包括客戶端生成查詢令牌和結(jié)果搜索2 個步驟，即生成查詢令牌和結(jié)果搜索.

1） 查詢令牌生成.查詢令牌生成算法在客戶端運(yùn)行，輸入 (K,w,σ)， 通過查詢本地MS K,C,A,D的值，生成查詢令牌tkn和 穿刺密鑰skR，并發(fā)送到服務(wù)器.

Step1 中，客戶端執(zhí)行行①～⑥，根據(jù)待查詢的關(guān)鍵詞w，從MS K獲取密鑰mskw， 使用S RE算法生成撤消加密密鑰skR，使用偽隨機(jī)函數(shù)F生成查詢令牌tkn，將(tkn,skR)發(fā)送至密文索引服務(wù)器.執(zhí)行行⑦⑧，更新本地存儲狀態(tài) σ，隱藏查詢特征.同時由于行⑦⑧與Step2 在時間上可并行執(zhí)行，并不會對查詢效率造成明顯影響.

2） 結(jié)果搜索.服務(wù)器接收到查詢請求，解析查詢令牌tkn和 穿刺密鑰skR，運(yùn)行 Σadd搜索算法查詢密文索引數(shù)據(jù)庫EDB， 獲取關(guān)鍵詞w未穿刺節(jié)點(diǎn)所有密文索引，將搜索結(jié)果返回客戶端.

Step2 中，通 過 調(diào) 用 Σadd方 案 的 Σadd.S earch和S RE算法，計算查詢關(guān)鍵詞w相關(guān)的索引，去除已刪除索引，更新服務(wù)器端結(jié)果緩存EDBcache，并向客戶端返回查詢結(jié)果.

算法3.更新 Σ.Update(K,σ,op,w,ind;EDB).

輸入：客戶端輸入密鑰集K、關(guān)鍵詞狀態(tài) σ、操作類型op、更新關(guān)鍵詞w及對應(yīng)文檔索引ind，服務(wù)器輸入為密文索引數(shù)據(jù)庫EDB；

輸出：更新后的關(guān)鍵詞狀態(tài) σ′，密文索引數(shù)據(jù)EDB′.

客戶端：

①mskw←MS K[w]，i←C[w]，D←D[w]，A←A[w]；

②ifmskw←⊥then

③ (mskw,A)←S RE.KGen(1λ) ；

④MS K[w]←mskw，D[w]←D；

⑤i←0，C[w]←i；

⑥ end if

⑦ ifop=add then

⑧ 計算 (rst,t,A′)←FKt(w,ind)，InsPos.Insert(w,dmax,A)；

⑨ct←S RE.Enc(dmax,(mskw,A),ind,t)；

⑩A←A′； /*更新添加列表*/

? 運(yùn)行Σadd.Update(Kadd,add,w||i,(ct,t),σadd;EDBadd)； /*客戶端&服務(wù)器運(yùn)行*/

? else(i.e.,op=del)

?D←D[w]；

? ifposw≥0 then

?D′=InsPos.Insert(w,dmax,D)；

?D[w]←D′； /*更新刪除列表*/

? end if

? end if

數(shù)據(jù)更新包括插入和刪除2 類，即op=add和op=del.

插入文檔索引時，客戶端查找主密鑰列表，找出w對應(yīng)密鑰信息，利用節(jié)點(diǎn)位置選擇算法查找插入點(diǎn)位置，并利用SRE.Enc算法對索引進(jìn)行加密，修改本地密鑰位置使用標(biāo)志.將密文和標(biāo)簽對 (ct,A)發(fā)送至服務(wù)器，服務(wù)器運(yùn)行 Σadd.Update算法更新密文索引數(shù)據(jù)庫EDB.

刪除文檔索引時，通過InsPos.Test查找需要刪除的節(jié)點(diǎn)位置，并在刪除列表記錄刪除標(biāo)記，在下次生成搜索密鑰時對應(yīng)位置密鑰進(jìn)行穿刺，服務(wù)器因無法恢復(fù)對應(yīng)節(jié)點(diǎn)密鑰信息而無法解密，從而實現(xiàn)后向隱私.

5 方案分析

下面從插入位置選擇算法和搜索方案分析2 個方面對方案進(jìn)行理論分析.

5.1 插入位置選擇算法分析

需要記錄每個位置使用情況，至少需要1 b，對于一個節(jié)點(diǎn)規(guī)模為b列表，算法工作時需要分配b比特存儲空間.插入時的時間復(fù)雜度為多項式時間O(n).為了進(jìn)一步對算法的性能進(jìn)行評價，現(xiàn)給出節(jié)點(diǎn)利用率定義.

定義10.節(jié)點(diǎn)利用率.當(dāng)InsPos.Insert(x,dmax,Lb)首次輸出Rst=false 時，節(jié)點(diǎn)利用率 ρ=N/b，其中N為Lb中元素為1 的個數(shù).

由定義10 可以看出，因為0 ＜N≤b， 所以0 ＜ρ ≤1.隨著搜索深度dmax的增大，插入點(diǎn)生成時間增大，空間利用率逐步升高.當(dāng)dmax=b時，搜索插入點(diǎn)位置時間最長，節(jié)點(diǎn)利用率 ρ=1.在實際方案構(gòu)造過程中，提高節(jié)點(diǎn)利用率可有效減小節(jié)點(diǎn)規(guī)模、減少搜索時的通信開銷.

由定理1 可知，插入消息mi后導(dǎo)致發(fā)生誤刪除的概率與消息mi在 插入位置選擇算法中Rst=false的概率相等.當(dāng)最大搜索深度為dmax時 ，第i（i∈[b]）次選擇插入位置時InsPos.Insert算法輸出發(fā)生Rst=false的概率等于Lb在pm后 連續(xù)dmax+1個節(jié)點(diǎn)為1 的概率.

設(shè)位置選擇時每次均是從空余節(jié)點(diǎn)中隨機(jī)選擇一個位置，則設(shè)指紋長度足夠的情況下，節(jié)點(diǎn)規(guī)模為b、搜索深度為dmax的 列表在第N+1(N≥dmax)次插入失敗的概率為

5.2 搜索方案分析

結(jié)合本文方案的實現(xiàn)過程，從搜索效率、存儲開銷、通信開銷和安全性等方面進(jìn)行分析.

1）搜索效率

搜索時服務(wù)器僅需要計算使用的密鑰節(jié)點(diǎn)，相比每次均需要計算GGM 樹所有節(jié)點(diǎn)密鑰的Aura 方案，平均搜索時間更低.實際上GGM 樹節(jié)點(diǎn)計算隨著節(jié)點(diǎn)規(guī)模的擴(kuò)大而迅速增加，在節(jié)點(diǎn)規(guī)模較大、但使用節(jié)點(diǎn)較少的場景中，每個索引平均搜索時間將迅速增加.本文方案平均搜索時間受節(jié)點(diǎn)規(guī)模影響較小，在節(jié)點(diǎn)規(guī)模較大但使用節(jié)點(diǎn)較少時具有明顯的優(yōu)勢.

2）存儲開銷

客戶端需要為每個節(jié)點(diǎn)存儲指紋、使用標(biāo)志、刪除標(biāo)志，通常使用標(biāo)志和刪除標(biāo)志僅需1 b 存儲空間，則客戶端需要預(yù)先為每個節(jié)點(diǎn)分配n+2比特存儲空間，其中n為每個節(jié)點(diǎn)指紋寬度.

服務(wù)器中需要存儲索引密文和節(jié)點(diǎn)位置信息，相比Aura 中密文大小為索引密文大小的整數(shù)倍，不會導(dǎo)致密文規(guī)模擴(kuò)張，存儲空間占用更低，如表2 所示.

Table 2 Scheme Comparison表2 方案對比

3）通信開銷

本文方案采用文獻(xiàn)[22]的節(jié)點(diǎn)壓縮算法對傳輸節(jié)點(diǎn)進(jìn)行壓縮，但與Aura 刪除前僅需傳輸單個節(jié)點(diǎn)信息不同，由于每次選擇節(jié)點(diǎn)位置是隨機(jī)的，在插入文檔索引較少時，節(jié)點(diǎn)壓縮率也較低，隨著使用節(jié)點(diǎn)數(shù)量增多，傳輸節(jié)點(diǎn)數(shù)量將逐步降低.

在刪除索引時，Aura 由于中間使用的索引位置被刪除，通常需要發(fā)送更多的節(jié)點(diǎn).

4）安全性

本文方案通過在服務(wù)器端增加EDBcache保存上次查詢結(jié)果，并在每次查詢后更新查詢密鑰，以保護(hù)數(shù)據(jù)訪問特征.下面通過真實游戲Real和理想游戲Idea對方案安全性進(jìn)行證明.

RealΣA(k).攻 擊 者 A選 擇 數(shù) 據(jù) 庫DB，DO 運(yùn) 行S etup(DB)算法生成檢索索引EDB并發(fā)送給攻擊者.A按一定規(guī)則選擇一系列查詢q， DO 運(yùn)行Trapdoor(q)算法生成的 Tq并發(fā)送給 A.服務(wù)器運(yùn)行Search(EDB,將運(yùn)行的所有結(jié)果發(fā)送給A.最后， A輸出一個比特b.

IdeaΣA,S.模擬器初始化查詢數(shù)組q.A 選擇數(shù)據(jù)庫DB，DO 運(yùn)行 S(L(DB))算法生成檢索索引并發(fā)送給A.接著， A 按一定規(guī)則的選擇查詢q.模擬器記錄下查詢q[i]， 運(yùn)行S(L(q,DB)).最后， A 輸出一個比特b.

定理2.方案 Σ后向隱私自適應(yīng)安全.設(shè)sp(w)為關(guān)鍵詞w的搜索特征，TimeDB(w) 表 示關(guān)鍵詞w有關(guān)索引（去除刪除索引），DelTime(w) 表示關(guān)鍵詞w上的刪除操作的時間戳，方案 Σ的泄露函數(shù) LBS定義為

其中：

若 Σadd為前向自適應(yīng)隱私的對稱可搜索加密方案，SRE 滿足IND-sREV-CPA 安全，則方案 Σ為隨機(jī)預(yù)言機(jī)模型下對所有多項式時間攻擊者 A是TypeⅡ后向隱私自適應(yīng)安全的.

證明.設(shè)多項式時間攻擊者 A在模擬器S中所取得的最大優(yōu)勢記為AdvA,S(λ)，Gi表 示Gamei，Pr[E]表示事件E發(fā)生的概率.證明定理2的關(guān)鍵是針對自適應(yīng)A構(gòu)造一個高效的模擬器S，使得Pr[=1]-(λ)成 立，其中(λ)是可忽略的.

利用構(gòu)造法，從真實游戲構(gòu)造一個滿足要求的高效模擬器S，進(jìn)而證明定理2.

Game 0.G0為 完全按照方案 Σ運(yùn)行的真實游戲，則有

Game 1.在G0基 礎(chǔ)上，將偽隨機(jī)函數(shù)F使用隨機(jī)數(shù)代替，并將生成的隨機(jī)數(shù)存入數(shù)組中，在下次調(diào)用時重新找出生成的隨機(jī)數(shù).在攻擊者視野下，相同的輸入均會獲得相同的隨機(jī)數(shù).

由于偽隨機(jī)函數(shù)計算上具有不可區(qū)分性，不防設(shè)使用真隨機(jī)數(shù)代替函數(shù)F，對所有多項式時間攻擊者B1獲 得 的最 大 優(yōu) 勢 為(λ) ，其 中(λ)是可忽略函數(shù).

方案 Σ中每次新加入的關(guān)鍵詞和生成密文標(biāo)簽均采用隨機(jī)數(shù)代替，則攻擊者B1能夠獲得2 倍的優(yōu)勢，即

Game 2.在G1基 礎(chǔ)上，將前向安全SSE 方案Σadd使用模擬器代替，同時在服務(wù)器端維護(hù)一個更新操作列表Ladd，在攻擊者發(fā)出查詢操作時再執(zhí)行更新操作.由于 Σadd滿足前向隱私，更新操作不會泄露關(guān)鍵詞和索引的有關(guān)信息.

Ladd包 含了方案 Σ 搜索時泄露的信息，即搜索特征sp(w) 、 索引密文及對應(yīng)標(biāo)簽、更新時間u.Ladd反映了關(guān)鍵詞w通過方案 Σadd執(zhí)行添加操作更新的歷史記錄，并作為方案 Σadd的模擬器的輸入.針對方案 Σadd的多項式時間的攻擊者Badd，存在一個模擬器，滿足

其中(λ)是可忽略的.

Game 3.在G2基礎(chǔ)上，在執(zhí)行可穿刺加密操作前將已刪除文檔索引置為0.由于SRE 是IND-sREVCPA 安全的[22]，因此對攻擊者B3存在一個高效的模擬器SSRE，滿足

其中(λ)是可忽略的.

Game 4.使用更新列表獲得泄露信息TimeDB和DelHist，重建索引添加列表Ladd、 使用標(biāo)志A和刪除標(biāo)志D，并作為模擬器的輸入.若假設(shè)每個文檔索引只會被添1 次和刪除1 次，則標(biāo)簽不會被重復(fù)使用，也就不必為了保證一致性而為每個密文索引存儲對應(yīng)的密文標(biāo)簽.

在G4中，僅對模擬器的工作方式進(jìn)行了修改，即

為構(gòu)造理想游戲的模擬器，不能直接調(diào)用關(guān)鍵詞w，而改用查詢特征sp[w] 來生成令牌信息.同時，不再保持維護(hù)更新記錄的列表，而是利用搜索查詢中的泄露信息TimeDB(w)，DelTime(w)重建添加列表Ladd和 節(jié)點(diǎn)使用標(biāo)志A、 刪除標(biāo)志D.這樣利用 LBS有關(guān)信息，構(gòu)造了一個高效的模擬器S，使得

將以上多項式時間攻擊者B1，Badd，B3對 方案 Σ攻擊所獲得的優(yōu)勢相加，可得

其中(λ)是可忽略的，即定理2 成立.證畢.

6 方案測試

方案性能測試所采用的軟/硬件環(huán)境配置如表3所示.

Table 3 Environment Configuration of Software/Hardware for Testing表3 測試軟/硬環(huán)境配置

6.1 插入點(diǎn)位置選擇算法測試

插入點(diǎn)位置選擇算法中，消息位置、消息指紋所使用的哈希函數(shù)均采用SpookyHash V2 算法，隨機(jī)生成消息m，發(fā)生第1 次插入失敗（即未找到可用節(jié)點(diǎn)或發(fā)生指紋沖突）時，每個搜索深度下隨機(jī)生成500組索引，節(jié)點(diǎn)利用率 ρ的平均值隨指紋寬度n和搜索深度dmax的變化關(guān)系如圖3 所示.

Fig.3 The curve of node utilization rate圖3 節(jié)點(diǎn)利用率曲線

可以看出，在n=32，dmax=100時能夠保證較高的節(jié)點(diǎn)利用率.

6.2 搜索方案性能測試

對稱加密算法采用AES，哈希算法選用計算速度較快的SpookyHash V2，偽隨機(jī)數(shù)發(fā)生器采用GGM 算法實現(xiàn)，采用支持分布式部署的非關(guān)系數(shù)據(jù)庫rocksDB 作為密文索引數(shù)據(jù)庫.測試中，隨機(jī)生成文檔索引，利用 Σ.Update算法添加至密文索引數(shù)據(jù)庫.

如表4 所示，從存儲空間開銷可以看出，Aura 在服務(wù)器中因需要同時存儲多個密文備份，服務(wù)器占用空間開銷更大.相比Aura 方案，本文方案每個密文索引不存在密文擴(kuò)展，實際平均每條索引占用存儲空間開銷更小.在客戶端，密文刪除操作需要為每個節(jié)點(diǎn)存儲一個指紋，存儲客戶端存儲空間開銷為O(b).節(jié)點(diǎn)實際占用空間包含了rocksDB 內(nèi)部存儲結(jié)構(gòu)數(shù)據(jù)，方案實際占用的空間相比測試值要更小.另外，采用質(zhì)量更好的指紋哈希算法，降低每個節(jié)點(diǎn)的指紋長度，也可進(jìn)一步快速降低客戶端中存儲空間的大小.

Table 4 Actual Storage Overhead of Schemes表4 方案實際存儲開銷

由于GGM 樹隨著節(jié)點(diǎn)規(guī)模的擴(kuò)大，其計算時間迅速增加，如圖4 所示，本文方案通過增加節(jié)點(diǎn)使用列表，避免每次搜索時服務(wù)器需要生成全部穿刺密鑰，大大減少在匹配節(jié)點(diǎn)較少時搜索的響應(yīng)時間，隨著匹配節(jié)點(diǎn)數(shù)的增多，方案平均搜索時間趨于一致.

Fig.4 The comparison of actual search time（N = 100 000）圖4 實際搜索時間對比（N = 100 000）

如圖5 所示，在節(jié)點(diǎn)規(guī)模b=60 000時，客戶端運(yùn)行查詢算法時向服務(wù)器發(fā)送的節(jié)點(diǎn)個數(shù)隨節(jié)點(diǎn)利用率 ρ的變化情況.在插入文檔索引較少時，發(fā)送數(shù)據(jù)隨文檔索引增加而增加，當(dāng) ρ ＞0.3時，發(fā)送的節(jié)點(diǎn)數(shù)逐漸提高.

圖6 為刪除索引后查詢到的匹配節(jié)點(diǎn)個數(shù)變化情況，可以看出本文方案不會發(fā)生誤刪除.圖7 為刪除索引時方案通信開銷變化情況.從圖7 可以看出，在頻繁發(fā)生索引刪除的DSSE 應(yīng)用場景下，本文方案通信開銷也隨著刪除節(jié)點(diǎn)增多而逐漸降低.

Fig.6 Search results after index deletion（b = 60 000, N =30 000）圖6 刪除索引后搜索結(jié)果（b = 60 000, N = 30 000）

Fig.7 Scheme communication overhead comparison after index deletion（b = 60 000, N = 30 000）圖7 刪除索引后方案通信開銷對比（b = 60 000, N =30 000）

7 總 結(jié)

本文結(jié)合可搜索加密方案的應(yīng)用場景，給出了動態(tài)對稱可搜索方案的形式化描述.同時給出了SRE 更嚴(yán)格的正確性定義，并通過理論分析證明了避免誤刪除發(fā)生的條件.在設(shè)計插入點(diǎn)位置選擇算法的基礎(chǔ)上，構(gòu)造了基于SRE 的對稱可搜索加密方案.

大多數(shù)情況下，關(guān)鍵詞的使用密鑰節(jié)點(diǎn)數(shù)遠(yuǎn)小于未使用節(jié)點(diǎn)數(shù)，通過為每個關(guān)鍵詞添加節(jié)點(diǎn)插入標(biāo)志，記錄每個關(guān)鍵詞實際使用的節(jié)點(diǎn)位置信息，查詢時只發(fā)送已使用節(jié)點(diǎn)，可以大大降低服務(wù)器恢復(fù)密鑰時的時間開銷.理論分析和實現(xiàn)結(jié)果表明，本文方案進(jìn)一步優(yōu)化了Aura 方案搜索效率，有效避免了節(jié)點(diǎn)誤刪除問題.然而方案需要在客戶端存儲更多節(jié)點(diǎn)信息，增加了客戶端數(shù)據(jù)存儲開銷，同時在刪除索引較少的場景下，本文方案具有更大的通信開銷.下一步將在減少客戶端存儲開銷、方案通信開銷以及多客戶端場景下的擴(kuò)展等問題上展開進(jìn)一步研究.

作者貢獻(xiàn)聲明：黃一才提出了算法思路和實驗方案，并撰寫了論文；郁濱提出指導(dǎo)意見并修改論文；李森森參與了實驗方案制定及部分?jǐn)?shù)據(jù)分析與整理.