基于同態(tài)加密的機(jī)器學(xué)習(xí)研究綜述

孟書(shū)海

摘要：目前，機(jī)器學(xué)習(xí)技術(shù)在各行業(yè)已經(jīng)被廣泛應(yīng)用，隨著云服務(wù)模式的快速發(fā)展，越來(lái)越多的云服務(wù)商提供機(jī)器學(xué)習(xí)平臺(tái)供用戶使用。但隨著現(xiàn)代社會(huì)對(duì)隱私保護(hù)越來(lái)越重視，如何在計(jì)算的過(guò)程中既保證數(shù)據(jù)的隱私性，又保證算法的有效性越來(lái)越成為機(jī)器學(xué)習(xí)領(lǐng)域中的一大難題。為了解決這一問(wèn)題，各種同態(tài)加密算法被相繼提出。本文介紹了同態(tài)加密的相關(guān)概念，并重點(diǎn)介紹了同態(tài)加密技術(shù)在機(jī)器學(xué)習(xí)領(lǐng)域的研究進(jìn)展，提出了未來(lái)的研究方向。

關(guān)鍵詞：云服務(wù)；同態(tài)加密；隱私保護(hù)；機(jī)器學(xué)習(xí)；數(shù)據(jù)挖掘

中圖分類(lèi)號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2019）04-0182-02

為了解決機(jī)器學(xué)習(xí)中的隱私保護(hù)問(wèn)題，假設(shè)基于這樣一種場(chǎng)景，客戶將數(shù)據(jù)提交給第三方云服務(wù)商之前，首先用某種同態(tài)加密方案對(duì)數(shù)據(jù)加密，然后機(jī)器學(xué)習(xí)模型對(duì)加密的數(shù)據(jù)進(jìn)行分析處理，得到的結(jié)果仍然是加密的，之后第三方服務(wù)商將加密數(shù)據(jù)返回給客戶，客戶運(yùn)用自己的私鑰進(jìn)行解密即可得到相應(yīng)的結(jié)果。整個(gè)過(guò)程中，由于第三方服務(wù)商一直都是對(duì)密文進(jìn)行操作，因此客戶的數(shù)據(jù)一直是安全的。另一種情形，當(dāng)云服務(wù)商需要客戶的數(shù)據(jù)進(jìn)行模型的訓(xùn)練時(shí)，我們也采取同樣的方式。

1 同態(tài)加密算法

同態(tài)加密（homomorphic encryption）的概念是由Rivest[1]等人于1978年最先提出，它允許人們對(duì)密文進(jìn)行特定形式的代數(shù)運(yùn)算得到仍然是加密的結(jié)果，將其解密所得到的結(jié)果與對(duì)明文進(jìn)行同樣的運(yùn)算結(jié)果一樣。同態(tài)加密方案由以下四個(gè)部分構(gòu)成：、

（1）密鑰生成（KeyGen）：由安全參數(shù)計(jì)算一對(duì)公私鑰。

（2）加密（Enc）：根據(jù)第一步生成的密鑰計(jì)算出密文。

（3）求值（Eval）：在密文上進(jìn)行運(yùn)算（加法，乘法等）。

（4）解密（Dec）：將計(jì)算后的密文進(jìn)行解密，得到明文。

根據(jù)在密文上操作的不同，可將同態(tài)加密方案分為部分同態(tài)加密方案和完全同態(tài)加密方案。

1.1 部分同態(tài)加密

部分同態(tài)加密方案（Partially homomorphic cryptosystems，簡(jiǎn)稱(chēng)PHE）支持的操作一般是加法和乘法。應(yīng)用廣泛的部分同態(tài)加密方案包括：支持加法同態(tài)的Benalol[2]和Paillier[3]算法，支持乘法同態(tài)的RSA[4]和EIGamal[5]算法，以及支持比特異或同態(tài)的Goldwasser Micali[6]算法。這些經(jīng)典的部分同態(tài)加密方案安全性高，且計(jì)算較為高效，對(duì)于符合條件的應(yīng)用場(chǎng)景，能夠保證數(shù)據(jù)的安全性并且滿足計(jì)算效率的要求。

1.2 完全同態(tài)加密

完全同態(tài)加密或全同態(tài)加密（fully homomorphic encryption，簡(jiǎn)稱(chēng)FHE），即可以在不解密的條件下對(duì)加密數(shù)據(jù)進(jìn)行任何可以在明文上進(jìn)行的運(yùn)算。2009年，IBM研究人員Gentry[7]從理論角度首先提出了基于理想格的全同態(tài)加密算法，引起了學(xué)術(shù)界對(duì)全同態(tài)加密的研究熱潮。后續(xù)的研究工作基本上都在Gentry的基礎(chǔ)上進(jìn)行，并致力于降低計(jì)算開(kāi)銷(xiāo)，提高計(jì)算效率并兼顧安全性。理論上來(lái)說(shuō)，全同態(tài)加密方案是既能夠保護(hù)數(shù)據(jù)機(jī)密性又不損失數(shù)據(jù)可用性的最佳選擇，但是由于方案本身、計(jì)算模型以及高安全性帶來(lái)的開(kāi)銷(xiāo)過(guò)高，使其無(wú)法在實(shí)際中應(yīng)用。但是之后學(xué)者們提出了一定程度上的完全同態(tài)加密方案類(lèi)同態(tài)加密技術(shù)（somewhat homomorphic encryption，簡(jiǎn)稱(chēng)SWHE） [8]，這種加密方式只適用于低階多項(xiàng)式的運(yùn)算，只允許在加密數(shù)據(jù)上進(jìn)行有限次數(shù)的同態(tài)加法和乘法運(yùn)算，有較好的實(shí)用性。

2 基于同態(tài)加密的機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘研究現(xiàn)狀

Graepel等人[9]提出了一種將模型的預(yù)測(cè)函數(shù)通過(guò)數(shù)學(xué)方法表示為低次多項(xiàng)式的解決方案來(lái)解決同態(tài)加密操作引起的“噪音“過(guò)大問(wèn)題。研究是在訓(xùn)練階段的隱私保護(hù)問(wèn)題，這種方案有效地限制了在加密數(shù)據(jù)上進(jìn)行同態(tài)操作的次數(shù)，并將同態(tài)操作限制在加法和乘法上，最后將其運(yùn)用在LM和FLD分類(lèi)器上并取得了實(shí)際的效果。之后Wu等人[10]利用批量計(jì)算和基于CRT的消息編碼技術(shù)實(shí)現(xiàn)了對(duì)大規(guī)模數(shù)據(jù)集和高維數(shù)據(jù)進(jìn)行同態(tài)加密，然后在加密數(shù)據(jù)上進(jìn)行線性回歸等統(tǒng)計(jì)學(xué)分析，適合多源數(shù)據(jù)的場(chǎng)景。由于一定程度上的同態(tài)加密只支持有限的同態(tài)操作，而低次多項(xiàng)式則可以滿足這一性質(zhì)。因而Dowlin[11]利用切比雪夫近似理論將神經(jīng)網(wǎng)絡(luò)模型中的非線性激活函數(shù)用低次多項(xiàng)式函數(shù)代替從而實(shí)現(xiàn)了可對(duì)密文進(jìn)行處理的神經(jīng)網(wǎng)絡(luò)CryptoNets，并通過(guò)在真實(shí)數(shù)據(jù)集MNIST上的實(shí)驗(yàn)說(shuō)明了模型的合理性，是在分類(lèi)階段做的研究，因?yàn)樯窠?jīng)網(wǎng)絡(luò)模型比線性分類(lèi)器有著更好的準(zhǔn)確度，這是一個(gè)很好的突破。Bost等人[12]在超平面分割（hyperplane decision）、樸素貝葉斯（na?ve bayes）和決策樹(shù)分類(lèi)器上嘗試了對(duì)密文的處理，也是在分類(lèi)階段做的研究。由于Dowlin等人提出的CryptoNets在深度神經(jīng)網(wǎng)絡(luò)上表現(xiàn)并不好，因此Chabanne等人[13]在此基礎(chǔ)上再次提出了改進(jìn)，提出的卷積神經(jīng)網(wǎng)絡(luò)模型比CryptoNets有著更高的準(zhǔn)確性，這也是同態(tài)加密與深度神經(jīng)網(wǎng)絡(luò)相結(jié)合第一次成功的嘗試。除此之外，Aono[14]運(yùn)用加法同態(tài)加密提出了可在密文上進(jìn)行計(jì)算的邏輯回歸模型?？梢钥闯觯谕瑧B(tài)加密的數(shù)據(jù)已經(jīng)被應(yīng)用于很多常見(jiàn)的機(jī)器學(xué)習(xí)模型上，并取得了較好的準(zhǔn)確性。但是值得一提的是，由于計(jì)算模型較為復(fù)雜，相比于明文上的處理，計(jì)算時(shí)間普遍都大大延長(zhǎng)了，比如在Xie[15]的實(shí)驗(yàn)中，神經(jīng)網(wǎng)絡(luò)中的激活函數(shù)經(jīng)過(guò)多項(xiàng)式近似之后，需要的預(yù)測(cè)時(shí)間高達(dá)一個(gè)小時(shí)，而傳統(tǒng)的神經(jīng)網(wǎng)絡(luò)則在瞬間就可以完成預(yù)測(cè)。在Graepel等人[9]的實(shí)驗(yàn)中，線性分類(lèi)器LM在密文上的訓(xùn)練和分類(lèi)時(shí)間大約比明文上慢五到六個(gè)數(shù)量級(jí)。

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

本文重點(diǎn)總結(jié)了同態(tài)加密算法在機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘領(lǐng)域的研究進(jìn)展，并提出了研究過(guò)程中面臨的主要難題，提出效率更高的同態(tài)加密方案應(yīng)該是以后的研究方向，也是未來(lái)隱私保護(hù)的重要研究方向之一。

參考文獻(xiàn)：

[1] R L Rivest，L Adleman，and M L Dertouzos.On data banks and privacy homomorphisms[M]. Foundations of Secure Computation， Academia Press， 1978.

[2] Benaloh J. Verifiable secret-ballot elections [Ph.D. Thesis][M]. New Haven： Yale University， 1988 .

[3] Paillier P. Public-Key cryptosystems based on composite degree residuosity classes[M]//Stern J， ed. Advances in Cryptology— EUROCRYPT 1999. Heidelberg： Springer-Verlag， 1999. 223-238.

[4] Rivest RL， Shamir A， Adleman L. A method for obtaining digital signatures and public-key cryptosystems[J]. Communications of the ACM， 1978， 21 （2） ：120–126.

[5] Elgamal T. A public key cryptosystem and a signature scheme based on discrete logarithms[J]. IEEE Trans. on Information Theory， 1985， 31 （4） ：469–472.

[6] Goldwasser S， Micali S. Probabilistic encryption and how to play mental poker keeping secret all partial information[M]//Proc. of the 14th ACM Symp. on Theory of Computing （STOC 1982）. New York： ACM Press， 1982. 365-377.

[7] Gentry C. Fully homomorphic encryption using ideal lattices. In： Proc. of the 41st ACM Symp. on Theory of Computing （STOC 2009）[M]. New York： ACM Press， 2009. 169-178.

[8] Junfeng Fan and Frederik Vercauteren， Somewhat practical fully homomorphic encryption[M]. IACR Cryptology ePrint Archive， （2012/144）.

[9] T. Graepel， K. Lauter， and M. Naehrig， ML confidential： Machine learning on encrypted data[C]//Information Security and Cryptology （ICISC）， 2012， pp. 1–21.

[10] Wu， David and Haven， Jacob. Using homomorphic encryption for large scale statistical analysis. 2012.

[11] R. Gilad-Bachrach， N. Dowlin， K. Laine， K. Lauter， M. Naehrig， and J. Wernsing， Cryptonets： Applying neural networks to encrypted data with high throughput and accuracy[C]//Proceedings of The 33rd International Conference on Machine Learning， 2016， pp. 201–210.

[12] R. Bost， R. A. Popa， S. Tu， and S. Goldwasser. Machine learning classification over encrypted data. In 22nd Annual Network and Distributed System Security Symposium， NDSS 2015. The Internet Society， 2015.

[13] H. Chabanne， A. de Wargny， J. Milgram， C. Morel， and E. Prouff. Privacyp-reserving classification on deep neural network. Cryptology ePrint Archive， Report 2017/035， 2017.

[14] Aono， Y.， Hayashi， T.， Trieu Phong， L.， and Wang， L. Scalable and secure logistic regression via homomorphic encryption[C]//Proceedings of the Sixth ACM Conference on Data and Application Security and Privacy （2016）， ACM， pp. 142–144.

[15] P. Xie， M. Bilenko， T. Finley， R. Gilad-Bachrach， K. Lauter， and M. Naehrig. Crypto-nets： Neural networks over encrypted data. arXiv：1412.6181， 2014.

【通聯(lián)編輯：梁書(shū)】