王澤賢,汪學(xué)明

（貴州大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,貴陽 550025）

為了降低本地資源的計(jì)算開銷,越來越多的人選擇將個人數(shù)據(jù)上傳到不可信的云存儲服務(wù)器中,然而云服務(wù)器存在泄露用戶隱私的諸多威脅.權(quán)衡云環(huán)境既存在安全威脅又具備便利性的特點(diǎn),很多人將本地信息加密后在上傳到云服務(wù)器中從而起到保護(hù)數(shù)據(jù)安全的作用.隨著用戶和企業(yè)數(shù)據(jù)存儲量逐年增長,如果將全部數(shù)據(jù)不加區(qū)分地放在一起進(jìn)行加密和搜索,不僅增加加密復(fù)雜度,而且影響搜索效率.

可搜索加密（Searchable Encryption,SE）技術(shù)[1]是實(shí)現(xiàn)隱私數(shù)據(jù)加密上傳到云端后搜索的重要技術(shù).對此國內(nèi)外學(xué)者展開研究取得了許多成果.Song等[2]首先提出了一個數(shù)據(jù)共享者和一個查詢用戶模型下的對稱可搜索加密方案,該方案通過對所有密文進(jìn)行線性掃描的方式完成搜索.為了提升SE方案的可用性,2011年Cao等人[3]首次提出了MRSE方案,該方案成功解決了多關(guān)鍵字的排序問題,但該方案的缺點(diǎn)是既不支持相似性搜索查詢且效率也較低.隨后Xia等[4]設(shè)計(jì)了一種特殊的樹狀索引結(jié)構(gòu),采用貪婪深度搜索算法提高效率,同時用KNN技術(shù)加密文件和索引保證方案的安全性.

上述方案基本解決了SSE方案搜索需求的問題.但是本地數(shù)據(jù)的大量產(chǎn)生,用戶急需對云端的文檔進(jìn)行更新從而保證文檔的完整性.這使得支持動態(tài)更新的SE方案成為新的研究熱點(diǎn).然而Zhang等人[5]在2016年發(fā)現(xiàn)文檔更新時通過文件注入式攻擊會泄露用戶的隱私.為解決這一問題Bost等人[6]在2017年提出了支持前向安全和后向安全的SSE方案.但是該方案只支持單關(guān)鍵字的搜索,為了進(jìn)一步提升動態(tài)可搜索加密的性能和效率國內(nèi)外學(xué)者展開廣泛研究并取得豐碩成果.

為應(yīng)對惡意服務(wù)器環(huán)境,Wang等人[7]提出一種可驗(yàn)證的動態(tài)可搜索加密方案.該方案構(gòu)造了基于時間戳鏈表和Merkle樹結(jié)果驗(yàn)證機(jī)制,實(shí)現(xiàn)惡意服務(wù)器環(huán)境下的正確搜索.

為提高搜索效率,2019年Xu等人[8]提出了基于R-樹動態(tài)范圍搜索SE方案.該方案采用R-樹索引結(jié)構(gòu)顯著提高搜索效率,并提出一種新的訪問控制策略EGRQ實(shí)現(xiàn)用戶的細(xì)化訪問.

為提高更新效率,2020年Huang等人[9]提出了基于完美二叉樹的前向安全SE方案.作者通過預(yù)估更新大小,構(gòu)建完美索引樹結(jié)構(gòu),避免更新時重構(gòu)節(jié)點(diǎn)造成的本地開銷.Kermanshahi等人[10]首次提出了內(nèi)容隱私的定義.該方案在更新時,本地客戶端首先構(gòu)建更新令牌（包含更新的位置和更新內(nèi)容）并加密上傳到云端.具體的更新過程由服務(wù)器完成,從而降低本地開銷.孫曉玲等人[11]提出了基于三鏈表索引結(jié)構(gòu)的高效動態(tài)可搜索加密方案.該方案通過每次搜索操作更新查詢鏈表和刪除鏈表的策略有效的提高了更新的效率.

在多用戶場景下,Wang等人[12]通過引入半可信的第三方服務(wù)器用于記錄關(guān)鍵詞的狀態(tài)信息,提出了一種支持多用戶訪問的前向安全動態(tài)可搜索加密方案.但該方案存在無法抵抗重放攻擊和竊聽攻擊等安全缺陷.隨后盧冰潔等人[13]對此做出了改進(jìn),通過引入完全可信第三方服務(wù)和構(gòu)建新的索引結(jié)構(gòu),提高了方案的安全性和刪除效率.

上述方案雖然在性能和效率方面取得巨大提升,但對索引結(jié)構(gòu)的更新大多采用在已有索引的尾部直接添加的方法,泄露了新添加關(guān)鍵字和已有文檔的信息,以及新添加關(guān)鍵字在字典中排列的位置.這造成更新時極大的安全隱患.

為此本文提出了基于語義分組的動態(tài)更新可搜索加密方案（Scheme of Dynamic Searchable Encryption based on semantic grouping,SDSE）.首先通過TFIDF和空間向量模型構(gòu)建節(jié)點(diǎn)向量,根據(jù)計(jì)算節(jié)點(diǎn)的相關(guān)性進(jìn)行語義分組構(gòu)建索引樹.然后向節(jié)點(diǎn)向量中添加虛擬關(guān)鍵字完成向量擴(kuò)充,保證字典排布的安全性.最后結(jié)合分區(qū)矩陣思想提出一種更新方法.實(shí)現(xiàn)了在原有關(guān)鍵字字典的基礎(chǔ)上能夠動態(tài)更新云端文件.

1 系統(tǒng)模型

（1）數(shù)據(jù)擁有者DO創(chuàng)建關(guān)鍵詞字典、加密文檔、構(gòu)建安全索引,將它們上傳到云服務(wù)器.

（2）用戶DU生成查詢陷門,并將陷門和想要返回的結(jié)果數(shù)量K發(fā)送到云服務(wù)器,收到云端計(jì)算完成的最相關(guān)的K個結(jié)果文檔后對其進(jìn)行解密.

（3）云服務(wù)器收到DU的搜索請求后,CS對加密索引進(jìn)行搜索,并計(jì)算返回用戶最希望的前K個結(jié)果文檔.系統(tǒng)模型圖如圖1所示.

圖1 系統(tǒng)模型圖

2 相關(guān)工作

2.1 符號定義

F:表示明文文件集合F={f1,f2,…,fn}.

C:表示對應(yīng)明文F的密文集合C={c1,c2,…,cn}.

W:表示關(guān)鍵詞字典W={w1,w2,…,wm}.

Q:查詢向量.

T:未加密的索引向量.

I:加密的索引向量.

Tw:搜索陷門.

K:返回結(jié)果數(shù).

sk:對稱密鑰.

Fup:更新文檔集.

Wup:更新關(guān)鍵詞集.

SK:安全密鑰對{S,M1,M2}.

S:m+d階隨機(jī)二進(jìn)制向量.

M1,M2:（m+d）×（m+d）階可逆矩陣.

u.ID:樹節(jié)點(diǎn)u的唯一標(biāo)識.

u.FID:葉子結(jié)點(diǎn)指向的文件的標(biāo)識.如果u為非葉子結(jié)點(diǎn),則u.FID=none.

u.V:表示結(jié)點(diǎn)u所包含的m長的向量,如果u是葉節(jié)點(diǎn),則u.V為文件u.FID的加權(quán)索引.如果u是非葉子結(jié)點(diǎn),則u.V表示為以u為根的子樹中所有結(jié)點(diǎn)向量對應(yīng)維度的最大值u.V[t]=max（u1.V[t],u2.V[t],…）t∈{1,2,…,m}.

Left,right:當(dāng)節(jié)點(diǎn)u為非葉子節(jié)點(diǎn)時,left為其左孩子節(jié)點(diǎn),right為其右孩子節(jié)點(diǎn).

Tu:表示樹節(jié)點(diǎn)u的加權(quán)索引向量.

ResultNodeSet:表示一個分組集合.

2.2 安全性定義

定義1.泄露函數(shù)L1,L2,L3

1）L1（F）以文檔作為輸入,L1輸出關(guān)鍵詞的個數(shù)m,文檔數(shù)n,每個文檔的標(biāo)識以及文檔fj包含關(guān)鍵詞的個數(shù),關(guān)鍵字字典W.具體形式如下:

如果方案SDSE對于自適應(yīng)關(guān)鍵字搜索是安全的,那么對于任意多項(xiàng)式時間內(nèi)的敵手,一定存在模擬器S使得式（4）成立:

2.3 TF-IDF和空間向量模型

空間向量模型和TF-IDF規(guī)則是解決傳統(tǒng)搜索領(lǐng)域的有效手段,通過建立關(guān)鍵詞字典集合與查詢文檔之間的關(guān)系,實(shí)現(xiàn)多關(guān)鍵詞的有效排序搜索.TFfj,wi表示在文檔fj中關(guān)鍵詞wi出現(xiàn)的頻率.令I(lǐng)DFwi表示含有關(guān)鍵詞wi的文件在文檔總集中出現(xiàn)的頻率.TFfj,wi和IDFwi分別采用式（5）和式（6）計(jì)算得到:

其中,TFfj,wi為fj中關(guān)鍵字wi的個數(shù);n為F中的文件總數(shù);Nwi為包含關(guān)鍵詞wi的文件數(shù).一般采用歸一化的詞頻TF'fj,wi和逆文檔頻率IDF'wi,即:

向量空間模型將文檔和查詢都看成是關(guān)鍵詞的集合,是關(guān)鍵詞的有序排列.我們可以根據(jù)倒排序列構(gòu)建關(guān)鍵詞的字典,用二進(jìn)制向量來表示文檔和查詢.把查詢抽象化為數(shù)學(xué)形式表示,用0和1表示查詢文檔中是否存在詞典對應(yīng)位置的關(guān)鍵詞.

2.4 ASPE加密算法

ASPS算法由Wang等人[14]在2009年Sigmoid上提出,ASPE算法核心功能其實(shí)是實(shí)現(xiàn)了兩個加密向量之間的安全內(nèi)積計(jì)算.

定義3.非對稱保內(nèi)積加密.對于加密算法E（）,查詢點(diǎn)記為q,數(shù)據(jù)D中任意點(diǎn)記為Pi,如果E（）滿足下列兩個條件,則稱之為非對稱的保內(nèi)積加密算法:

3 基于語義分組的動態(tài)可搜索加密方案定義

SDSE方案由如下5個算法組成:（初始化（Setup）、構(gòu)建索引（Index）、構(gòu)建陷門（Trapdoor）、查詢（Search）,更新（Update）具體定義如下所示:

4 基于語義分組的動態(tài)可搜索加密方案

4.1 方案構(gòu)造

初始化階段DO根據(jù)關(guān)鍵詞字典產(chǎn)生用于拆分索引和查詢向量的m+d維二進(jìn)制向量S,以及兩個（m+d）×（m+d）階可逆矩陣{M1,M2}用于加密拆分后的向量.對稱密鑰sk用于加密明文文檔,安全密鑰SK={S,M1,M2}用于加密安全索引和查詢向量.

構(gòu)建索引分為如下5個步驟.

1）抽取關(guān)鍵詞:數(shù)據(jù)擁有者對文檔集F抽取關(guān)鍵詞得到關(guān)鍵字字典W={w1,w2,…,wn}.

2）構(gòu)建明文形式的二進(jìn)制索引:根據(jù)空間向量模型數(shù)據(jù)擁有者為文檔fj,生成二進(jìn)制向量Tj.Tj的每個比特表示fj中相應(yīng)關(guān)鍵詞存在與否.

3）生成加權(quán)索引:本文中關(guān)鍵詞的權(quán)重由關(guān)鍵詞出現(xiàn)的概率以及它出現(xiàn)的位置決定.TF-IDF的方法來計(jì)算關(guān)鍵詞和文檔之間的相關(guān)度.在根據(jù)關(guān)鍵詞在文中所處的位置分別賦予不同的權(quán)重,本文把關(guān)鍵詞的位置分為如下3類:標(biāo)題,摘要,正文.分別使得標(biāo)題占0.6,摘要占0.3,正文占0.1的權(quán)重.假設(shè)某文檔f中關(guān)鍵詞w出現(xiàn)在標(biāo)題和正文中,我們用如下公式來表示它的權(quán)重:X=0.6×1+0.3×0+0.1×1=0.7,采用TF-IDF權(quán)值計(jì)算方法來計(jì)算關(guān)鍵詞相關(guān)度分?jǐn)?shù):

其中,|f|表示文檔的長度,tfi,j表示關(guān)鍵詞i在文檔fj中出現(xiàn)的概率,dfi表示包含關(guān)鍵詞i的文檔數(shù)量.

4）構(gòu)建索引樹:本方案設(shè)計(jì)了一種新的索引結(jié)構(gòu)-分組平衡二叉樹,構(gòu)建這種樹型索引時,以自下而上的策略對每一層的樹節(jié)點(diǎn)進(jìn)行分組,使得主題越接近的文檔盡可能地分布于索引樹的同一分支.

所有葉子結(jié)點(diǎn)生成完畢后,采用自下而上的策略,基于分組構(gòu)造索引樹.每一層的非葉子結(jié)點(diǎn)都是由分組算法生成,把加權(quán)索引的余弦值較小的兩個結(jié)點(diǎn)組成一對.

為完成節(jié)點(diǎn)分組,設(shè)計(jì)了算法1.

樹節(jié)點(diǎn)分組完成后,如果節(jié)點(diǎn)總數(shù)為2n個,那么ResultNodeSet中就有n個節(jié)點(diǎn)對; 如果節(jié)點(diǎn)總數(shù)為2n+1個,那么就有n個節(jié)點(diǎn)對和1個單節(jié)點(diǎn).然后在分組對的基礎(chǔ)上構(gòu)造一個新的節(jié)點(diǎn)作為他們的父節(jié)點(diǎn),這樣反復(fù)迭代直到最終生成唯一的根節(jié)點(diǎn).

由算法1構(gòu)成的索引樹如圖2所示.

圖2 由6個文件、5個關(guān)鍵詞構(gòu)成的索引樹

收到DU的搜索請求后,CS使用深度貪婪優(yōu)先算法在上傳的加密安全索引樹上進(jìn)行搜索.具體形式如算法2.

在分組平衡二叉樹中是如何執(zhí)行貪婪深度優(yōu)先搜索的過程如圖3所示.

圖3 分組平衡二叉樹查詢

當(dāng)計(jì)算加密索引和安全陷門相關(guān)后,返回得分前K的文檔,用戶使用對應(yīng)密鑰解密文檔.搜索完畢.

分區(qū)矩陣保證了已有的節(jié)點(diǎn)向量不變的基礎(chǔ)上,僅對更新文檔進(jìn)行構(gòu)建加密.既不會泄露新添加關(guān)鍵字在字典中的分布,也減少了更新時產(chǎn)生的計(jì)算開銷.

4.2 方案正確性分析

本節(jié)進(jìn)行證明即使矩陣擴(kuò)展到m+d+l階,仍然可以正常匹配.并不會影響搜索結(jié)果的排序.其中ε為添加虛擬關(guān)鍵字時產(chǎn)生的平衡參數(shù).即使搜索相同的關(guān)鍵字得分也存在差異從而保證了在搜索過程中索引和陷門的安全.但由于ε的取值遠(yuǎn)小于TF的最小值,故不影響相關(guān)性結(jié)果的正常排序.以下為索引和陷門匹配的過程.

4.3 方案安全性分析

根據(jù)定義1可知,本文方案執(zhí)行搜索和更新時會泄露相關(guān)的信息.在分析SDSE方案的安全性之前,我們假設(shè)加密明文文檔的對稱加密算法是滿足選擇明文攻擊（CPA）的.

根據(jù)定義2可得,如果本文方案滿足對于任意多項(xiàng)式時間內(nèi)的敵手都能使得式（14）成立:

那么我們認(rèn)為本文方案在自適應(yīng)不可區(qū)分的意義上是安全的.敵手可以通過分析密鑰、索引、密文、陷門的不相關(guān)、關(guān)鍵字字典來獲得模擬游戲的勝利.

具體的證明過程如下:

Adv（A（SK,sk））表示敵手A判斷密鑰和隨機(jī)矩陣的優(yōu)勢.Adv（A（I））表示敵手A判斷云端存儲索引的優(yōu)勢.Adv（A（C））表示敵手A區(qū)分真實(shí)密文中加密文檔的優(yōu)勢.Adv（A（Tw））表示敵手判斷不同陷門之間相關(guān)性的優(yōu)勢.Adv（A（W））表示敵手A判斷關(guān)鍵字字典中關(guān)鍵字分布的優(yōu)勢.

本文方案中的安全密鑰是由兩個（m+d）×（m+d）階可逆矩陣和分割向量組成SK={S,M1,M2}.可逆矩陣和分割向量S組成的密鑰同隨機(jī)數(shù)矩陣和一串隨機(jī)二進(jìn)制數(shù)組成的密鑰在計(jì)算上是不可區(qū)分的,概率可以忽略不計(jì).故式（16）成立.

本文方案中的索引是由關(guān)鍵字字典加虛擬關(guān)鍵字在ASPE加密算法加密后得到.通過添加虛擬關(guān)鍵字模糊真實(shí)關(guān)鍵字的數(shù)量起到隱藏與關(guān)鍵字有關(guān)的標(biāo)識符.由于ASPE算法加密結(jié)果的不確定性使得即使得相同明文加密得出的密文也不同.故在計(jì)算上也是不可區(qū)分的.故式（17）成立:

根據(jù)前提假設(shè)可知本文加密算法是滿足CPA安全的,故式（18）成立:

本文方案中陷門是由關(guān)鍵字請求向量加虛擬關(guān)鍵字構(gòu)成.即使搜索相同的關(guān)鍵字在不同的時間段產(chǎn)生的請求向量也是不同的.然后通過ASPE加密算法進(jìn)行加密更加無法判斷.故式（19）成立:

本文方案中初始的關(guān)鍵字字典的安全性是由虛擬關(guān)鍵字和ASPE加密保證的.著重介紹更新時關(guān)鍵字字典的安全性.對于新產(chǎn)生的關(guān)鍵字通過添加虛擬關(guān)鍵字來模糊其在字典中的位置,然后通過分區(qū)矩陣的思想使其添加到原始字典中.這使得在判斷新添加關(guān)鍵字在字典中的位置以及相關(guān)文檔的概率可以忽略不計(jì).故式（20）成立:

綜上所述可得:

使得式（22）成立:

因此本文方案在泄露信息L1,L2,L3的情況下是安全的.

4.4 方案效率分析

本節(jié)從構(gòu)建加密索引、搜索、更新3個方面進(jìn)行效率分析,將本文方案與文獻(xiàn)[8-11,13]方案進(jìn)行對比.

在構(gòu)建索引上,本文方案和文獻(xiàn)[8-10]所提方案是基于二叉樹索引結(jié)構(gòu).分析加密索引樹效率時分3步; 構(gòu)建未加密索引樹需要經(jīng)過生成葉子結(jié)點(diǎn)、結(jié)點(diǎn)分組和構(gòu)建索引樹3個步驟.生成結(jié)點(diǎn)需要O（z）,因?yàn)殛P(guān)鍵詞字典的大小為m,所以每個結(jié)點(diǎn)生成索引向量耗時O（m）.計(jì)算關(guān)鍵詞之間相關(guān)度時間復(fù)雜度為O（m）.由于樹節(jié)點(diǎn)分組算法的時間復(fù)雜度為O（zm2）.所以構(gòu)建索引樹時間復(fù)雜度為O（zm2）.二叉樹中共有z個節(jié)點(diǎn),需要加密O（z）個節(jié)點(diǎn),向量分割時間復(fù)雜度為O（m）,語義相似度矩陣的兩次乘法時間復(fù)雜度為O（m2）.所以加密索引樹需要耗時O（zm2）.

在關(guān)鍵詞搜索方面,其搜索的時間取決于訪問的葉子節(jié)點(diǎn)數(shù),假設(shè)實(shí)際訪問的葉子節(jié)點(diǎn)數(shù)為L個,顯然L>k與k呈正相關(guān),文獻(xiàn)[9]中方案所構(gòu)造的搜索的時間復(fù)雜度O（Llog2n）.但本文方案與文獻(xiàn)[9]中方案的區(qū)別在于,平衡分組二叉樹把相關(guān)度高的結(jié)點(diǎn)都分到了同一子樹下,所以需要遍歷搜索的葉子節(jié)點(diǎn)數(shù)會大大少于未分組的平衡二叉樹,從而得到更高的查詢效率.

在文檔更新方面.本文采用分區(qū)矩陣思想進(jìn)行更新,保持原有字典不變的基礎(chǔ)上通過構(gòu)建l×l階矩陣完成更新.L為真實(shí)關(guān)鍵字和虛擬關(guān)鍵字的總數(shù).故時間復(fù)雜度為O（l2）.

表1給出了本案與已有方案的效率分析對比.其中,z表示二叉樹中節(jié)點(diǎn)總數(shù),m表示關(guān)鍵詞字典大小,n表示文檔總數(shù),L表示二叉樹索引中實(shí)際訪問節(jié)點(diǎn)數(shù),R表示范圍查詢的半徑,t表示范圍查詢坐標(biāo)位長,p表示更新文檔數(shù),l表示更新關(guān)鍵詞數(shù).

表1 效率分析對比

通過與最新成果對比可得,本文在搜索和更新方面具備較高效率.

5 結(jié)束語

本文提出了一種基于語義分組的動態(tài)關(guān)鍵詞可搜索加密方案.提出平衡分組二叉樹作為索引結(jié)構(gòu)使得返回的文檔更符合用戶的請求.結(jié)合分區(qū)矩陣思想進(jìn)行文檔更新.在保證關(guān)鍵字字典安全性的同時,減少了更新時的計(jì)算開銷.與現(xiàn)有的方案相比,本文方案具備更高的搜索效率和更新效率.但本文方案只考慮了單用戶模型,為更貼近云服務(wù)工作的實(shí)際情況.接下來的工作把本文方案拓展到多用戶場景下.