基于同态加密的机器学习研究综述

孟书海

摘要：目前，机器学习技术在各行业已经被广泛应用，随着云服务模式的快速发展，越来越多的云服务商提供机器学习平台供用户使用。但随着现代社会对隐私保护越来越重视，如何在计算的过程中既保证数据的隐私性，又保证算法的有效性越来越成为机器学习领域中的一大难题。为了解决这一问题，各种同态加密算法被相继提出。本文介绍了同态加密的相关概念，并重点介绍了同态加密技术在机器学习领域的研究进展，提出了未来的研究方向。

关键词：云服务；同态加密；隐私保护；机器学习；数据挖掘

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2019）04-0182-02

为了解决机器学习中的隐私保护问题，假设基于这样一种场景，客户将数据提交给第三方云服务商之前，首先用某种同态加密方案对数据加密，然后机器学习模型对加密的数据进行分析处理，得到的结果仍然是加密的，之后第三方服务商将加密数据返回给客户，客户运用自己的私钥进行解密即可得到相应的结果。整个过程中，由于第三方服务商一直都是对密文进行操作，因此客户的数据一直是安全的。另一种情形，当云服务商需要客户的数据进行模型的训练时，我们也采取同样的方式。

1 同态加密算法

同态加密（homomorphic encryption）的概念是由Rivest[1]等人于1978年最先提出，它允许人们对密文进行特定形式的代数运算得到仍然是加密的结果，将其解密所得到的结果与对明文进行同样的运算结果一样。同态加密方案由以下四个部分构成：、

（1）密钥生成（KeyGen）：由安全参数计算一对公私钥。

（2）加密（Enc）：根据第一步生成的密鑰计算出密文。

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

（4）解密（Dec）：将计算后的密文进行解密，得到明文。

根据在密文上操作的不同，可将同态加密方案分为部分同态加密方案和完全同态加密方案。

1.1 部分同态加密

部分同态加密方案（Partially homomorphic cryptosystems，简称PHE）支持的操作一般是加法和乘法。应用广泛的部分同态加密方案包括：支持加法同态的Benalol[2]和Paillier[3]算法，支持乘法同态的RSA[4]和EIGamal[5]算法，以及支持比特异或同态的Goldwasser Micali[6]算法。这些经典的部分同态加密方案安全性高，且计算较为高效，对于符合条件的应用场景，能够保证数据的安全性并且满足计算效率的要求。

1.2 完全同态加密

完全同态加密或全同态加密（fully homomorphic encryption，简称FHE），即可以在不解密的条件下对加密数据进行任何可以在明文上进行的运算。2009年，IBM研究人员Gentry[7]从理论角度首先提出了基于理想格的全同态加密算法，引起了学术界对全同态加密的研究热潮。后续的研究工作基本上都在Gentry的基础上进行，并致力于降低计算开销，提高计算效率并兼顾安全性。理论上来说，全同态加密方案是既能够保护数据机密性又不损失数据可用性的最佳选择，但是由于方案本身、计算模型以及高安全性带来的开销过高，使其无法在实际中应用。但是之后学者们提出了一定程度上的完全同态加密方案类同态加密技术（somewhat homomorphic encryption，简称SWHE） [8]，这种加密方式只适用于低阶多项式的运算，只允许在加密数据上进行有限次数的同态加法和乘法运算，有较好的实用性。

2 基于同态加密的机器学习和数据挖掘研究现状

Graepel等人[9]提出了一种将模型的预测函数通过数学方法表示为低次多项式的解决方案来解决同态加密操作引起的“噪音“过大问题。研究是在训练阶段的隐私保护问题，这种方案有效地限制了在加密数据上进行同态操作的次数，并将同态操作限制在加法和乘法上，最后将其运用在LM和FLD分类器上并取得了实际的效果。之后Wu等人[10]利用批量计算和基于CRT的消息编码技术实现了对大规模数据集和高维数据进行同态加密，然后在加密数据上进行线性回归等统计学分析，适合多源数据的场景。由于一定程度上的同态加密只支持有限的同态操作，而低次多项式则可以满足这一性质。因而Dowlin[11]利用切比雪夫近似理论将神经网络模型中的非线性激活函数用低次多项式函数代替从而实现了可对密文进行处理的神经网络CryptoNets，并通过在真实数据集MNIST上的实验说明了模型的合理性，是在分类阶段做的研究，因为神经网络模型比线性分类器有着更好的准确度，这是一个很好的突破。Bost等人[12]在超平面分割（hyperplane decision）、朴素贝叶斯（na?ve bayes）和决策树分类器上尝试了对密文的处理，也是在分类阶段做的研究。由于Dowlin等人提出的CryptoNets在深度神经网络上表现并不好，因此Chabanne等人[13]在此基础上再次提出了改进，提出的卷积神经网络模型比CryptoNets有着更高的准确性，这也是同态加密与深度神经网络相结合第一次成功的尝试。除此之外，Aono[14]运用加法同态加密提出了可在密文上进行计算的逻辑回归模型。可以看出，基于同态加密的数据已经被应用于很多常见的机器学习模型上，并取得了较好的准确性。但是值得一提的是，由于计算模型较为复杂，相比于明文上的处理，计算时间普遍都大大延长了，比如在Xie[15]的实验中，神经网络中的激活函数经过多项式近似之后，需要的预测时间高达一个小时，而传统的神经网络则在瞬间就可以完成预测。在Graepel等人[9]的实验中，线性分类器LM在密文上的训练和分类时间大约比明文上慢五到六个数量级。

3 结束语

本文重点总结了同态加密算法在机器学习和数据挖掘领域的研究进展，并提出了研究过程中面临的主要难题，提出效率更高的同态加密方案应该是以后的研究方向，也是未来隐私保护的重要研究方向之一。

参考文献：

[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.

【通聯编辑：梁书】