云服務(wù)器中基于同態(tài)加密的關(guān)鍵詞檢索方案

劉家森， 王緒安， 王 涵， 趙凱洋， 閆紀(jì)寧

(武警工程大學(xué)網(wǎng)絡(luò)與信息安全武警部隊(duì)重點(diǎn)實(shí)驗(yàn)室， 西安 710086)

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

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

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

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

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

最近Cheon等[21]基于錯(cuò)誤學(xué)習(xí)問題提出CKKS方案，其因?yàn)橹С謱γ芪牡慕七\(yùn)算而得到普及應(yīng)用。Gong等[22]基于Grover算法提出了一種新的量子同態(tài)加密密文檢索(QHECR)方案。Wang等[23]提出了一種基于全同態(tài)加密企業(yè)云存儲(ECRS)的加密密文檢索方案。

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

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

1 加密檢索機(jī)制設(shè)計(jì)

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

1.1 系統(tǒng)模型

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

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

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

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

表1 符號定義

1.2 預(yù)備知識

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λ)

隨機(jī)選取兩個(gè)大素?cái)?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)]

計(jì)算明文

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

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

最后云服務(wù)器按照設(shè)定，返回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)加法

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

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

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

2.3.1 存儲方案安全性

2.3.2 檢索方案安全性

3 實(shí)驗(yàn)分析

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

3.1 加密效率測試

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

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

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

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

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

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

3.2 檢索效率測試

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

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

3.3 檢索準(zhǔn)確率測試

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

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

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

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

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

4 結(jié)論

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