Document Type : Research Article
Authors
Department of Computer Engineering, Sharif University of Technology, Tehran, Iran
Abstract
Secure multi-party computation (MPC) allows a group of parties to compute a function on their private inputs securely. Classic MPC protocols for two parties use either Yao's garbled circuit (GC) or the Goldreich-Micali-Wigderson (GMW) protocol. In this paper, we propose MISC, a multi-input secure computation protocol, by combining GC and GMW in a novel way. MISC can evaluate multi-input AND gates, which can reduce the round complexity. Moreover, MISC reduces the communication overhead by 1.7x and 2.4x for 2-input and by 2x and 2.8x for 4-input AND gates compared to the state-of-the-art GMW-style and GC-style protocols, respectively. In order to use the MISC efficiently in different applications, we redesign common building block with multi-input AND gates such as Equality checking, Maxpool, Comparison, and Argmax/Argmin. Results on privacy-preserving applications, e.g., circuit-based private set intersection (PSI) and private machine learning (CNN inference) show that compared to GMW, MISC improves the total communication overhead by 3x and the total run time by 1.5x.
Keywords
[1]Moni Naor, Benny Pinkas, and Reuban Sumner. Privacy preserving auctions and mechanism design. In ACM Conference on Electronic Commerce, 1999.
[2] Oleksandr Tkachenko, Christian Weinert, Thomas Schneider, and Kay Hamacher. Large-scale privacy-preserving statistical computations for distributed genome-wide associati, organization=ACM on studies. In ASIACCS. ACM, 2018.
[3] Wilko Henecka, Stefan K¨ogl, Ahmad Reza Sadeghi, Thomas Schneider, and Immo Wehrenberg. TASTY: Tool for automating secure two-party computations. In CCS. ACM, 2010.
[4] Farhad Taheri, Siavash Bayat-Sarmadi, and Shahriar Ebrahimi. Efficient hardware implementations of legendre symbol suitable for mpcapplications. IEEE Transactions on Circuits and Systems I: Regular Papers, 2021.
[5] Payman Mohassel and Yupeng Zhang. SecureML: A system for scalable privacy-preserving machine learning. In IEEE S&P, 2017.
[6] Payman Mohassel and Peter Rindal. ABY 3 : A mixed protocol framework for machine learning. In CCS. ACM, 2018.
[7] Fabian Boemer, Rosario Cammarota, Daniel Demmler, Thomas Schneider, and Hossein Yalame. MP2ML: A mixed-protocol machine learning framework for private inference. In ARES. ACM, 2020.
[8] Andrew Chi Chih Yao. How to generate and exchange secrets. In FOCS, 1986.
[9] Oded Goldreich, Silvio Micali, and Avi Wigderson. How to play any mental game. In STOC, 1987.
[10] Vladimir Kolesnikov and Thomas Schneider. Improved garbled circuit: Free XOR gates and applications. In ICALP. Springer, 2008.
[11] Samee Zahur, Mike Rosulek, and David Evans. Two halves make a whole: Reducing data transfer in garbled circuits using half gates. In EUROCRYPT. Springer, 2015.
[12] Mike Rosulek and Lawrence Roy. Three halves make a whole? beating the half-gates lower bound for garbled circuits. In CRYPTO, 2021.
[13] Mihir Bellare, Viet Tung Hoang, Sriram Keelveedhi, and Phillip Rogaway. Efficient garbling from a fixed-key blockcipher. In IEEE S&P, 2013.
[14] Benny Pinkas, Thomas Schneider, Gil Segev, and Michael Zohner. Phasing: Private set intersection using permutation-based hashing. In USENIX Security, 2015.
[15] Satsuya Ohata and Koji Nuida. Towards high-throughput secure MPC over the Internet: Communication-efficient two-party protocols and its application. In FC, 2020.
[16] Ghada Dessouky, Farinaz Koushanfar, Ahmad Reza Sadeghi, Thomas Schneider, Shaza Zeitouni, and Michael Zohner. Pushing the communication barrier in secure computation using lookup tables. In NDSS, 2017.
[17] Arpita Patra, Thomas Schneider, Ajith Suresh, and Hossein Yalame. ABY2.0: Improved mixed-protocol secure two-party computation. In USENIX Security, 2021.
[18] D. Beaver. Efficient multiparty protocols using circuit randomization. In CRYPTO, 1991.
[19] Daniel Demmler, Thomas Schneider, and Michael Zohner. ABY-a framework for efficient mixed-protocol secure two-party computation. In NDSS, 2015.
[20] M Sadegh Riazi, Christian Weinert, Oleksandr Tkachenko, Ebrahim M Songhori, Thomas Schneider, and Farinaz Koushanfar. Chameleon: A hybrid secure computation framework for machine learning applications. In Asia conference on computer and communications security, pages 707–721, 2018.
[21] Hossein Yalame, Hossein Farzam, and Siavash Bayat-Sarmadi. Secure two-party computation using an efficient garbled circuit by reducing data transfer. In Applications and Techniques in Information Security. Springer, 2017.
[22] Oded Goldreich. Foundations of cryptography: volume 2, basic applications. Cambridge University Press, 2009.
[23] Thomas Schneider and Michael Zohner. GMW vs. Yao? Efficient secure two-party computation with low depth circuits. In FC, 2013.
[24] D. Beaver, S. Micali, and P. Rogaway. The round complexity of secure protocols. In TC, 1990.
[25] Ivan Damg˚ard, Valerio Pastro, Nigel Smart, and Sarah Zakarias. Multiparty computation from somewhat homomorphic encryptio. In CRYPTO, 2012.
[26] Moni Naor and Benny Pinkas. Computationally secure oblivious transfer. Journal of Cryptology, 2005.
[27] Russell Impagliazzo and Steven Rudich. Limits on the provable consequences of one-way permutations. In STOC, 1989.
[28] G. Asharov, Y. Lindell, T. Schneider, and M. Zohner. More efficient oblivious transfer and extensions for faster secure computation. In CCS.ACM, 2013.
[29] D. Beaver. Precomputing oblivious transfer. In CRYPTO, 1995.
[30] Donald Beaver. Efficient multiparty protocols using circuit randomization. In CRYPTO, 1991.
[31] A. C. Yao. Protocols for secure computations. In FOCS, 1982.
[32] Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai, Lisa Kohl, Peter Rindal, and Peter Scholl. Efficient two-round OT extension and silent non-interactive secure computation. In CCS. ACM, 2019.
[33] Kang Yang, Chenkai Weng, Xiao Lan, Jiang Zhang, and Xiao Wang. Ferret: Fast extension for correlated OT with small communication. In CCS. ACM, 2020.
[34] Vladimir Kolesnikov, Ahmad Reza Sadeghi, and Thomas Schneider. Improved garbled circuit building blocks and applications to auctions and computing minima. In CANS, 2009.
[35] Niklas Buescher, Andreas Holzer, Alina Weber, and Stefan Katzenbeisser. Compiling low depth circuits for practical secure computation. In ESORICS, 2016.
[36] Juan Garay, Berry Schoenmakers, and Jos´e Villegas. Practical and secure solutions for integer comparison. In International Workshop on Public Key Cryptography, pages 330–342. Springer, 2007.
[37] Pratyush Mishra, Ryan Lehmkuhl, Akshayaram Srinivasan, Wenting Zheng, and Raluca Ada Popa. Delphi: A cryptographic inference service for neural networks. In USENIX Security, 2020.
[38] Nishant Kumar, Mayank Rathee, Nishanth Chandran, Divya Gupta, Aseem Rastogi, and Rahul Sharma. Cryptflow: Secure tensorflow inference. In IEEE S&P, 2020.
[39] Daniel Kales, Christian Rechberger, Thomas Schneider, Matthias Senker, and Christian Weinert. Mobile private contact discovery at scale. In USENIX Security, 2019.
[40] Benny Pinkas, Thomas Schneider, and Michael Zohner. Scalable private set intersection based on OT extension. ACM TOPS, 2018.
[41] Benny Pinkas, Thomas Schneider, Christian Weinert, and Udi Wieder. Efficient circuit-based PSI via cuckoo hashing. In EUROCRYPT. Springer, 2018.
[42] Benny Pinkas, Thomas Schneider, Oleksandr Tkachenko, and Avishay Yanai. Efficient circuit-based PSI with linear communication. In EUROCRYPT. Springer, 2019.
[43] OTextention. https://github.com/encryptogroup/ \uppercase {OT}extention. Accessed: October. 2020.
[44] Yan Huang, David Evans, and Jonathan Katz. Private set intersection: Are garbled circuits better than custom protocols? In NDSS, 2012.
[45] Brett Hemenway Falk, Daniel Noble, and Rafail Ostrovsky. Private set intersection with linear communication from general assumptions. In WPES, 2019.
[46] Jian Liu, Mika Juuti, Yao Lu, and Nadarajah Asokan. Oblivious neural network predictions via minionn transformations. In CCS. ACM, 2017.
[47] Qiao Zhang, Chunsheng Xin, and Hongyi Wu.Gala: Greedy computation for linear algebra in privacy-preserved neural networks. NDSS, 2021.
[2] Oleksandr Tkachenko, Christian Weinert, Thomas Schneider, and Kay Hamacher. Large-scale privacy-preserving statistical computations for distributed genome-wide associati, organization=ACM on studies. In ASIACCS. ACM, 2018.
[3] Wilko Henecka, Stefan K¨ogl, Ahmad Reza Sadeghi, Thomas Schneider, and Immo Wehrenberg. TASTY: Tool for automating secure two-party computations. In CCS. ACM, 2010.
[4] Farhad Taheri, Siavash Bayat-Sarmadi, and Shahriar Ebrahimi. Efficient hardware implementations of legendre symbol suitable for mpcapplications. IEEE Transactions on Circuits and Systems I: Regular Papers, 2021.
[5] Payman Mohassel and Yupeng Zhang. SecureML: A system for scalable privacy-preserving machine learning. In IEEE S&P, 2017.
[6] Payman Mohassel and Peter Rindal. ABY 3 : A mixed protocol framework for machine learning. In CCS. ACM, 2018.
[7] Fabian Boemer, Rosario Cammarota, Daniel Demmler, Thomas Schneider, and Hossein Yalame. MP2ML: A mixed-protocol machine learning framework for private inference. In ARES. ACM, 2020.
[8] Andrew Chi Chih Yao. How to generate and exchange secrets. In FOCS, 1986.
[9] Oded Goldreich, Silvio Micali, and Avi Wigderson. How to play any mental game. In STOC, 1987.
[10] Vladimir Kolesnikov and Thomas Schneider. Improved garbled circuit: Free XOR gates and applications. In ICALP. Springer, 2008.
[11] Samee Zahur, Mike Rosulek, and David Evans. Two halves make a whole: Reducing data transfer in garbled circuits using half gates. In EUROCRYPT. Springer, 2015.
[12] Mike Rosulek and Lawrence Roy. Three halves make a whole? beating the half-gates lower bound for garbled circuits. In CRYPTO, 2021.
[13] Mihir Bellare, Viet Tung Hoang, Sriram Keelveedhi, and Phillip Rogaway. Efficient garbling from a fixed-key blockcipher. In IEEE S&P, 2013.
[14] Benny Pinkas, Thomas Schneider, Gil Segev, and Michael Zohner. Phasing: Private set intersection using permutation-based hashing. In USENIX Security, 2015.
[15] Satsuya Ohata and Koji Nuida. Towards high-throughput secure MPC over the Internet: Communication-efficient two-party protocols and its application. In FC, 2020.
[16] Ghada Dessouky, Farinaz Koushanfar, Ahmad Reza Sadeghi, Thomas Schneider, Shaza Zeitouni, and Michael Zohner. Pushing the communication barrier in secure computation using lookup tables. In NDSS, 2017.
[17] Arpita Patra, Thomas Schneider, Ajith Suresh, and Hossein Yalame. ABY2.0: Improved mixed-protocol secure two-party computation. In USENIX Security, 2021.
[18] D. Beaver. Efficient multiparty protocols using circuit randomization. In CRYPTO, 1991.
[19] Daniel Demmler, Thomas Schneider, and Michael Zohner. ABY-a framework for efficient mixed-protocol secure two-party computation. In NDSS, 2015.
[20] M Sadegh Riazi, Christian Weinert, Oleksandr Tkachenko, Ebrahim M Songhori, Thomas Schneider, and Farinaz Koushanfar. Chameleon: A hybrid secure computation framework for machine learning applications. In Asia conference on computer and communications security, pages 707–721, 2018.
[21] Hossein Yalame, Hossein Farzam, and Siavash Bayat-Sarmadi. Secure two-party computation using an efficient garbled circuit by reducing data transfer. In Applications and Techniques in Information Security. Springer, 2017.
[22] Oded Goldreich. Foundations of cryptography: volume 2, basic applications. Cambridge University Press, 2009.
[23] Thomas Schneider and Michael Zohner. GMW vs. Yao? Efficient secure two-party computation with low depth circuits. In FC, 2013.
[24] D. Beaver, S. Micali, and P. Rogaway. The round complexity of secure protocols. In TC, 1990.
[25] Ivan Damg˚ard, Valerio Pastro, Nigel Smart, and Sarah Zakarias. Multiparty computation from somewhat homomorphic encryptio. In CRYPTO, 2012.
[26] Moni Naor and Benny Pinkas. Computationally secure oblivious transfer. Journal of Cryptology, 2005.
[27] Russell Impagliazzo and Steven Rudich. Limits on the provable consequences of one-way permutations. In STOC, 1989.
[28] G. Asharov, Y. Lindell, T. Schneider, and M. Zohner. More efficient oblivious transfer and extensions for faster secure computation. In CCS.ACM, 2013.
[29] D. Beaver. Precomputing oblivious transfer. In CRYPTO, 1995.
[30] Donald Beaver. Efficient multiparty protocols using circuit randomization. In CRYPTO, 1991.
[31] A. C. Yao. Protocols for secure computations. In FOCS, 1982.
[32] Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai, Lisa Kohl, Peter Rindal, and Peter Scholl. Efficient two-round OT extension and silent non-interactive secure computation. In CCS. ACM, 2019.
[33] Kang Yang, Chenkai Weng, Xiao Lan, Jiang Zhang, and Xiao Wang. Ferret: Fast extension for correlated OT with small communication. In CCS. ACM, 2020.
[34] Vladimir Kolesnikov, Ahmad Reza Sadeghi, and Thomas Schneider. Improved garbled circuit building blocks and applications to auctions and computing minima. In CANS, 2009.
[35] Niklas Buescher, Andreas Holzer, Alina Weber, and Stefan Katzenbeisser. Compiling low depth circuits for practical secure computation. In ESORICS, 2016.
[36] Juan Garay, Berry Schoenmakers, and Jos´e Villegas. Practical and secure solutions for integer comparison. In International Workshop on Public Key Cryptography, pages 330–342. Springer, 2007.
[37] Pratyush Mishra, Ryan Lehmkuhl, Akshayaram Srinivasan, Wenting Zheng, and Raluca Ada Popa. Delphi: A cryptographic inference service for neural networks. In USENIX Security, 2020.
[38] Nishant Kumar, Mayank Rathee, Nishanth Chandran, Divya Gupta, Aseem Rastogi, and Rahul Sharma. Cryptflow: Secure tensorflow inference. In IEEE S&P, 2020.
[39] Daniel Kales, Christian Rechberger, Thomas Schneider, Matthias Senker, and Christian Weinert. Mobile private contact discovery at scale. In USENIX Security, 2019.
[40] Benny Pinkas, Thomas Schneider, and Michael Zohner. Scalable private set intersection based on OT extension. ACM TOPS, 2018.
[41] Benny Pinkas, Thomas Schneider, Christian Weinert, and Udi Wieder. Efficient circuit-based PSI via cuckoo hashing. In EUROCRYPT. Springer, 2018.
[42] Benny Pinkas, Thomas Schneider, Oleksandr Tkachenko, and Avishay Yanai. Efficient circuit-based PSI with linear communication. In EUROCRYPT. Springer, 2019.
[43] OTextention. https://github.com/encryptogroup/ \uppercase {OT}extention. Accessed: October. 2020.
[44] Yan Huang, David Evans, and Jonathan Katz. Private set intersection: Are garbled circuits better than custom protocols? In NDSS, 2012.
[45] Brett Hemenway Falk, Daniel Noble, and Rafail Ostrovsky. Private set intersection with linear communication from general assumptions. In WPES, 2019.
[46] Jian Liu, Mika Juuti, Yao Lu, and Nadarajah Asokan. Oblivious neural network predictions via minionn transformations. In CCS. ACM, 2017.
[47] Qiao Zhang, Chunsheng Xin, and Hongyi Wu.Gala: Greedy computation for linear algebra in privacy-preserved neural networks. NDSS, 2021.
)