韓 邦,李子臣,湯永利
1.河南理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,河南 焦作 454003
2.北京印刷學(xué)院 信息工程學(xué)院,北京 102600
隨著云存儲(chǔ)技術(shù)的發(fā)展,越來(lái)越多的用戶傾向?qū)⑺麄兊臄?shù)據(jù)存放在云平臺(tái),并利用足夠的計(jì)算能力來(lái)處理他們的數(shù)據(jù)。云存儲(chǔ)具有服務(wù)范圍廣、用戶規(guī)模大、訪問透明等特點(diǎn)[1-2]。人們?cè)谠拼鎯?chǔ)及信息安全方面取得了許多的成果,但是在數(shù)據(jù)安全保護(hù)方面還面臨著一些問題。在傳統(tǒng)的分布式計(jì)算中,用戶將數(shù)據(jù)存儲(chǔ)在本地被監(jiān)管。但是隨著云計(jì)算的發(fā)展,用戶的隱私數(shù)據(jù)和計(jì)算都交至云端服務(wù)器,由云服務(wù)器進(jìn)行操作。這樣,使得用戶的數(shù)據(jù)處于一種不可控的狀態(tài)[3]。一方面,網(wǎng)絡(luò)時(shí)代的數(shù)據(jù)信息中包含了很多隱私信息,包括企業(yè)的商業(yè)秘密和個(gè)人隱私等;另一方面,提供存儲(chǔ)服務(wù)的第三方服務(wù)器往往是獨(dú)立運(yùn)營(yíng)的組織或管理機(jī)構(gòu),并不能完全受信賴[4-5]。因此,許多企業(yè)和個(gè)人在使用云服務(wù)器存儲(chǔ)重要的數(shù)據(jù)時(shí)都心存顧慮。在這種情況下,保證云存儲(chǔ)環(huán)境中敏感數(shù)據(jù)的機(jī)密性[6-8]變得尤為重要,亟待解決。
為了解決云存儲(chǔ)數(shù)據(jù)的安全性,用戶將數(shù)據(jù)先加密,然后存儲(chǔ)在云中。但當(dāng)存儲(chǔ)在云服務(wù)器的加密數(shù)據(jù)非常龐大時(shí),對(duì)這些密文數(shù)據(jù)進(jìn)行檢索則是非常困難。傳統(tǒng)采用先解密后檢索的方式,使得檢索效率極低,無(wú)法適應(yīng)當(dāng)下大數(shù)據(jù)時(shí)代的需求。因此,需要設(shè)計(jì)一種新的檢索方案。與此同時(shí),同態(tài)加密算法很好地滿足了檢索云中數(shù)據(jù)的高效性和準(zhǔn)確性,又能夠保障數(shù)據(jù)的安全。
同態(tài)加密的概念由Rivest 等人[9]于1978 年首次提出,它不需要先對(duì)密文解密,就可以在密文數(shù)據(jù)上進(jìn)行任何可以在明文上的代數(shù)運(yùn)算操作。同態(tài)加密技術(shù)因其具有針對(duì)密文運(yùn)算的功能在云計(jì)算安全領(lǐng)域得到了廣泛應(yīng)用[10]。為了解決全同態(tài)和部分同態(tài)加密方案效率極低難以實(shí)現(xiàn)的問題。Zhou 等人[11]開發(fā)了一個(gè)整數(shù)向量的加密系統(tǒng)(Efficient Integer Vector Homomorphic Encryption)下文簡(jiǎn)稱為VHE方案,支持加法、線性變換和內(nèi)積計(jì)算。VHE能夠直接對(duì)一個(gè)整數(shù)向量進(jìn)行加密,與之前的基于單個(gè)比特或者單個(gè)整數(shù)加密的同態(tài)加密方案相比,大大提高密文域內(nèi)的運(yùn)算效率。雖然無(wú)法達(dá)到全同態(tài),但在進(jìn)行某些特定的應(yīng)用時(shí),通信成本和計(jì)算效率較高。VHE方案在處理來(lái)自不同用戶秘鑰下的加密數(shù)據(jù)以及在第三方不可信云平臺(tái)沒有解密秘鑰的情況下對(duì)加密數(shù)據(jù)執(zhí)行數(shù)據(jù)挖掘過(guò)程具有良好的應(yīng)用[12]。
本文提出一種新的云存儲(chǔ)服務(wù)器關(guān)鍵詞密文檢索方案?;赩HE 方案,根據(jù)向量空間模型余弦相似性計(jì)算,并將其運(yùn)用到云端密文檢索場(chǎng)景,實(shí)現(xiàn)了在服務(wù)器不可信的場(chǎng)景下對(duì)數(shù)據(jù)進(jìn)行高效精確檢索。
在這個(gè)部分簡(jiǎn)單敘述一個(gè)改進(jìn)的整數(shù)向量加密方案。它不是對(duì)向量中的每一個(gè)條目進(jìn)行加密,而是把向量作為一個(gè)整體,通過(guò)密鑰轉(zhuǎn)換進(jìn)行加密,支持向量?jī)?nèi)積操作。
算法1密鑰轉(zhuǎn)換(Trans)
輸出:S′,M。
(4)計(jì)算S′=St I1,M=I2Mt
假設(shè)有私鑰S,密文c,以矩陣S作為輸入進(jìn)行密鑰轉(zhuǎn)換得到S′與M。
算法2密鑰對(duì)生成(GenKey)
輸入:參數(shù)m。
輸出:S,M。
(1)生成單位矩陣I∈Zm
(2)計(jì)算S,M=Trans(ωI)
在算法2 中,將矩陣ωI作為明文向量對(duì)應(yīng)的私鑰進(jìn)行一次密鑰轉(zhuǎn)換,得到公鑰M,私鑰S。
算法3加密算法
輸入:參數(shù)M,x。
輸出:c。
(1)生成隨機(jī)向量e∈Zqm。
(2)計(jì)算c=Mx+e。
加密按照密鑰轉(zhuǎn)換過(guò)程計(jì)算新密文的方式,對(duì)明文向量做相同處理。e是一個(gè)誤差項(xiàng),加密結(jié)果滿足LWE問題。
算法4解密算法
輸入:參數(shù)S,c。
輸出:x。
通過(guò)私鑰S,解密過(guò)程簡(jiǎn)單。
向量空間模型和TF-IDF 規(guī)則廣泛應(yīng)用于明文信息檢索領(lǐng)域,是最為經(jīng)典的計(jì)算模型。向量空間模型(Vector Space Model,VSM)是由哈佛大學(xué)Salton等人[13]提出。VSM 概念簡(jiǎn)單,基本思想是把文檔簡(jiǎn)化為以特征項(xiàng)(關(guān)鍵詞)的權(quán)重為分量的m維向量表示,每個(gè)文檔用一個(gè)特征向量來(lái)表示該文檔的多維信息,使得模型具備了可計(jì)算性。以空間上的余弦相似度來(lái)表示語(yǔ)義上的相似,當(dāng)文檔被表示為向量,就可以計(jì)算向量之間的余弦相似度來(lái)得到文檔間的相似度。
給定文檔文本集,則文本集的VSM表示為:
其中,wij表示為關(guān)鍵詞j在文本i中的權(quán)重。構(gòu)建VSM的關(guān)鍵有兩個(gè):一是關(guān)鍵詞的維度m。二是如何計(jì)算權(quán)重wij。
(1)關(guān)鍵詞集的維度m
關(guān)鍵詞用于表征該文檔特性,是能夠代表該文檔內(nèi)容的基本語(yǔ)言單位。文獻(xiàn)[14]對(duì)比分析了多種關(guān)鍵詞提取方法。關(guān)鍵詞數(shù)量增加會(huì)導(dǎo)致F的維度m增大,從而引起時(shí)間復(fù)雜度增加。當(dāng)提取關(guān)鍵詞后,采用TF-IDF算法,從而得出文檔集的維度m。
(2)權(quán)重wij的計(jì)算
最常用和有效的權(quán)重計(jì)算方法為TF-IDF 表示法,在信息檢索領(lǐng)域,該技術(shù)已經(jīng)非常成熟。
TF-IDF 算法的計(jì)算分為詞頻(TF)和逆文檔頻率(IDF)兩部分。由這兩部分的乘積共同決定文檔詞的權(quán)重。TF-IDF算法有多重形式,通過(guò)實(shí)驗(yàn),在本文采用的計(jì)算方法為:
ni,j表示關(guān)鍵詞i在文檔j中的次數(shù),nj表示文檔的總詞數(shù)。
其中,N為文檔集合中的文檔數(shù)目,Ni為關(guān)鍵詞i出現(xiàn)過(guò)的文檔數(shù)。權(quán)重由TF和IDF計(jì)算為:
關(guān)注的是如圖1所示的系統(tǒng)模型,參與方是數(shù)據(jù)擁有者、用戶和云服務(wù)器。
圖1 云存儲(chǔ)密文檢索系統(tǒng)模型
(1)數(shù)據(jù)擁有者:數(shù)據(jù)擁有者將加密數(shù)據(jù)上傳至云服務(wù)器,以及給有權(quán)限的用戶提供密鑰。
(2)用戶:用戶獲得數(shù)據(jù)擁有者的密鑰,上傳檢索向量,下載所需文檔。
(3)云服務(wù)器:云服務(wù)器充當(dāng)存儲(chǔ)和計(jì)算的平臺(tái)。在密文下進(jìn)行檢索計(jì)算,并返回結(jié)果給用戶。
假設(shè)數(shù)據(jù)擁有者和用戶均是誠(chéng)實(shí)的,云服務(wù)器是誠(chéng)實(shí)又好奇,即云服務(wù)器會(huì)正確執(zhí)行協(xié)議,但嘗試推斷敏感信息。用戶和云之間沒有勾結(jié)。云中的攻擊者只會(huì)觀察到加密的數(shù)據(jù),而不知道任何有關(guān)未加密的數(shù)據(jù)。
(1)初始化:數(shù)據(jù)擁有者在客戶端,根據(jù)參數(shù)m生成整數(shù)向量加密算法的公私鑰對(duì)(S,M),SM4 加密算法的秘鑰E。
(2)數(shù)據(jù)加密:數(shù)據(jù)擁有者根據(jù)文檔集合生成向量空間模型中的文檔向量D。將文檔向量D使用M加密得到DM。將原文檔使用E進(jìn)行加密得到DE。將DM以及DE一起上傳至云服務(wù)器存儲(chǔ)。
(3)檢索:獲得權(quán)限的檢索者向數(shù)據(jù)擁有者申請(qǐng)S、M、E。當(dāng)檢索者執(zhí)行檢索操作時(shí),先將原始檢索向量擴(kuò)充為與加密一致維數(shù),即標(biāo)準(zhǔn)檢索向量Q,使用M加密后得到QM,再向云服務(wù)器提交檢索請(qǐng)求。
(4)相關(guān)性計(jì)算:云服務(wù)器接收到檢索請(qǐng)求后,計(jì)算檢索向量QM和文檔向量DM之間的余弦相似度,即相關(guān)性分?jǐn)?shù),將計(jì)算出的每個(gè)文檔相關(guān)性分?jǐn)?shù)返回給客戶端。
(5)解密:用戶在客戶端收到相關(guān)性分?jǐn)?shù)后,用S將相關(guān)性分?jǐn)?shù)解密,并通過(guò)快速排序算法得到相關(guān)度由高到低的文檔編號(hào)。用戶按照需求向云服務(wù)器請(qǐng)求文檔數(shù)據(jù)。云服務(wù)器接收到請(qǐng)求后,將所請(qǐng)求的加密文檔返回給客戶端??蛻舳耸褂肊對(duì)文檔解密。
如圖2 所示,是云存儲(chǔ)密文檢索系統(tǒng)整體框架,基于方案,在云服務(wù)器下進(jìn)行了實(shí)現(xiàn)。
圖2 云存儲(chǔ)密文檢索系統(tǒng)整體框架
用戶A上傳文件時(shí),首先客戶端將原文本文件進(jìn)行預(yù)處理,生成文檔向量。然后使用客戶端生成的同態(tài)加密算法的公鑰對(duì)文檔向量進(jìn)行同態(tài)加密處理得到密文文檔向量。同時(shí)客戶端對(duì)原文本文件使用SM4分組密碼加密,將密文文件和密文文檔向量一起上傳至云服務(wù)器。
用戶B檢索文件時(shí),向云服務(wù)器提交同樣使用同態(tài)加密算法加密后的檢索向量。云服務(wù)器通過(guò)計(jì)算檢索向量與文檔向量之間的余弦相似性,得到相關(guān)性分?jǐn)?shù)。并將相關(guān)性分?jǐn)?shù)返回給客戶端,用戶解密后,將所需下載請(qǐng)求發(fā)送給云服務(wù)器,云服務(wù)器將文件下載至客戶端,用戶通過(guò)SM4秘鑰對(duì)文件進(jìn)行解密即可。
(1)用戶加密上傳文件
用戶上傳文件流程如圖3所示。
圖3 用戶上傳文件流程
①對(duì)原文件進(jìn)行特征項(xiàng)預(yù)處理。利用TF-IDF算法賦予特征項(xiàng)權(quán)重,構(gòu)建向量空間模型,生成文檔向量D=(w1j,w2j,…,wij)。其中,wij表示第i個(gè)特征項(xiàng)(即關(guān)鍵詞)。
②對(duì)文檔向量D中的每個(gè)特征項(xiàng)wiq使用VHE進(jìn)行同態(tài)加密。客戶端根據(jù)生成秘鑰對(duì)S、M、S作為用戶秘鑰,利用公鑰M對(duì)D進(jìn)行加密,計(jì)算:
得到相應(yīng)的密文文檔向量DM。
③對(duì)原文件進(jìn)行SM4 加密??蛻舳松?28 位的隨機(jī)數(shù)作為SM4 秘鑰E并保存在本地。利用E對(duì)原文件進(jìn)行加密得到密文文件DE。將DM和DE一起發(fā)送至服務(wù)器存儲(chǔ)。
(2)用戶檢索下載文件
用戶檢索文件流程如圖4 所示,該部分共包含4 個(gè)階段。
圖4 用戶檢索文件流程
詳細(xì)過(guò)程如下:
①計(jì)算密文檢索向量??蛻舳藢?duì)用戶輸入的檢索語(yǔ)句,同樣根據(jù)向量空間模型和TF-IDF 算法生成檢索向量,為了保證維數(shù)相同,將原始檢索向量擴(kuò)充為與文檔向量一致,得到檢索向量Q,利用之前生成的VHE算法的秘鑰S對(duì)檢索向量進(jìn)行同態(tài)加密,計(jì)算:
得到相應(yīng)的密文檢索向量QM,將其發(fā)送給云服務(wù)器。
②云服務(wù)器計(jì)算相關(guān)性分?jǐn)?shù)。云服務(wù)器接收到DM后,計(jì)算檢索向量QM與文檔向量之間DM的相關(guān)性分?jǐn)?shù)HM。計(jì)算公式:
通過(guò)計(jì)算向量之間的余弦相似度,得到檢索向量和文檔向量之間的相關(guān)性分?jǐn)?shù)HM,把相似度高低作為檢索結(jié)果排序的依據(jù)。
③云服務(wù)器將相關(guān)性分?jǐn)?shù)HM返回給客戶端??蛻舳私邮盏较嚓P(guān)性分?jǐn)?shù)后,用S將其解密,得到H。
使用快速排序算法(Quicksort),得到相關(guān)度從高到低的n個(gè)文檔編號(hào),將所需要的文檔請(qǐng)求發(fā)送給云服務(wù)器。
④云服務(wù)器將文件下載至客戶端。云服務(wù)器接收到文檔請(qǐng)求后,讀取存儲(chǔ)在服務(wù)器中的文件,返回給客戶端,客戶端利用SM4秘鑰E對(duì)文件解密,得到最終的明文檢索結(jié)果文件。
(1)原文件安全性
原文件采用了SM4分組加密算法。加解密過(guò)程均由用戶在客戶端完成,云存儲(chǔ)服務(wù)器無(wú)法獲知其私鑰Ek。SM4保證了文件的安全性,可以抵抗差分攻擊、線性攻擊。使得敵手即使獲得了密文和明文,也無(wú)法求出密鑰的任何信息;即使獲得了密文和明文的統(tǒng)計(jì)規(guī)律,也無(wú)法求出明文的任何信息。
(2)檢索過(guò)程安全性
檢索部分采用了整數(shù)向量加密算法,對(duì)文檔向量以及檢索向量進(jìn)行加密和解密,方案滿足部分同態(tài)。公私鑰生成均由用戶在客戶端生成,用戶將文檔向量加密后存儲(chǔ)在云服務(wù)器上,以密文形式存儲(chǔ)。檢索者將檢索向量加密后發(fā)給云服務(wù)器,利用同態(tài)加密的性質(zhì),在密文下進(jìn)行余弦相似性內(nèi)積計(jì)算,并將相關(guān)性分?jǐn)?shù)返回給客戶端,在客戶端通過(guò)私鑰解密。整個(gè)過(guò)程均是在密文下進(jìn)行的,云服務(wù)器無(wú)法獲知任何關(guān)于明文的數(shù)據(jù),只有用戶和檢索者能夠獲得明文,保證了數(shù)據(jù)的安全性。
(1)效率分析
從效率分析,方案主要消耗是在同態(tài)加密和內(nèi)積計(jì)算過(guò)程中,密鑰生成和向量空間模型的建立只執(zhí)行一次。因此方案的性能主要取決于加解密算法的效率。在加密過(guò)程中,大多數(shù)全同態(tài)加密方案在實(shí)際應(yīng)用中效率極低而難以實(shí)現(xiàn),本文采用的針對(duì)整數(shù)向量的同態(tài)加密方案僅關(guān)注在構(gòu)建應(yīng)用時(shí)需要的計(jì)算種類和計(jì)算深度,雖然無(wú)達(dá)到全同態(tài),但其滿足進(jìn)行余弦相似度計(jì)算的向量?jī)?nèi)積操作。將文檔文本構(gòu)建向量空間模型后,需要對(duì)文檔向量和檢索向量進(jìn)行加密。常規(guī)的同態(tài)加密算法是對(duì)向量中每個(gè)條目進(jìn)行逐比特加密,而VHE 是把向量作為一個(gè)整體進(jìn)行加密,提高了向量加密的效率。在實(shí)驗(yàn)中,測(cè)試向量加密和內(nèi)積計(jì)算所用時(shí)間,結(jié)果如表1和表2所示,由表可知對(duì)比常見同態(tài)加密算法,在進(jìn)行向量加密時(shí)VHE效率高。對(duì)原文件的加解密采用SM4分組密碼,其軟件實(shí)現(xiàn)容易,與其他算法相比所需的內(nèi)存空間小,適用于內(nèi)存受限的環(huán)境,加解密速度快。與文獻(xiàn)[15]中采用BGV算法對(duì)比,本文采用的VHE進(jìn)行向量加密效率更高。
表1 向量加密效率對(duì)比 μs
表2 內(nèi)積計(jì)算效率對(duì)比 μs
(2)精確性分析
從精確性分析,本方案通過(guò)采用信息檢索領(lǐng)域最為經(jīng)典的計(jì)算模型,構(gòu)建向量空間模型,選取合適權(quán)重,計(jì)算余弦相似性,來(lái)檢索云存儲(chǔ)服務(wù)器中的文本數(shù)據(jù),其精確度要遠(yuǎn)高于[16]利用加密算法性質(zhì)進(jìn)行關(guān)鍵詞匹配的檢索方法。
方案支持多關(guān)鍵詞檢索,但關(guān)鍵詞數(shù)量增加會(huì)引起向量空間模型的維度增大,從而引起時(shí)間復(fù)雜度增加。因此在保證檢索效果以及減少時(shí)間開銷的前提下,通過(guò)實(shí)驗(yàn)得出本方案檢索關(guān)鍵詞數(shù)量在(5,8)之間效果最好。
本文將整數(shù)向量加密算法以及在文本檢索領(lǐng)域使用最廣的向量空間模型相結(jié)合,應(yīng)用在第三方不可信云存儲(chǔ)的全文檢索中。提出一個(gè)基于同態(tài)加密的檢索方案,檢索方案具有較高的執(zhí)行效率。整個(gè)檢索過(guò)程安全性較高,可以抵抗不可信云服務(wù)器,有實(shí)際應(yīng)用價(jià)值。