云計算下支持語義的可搜索加密方法研究

楊清琳，黃治國，錢文標，楊曉雷

(1.廣西財經學院 現代教育技術部，廣西 南寧 530003；2.河南工程學院 計算機學院，河南 鄭州 451191)

0 引 言

隨著云計算技術的日趨成熟和快速發展，把數據存儲在云端，只需較小的代價就能享受高效快捷的文件存儲和處理服務已經成為當下數據存儲的一種重要選擇。然而，數據安全和隱私保護如何有效地得到保障仍然是很多用戶所擔心的問題。常見的解決方法是將用戶數據先進行加密，再將加密后的密文數據上傳到云端，當用戶需要使用某個數據時，再從用戶密文中檢索出需要的文檔。如何對加密數據執行檢索等操作，是近年來可搜索加密(searchable encryption，SE)技術[1-2]研究的內容。

針對國內外學者可搜索加密技術的相關研究，大致可以分為單關鍵詞可搜索加密、多關鍵詞可搜索加密和模糊加密搜索。單關鍵詞可搜索加密[3-5]是基于對稱密碼學的精確的單關鍵字搜索機制，用戶只能在一次搜索過程中發送1個單詞，很難實現用戶的個性化需求，無法滿足用戶多關鍵詞查詢需求，因此支持多關鍵詞的可搜索加密被提出。Cao等[6]提出了MRSE(multi-keyword ranked search over encrypted cloud data)算法，該算法基于安全KNN(k-nearest neighbor)查詢技術創建文檔向量，增強了隱私數據保護，并利用可逆矩陣與文檔向量間“內積相似度”來實現多關鍵字的排序查詢。文獻[7]提出的多關鍵字的排序搜索方案利用樹構建索引結構，減少了搜索時間。文獻[8]基于同義詞查詢技術，提出了一種多關鍵字排序搜索算法，實現了在加密云數據上進行多關鍵詞排序搜索的功能。文獻[9]提出一種安全且高效的多關鍵詞密文排序檢索方案，同時支持動態更新和并行檢索。以上方法只有查詢關鍵詞跟預置的關鍵字完全匹配時，才能有檢索結果返回。為解決實際應用中用戶輸入的搜索請求會出現拼寫錯誤或格式不匹配的問題，模糊搜索方案被提出，實現了當用戶輸入的查詢關鍵字與預置的關鍵字不能精確匹配時，也能找到相關文檔。文獻[8，10]提出了一種將LSH(locality sensitive hashing)和安全KNN方法結合的新型多關鍵詞模糊搜索方案。文獻[11]基于布隆過濾器使用對偶編碼函數和位置敏感Hash函數來構建文件索引,并使用距離可恢復加密算法加密索引,實現了對多關鍵字的密文模糊搜索。文獻[12]將計數型布隆過濾器與MinHash算法結合，實現了一種可以減少索引構建和查詢陷門生成時間的模糊多關鍵詞檢索方案。然而，現有的模糊搜索方法中，針對的只是字符串上的模糊，而沒有實現關鍵詞語義上的搜索。例如，當用戶輸入關鍵詞“搜索”時，基于字符串匹配的方案只能返回那些包含有關鍵詞“搜索”的文檔，而實際應用中，包含了“檢索”或者“查詢”關鍵詞的文檔也有可能是用戶需要的結果。

針對現有的可搜索加密方案沒有對查詢關鍵詞進行語義擴展，導致用戶查詢意圖與返回結果存在語義偏差，無法滿足人們對智能搜索的要求，文中提出了一種支持語義的可搜索加密方法。利用本體知識庫對用戶查詢進行語義拓展，并引入了語義相似度和關鍵詞不同域加權評分，實現了對拓展后的關鍵詞進行權重計算并根據用戶需求設定閾值，防止因拓展詞過多而語義相似度較大時，影響檢索的精確度。并基于向量空間模型，利用文檔向量、查詢向量分塊技術構造出對應的標記向量，以過濾大量的無關文檔，并將語義相似度、關鍵詞不同位置加權評分及關鍵詞-文檔相關度等影響因子引入到查詢-文檔的相似度計算得分中，實現了檢索結果的有效排序。

1 支持語義的可搜索加密方法系統模型

1.1 系統框架模型

文中設定的系統框架模型如圖1所示。其中密鑰管理中心負責密鑰的生成和發放。數據用戶一方面將明文文檔及文檔索引加密成密文文檔及安全索引，并發送至公有云服務器，另一方面從明文文檔構造出文檔標記向量，發送至私有云。授權用戶根據自身需要輸入查詢關鍵詞，通過本體知識庫對關鍵詞進行語義擴展，再將擴展后的查詢生成查詢標記向量上傳給私有云，并使用密鑰對擴展后的查詢構造出陷門上傳給公有云服務器。私有云服務器的主要責任是存儲文檔標記向量，并根據授權用戶提交的查詢標記向量生成可能滿足授權用戶查詢請求的候選索引標識符， 提交給公有云，由公有云執行進一步的檢索操作。公有云服務器的主要責任是存儲密文文檔及安全索引，并根據授權用戶的查詢請求執行檢索服務。公有云通過私有云提交的候選索引標識符找出與之相應的安全索引，并用找出的安全索引與授權用戶提交的陷門來計算查詢-文檔相關度得分，返回得分最高的前Top-k篇文檔給授權用戶。

圖1 云計算下支持語義的可搜索加密系統模型

1.2 系統威脅分析

從圖1的系統模型中可以看出，用戶數據通過網絡上傳到云服務器中儲存，存在網絡攻擊者截取竊聽用戶數據的可能，但由于用戶數據上傳前是經過加密的，即使攻擊者盜取用戶數據，如果沒有獲取解密密鑰，也不能破解加密文件，因此該類攻擊對系統的威脅較弱。

另外公有云服務器具有“誠實而好奇”的特征[13-14]，它會正確地執行授權用戶提交的陷門完成查詢請求，并會根據私有云上傳的候選索引標識符找出與之相對的安全索引，完成檢索服務后會如實返回檢索結果，但是無法保證公有云不會采取一些措施去分析用戶數據、索引及查詢請求以獲取額外的用戶隱私信息。

文中探討的為已知密文模型，假設公有云在知道數據用戶上傳的加密文檔、加密索引和授權用戶發送的查詢陷門的前提下，無法利用查詢陷門構造出一個新的查詢陷門，并且私有云不會對外泄露標記向量信息，會如實地完成授權用戶提交的查詢請求并提交給公有云。并假定數據用戶和授權用戶是完全可信的，對存儲在公有云上的加密文檔有權限共享，不會通過其已了解的部分數據、索引、陷門、密鑰等信息來試圖攻擊其他用戶隱私信息，且密鑰已經安全分發，即數據用戶與授權用戶之間的密鑰授權已經完成。

2 云計算下支持語義的可搜索加密方法

2.1 關鍵詞-位置加權評分

(1)

2.2 基于領域本體的語義相似度計算

本體是以樹狀層次結構對概念進行描述和組織，從而構建出概念的語義空間，并使得概念樹中任意兩個概念節點之間的語義距離具有可計算性。

定義1：文中使用兩個節點間的語義距離來計算其語義相似度，對于已知的有向邊A→B，節點A的深度Deep(A)代表有向邊A→B的深度，則該A→B的語義距離定義為：

(2)

定義2：兩個概念節點Vi,Vj之間的語義距離定義為：

Dist(Vi,Vj)=Dist(Vi,Can(Vi,Vj))+

Dist(Vj,Can(Vi,Vj))

(3)

(4)

其中，MaxDeep為本體層次結構的最大深度。

2.3 計算關鍵詞-文檔相關度得分

文中使用關鍵詞詞頻*逆文檔率來計算關鍵詞與文檔的相關度，計算公式為：

tf-idf=tf(f,t)*idf(t)

(5)

其中，tf(f,t)為關鍵詞t在文檔f中出現的頻率，idf的計算公式為:

(6)

其中，N表示整個文檔集D中包含的所有文檔個數，n表示整個文檔集D中包含有關鍵詞t的文檔個數。

不難發現上述公式存在如下問題：一般情況下，文檔集中會包含長短不一的各類文檔，而長文檔(即大文檔)所包含的詞條個數通常會大于短文檔(小文檔)中所包含的詞條個數，如果同一個關鍵詞在長文檔(10 000個分詞)和短文檔(100個分詞)中的詞頻都為10次，顯然上述公式的計算方法不利于短文檔中關鍵詞對文檔的相關度得分計算。為公平起見，將對詞頻做歸一化處理，以保證詞頻計算權重公式更加合理。

(7)

gf_idf=gf(f,t)*idf(t)

(8)

2.4 算法描述

文中基于向量空間模型實現文檔檢索，每個文檔構造一個文檔向量，其維度為文檔集抽取的關鍵詞集合的個數，從文檔中抽取的每個關鍵詞對應向量的每一維，每一維的值設置為相應關鍵詞的權重。用戶的查詢也被構造成一個查詢向量，維度與文檔向量一致。用查詢向量與文檔向量進行內積來計算查詢-文檔的相關度得分并用該相關度分數對文檔進行排序。文中支持語義的可搜索加密算法描述如下：

Step1：數據用戶從整個文檔集D=(d1,d2,…,di,…,dm)中使用分詞工具提取出關鍵詞集合T=(t1,t2,…,tj,…,tn)。

Step2：KMS生成對稱密鑰K，生成的密鑰用三元組形式表示：{S,M1,M2}，其中S為n維隨機比特指示向量，M1、M2為n維可逆矩陣，并將密鑰K安全分發到數據用戶和授權用戶手中。

Step3：數據用戶用式(1)計算關鍵詞的位置加權評分L，用式(8)計算出關鍵詞在文檔中的相關度得分gf_idf。

Step4：數據用戶為每個文檔di構造出相應的文檔向量DVi，若tj∈di，則DVi[j]=1，否則為0。

Step5：數據用戶將文檔向量DVi平均分成u塊，u滿足條件u|n，生成文檔標記向量DMVi=(DMVi1,DMVi2,…,DMVij,…,DMViu)，方法是如果某塊全為0，則DMVij=0，否則為1。并生成對應索引標識符IMi=(DMVi,idi)，后將文檔標記向量DMVi及其對應的索引標識符IMi上傳到私有云。

Step7：數據用戶使用加密密鑰K對文檔集合進行D=(d1,d2,…,di,…,dm)加密，生成密文文檔集合C=(c1,c2,…,ci,…,cm)，然后提交至公有云上存儲。

Step8：授權用戶輸入初始查詢關鍵字Q=(q1,q2,…,qi,…,qn)，再使用本體知識庫進行語義擴展，并使用語義相似度公式(4)計算初始關鍵字與擴展詞的語義相似度，選擇相似度排前的s個擴展詞(c1,c2,…,cs)加入到初始查詢來構成最終的查詢關鍵字集合Q'=(q1,q2,…,qi,…,qn,c1,c2,…,cs)，其對應的語義相似度為SC=(sc1,sc2,…,scn,scn+1,…,scn+s)。

Step9：根據語義擴展后的查詢關鍵字集合Q'構造查詢向量QV，方法是若ti∈Q'，則QV[i]=1，否則為0。將查詢向量QV平均分成u塊，u滿足條件u|n，生成查詢標記向量QMV=(QMV1,QMV2,…,QMVi,…,QMVu)，方法是如果某塊全為0，則QMVi=0，否則為1。將查詢標記向量上傳至私有云。

Step11：私有云對查詢標記向量QMV中的每一位1的值與文檔標記向量DMVi進行匹配，相同位置上都為1，則說明該文檔對應的塊包含有查詢關鍵詞，則將文檔標記向量DMVi對應的索引標識符上的idi記錄下來，最終得到所有可能包含查詢關鍵詞的候選索引標識集合ID'={…,idi,…,idj}，并將其提交至公有云。公有云根據ID'找到對應的安全索引Ii，將對應的SVi與陷門T進行內積來計算查詢與文檔的相似度得分。

Step12:對查詢-文檔的相似度得分進行排序，將前Top_k篇文檔返回給授權用戶。

Step13:授權用戶使用密鑰K對返回的文檔進行解密，得到原始的明文文檔。

3 實驗結果分析

文中實驗環境為：Windows 7，CPU：i7四核3.4 GHz，內存：8 GB，硬盤空間：1 TB，仿真實驗編程語言：Java。建立了一個計算機領域本體知識庫，并從Web上抓取計算機領域網頁3 000 個作為測試數據集，使用ICTCLAS分詞系統抽取出文檔關鍵詞。實驗的目的是驗證在用戶初始查詢中加入了本體語義推理的擴展詞及在查詢-文檔的相關度分數中引入了語義相似度、關鍵詞不同位置加權評分及關鍵詞-文檔相關度得分影響因子后，密文檢索效率(用F_measure來衡量)是否被提高。

(9)

當參數α取值為1時，就是常用的F1調和平均考慮了precision和recall的結果，F1值較高則證明文中方法的有效性。

圖2給出了文中方法與MRSE方法創建索引所花費時間的變化趨勢，可以看出隨著文檔關鍵詞數量的增加，兩種方法創建索引的時間都與之成正比，但由于文中方法需要對文檔向量進行分塊標記，因此創建索引的時間略有增加。但是對數據用戶來說創建索引是外源到云端前的操作，因此對時間上的要求不是很高。

圖2 索引創建時間對比分析

由于文中方法基于文檔向量和查詢向量的分塊技術，因此所分塊的數量u的取值直接決定了標記向量的維度，u的取值與檢索時間成反比。因為u值越大，那么文檔向量所分的塊數越多，每塊的維度“u|n”越小，塊全為0的概率越大，私有云對查詢標記向量與文檔標記向量匹配時，能過濾掉更多的無關文檔，從而會節省花費在計算不相關文檔相關度分數和文檔排序上的時間。但是查詢標記向量與文檔標記向量是明文保存在私有云上的，u值越大，每塊的維度“u|n”越小，越會暴露查詢向量與文檔向量的信息，因此，需要在考慮檢索時間和保護隱私兩者間權衡u的取值。

圖3 檢索時間對比分析

圖3給出了文中方法與MRSE方法檢索時間的變化趨勢，可以看出隨著文檔關鍵詞數量的增加，兩種方法的查詢時間都與之成正比，但是文中方法比MRSE方法大大降低了檢索時間。因為文中方法基于標記向量，提前過濾了不相關文檔，從而節省了花費在計算不相關文檔相關度分數和文檔排序上的時間。

圖4給出了文中方法與MRSE方法的F1比較，其中相關性的判斷采用專家評判的方法。可以看出文中方法取得了顯著結果，獲得了更高的F1值，也即相關度得分更高。因為MRSE采用的是關鍵詞精確匹配，沒有上升到語義層面的檢索，必然不會檢索出與關鍵詞語義上相似的文檔。

圖4 F-measure(F1)對比分析

4 結束語

針對傳統的可搜索加密算法基于關鍵詞精確匹配，查全查準率低，對檢索結果沒有進行合理的相關度排序，無法滿足用戶對智能搜索的要求，提出了一種支持語義的可搜索加密方法。該方法利用本體知識庫對用戶查詢進行了語義拓展，通過語義相似度來控制擴展詞的規模，防止因拓展詞過多產生“查詢漂移”。結合向量空間模型實現文檔檢索，通過文檔向量、查詢向量分塊技術構造出對應的標記向量，過濾無關文檔，提高了檢索效率，并通過引入語義相似度、關鍵詞不同位置加權評分及關鍵詞-文檔相關度得分來構造索引，在查詢-文檔的相似度得分函數中也引入這三個影響因子，進一步改善了排序效果，從而滿足了授權用戶對檢索結果排序的需求。