Secure Multi-Party Computation

ABSTRACT

Secure multi-party computation (SMC) is an emerging topic which has been drawing growing attention during recent decades. There are many examples which show importance of SMC constructions in practice, such as privacy-preserving decision making and machine learning, auctions, private set intersection, and others. In this tutorial, we provide a comprehensive coverage of SMC techniques, starting from precise definitions and fundamental techniques. Consequently, a significant portion of the tutorial focuses on recent advances in general SMC constructions. We cover garbled circuit evaluation (GCE) and linear secret sharing (LSS) which are commonly used for secure two-party and multi-party computation, respectively. The coverage includes both standard adversarial models: semi-honest and malicious. For GCE, we start with the original Yao's garbled circuits construction [30] for semi-honest adversaries and consequently cover its recent optimizations such as the "free XOR,'' the garbled row reduction, the half-gates optimization, and the use of AES NI techniques. We follow with a discussion of techniques for making GCE resilient to malicious behavior, which includes the cut-and-choose approach and additional techniques to deter known attacks in the presence of malicious participants. In addition, we include the-state-of-the-art protocols for oblivious transfer (OT) and OT extension in the presence of semi-honest and malicious users. For LSS, we start from standard solutions for the semi-honest adversarial model including [5, 28] and consequently move to recent efficient constructions for semi-honest and malicious adversarial models. The coverage includes different types of corruption thresholds (with and without honest majority), which imply different guarantees with respect to abort.

References

1. G. Asharov, Y. Lindell, and T. Rabin. 2011. Perfectly-Secure Multiplication for Any $t < n/3$. In CRYPTO. 240--258.
2. G. Asharov, Y. Lindell, T. Schneider, and M. Zohner. 2013. More Efficient Oblivious Transfer and Extensions for Faster Secure Computation ACM Conference on Computer and Communications Security (CCS). 535--548.
3. G. Asharov, Y. Lindell, T. Schneider, and M. Zohner. 2015. More Efficient Oblivious Transfer Extensions with Security for Malicious Adversaries. In EUROCRYPT. 673--701.
4. M. Bellare, V. Hoang, S. Keelveedhi, and P. Rogaway. 2013. Efficient Garbling from a Fixed-Key Blockcipher. In IEEE Symposium on Security and Privacy (S&P). 478--492.
5. G. R. Blakley. 1979. Safeguarding Cryptographic Keys. In National Computer Conference, Vol. Vol. 48. 313--317.
6. D. Bogdanov, S. Laur, and J. Willemson. 2008. Sharemind: A Framework for Fast Privacy-Preserving Computations European Symposium on Research in Computer Security (ESORICS). 192--206.
7. I. Damgård, M. Geisler, M. Krøigaard, and J. B. Nielsen. 2009. Asynchronous Multiparty Computation: Theory and Implementation International Workshop on Public Key Cryptography (PKC). 160--179.
8. I. Damgård, Y. Ishai, and M. Krøigaard. 2010. Perfectly Secure Multiparty Computation and the Computational Overhead of Cryptography. In EUROCRYPT. 445--465.
9. I. Damgård, M. Keller, E. Larraia, V. Pastro, P. Scholl, and N. P. Smart. 2013. Practical Covertly Secure MPC for Dishonest Majority--Or: Breaking the SPDZ Limits. In European Symposium on Research in Computer Security (ESORICS). 1--18.
10. I. Damgård and J. B. Nielsen. 2007. Scalable and Unconditionally Secure Multiparty Computation CRYPTO. 572--590.
11. I. Damgård, V. Pastro, N. Smart, and S. Zakarias. 2012. Multiparty Computation from Somewhat Homomorphic Encryption CRYPTO. 643--662.
12. R. Gennaro, M. Rabin, and T. Rabin. 1998. Simplified VSS and Fast-Track Multiparty Computations with Applications to Threshold Cryptography. In ACM Symposium on Principles of Distributed Computing (PODC). 101--111.
13. O. Goldreich, S. Micali, and A. Wigderson. 1991. Proofs that Yield Nothing but their Validity or All Languages in NP Have Zero-Knowledge Proof Systems. J. ACM Vol. 38, 3 (1991), 690--728.
14. S. Goldwasser, S. Micali, and A. Wigderson. 1987. How to Play Any Mental Game, or a Completeness Theorem for Protocols with an Honest Majority. In ACM Symposium on the Theory of Computing (STOC). 218--229.
15. A. Holzer, M. Franz, S. Katzenbeisser, and H. Veith. 2012. Secure Two-Party Computations in ANSI C. In AMC Conference on Computer and Communications Security (CCS). 772--783.
16. Y. Ishai, J. Kilian, K. Nissim, and E. Petrank. 2003. Extending Oblivious Transfers Efficiently. In CRYPTO. 145--161.
17. M. Keller, V. Pastro, and D. Rotaru. 2018. Overdrive: Making SPDZ Great Again. In EUROCRYPT. 158--189.
18. M. Kiraz. 2008. Secure and Fair Two-Party Computation. Ph.D. Dissertation. Technische Universiteit Eindhoven.
19. M. Kiraz and B. Schoenmakers. 2006. A Protocol Issue for the Malicious Case of Yao's Garbled Circuit Construction Symposium on Information Theory in the Benelux. 283--290.
20. V. Kolesnikov and T. Schneider. 2008. Improved Garbled Circuit: Free XOR Gates and Applications International Colloquium on Automata, Languages, and Programming (ICALP). 486--498.
21. B. Kreuter, A. Shelat, and C. H. Shen. 2012. Billion-Gate Secure Computation with Malicious Adversaries USENIX Security Symposium. 285--300.
22. Y. Lindell. 2013. Fast Cut-and-Choose Based Protocols for Malicious and Covert Adversaries CRYPTO. 1--17.
23. Y. Lindell and B. Pinkas. 2007. An Efficient Protocol for Secure Two-Party Computation in the Presence of Malicious Adversaries. In EUROCRYPT. 52--78.
24. C. Liu, X. S. Wang, K. Nayak, Y. Huang, and E. Shi. 2015. ObliVM: A Programming Framework for Secure Computation IEEE Symposium on Security and Privacy (S&P). 359--376.
25. P. Mohassel and M. Franklin. 2006. Efficiency Tradeoffs for Malicious Two-Party Computation International Workshop on Public Key Cryptography (PKC). 458--473.
26. M. Naor and B. Pinkas. 2001. Efficient Oblivious Transfer Protocols. In ACM-SIAM Symposium on Discrete Algorithms (SODA). 448--457.
27. B. Pinkas, T. Schneider, N. P. Smart, and S. C. Williams. 2009. Secure Two-Party Computation is Practical. In ASIACRYPT. 250--267.
28. A. Shamir. 1979. How to Share a Secret. Commun. ACM Vol. 22, 11 (1979), 612--613.
29. A. Shelat and C. Shen. 2011. Two-Output Secure Computation with Malicious Adversaries EUROCRYPT. 386--405.
30. A. C. Yao. 1986. How to Generate and Exchange Secrets. In IEEE Symposium on Foundations of Computer Science (FOCS). 162--167.
31. S. Zahur and D. Evans. 2015. Obliv-C: A Language for Extensible Data-Oblivious Computation. IACR Cryptology ePrint Archive Report 2015/1153.
32. S. Zahur, M. Rosulek, and D. Evans. 2015. Two Halves Make a Whole: Reducing Data Transfer in Garbled Circuits Using Half Gates EUROCRYPT. 220--250.
33. Y. Zhang, M. Blanton, and F. Bayatbabolghani. 2017. Enforcing Input Correctness via Certification in Garbled Circuit Evaluation European Symposium on Research in Computer Security (ESORICS). 552--569.
34. Y. Zhang, A. Steele, and M. Blanton. 2013. PICCO: A General-Purpose Compiler for Private Distributed Computation ACM Conference on Computer and Communications Security (CCS). 813--826.

Index Terms

• Security and privacy

  • Cryptography

    • Symmetric cryptography and hash functions

  • Security services

    • Privacy-preserving protocols