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

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

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

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

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

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

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

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

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

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

1 加密檢索機制設計

基于同態(tài)加密的關(guān)鍵詞密文檢索方案包括同態(tài)加密方案以及基于關(guān)鍵詞密文檢索方案兩個部分。

1.1 系統(tǒng)模型

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

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

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

圖1 系統(tǒng)模型Fig.1 System model

表1 符號定義

1.2 預備知識

1.2.1 LWE：Learning with errors

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

1.2.2 AGCD：Approximate-GCD

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

1.3 同態(tài)加密方案

1.3.1 系統(tǒng)參數(shù)生成函數(shù)：ParamGen(1λ)

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

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

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

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

計算明文

1.4 單關(guān)鍵詞密文檢索方案

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

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

1.5 多關(guān)鍵詞密文檢索方案

2 理論分析

2.1 正確性分析

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

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

2.2 同態(tài)性分析

2.2.1 同態(tài)加法

給定兩個關(guān)鍵詞及其對應的密文F1、F2∈Zp,C1=(r1,c1),C2=(r2,c2)，對密文上的運算滿足加法同態(tài)性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 同態(tài)乘法

給定兩個關(guān)鍵詞及其對應的密文F1、F2∈Zp,C1=(r1,c1),C2=(r2,c2)，對密文上的運算滿足乘法同態(tài)性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 安全性分析

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

2.3.1 存儲方案安全性

2.3.2 檢索方案安全性

3 實驗分析

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

3.1 加密效率測試

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

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

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

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

圖3 加密索引構(gòu)建效率Fig.3 Encrypted index construction efficiency

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

3.2 檢索效率測試

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

圖4 不同數(shù)量關(guān)鍵詞的檢索效率Fig.4 Retrieving efficiency of different number of keywords

3.3 檢索準確率測試

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

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

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

圖5 不同數(shù)量關(guān)鍵詞的檢索準確率Fig.5 Retrieval accuracy of different number of keywords

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

4 結(jié)論

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