韓 邦，李子臣，湯永利

1.河南理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，河南 焦作 454003

2.北京印刷學(xué)院 信息工程學(xué)院，北京 102600

1 引言

隨著云存儲(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)行高效精確檢索。

2 預(yù)備知識(shí)

2.1 整數(shù)向量加密

在這個(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)單。

2.2 向量空間模型

向量空間模型和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ì)算為：

3 方案設(shè)計(jì)

3.1 系統(tǒng)模型

關(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é)果給用戶。

3.2 威脅模型

假設(shè)數(shù)據(jù)擁有者和用戶均是誠(chéng)實(shí)的，云服務(wù)器是誠(chéng)實(shí)又好奇，即云服務(wù)器會(huì)正確執(zhí)行協(xié)議，但嘗試推斷敏感信息。用戶和云之間沒有勾結(jié)。云中的攻擊者只會(huì)觀察到加密的數(shù)據(jù)，而不知道任何有關(guān)未加密的數(shù)據(jù)。

3.3 檢索方案

（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ì)文檔解密。

4 系統(tǒng)實(shí)現(xiàn)

4.1 系統(tǒng)整體框架

如圖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)行解密即可。

4.2 系統(tǒng)具體實(shí)現(xià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é)果文件。

5 安全性及性能分析

5.1 安全性分析

（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ù)的安全性。

5.2 性能分析

（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）之間效果最好。

6 結(jié)束語(yǔ)

本文將整數(shù)向量加密算法以及在文本檢索領(lǐng)域使用最廣的向量空間模型相結(jié)合，應(yīng)用在第三方不可信云存儲(chǔ)的全文檢索中。提出一個(gè)基于同態(tài)加密的檢索方案，檢索方案具有較高的執(zhí)行效率。整個(gè)檢索過(guò)程安全性較高，可以抵抗不可信云服務(wù)器，有實(shí)際應(yīng)用價(jià)值。