鄧 江，許春香，楊浩淼

?

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

鄧 江，許春香，楊浩淼

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

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

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

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

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

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

1 相關(guān)研究

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

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

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

2 本文方案

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

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

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

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

2.2 打包和SIMD技術(shù)

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

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

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

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

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

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

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

圖1 用戶將明文向量的所有坐標(biāo)打包到一個(gè)密文

表1 基于SIMD并行計(jì)算

表1 基于SIMD并行計(jì)算

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

3 方案比較

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

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

表3 兩個(gè)方案的性能比較

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

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

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

參 考 文 獻(xiàn)

[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

國(guó)家自然科學(xué)基金面上項(xiàng)目(61472065, 61370203)

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