一種全同態(tài)加密的安全內(nèi)積計算方案

鄧 江，許春香，楊浩淼

?

一種全同態(tài)加密的安全內(nèi)積計算方案

鄧 江，許春香，楊浩淼

(電子科技大學(xué)計算機科學(xué)與工程學(xué)院 成都 611731)

在云計算環(huán)境下密文top-檢索的眾多方法中，該文聚焦于同態(tài)加密方法，該公鑰加密方法具有不解密就能對密文進行操作的優(yōu)點。在密文top-查詢中，內(nèi)積相似性是度量索引向量和查詢向量的相似性的最常用的一個指標。該文提出一個安全計算兩向量內(nèi)積相似性的方案，該方案使用基于環(huán)上錯誤學(xué)習(xí)問題的批處理和打包的同態(tài)加密來保護隱私。與其他方法相比，該方案具有通信代價低和計算代價低的優(yōu)點。

中國剩余定理; 全同態(tài)加密; 環(huán)上錯誤學(xué)習(xí)問題; 單指令多數(shù)據(jù)流

在云計算中，由于數(shù)據(jù)如何在云中存儲對用戶來說是不透明的，因此，用戶常常擔(dān)心其存儲在云中數(shù)據(jù)的安全性。雖然可以通過認證、授權(quán)、訪問控制等傳統(tǒng)數(shù)據(jù)安全方法來保護存儲數(shù)據(jù)，但這些都是建立在云服務(wù)提供商是可信任基礎(chǔ)上的，而云服務(wù)提供商并不都像用戶所希望的那樣值得信任。2013年的棱鏡門事件，就是這樣一個侵犯云安全的典型案例。當云存儲提供商不那么可信時，保障云安全的一種方法，是對所有的云數(shù)據(jù)進行加密，但加密限制了數(shù)據(jù)的使用，特別是查詢和索引數(shù)據(jù)會變得異常困難。因此，如何在云計算環(huán)境下進行密文檢索是一個具有挑戰(zhàn)性的問題。

密文檢索的另一重要問題是多關(guān)鍵字排序。從云中檢索返回的大量文檔，需要進行相關(guān)性排序，使用戶快速找到最相關(guān)的個結(jié)果(top-檢索)。另一方面，由于單一的關(guān)鍵字搜索往往會產(chǎn)生過于粗糙的結(jié)果，為提高搜索結(jié)果的準確性以及提升用戶搜索體驗，還需支持多個關(guān)鍵字的搜索?，F(xiàn)在網(wǎng)絡(luò)搜索引擎(如：谷歌)的通常做法是，用戶提供一組關(guān)鍵字來檢索最相關(guān)的數(shù)據(jù)。對于多關(guān)鍵字排序的檢索，常常采用坐標匹配[1]的原則，即盡可能多的匹配，來度量相似性。在具體實現(xiàn)中，內(nèi)積相似性是最常用的一種方法，已被廣泛用于在云計算環(huán)境下的密文top-檢索。

在云計算的密文top-檢索中，通過云存儲文檔的特征向量和用戶查詢向量中的各個坐標盡可能多的匹配，來返回最相似的個文檔。如何度量這種相似性？一種最常用的方法是計算特征向量和查詢向量的內(nèi)積，內(nèi)積大者更相似。為了保護用戶的隱私，無論是特征向量和查詢向量都應(yīng)該加密。然而加密限制了數(shù)據(jù)的使用，云服務(wù)器很難采用傳統(tǒng)的加密方法來安全計算內(nèi)積。而全同態(tài)加密(fully homomorphic encryption, FHE)在不解密的情況下能夠直接基于密文計算[2-7]。于是一些學(xué)者使用全同態(tài)加密的方法來安全計算兩個密文向量內(nèi)積。

1 相關(guān)研究

文獻[8]基于整數(shù)上的全同態(tài)加密來安全計算內(nèi)積，首先使用全同態(tài)加密(FHE)對向量的每一坐標分別加密得到和，其中用表示對的加密，然后同態(tài)計算。然而，這種方法雖然簡單，但存在巨大問題。首先，當向量維數(shù)比較大時，需要傳送2個密文，通信代價很大；在用戶端需要計算2個加密，在云服務(wù)器端，為了同態(tài)計算內(nèi)積，服務(wù)器需要做個同態(tài)乘和個同態(tài)加，計算量都較大。此外，基于整數(shù)的全同態(tài)加密的安全性也是值得懷疑的。文獻[9]就給出了基于整數(shù)的全同態(tài)加密的密碼分析。

文獻[10]在基于生物認證的認證中，利用基于理想格的全同態(tài)加密來安全計算內(nèi)積。使用打包的技巧來將一個明文向量的所有坐標打包到一個密文中。但是該方案的計算效率并不高，如對兩個2 048維的bit向量，為了安全計算內(nèi)積，其預(yù)計計算的時間需要38 s。此外，該方案也不適合計算其他相似性指標，如余弦相似性。

因此，本文提出了一種基于全同態(tài)加密的安全計算內(nèi)積方案，該方案計算量低、通信開銷小、針對整數(shù)向量而不僅是bit向量，安全性高。

2 本文方案

本文使用基于格上的環(huán)上錯誤學(xué)習(xí)問題(learning with errors over ring, RLWE)的同態(tài)加密方法，安全高效地計算兩個高維向量的內(nèi)積。其主要思想是用戶首先將明文向量的所有坐標打包到一個密文里，然后云服務(wù)器以單指令多數(shù)據(jù)流(simple instruction multiple data，SIMD)的方式并行計算兩個向量的內(nèi)積。方案具體包括3個部分：基于RLWE的Somewhat同態(tài)加密方案的構(gòu)造、打包和SIMD并行化技術(shù)和安全內(nèi)積計算。

2.1 基于RLWE的Somewhat同態(tài)加密方案的構(gòu)造

本文基于RLWE來構(gòu)造Somewhat同態(tài)加密方案，該方案基于方案SHE(somewhat homomorphic encryption)[11]上為多項式時間算法的六元組(Setup, KeyGen, Enc, Dec, Add, Mult)，具體描述如下：

密鑰生成(SHE.KeyGen)：在高斯分布上隨機選擇一個元素作為私鑰，然后在上隨機均勻選取一個元素，同時在高斯分布上隨機選取一個差錯，計算。令私鑰，公鑰。

2.2 打包和SIMD技術(shù)

文獻[12]在基于理想格的全同態(tài)加密方案引入了打包和單指令多數(shù)據(jù)流(simple instruction multiple data, SIMD)方法，本文將該方法用于上述基于RLWE的SHE方案中，具體過程描述如下。

在對打包后的密文進行操作時，加同態(tài)和乘同態(tài)能在這些明文槽上并行地執(zhí)行，這樣極大地減輕了計算量。具體過程為：令一個打包后的密文為，對應(yīng)在個明文槽的明文分別為，令另一個打包后的密文為，對應(yīng)在個明文槽的明文則分別為，加同態(tài)SHE. Add對應(yīng)在各個明文槽的明文就分別為：，可以得到乘同態(tài)SHE. Mult對應(yīng)在各個明文槽的明文為：。因此同態(tài)操作可以看成是在明文槽上使用SIMD并行執(zhí)行的。

2.3 安全內(nèi)積計算

如前所述，基本方案只能對向量中的每一個坐標分別進行加密。本文將向量打包成一個單一的密文，再以SIMD并行的方式計算兩個向量的內(nèi)積。計算內(nèi)積的過程如下：

1) 系統(tǒng)選擇合適的參數(shù)和，使得明文空間分解為個明文槽，其中，的次數(shù)為；

2) 用戶擁有向量，對于維向量，將分別編碼為，其中，；

4) 類似地，用戶通過同樣步驟將維向量打包到，本文以用戶將向量打包為為例，具體過程如圖1所示；

圖1 用戶將明文向量的所有坐標打包到一個密文

表1 基于SIMD并行計算

表1 基于SIMD并行計算

打包后的密文對應(yīng)于各自空間的明文 乘同態(tài)

3 方案比較

將本文方案和已有的兩個基于全同態(tài)加密的安全內(nèi)積計算方案進行比較，結(jié)果如表2、表3所示。

表2 三種基于全同態(tài)加密的方案比較

表3 兩個方案的性能比較

從表中可以看出，本文方案使用基于RLWE的FHE計算兩個向量的內(nèi)積，不僅針對bit向量，還可以針對一般的整數(shù)向量，這一點與文獻[8]的方案相同，而文獻[10]的方案只能針對bit向量，因此，本文方案和文獻[8]的方案在實際應(yīng)用中更加廣泛。而與文獻[8]的方案相比，本文方案在計算中使用了打包技巧，將一個向量的所有坐標打包到一個密文中，同時使用了SIMD技巧以進行并行化處理，使得本文方案有著較高的計算效率。就通信成本而言，兩個方案中的明文空間均被劃分為個明文槽，因此本文方案有著較低的通信成本和計算代價。

4 結(jié)束語

本文提出一個適合于云計算中top-檢索的安全計算兩向量內(nèi)積相似性的方案，該方案使用基于RLWE的批處理同態(tài)加密來保護隱私。與其他方案相比，該方案具有通信開銷小和計算代價低的優(yōu)點。此外，在社交網(wǎng)絡(luò)中的群體挖掘，以及基于生物特征的認證等場景，也需要用到相似性度量。因此下一步的工作將研究如何將本文提出的方案應(yīng)用到其他場景。

參 考 文 獻

[1] WITTEN H, MOFFAT A，BELL T C. Managing gigabytes: Compressing and indexing documents and images[M]. San Francisco: Morgan Kaufmann Publishing, 1999.

[2] GENTRY C. Fully homomorphic encryption using ideal lattices[C]//Proceedings of the 41st Annual ACM Symposium on Symposium on Theory of Computing- STOC'09. [S.l.]: ACM Press, 2009: 169-178.

[3] SMART N P, VERCAUTEREN F. Fully homomorphic encryption with relatively small key and ciphertext sizes[C]//Public Key Cryptography-PKC 2010. Berlin: Springer, 2010: 420-443.

[4] STEHLE D, STEINFELD R. Faster fully homomorphic encryption[C]//Advances in Cryptology-ASIACRYPT 2010. Berlin: Springer, 2010: 377-394.

[5] GU Chun-sheng. Cryptanalysis of the Smart-Vercauteren and Gentry-Halevi’s fully homomorphic encryption[J]. International Journal of Security & Its Applications, 2012, 6(2): 176-184.

[6] CORON J S, MANDAL A, NACCACHE D, et al. Fully homomorphic encryption over the integers with shorter public keys[C]//Advances in Cryptology-CRYPTO 2011. Berlin: Springer, 2011: 487-504.

[7] GENTRY C, HALEVI S. Implementing Gentry’s fully-homomorphic encryption scheme[C]//Advances in Cryptology-EUROCRYPT 2011. Berlin: Springer, 2011: 129-148.

[8] YU J, LU P, ZHU Y, et al. Towards secure multi-keyword top-retrieval over encrypted cloud data[J]. IEEE Transactions on Dependable and SecureComputing, 2013, 10(4): 239-250.

[9] DING J, TAO C. A new algorithm for solving the general approximate common divisors problem and cryptanalysis of the fhe based on the gacd problem[DB/OL]. [2014-04-07]. http://eprint.iacr.org/2014/042.

[10] YASUDA M, SHIMOYAMA T, KOGURE J, et al. Packed homomorphic encryption based on ideal lattices and its application to biometrics[J]. Security Engineering and Intelligence Informatics, 2013(8128): 55-74.

[11] NAEHRIG M, LAUTER K, VAIKUNTANATHAN V. Can homomorphic encryption be practical?[C]//Proceedings of the 3rd ACM Workshop on Cloud Computing Security Workshop. Rome: ACM Press, 2011: 113-124.

[12] SMART N P, VERCAUTEREN F. Fully homomorphic SIMD operations[J]. Designs, Codes and Cryptography, 2014, 71(1): 57-81.

編 輯 蔣 曉

A Secure Computation Scheme of Inner Product Based on Fully Homomorphic Encryption

DENG Jiang, XU Chun-xiang, and YANG Hao-miao

(School of Computer Science and Engineering, University of Electronic Science and Technology of China Chengdu 611731)

Among many approaches to solve the problem of top-retrieval over encrypted cloud data, we focus on an approach with homomorphic encryption, which is public key encryption supporting some operations on encrypted data. In top-retrieval of encrypted data, the inner product is often used as a metric to compute the similarity between the file feature vector and the query vector. In this paper, we propose an efficient scheme to compute the inner product on encrypted data using the homomorphic encryption based on the learning with errors over ring (RLWE) problem, in which batch and packing techniques are adopted to achieve lower computation and communication cost.

Chinese remainder theorem; fully homomorphic encryption; learning with errors over ring; single instruction multiple data

TP309

A

10.3969/j.issn.1001-0548.2016.05.017

2015-03-11；

2015-06-20

國家自然科學(xué)基金面上項目(61472065, 61370203)

鄧江(1982-)，男，博士，主要從事信息安全方面的研究.