基于同態(tài)加密的機器學習研究綜述

孟書海

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

關鍵詞：云服務；同態(tài)加密；隱私保護；機器學習；數(shù)據(jù)挖掘

中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2019）04-0182-02

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

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

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

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

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

（3）求值（Eval）：在密文上進行運算（加法，乘法等）。

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

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

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

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

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

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

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

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

3 結束語

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

參考文獻：

[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)編輯：梁書】