基于同態加密的全文檢索方案設計與實現

韓 邦，李子臣，湯永利

1.河南理工大學 計算機科學與技術學院，河南 焦作 454003

2.北京印刷學院 信息工程學院，北京 102600

1 引言

隨著云存儲技術的發展，越來越多的用戶傾向將他們的數據存放在云平臺，并利用足夠的計算能力來處理他們的數據。云存儲具有服務范圍廣、用戶規模大、訪問透明等特點[1-2]。人們在云存儲及信息安全方面取得了許多的成果，但是在數據安全保護方面還面臨著一些問題。在傳統的分布式計算中，用戶將數據存儲在本地被監管。但是隨著云計算的發展，用戶的隱私數據和計算都交至云端服務器，由云服務器進行操作。這樣，使得用戶的數據處于一種不可控的狀態[3]。一方面，網絡時代的數據信息中包含了很多隱私信息，包括企業的商業秘密和個人隱私等；另一方面，提供存儲服務的第三方服務器往往是獨立運營的組織或管理機構，并不能完全受信賴[4-5]。因此，許多企業和個人在使用云服務器存儲重要的數據時都心存顧慮。在這種情況下，保證云存儲環境中敏感數據的機密性[6-8]變得尤為重要，亟待解決。

為了解決云存儲數據的安全性，用戶將數據先加密，然后存儲在云中。但當存儲在云服務器的加密數據非常龐大時，對這些密文數據進行檢索則是非常困難。傳統采用先解密后檢索的方式，使得檢索效率極低，無法適應當下大數據時代的需求。因此，需要設計一種新的檢索方案。與此同時，同態加密算法很好地滿足了檢索云中數據的高效性和準確性，又能夠保障數據的安全。

同態加密的概念由Rivest 等人[9]于1978 年首次提出，它不需要先對密文解密，就可以在密文數據上進行任何可以在明文上的代數運算操作。同態加密技術因其具有針對密文運算的功能在云計算安全領域得到了廣泛應用[10]。為了解決全同態和部分同態加密方案效率極低難以實現的問題。Zhou 等人[11]開發了一個整數向量的加密系統（Efficient Integer Vector Homomorphic Encryption）下文簡稱為VHE方案，支持加法、線性變換和內積計算。VHE能夠直接對一個整數向量進行加密，與之前的基于單個比特或者單個整數加密的同態加密方案相比，大大提高密文域內的運算效率。雖然無法達到全同態，但在進行某些特定的應用時，通信成本和計算效率較高。VHE方案在處理來自不同用戶秘鑰下的加密數據以及在第三方不可信云平臺沒有解密秘鑰的情況下對加密數據執行數據挖掘過程具有良好的應用[12]。

本文提出一種新的云存儲服務器關鍵詞密文檢索方案。基于VHE 方案，根據向量空間模型余弦相似性計算，并將其運用到云端密文檢索場景，實現了在服務器不可信的場景下對數據進行高效精確檢索。

2 預備知識

2.1 整數向量加密

在這個部分簡單敘述一個改進的整數向量加密方案。它不是對向量中的每一個條目進行加密，而是把向量作為一個整體，通過密鑰轉換進行加密，支持向量內積操作。

算法1密鑰轉換（Trans）

輸出：S′，M。

（4）計算S′=St I1，M=I2Mt

假設有私鑰S，密文c，以矩陣S作為輸入進行密鑰轉換得到S′與M。

算法2密鑰對生成（GenKey）

輸入：參數m。

輸出：S，M。

（1）生成單位矩陣I∈Zm

（2）計算S,M=Trans(ωI)

在算法2 中，將矩陣ωI作為明文向量對應的私鑰進行一次密鑰轉換，得到公鑰M，私鑰S。

算法3加密算法

輸入：參數M,x。

輸出：c。

（1）生成隨機向量e∈Zqm。

（2）計算c=Mx+e。

加密按照密鑰轉換過程計算新密文的方式，對明文向量做相同處理。e是一個誤差項，加密結果滿足LWE問題。

算法4解密算法

輸入：參數S,c。

輸出：x。

通過私鑰S，解密過程簡單。

2.2 向量空間模型

向量空間模型和TF-IDF 規則廣泛應用于明文信息檢索領域，是最為經典的計算模型。向量空間模型（Vector Space Model，VSM）是由哈佛大學Salton等人[13]提出。VSM 概念簡單，基本思想是把文檔簡化為以特征項（關鍵詞）的權重為分量的m維向量表示，每個文檔用一個特征向量來表示該文檔的多維信息，使得模型具備了可計算性。以空間上的余弦相似度來表示語義上的相似，當文檔被表示為向量，就可以計算向量之間的余弦相似度來得到文檔間的相似度。

給定文檔文本集，則文本集的VSM表示為：

其中，wij表示為關鍵詞j在文本i中的權重。構建VSM的關鍵有兩個：一是關鍵詞的維度m。二是如何計算權重wij。

（1）關鍵詞集的維度m

關鍵詞用于表征該文檔特性，是能夠代表該文檔內容的基本語言單位。文獻[14]對比分析了多種關鍵詞提取方法。關鍵詞數量增加會導致F的維度m增大，從而引起時間復雜度增加。當提取關鍵詞后，采用TF-IDF算法，從而得出文檔集的維度m。

（2）權重wij的計算

最常用和有效的權重計算方法為TF-IDF 表示法，在信息檢索領域，該技術已經非常成熟。

TF-IDF 算法的計算分為詞頻（TF）和逆文檔頻率（IDF）兩部分。由這兩部分的乘積共同決定文檔詞的權重。TF-IDF算法有多重形式，通過實驗，在本文采用的計算方法為：

ni,j表示關鍵詞i在文檔j中的次數，nj表示文檔的總詞數。

其中，N為文檔集合中的文檔數目，Ni為關鍵詞i出現過的文檔數。權重由TF和IDF計算為：

3 方案設計

3.1 系統模型

關注的是如圖1所示的系統模型，參與方是數據擁有者、用戶和云服務器。

圖1 云存儲密文檢索系統模型

（1）數據擁有者：數據擁有者將加密數據上傳至云服務器，以及給有權限的用戶提供密鑰。

（2）用戶：用戶獲得數據擁有者的密鑰，上傳檢索向量，下載所需文檔。

（3）云服務器：云服務器充當存儲和計算的平臺。在密文下進行檢索計算，并返回結果給用戶。

3.2 威脅模型

假設數據擁有者和用戶均是誠實的，云服務器是誠實又好奇，即云服務器會正確執行協議，但嘗試推斷敏感信息。用戶和云之間沒有勾結。云中的攻擊者只會觀察到加密的數據，而不知道任何有關未加密的數據。

3.3 檢索方案

（1）初始化：數據擁有者在客戶端，根據參數m生成整數向量加密算法的公私鑰對(S,M)，SM4 加密算法的秘鑰E。

（2）數據加密：數據擁有者根據文檔集合生成向量空間模型中的文檔向量D。將文檔向量D使用M加密得到DM。將原文檔使用E進行加密得到DE。將DM以及DE一起上傳至云服務器存儲。

（3）檢索：獲得權限的檢索者向數據擁有者申請S、M、E。當檢索者執行檢索操作時，先將原始檢索向量擴充為與加密一致維數，即標準檢索向量Q，使用M加密后得到QM，再向云服務器提交檢索請求。

（4）相關性計算：云服務器接收到檢索請求后，計算檢索向量QM和文檔向量DM之間的余弦相似度，即相關性分數，將計算出的每個文檔相關性分數返回給客戶端。

（5）解密：用戶在客戶端收到相關性分數后，用S將相關性分數解密，并通過快速排序算法得到相關度由高到低的文檔編號。用戶按照需求向云服務器請求文檔數據。云服務器接收到請求后，將所請求的加密文檔返回給客戶端。客戶端使用E對文檔解密。

4 系統實現

4.1 系統整體框架

如圖2 所示，是云存儲密文檢索系統整體框架，基于方案，在云服務器下進行了實現。

圖2 云存儲密文檢索系統整體框架

用戶A上傳文件時，首先客戶端將原文本文件進行預處理，生成文檔向量。然后使用客戶端生成的同態加密算法的公鑰對文檔向量進行同態加密處理得到密文文檔向量。同時客戶端對原文本文件使用SM4分組密碼加密，將密文文件和密文文檔向量一起上傳至云服務器。

用戶B檢索文件時，向云服務器提交同樣使用同態加密算法加密后的檢索向量。云服務器通過計算檢索向量與文檔向量之間的余弦相似性，得到相關性分數。并將相關性分數返回給客戶端，用戶解密后，將所需下載請求發送給云服務器，云服務器將文件下載至客戶端，用戶通過SM4秘鑰對文件進行解密即可。

4.2 系統具體實現

（1）用戶加密上傳文件

用戶上傳文件流程如圖3所示。

圖3 用戶上傳文件流程

①對原文件進行特征項預處理。利用TF-IDF算法賦予特征項權重，構建向量空間模型，生成文檔向量D=(w1j,w2j,…,wij)。其中，wij表示第i個特征項（即關鍵詞）。

②對文檔向量D中的每個特征項wiq使用VHE進行同態加密。客戶端根據生成秘鑰對S、M、S作為用戶秘鑰，利用公鑰M對D進行加密，計算：

得到相應的密文文檔向量DM。

③對原文件進行SM4 加密。客戶端生成128 位的隨機數作為SM4 秘鑰E并保存在本地。利用E對原文件進行加密得到密文文件DE。將DM和DE一起發送至服務器存儲。

（2）用戶檢索下載文件

用戶檢索文件流程如圖4 所示，該部分共包含4 個階段。

圖4 用戶檢索文件流程

詳細過程如下：

①計算密文檢索向量。客戶端對用戶輸入的檢索語句，同樣根據向量空間模型和TF-IDF 算法生成檢索向量，為了保證維數相同，將原始檢索向量擴充為與文檔向量一致，得到檢索向量Q，利用之前生成的VHE算法的秘鑰S對檢索向量進行同態加密，計算：

得到相應的密文檢索向量QM，將其發送給云服務器。

②云服務器計算相關性分數。云服務器接收到DM后，計算檢索向量QM與文檔向量之間DM的相關性分數HM。計算公式：

通過計算向量之間的余弦相似度，得到檢索向量和文檔向量之間的相關性分數HM，把相似度高低作為檢索結果排序的依據。

③云服務器將相關性分數HM返回給客戶端。客戶端接收到相關性分數后，用S將其解密，得到H。

使用快速排序算法（Quicksort），得到相關度從高到低的n個文檔編號，將所需要的文檔請求發送給云服務器。

④云服務器將文件下載至客戶端。云服務器接收到文檔請求后，讀取存儲在服務器中的文件，返回給客戶端，客戶端利用SM4秘鑰E對文件解密，得到最終的明文檢索結果文件。

5 安全性及性能分析

5.1 安全性分析

（1）原文件安全性

原文件采用了SM4分組加密算法。加解密過程均由用戶在客戶端完成，云存儲服務器無法獲知其私鑰Ek。SM4保證了文件的安全性，可以抵抗差分攻擊、線性攻擊。使得敵手即使獲得了密文和明文，也無法求出密鑰的任何信息；即使獲得了密文和明文的統計規律，也無法求出明文的任何信息。

（2）檢索過程安全性

檢索部分采用了整數向量加密算法，對文檔向量以及檢索向量進行加密和解密，方案滿足部分同態。公私鑰生成均由用戶在客戶端生成，用戶將文檔向量加密后存儲在云服務器上，以密文形式存儲。檢索者將檢索向量加密后發給云服務器，利用同態加密的性質，在密文下進行余弦相似性內積計算，并將相關性分數返回給客戶端，在客戶端通過私鑰解密。整個過程均是在密文下進行的，云服務器無法獲知任何關于明文的數據，只有用戶和檢索者能夠獲得明文，保證了數據的安全性。

5.2 性能分析

（1）效率分析

從效率分析，方案主要消耗是在同態加密和內積計算過程中，密鑰生成和向量空間模型的建立只執行一次。因此方案的性能主要取決于加解密算法的效率。在加密過程中，大多數全同態加密方案在實際應用中效率極低而難以實現，本文采用的針對整數向量的同態加密方案僅關注在構建應用時需要的計算種類和計算深度，雖然無達到全同態，但其滿足進行余弦相似度計算的向量內積操作。將文檔文本構建向量空間模型后，需要對文檔向量和檢索向量進行加密。常規的同態加密算法是對向量中每個條目進行逐比特加密，而VHE 是把向量作為一個整體進行加密，提高了向量加密的效率。在實驗中，測試向量加密和內積計算所用時間，結果如表1和表2所示，由表可知對比常見同態加密算法，在進行向量加密時VHE效率高。對原文件的加解密采用SM4分組密碼，其軟件實現容易，與其他算法相比所需的內存空間小，適用于內存受限的環境，加解密速度快。與文獻[15]中采用BGV算法對比，本文采用的VHE進行向量加密效率更高。

表1 向量加密效率對比 μs

表2 內積計算效率對比 μs

（2）精確性分析

從精確性分析，本方案通過采用信息檢索領域最為經典的計算模型，構建向量空間模型，選取合適權重，計算余弦相似性，來檢索云存儲服務器中的文本數據，其精確度要遠高于[16]利用加密算法性質進行關鍵詞匹配的檢索方法。

方案支持多關鍵詞檢索，但關鍵詞數量增加會引起向量空間模型的維度增大，從而引起時間復雜度增加。因此在保證檢索效果以及減少時間開銷的前提下，通過實驗得出本方案檢索關鍵詞數量在（5，8）之間效果最好。

6 結束語

本文將整數向量加密算法以及在文本檢索領域使用最廣的向量空間模型相結合，應用在第三方不可信云存儲的全文檢索中。提出一個基于同態加密的檢索方案，檢索方案具有較高的執行效率。整個檢索過程安全性較高，可以抵抗不可信云服務器，有實際應用價值。