云服務器中基于同態加密的關鍵詞檢索方案

劉家森， 王緒安， 王 涵， 趙凱洋， 閆紀寧

(武警工程大學網絡與信息安全武警部隊重點實驗室， 西安 710086)

對于一些機密性較高的數據，如個人隱私數據、病人健康數據、商業機密數據等，為了避免其他人獲得真實數據，用戶往往將其在本地加密后再上傳給云存儲系統，由自己保管相關密鑰。但是隨著云存儲系統中的數據量膨脹式增大，用戶需要快速準確地從加密數據中檢索到自己需要的文件。

最早密文檢索的方案由Song等[1]于2000年提出，其方案基于對密文的線性搜索，將關鍵詞與文本內容逐一匹配。之后研究人員在此基礎上進行了很多細化的研究，Boneh等[2]于2004年首次提出一種基于公鑰機制的非對稱可搜索加密方案，其通過雙線性映射將公鑰和私鑰的加密數據合并，使得只有公鑰或私鑰加密的相同關鍵字才能匹配。同年，Golle等[3]提出一種基于多關鍵詞的密文檢索方案。

近年來，針對云服務器中的密文檢索方案主要分為基于密文掃描檢索方案和基于安全索引的檢索方案。Chang等[4]于2005年基于建立文檔索引實現對精準的關鍵詞搜索。Wang等[5]于2010年通過使用倒置索引對加密數據進行安全排序，提出了一種單關鍵詞檢索方案。2013年，Cao等[6]通過引入向量空間模型，提出了一種多關鍵詞密文檢索方案。但是上述方案僅支持對關鍵詞的精準搜索，輸入格式錯誤會導致檢索結果不準確。2010年，Li等[7]通過為每個關鍵詞都建立模糊集，首次提出了一種基于模糊關鍵詞的檢索方案。

目前圍繞模糊關鍵詞檢索和多關鍵詞檢索產生了很多研究。Wang等[8]驗證了基于屬性加密的多關鍵字搜索方案中外包私鑰的正確性。Lang等[9]將復合概念的語義相似性與位置敏感哈希函數和安全k近鄰方案相結合，提出了一個多關鍵詞加密檢索方案。Xiao等[10]基于映射集匹配提出一種多關鍵詞排序檢索方案。陸海虹等[11]使用minhash函數對關鍵詞索引進行加密，但是加密效率和檢索精度較低。張全明等[12]和于曉明等[13]分別基于Solr搜索引擎技術和Lucene全文檢索引擎實現基于關鍵詞檢索和全文檢索的應用方案。

為了提高密文檢索的精度以及提高方案的安全性，許多研究將同態加密運用到密文檢索當中。用戶可以通過對文件進行同態加密，在保證數據隱私性的前提下，委托云服務器直接對密文進行同態操作，并且結果等價于明文上的操作。同態加密方案首次由Rivest等[14]于1978年提出，之后Gentry[15]于2009年在理論上實現同態加密，并在此后于2010年以及2013年分別提出DGHV方案[16]和GSW13方案[17]，前者基于近似最大公約數問題實現一個基于整數的全同態加密，后者基于錯誤學習問題提出第一個基于身份的同態加密方案。同時Brakerski等[18]基于標準格上困難問題提出了BV11方案，有效縮短了密文并降低了方案的解密復雜度，又于2012年和2014年分別提出Bra12方案[19]和BGV12方案[20]。前者通過避免模數轉換而建立層次型同態加密方案，后者無需自舉就能建立層次經同態加密。

最近Cheon等[21]基于錯誤學習問題提出CKKS方案，其因為支持對密文的近似運算而得到普及應用。Gong等[22]基于Grover算法提出了一種新的量子同態加密密文檢索(QHECR)方案。Wang等[23]提出了一種基于全同態加密企業云存儲(ECRS)的加密密文檢索方案。

目前的市場上應用的密文檢索方案主要分為兩種，一種基于關鍵詞與密文匹配的檢索方法，另一種基于文件索引的檢索方法。然而前者檢索效率低，而后者需要建立復雜的索引結構，都難以滿足用戶對云服務器中海量加密數據的檢索需求。

為了在保護用戶數據的隱私的同時，實現對云服務器中海量密文文件的高效準確的檢索功能，基于錯誤學習(learning with errors,LWE)問題以及近似最大公約數(approximate greatest common divisor, AGCD)問題提出了一種新型同態加密方案。并針對云服務器中大數據存儲及檢索的需求，在加密文件的同時，通過建立加密關鍵詞索引提出了一種模糊密文檢索方案。

1 加密檢索機制設計

基于同態加密的關鍵詞密文檢索方案包括同態加密方案以及基于關鍵詞密文檢索方案兩個部分。

1.1 系統模型

一般來說，云存儲系統都會誠實地按照規定對用戶提供高效的存儲服務，不會惡意地對用戶數據進行改動。但是有些云服務器為了自身利益，會有意收集用戶的各種數據，甚至將用戶數據出售給其他公司。

在數據隱私保護的前提下，針對云服務器中大數據存儲及檢索的需求，基于建立關鍵詞索引并利用全同態加密實現加密文檔檢索，系統模型如圖1所示。

圖1中，用戶首先對要上傳的文件建立關鍵詞索引，之后通過同態加密方案，將加密后的文件以及關鍵詞上傳至云服務器。云服務器只能獲得密文文檔及關鍵詞。當用戶需要檢索相關文檔時，首先將相關關鍵詞加密，并把加密后的關鍵詞上傳至云服務器中進行檢索。云服務器通過計算檢索請求的加密關鍵詞索引與云中存儲的關鍵詞索引的相似度，將匹配結果返回給用戶。最后用戶根據自己需求下載對應的密文文件，并解密獲得明文文件。符號定義如表1所示。

圖1 系統模型Fig.1 System model

表1 符號定義

1.2 預備知識

1.2.1 LWE：Learning with errors

Regev等[24]用量子規約算法證明了LWE問題的困難性等同于n維格上的最短向量問題(shortest vector problem, SVP)和最短線性無關向量問題(shortest linear independent vector problem,SIVP)。

1.2.2 AGCD：Approximate-GCD

Howgrave-Graham[25]提出AGCD問題。給定集合{x1,x2,…,xn|xi=pqi+ri}，其中qi和ri都是整數，且根據xi的不同而變化。求出隱藏的近似公約數p。DGHV[16]方案將該問題歸于基于因式分解加密體系中經典的硬核位的證明，結果證明其具有語義安全特性，且在選擇性明文攻擊模型下具有密文不可區分性。

1.3 同態加密方案

1.3.1 系統參數生成函數：ParamGen(1λ)

隨機選取兩個大素數q=q(λ)∈Z+，p=p(λ)∈Z+，使得gcd(p,q)=1，返回安全參數Param(p,q)。之后根據加密效率選取加密參數l,n∈R+。

1.3.2 密鑰生成函數：KeyGen(1λ)

1.3.3 加密函數：Enc(key,F∈Zp)

1.3.4 解密函數：Dec[key,C=(r,c)]

計算明文

1.4 單關鍵詞密文檢索方案

當用戶需要查詢文件時，首先選取一個或幾個關鍵詞F∈Zp，通過上述方案加密后上傳至云服務器，之后在云服務器中進行密文檢索。

最后云服務器按照設定，返回r>θ的密文給用戶。

1.5 多關鍵詞密文檢索方案

2 理論分析

2.1 正確性分析

正確擁有密鑰[S,K(l)]的用戶可以通過解密函數Dec()對密文C=(r,c)解密得到正確的明文F。

Dec[S,K(l),C=(r,c))=

2.2 同態性分析

2.2.1 同態加法

給定兩個關鍵詞及其對應的密文F1、F2∈Zp,C1=(r1,c1),C2=(r2,c2)，對密文上的運算滿足加法同態性Dec(r1,c1)+Dec(r2,c2)=Dec(r1+r2,c1+c2)。

Dec(r1+r2,c1+c2)=

[(r1+r2)S+c1+c2]lmodp=

F1+F2。

2.2.2 同態乘法

給定兩個關鍵詞及其對應的密文F1、F2∈Zp,C1=(r1,c1),C2=(r2,c2)，對密文上的運算滿足乘法同態性Dec(r1,c1)·Dec(r2,c2)=Dec[(r1,c1)(r2,c2)]。

Dec(c1r2,c1c2)=

c1F2；

Dec(r1r2,r1c2)=r1F2；

Dec[(r1,c1)·(r2,c2)]=Dec(r1F2,c1F2)=

F1F2。

2.3 安全性分析

在用戶對密文進行上傳存儲與檢索過程中，對于用戶數據的隱私性要保證兩方面：一是要保證云服務器無法從用戶存儲的密文破解出真實數據，二是要保證云服務器無法從檢索請求破解出用戶數據。

2.3.1 存儲方案安全性

2.3.2 檢索方案安全性

3 實驗分析

為了進一步分析方案的效率，在Intel?CoreTMi7-7700HQ CPU @ 2.80 GHz/16 GB Ram的環境下，在Windows10操作系統下使用IntelliJ IDEA Community Edition 2019.3 x64測試方案的效率。經對比多次試驗結果，確定系統參數Param(p,q)為128位。

3.1 加密效率測試

首先通過建立單一關鍵詞，對應不同的加密維度，對方案的加密效率進行測試。在測試過程中選取3個中文字符的關鍵詞，對應48位的比特長度。在每一對加密維度(l,n)進行30次加密試驗，取其平均計算時間作為最終結果，如圖2所示。

圖2 不同維度的加密效率Fig.2 Encryption efficiency in different dimensions

可見，當加密維度處于(128,128)之后，加密時間呈指數型上升，加密效率過低。因此后續實驗中選取(128,128)作為加密維度進行試驗。

下一步測試中，通過選取確定的加密維度，分別對不同比特的明文F構造密文索引，并與Wang等[23]的基于全同態加密企業云存儲的加密密文檢索方案(ECRS)進行對比，并取30次試驗的平均運行時間作為最終結果，如圖3所示。

圖3 加密索引構建效率Fig.3 Encrypted index construction efficiency

可見，隨著明文的比特長度增加，兩種加密方案所用的時間基本不變，證明本方案可有效地對任意長度的明文進行加密。

3.2 檢索效率測試

通過建立不同的關鍵詞索引，對不同數量的關鍵詞對進行檢索匹配試驗。建立100個文本文件作為測試文件，對每個文本建立4個關鍵詞，每個關鍵詞長度為3個中文字符。以(128,128)為加密維度對關鍵詞進行加密，建立加密關鍵詞索引。選取1～4個關鍵詞進行檢索，分別測試本文方案和ECRS的檢索效率，結果如圖4所示。

圖4 不同數量關鍵詞的檢索效率Fig.4 Retrieving efficiency of different number of keywords

3.3 檢索準確率測試

由于ECRS在進行多關鍵詞檢索的任務時需要逐一計算所有的關鍵詞權重的相似度，因此對其計算單個關鍵詞的檢索時間，并進行疊加。

可見，兩種方案對于單關鍵詞檢索速度相差不大，但是隨著關鍵詞數量增長，云端需要計算的匹配對數增多，ECRS的計算開銷呈線性增長趨勢，本文方案的計算開銷增長較為緩慢。

仍以上述100個文本文件作為測試文件，測試本文方案以及ECRS的檢索準確率并進行對比。分別取1到4個關鍵詞進行檢索，在每個條件下分別取10種關鍵詞組合進行測試并取平均值，結果如圖5所示。

圖5 不同數量關鍵詞的檢索準確率Fig.5 Retrieval accuracy of different number of keywords

可見，隨著待檢索的關鍵詞數量的增加，兩種方案的準確率基本不變，證明本文方案的可靠性。

4 結論

為滿足用戶在云存儲系統中海量加密數據進行密文檢索的操作需求，基于同態加密提出了一種加密關鍵詞檢索方案。首先通過LWE問題以及AGCD問題提出了一種針對關鍵詞的同態加密方案，并通過理論分析證明了加密方案的安全性以及同態性。之后參考余弦夾角相似度度量方法，在上面所提出的同態加密方案基礎上，提出了一種基于建立加密關鍵詞索引的密文檢索方案。通過實驗分析，測試不同加密維度下的加密效率，證明了加密方案的高效性。最后通過實驗對比，測試檢索方案的檢索效率以及檢索準確率，證明了檢索方案的有效性。