基于語義分組的動態可搜索加密方案①

王澤賢,汪學明

（貴州大學 計算機科學與技術學院,貴陽 550025）

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

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

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

為應對惡意服務器環境,Wang等人[7]提出一種可驗證的動態可搜索加密方案.該方案構造了基于時間戳鏈表和Merkle樹結果驗證機制,實現惡意服務器環境下的正確搜索.

為提高搜索效率,2019年Xu等人[8]提出了基于R-樹動態范圍搜索SE方案.該方案采用R-樹索引結構顯著提高搜索效率,并提出一種新的訪問控制策略EGRQ實現用戶的細化訪問.

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

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

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

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

1 系統模型

（1）數據擁有者DO創建關鍵詞字典、加密文檔、構建安全索引,將它們上傳到云服務器.

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

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

圖1 系統模型圖

2 相關工作

2.1 符號定義

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

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

W:表示關鍵詞字典W={w1,w2,…,wm}.

Q:查詢向量.

T:未加密的索引向量.

I:加密的索引向量.

Tw:搜索陷門.

K:返回結果數.

sk:對稱密鑰.

Fup:更新文檔集.

Wup:更新關鍵詞集.

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

S:m+d階隨機二進制向量.

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

u.ID:樹節點u的唯一標識.

u.FID:葉子結點指向的文件的標識.如果u為非葉子結點,則u.FID=none.

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

Left,right:當節點u為非葉子節點時,left為其左孩子節點,right為其右孩子節點.

Tu:表示樹節點u的加權索引向量.

ResultNodeSet:表示一個分組集合.

2.2 安全性定義

定義1.泄露函數L1,L2,L3

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

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

2.3 TF-IDF和空間向量模型

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

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

向量空間模型將文檔和查詢都看成是關鍵詞的集合,是關鍵詞的有序排列.我們可以根據倒排序列構建關鍵詞的字典,用二進制向量來表示文檔和查詢.把查詢抽象化為數學形式表示,用0和1表示查詢文檔中是否存在詞典對應位置的關鍵詞.

2.4 ASPE加密算法

ASPS算法由Wang等人[14]在2009年Sigmoid上提出,ASPE算法核心功能其實是實現了兩個加密向量之間的安全內積計算.

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

3 基于語義分組的動態可搜索加密方案定義

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

4 基于語義分組的動態可搜索加密方案

4.1 方案構造

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

構建索引分為如下5個步驟.

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

2）構建明文形式的二進制索引:根據空間向量模型數據擁有者為文檔fj,生成二進制向量Tj.Tj的每個比特表示fj中相應關鍵詞存在與否.

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

其中,|f|表示文檔的長度,tfi,j表示關鍵詞i在文檔fj中出現的概率,dfi表示包含關鍵詞i的文檔數量.

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

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

為完成節點分組,設計了算法1.

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

由算法1構成的索引樹如圖2所示.

圖2 由6個文件、5個關鍵詞構成的索引樹

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

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

圖3 分組平衡二叉樹查詢

當計算加密索引和安全陷門相關后,返回得分前K的文檔,用戶使用對應密鑰解密文檔.搜索完畢.

分區矩陣保證了已有的節點向量不變的基礎上,僅對更新文檔進行構建加密.既不會泄露新添加關鍵字在字典中的分布,也減少了更新時產生的計算開銷.

4.2 方案正確性分析

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

4.3 方案安全性分析

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

根據定義2可得,如果本文方案滿足對于任意多項式時間內的敵手都能使得式（14）成立:

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

具體的證明過程如下:

Adv（A（SK,sk））表示敵手A判斷密鑰和隨機矩陣的優勢.Adv（A（I））表示敵手A判斷云端存儲索引的優勢.Adv（A（C））表示敵手A區分真實密文中加密文檔的優勢.Adv（A（Tw））表示敵手判斷不同陷門之間相關性的優勢.Adv（A（W））表示敵手A判斷關鍵字字典中關鍵字分布的優勢.

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

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

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

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

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

綜上所述可得:

使得式（22）成立:

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

4.4 方案效率分析

本節從構建加密索引、搜索、更新3個方面進行效率分析,將本文方案與文獻[8-11,13]方案進行對比.

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

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

在文檔更新方面.本文采用分區矩陣思想進行更新,保持原有字典不變的基礎上通過構建l×l階矩陣完成更新.L為真實關鍵字和虛擬關鍵字的總數.故時間復雜度為O（l2）.

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

表1 效率分析對比

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

5 結束語

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