ABSTRACT
Homomorphic Encryption (HE) is a powerful cryptographic primitive to address privacy and security issues in outsourcing computation on sensitive data to an untrusted computation environment. Comparing to secure Multi-Party Computation (MPC), HE has advantages in supporting non-interactive operations and saving on communication costs. However, it has not come up with an optimal solution for modern learning frameworks, partially due to a lack of efficient matrix computation mechanisms. In this work, we present a practical solution to encrypt a matrix homomorphically and perform arithmetic operations on encrypted matrices. Our solution includes a novel matrix encoding method and an efficient evaluation strategy for basic matrix operations such as addition, multiplication, and transposition. We also explain how to encrypt more than one matrix in a single ciphertext, yielding better amortized performance. Our solution is generic in the sense that it can be applied to most of the existing HE schemes. It also achieves reasonable performance for practical use; for example, our implementation takes 9.21 seconds to multiply two encrypted square matrices of order 64 and 2.56 seconds to transpose a square matrix of order 64. Our secure matrix computation mechanism has a wide applicability to our new framework EDM, which stands for encrypted data and encrypted model. To the best of our knowledge, this is the first work that supports secure evaluation of the prediction phase based on both encrypted data and encrypted model, whereas previous work only supported applying a plain model to encrypted data. As a benchmark, we report an experimental result to classify handwritten images using convolutional neural networks (CNN). Our implementation on the MNIST dataset takes 28.59 seconds to compute ten likelihoods of 64 input images simultaneously, yielding an amortized rate of 0.45 seconds per image.
Supplemental Material
- Mart'in Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, Craig Citro, Greg S Corrado, Andy Davis, Jeffrey Dean, Matthieu Devin, et al. 2015. Tensorflow: Large-scale machine learning on heterogeneous distributed systems. (2015). https://www.tensorflow.org.Google Scholar
- Martin R Albrecht, Rachel Player, and Sam Scott. 2015. On the concrete hardness of learning with errors. Journal of Mathematical Cryptology, Vol. 9, 3 (2015), 169--203.Google ScholarCross Ref
- Cloud Security Alliance. 2009. Security guidance for critical areas of focus in cloud computing. (2009). http://www.cloudsecurityalliance.org.Google Scholar
- Mikhail J Atallah and Keith B Frikken. 2010. Securely outsourcing linear algebra computations. Proceedings of the 5th ACM Symposium on Information, Computer and Communications Security. ACM, 48--59. Google ScholarDigital Library
- Mauro Barni, Claudio Orlandi, and Alessandro Piva. 2006. A privacy-preserving protocol for neural-network-based computation. In Proceedings of the 8th workshop on Multimedia and security. ACM, 146--151. Google ScholarDigital Library
- Joppe W Bos, Kristin Lauter, Jake Loftus, and Michael Naehrig. 2013. Improved security for a ring-based fully homomorphic encryption scheme. Cryptography and Coding. Springer, 45--64. Google ScholarDigital Library
- Florian Bourse, Michele Minelli, Matthias Minihold, and Pascal Paillier. 2017. Fast Homomorphic Evaluation of Deep Discretized Neural Networks. Cryptology ePrint Archive, Report 2017/1114. (2017). https://eprint.iacr.org/2017/1114.Google Scholar
- Zvika Brakerski. 2012. Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP. Advances in Cryptology--CRYPTO 2012. Springer, 868--886. Google ScholarDigital Library
- Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan. 2012. (Leveled) fully homomorphic encryption without bootstrapping. In Proc. of ITCS. ACM, 309--325. Google ScholarDigital Library
- Hervé Chabanne, Amaury de Wargny, Jonathan Milgram, Constance Morel, and Emmanuel Prouff. 2017. Privacy-preserving classification on deep neural network. Cryptology ePrint Archive, Report 2017/035. (2017). https://eprint.iacr.org/2017/035.Google Scholar
- David Chaum and Torben Pryds Pedersen. 1992. Wallet databases with observers. In Annual International Cryptology Conference. Springer, 89--105. Google ScholarDigital Library
- Jung Hee Cheon, Kyoohyung Han, Andrey Kim, Miran Kim, and Yongsoo Song. 2018. Bootstrapping for Approximate Homomorphic Encryption. In Advances in Cryptology--EUROCRYPT 2018. Springer, 360--384.Google ScholarCross Ref
- Jung Hee Cheon, Andrey Kim, Miran Kim, and Yongsoo Song. 2016. Implementation of textHEAAN. (2016). https://github.com/kimandrik/HEAAN.Google Scholar
- Jung Hee Cheon, Andrey Kim, Miran Kim, and Yongsoo Song. 2017. Homomorphic encryption for arithmetic of approximate numbers. In Advances in Cryptology--ASIACRYPT 2017: 23rd International Conference on the Theory and Application of Cryptology and Information Security. Springer, 409--437.Google Scholar
- Francc ois Chollet et al. 2015. Keras. (2015). https://github.com/keras-team/keras.Google Scholar
- Kai-Min Chung, Yael Tauman Kalai, Feng-Hao Liu, and Ran Raz. 2011. Memory delegation. In Annual Cryptology Conference. Springer, 151--168. Google ScholarDigital Library
- Daniel Demmler, Thomas Schneider, and Michael Zohner. 2015. textABY-A Framework for Efficient Mixed-Protocol Secure Two-Party Computation. In NDSS .Google Scholar
- Dung Hoang Duong, Pradeep Kumar Mishra, and Masaya Yasuda. 2016. Efficient secure matrix multiplication over LWE-based homomorphic encryption. Tatra Mountains Mathematical Publications, Vol. 67, 1 (2016), 69--83.Google ScholarCross Ref
- Junfeng Fan and Frederik Vercauteren. 2012. Somewhat Practical Fully Homomorphic Encryption. Cryptology ePrint Archive, Report 2012/144. (2012). https://eprint.iacr.org/2012/144.Google Scholar
- Dario Fiore and Rosario Gennaro. 2012. Publicly verifiable delegation of large polynomials and matrix computations, with applications. In Proceedings of the 2012 ACM conference on Computer and communications security. ACM, 501--512. Google ScholarDigital Library
- Rosario Gennaro, Craig Gentry, and Bryan Parno. 2010. Non-interactive verifiable computing: Outsourcing computation to untrusted workers. In Annual Cryptology Conference. Springer, 465--482. Google ScholarDigital Library
- Craig Gentry et al. 2009. Fully homomorphic encryption using ideal lattices. In STOC, Vol. 9. 169--178. Google ScholarDigital Library
- Craig Gentry, Shai Halevi, and Nigel P Smart. 2012. Homomorphic evaluation of the AES circuit. Advances in Cryptology--CRYPTO 2012. Springer, 850--867. Google ScholarDigital Library
- Ran Gilad-Bachrach, Nathan Dowlin, Kim Laine, Kristin Lauter, Michael Naehrig, and John Wernsing. 2016. CryptoNets: Applying neural networks to encrypted data with high throughput and accuracy. In International Conference on Machine Learning. 201--210. Google ScholarDigital Library
- Shai Halevi and Victor Shoup. 2014. Algorithms in HElib. In Advances in Cryptology--CRYPTO 2014. Springer, 554--571.Google ScholarCross Ref
- Shai Halevi and Victor Shoup. 2015. Bootstrapping for HElib. Advances in Cryptology--EUROCRYPT 2015. Springer, 641--670.Google Scholar
- Shai Halevi and Victor Shoup. 2018. Faster Homomorphic Linear Transformations in HElib. Cryptology ePrint Archive, Report 2018/244. (2018). https://eprint.iacr.org/2018/244.Google Scholar
- Xiaoqian Jiang, Yongan Zhao, Xiaofeng Wang, Bradley Malin, Shuang Wang, Lucila Ohno-Machado, and Haixu Tang. 2014. A community assessment of privacy preserving techniques for human genomes. BMC Med. Inform. Decis. Mak., Vol. 14 Suppl 1, Suppl 1 (Dec. 2014), S1.Google ScholarCross Ref
- Chiraag Juvekar, Vinod Vaikuntanathan, and Anantha Chandrakasan. 2018. GAZELLE: A Low Latency Framework for Secure Neural Network Inference. In 27th USENIX Security Symposium (USENIX Security 18). USENIX Association, Baltimore, MD. Google ScholarDigital Library
- Miran Kim and Kristin Lauter. 2015. Private genome analysis through homomorphic encryption. BMC medical informatics and decision making, Vol. 15, Suppl 5 (2015), S3.Google Scholar
- Miran Kim, Yongsoo Song, Shuang Wang, Yuhou Xia, and Xiaoqian Jiang. 2018. Secure Logistic Regression based on Homomorphic Encryption: Design and Evaluation. JMIR medical informatics, Vol. 6, 2 (2018).Google Scholar
- Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. 2012. Imagenet classification with deep convolutional neural networks. In Advances in neural information processing systems. 1097--1105. Google ScholarDigital Library
- Yann LeCun. 1998. The MNIST database of handwritten digits. http://yann. lecun. com/exdb/mnist/ (1998).Google Scholar
- Jian Liu, Mika Juuti, Yao Lu, and N Asokan. 2017. Oblivious neural network predictions via minionn transformations. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. ACM, 619--631. Google ScholarDigital Library
- Eleftheria Makri, Dragos Rotaru, Nigel P Smart, and Frederik Vercauteren. 2017. PICS: Private Image Classification with textSVM. Cryptology ePrint Archive, Report 2017/1190. (2017). https://eprint.iacr.org/2017/1190.Google Scholar
- Riccardo Miotto, Fei Wang, Shuang Wang, Xiaoqian Jiang, and Joel T Dudley. 2017. Deep learning for healthcare: review, opportunities and challenges. Brief. Bioinform. (May 2017).Google Scholar
- Pradeep Kumar Mishra, Dung Hoang Duong, and Masaya Yasuda. 2017. Enhancement for Secure Multiple Matrix Multiplications over Ring-LWE Homomorphic Encryption. In International Conference on Information Security Practice and Experience. Springer, 320--330.Google ScholarCross Ref
- Payman Mohassel. 2011. Efficient and Secure Delegation of Linear Algebra. Cryptology ePrint Archive, Report 2011/605. (2011). https://eprint.iacr.org/2011/605.Google Scholar
- Payman Mohassel and Yupeng Zhang. 2017. SecureML: A system for scalable privacy-preserving machine learning. In Security and Privacy (SP), 2017 IEEE Symposium on. IEEE, 19--38.Google ScholarCross Ref
- Michael Naehrig, Kristin Lauter, and Vinod Vaikuntanathan. 2011. Can homomorphic encryption be practical?. In Proceedings of the 3rd ACM workshop on Cloud computing security workshop. ACM, 113--124. Google ScholarDigital Library
- Claudio Orlandi, Alessandro Piva, and Mauro Barni. 2007. Oblivious neural network computing via homomorphic encryption. EURASIP Journal on Information Security, Vol. 2007, 1 (2007), 037343.Google ScholarCross Ref
- M Sadegh Riazi, Christian Weinert, Oleksandr Tkachenko, Ebrahim M Songhori, Thomas Schneider, and Farinaz Koushanfar. 2018. Chameleon: A Hybrid Secure Computation Framework for Machine Learning Applications. arXiv preprint arXiv:1801.03239 (2018).Google Scholar
- Victor Shoup et al. 2001. NTL: A library for doing number theory. (2001).Google Scholar
- Karen Simonyan and Andrew Zisserman. 2014. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv:1409.1556 (2014).Google Scholar
- Nigel P Smart and Frederik Vercauteren. 2011. Fully homomorphic textSIMD operations. Cryptology ePrint Archive, Report 2011/133. (2011). https://eprint.iacr.org/2011/133.Google Scholar
- Hassan Takabi, James BD Joshi, and Gail-Joon Ahn. 2010. Security and privacy challenges in cloud computing environments. IEEE Security & Privacy, Vol. 8, 6 (2010), 24--31. Google ScholarDigital Library
- Shuang Wang, Xiaoqian Jiang, Haixu Tang, Xiaofeng Wang, Diyue Bu, Knox Carey, Stephanie O M Dyke, Dov Fox, Chao Jiang, Kristin Lauter, and Others. 2017. A community effort to protect genomic data sharing, collaboration and outsourcing. npj Genomic Medicine, Vol. 2, 1 (2017), 33.Google Scholar
- David Wu and Jacob Haven. 2012. Using homomorphic encryption for large scale statistical analysis. Technical Report. Technical Report: cs. stanford. edu/people/dwu4/papers/FHESI Report. pdf.Google Scholar
- Masaya Yasuda, Takeshi Shimoyama, Jun Kogure, Kazuhiro Yokoyama, and Takeshi Koshiba. 2015. New packing method in somewhat homomorphic encryption and its applications. Security and Communication Networks, Vol. 8, 13 (2015), 2194--2213. Google ScholarDigital Library
- Matthew D Zeiler. 2012. ADADELTA: an adaptive learning rate method. arXiv preprint arXiv:1212.5701 (2012).Google Scholar
Index Terms
- Secure Outsourced Matrix Computation and Application to Neural Networks
Recommendations
Chosen ciphertext secure keyed-homomorphic public-key cryptosystems
In homomorphic encryption schemes, anyone can perform homomorphic operations, and therefore, it is difficult to manage when, where and by whom they are performed. In addition, the property that anyone can "freely" perform the operation inevitably means ...
Delegatable homomorphic encryption with applications to secure outsourcing of computation
CT-RSA'12: Proceedings of the 12th conference on Topics in CryptologyWe propose a new cryptographic primitive called Delegatable Homomorphic Encryption (DHE). This allows a Trusted Authority to control/delegate the evaluation of circuits over encrypted data to untrusted workers/evaluators by issuing tokens. This ...
New verifiable outsourced computation scheme for an arbitrary function
We study the construction of efficient verifiable outsourced computation for arbitrary functions. We improve previous verifiable outsourced computation schemes for arbitrary functions by using hybrid encryption based on fully homomorphic encryption and ...
Comments