Document Open Access Logo

Efficient MPC with a Mixed Adversary

Authors Martin Hirt, Marta Mularczyk

PDF
Thumbnail PDF

File

LIPIcs.ITC.2020.3.pdf
  • Filesize: 0.58 MB
  • 23 pages

Document Identifiers

Author Details

Martin Hirt
  • ETH Zurich, Switzerland
Marta Mularczyk
  • ETH Zurich, Switzerland

Funding

  • Mularczyk, Marta: Research supported by the Zurich Information Security and Privacy Center (ZISC).

Cite AsGet BibTex

Martin Hirt and Marta Mularczyk. Efficient MPC with a Mixed Adversary. In 1st Conference on Information-Theoretic Cryptography (ITC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 163, pp. 3:1-3:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ITC.2020.3

Abstract

Over the past 20 years, the efficiency of secure multi-party protocols has been greatly improved. While the seminal protocols from the late 80’s require a communication of Ω(n⁶) field elements per multiplication among n parties, recent protocols offer linear communication complexity. This means that each party needs to communicate a constant number of field elements per multiplication, independent of n. However, these efficient protocols only offer active security, which implies that at most t<n/3 (perfect security), respectively t<n/2 (statistical or computational security) parties may be corrupted. Higher corruption thresholds (i.e., t≥ n/2) can only be achieved with degraded security (unfair abort), where one single corrupted party can prevent honest parties from learning their outputs. The aforementioned upper bounds (t<n/3 and t<n/2) have been circumvented by considering mixed adversaries (Fitzi et al., Crypto' 98), i.e., adversaries that corrupt, at the same time, some parties actively, some parties passively, and some parties in the fail-stop manner. It is possible, for example, to achieve perfect security even if 2/3 of the parties are faulty (three quarters of which may abort in the middle of the protocol, and a quarter may even arbitrarily misbehave). This setting is much better suited to many applications, where the crash of a party is more likely than a coordinated active attack. Surprisingly, since the presentation of the feasibility result for the mixed setting, no progress has been made in terms of efficiency: the state-of-the-art protocol still requires a communication of Ω(n⁶) field elements per multiplication. In this paper, we present a perfectly-secure MPC protocol for the mixed setting with essentially the same efficiency as the best MPC protocols for the active-only setting. For the first time, this allows to tolerate faulty majorities, while still providing optimal efficiency. As a special case, this also results in the first fully-secure MPC protocol secure against any number of crashing parties, with optimal (i.e., linear in n) communication. We provide simulation-based proofs of our construction.

Subject Classification

ACM Subject Classification
  • Security and privacy → Network security
Keywords
  • Multi-party Computation
  • Communication Cost

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Gilad Asharov and Yehuda Lindell. A full proof of the BGW protocol for perfectly secure multiparty computation. Journal of Cryptology, 30(1):58-151, January 2017. URL: https://doi.org/10.1007/s00145-015-9214-4.
  2. B. V. Ashwinkumar, Arpita Patra, Ashish Choudhary, Kannan Srinathan, and C. Pandu Rangan. On tradeoff between network connectivity, phase complexity and communication complexity of reliable communication tolerating mixed adversary. In Rida A. Bazzi and Boaz Patt-Shamir, editors, 27th ACM PODC, pages 115-124. ACM, August 2008. URL: https://doi.org/10.1145/1400751.1400768.
  3. Saikrishna Badrinarayanan, Aayush Jain, Nathan Manohar, and Amit Sahai. Secure MPC: Laziness leads to GOD. Cryptology ePrint Archive, Report 2018/580, 2018. URL: https://eprint.iacr.org/2018/580.
  4. Assi Barak, Martin Hirt, Lior Koskas, and Yehuda Lindell. An end-to-end system for large scale P2P MPC-as-a-service and low-bandwidth MPC for weak participants. In David Lie, Mohammad Mannan, Michael Backes, and XiaoFeng Wang, editors, ACM CCS 2018, pages 695-712. ACM Press, October 2018. URL: https://doi.org/10.1145/3243734.3243801.
  5. Donald Beaver. Multiparty protocols tolerating half faulty processors. In Gilles Brassard, editor, CRYPTO'89, volume 435 of LNCS, pages 560-572. Springer, Heidelberg, August 1990. URL: https://doi.org/10.1007/0-387-34805-0_49.
  6. Donald Beaver. Efficient multiparty protocols using circuit randomization. In Joan Feigenbaum, editor, CRYPTO'91, volume 576 of LNCS, pages 420-432. Springer, Heidelberg, August 1992. URL: https://doi.org/10.1007/3-540-46766-1_34.
  7. Zuzana Beerliová-Trubíniová, Matthias Fitzi, Martin Hirt, Ueli M. Maurer, and Vassilis Zikas. MPC vs. SFE: Perfect security in a unified corruption model. In Ran Canetti, editor, TCC 2008, volume 4948 of LNCS, pages 231-250. Springer, Heidelberg, March 2008. URL: https://doi.org/10.1007/978-3-540-78524-8_14.
  8. Zuzana Beerliová-Trubíniová and Martin Hirt. Perfectly-secure MPC with linear communication complexity. In Ran Canetti, editor, TCC 2008, volume 4948 of LNCS, pages 213-230. Springer, Heidelberg, March 2008. URL: https://doi.org/10.1007/978-3-540-78524-8_13.
  9. Michael Ben-Or, Shafi Goldwasser, and Avi Wigderson. Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended abstract). In 20th ACM STOC, pages 1-10. ACM Press, May 1988. URL: https://doi.org/10.1145/62212.62213.
  10. Eli Ben-Sasson, Serge Fehr, and Rafail Ostrovsky. Near-linear unconditionally-secure multiparty computation with a dishonest minority. In Reihaneh Safavi-Naini and Ran Canetti, editors, CRYPTO 2012, volume 7417 of LNCS, pages 663-680. Springer, Heidelberg, August 2012. URL: https://doi.org/10.1007/978-3-642-32009-5_39.
  11. Piotr Berman, Juan A Garay, and Kenneth J Perry. Bit optimal distributed consensus. In Computer science, pages 313-321. Springer, 1992. Google Scholar
  12. Ran Canetti. Security and composition of multiparty cryptographic protocols. Journal of Cryptology, 13(1):143-202, January 2000. URL: https://doi.org/10.1007/s001459910006.
  13. Ran Canetti. Universally composable security: A new paradigm for cryptographic protocols. In 42nd FOCS, pages 136-145. IEEE Computer Society Press, October 2001. URL: https://doi.org/10.1109/SFCS.2001.959888.
  14. David Chaum. The spymasters double-agent problem: Multiparty computations secure unconditionally from minorities and cryptographically from majorities. In Gilles Brassard, editor, CRYPTO'89, volume 435 of LNCS, pages 591-602. Springer, Heidelberg, August 1990. URL: https://doi.org/10.1007/0-387-34805-0_52.
  15. David Chaum, Claude Crépeau, and Ivan Damgard. Multiparty unconditionally secure protocols (extended abstract). In 20th ACM STOC, pages 11-19. ACM Press, May 1988. URL: https://doi.org/10.1145/62212.62214.
  16. Ashish Choudhary, Arpita Patra, B. V. Ashwinkumar, K. Srinathan, and C. Pandu Rangan. Perfectly reliable and secure communication tolerating static and mobile mixed adversary. In Reihaneh Safavi-Naini, editor, ICITS 08, volume 5155 of LNCS, pages 137-155. Springer, Heidelberg, August 2008. URL: https://doi.org/10.1007/978-3-540-85093-9_15.
  17. Ran Cohen and Yehuda Lindell. Fairness versus guaranteed output delivery in secure multiparty computation. In Palash Sarkar and Tetsu Iwata, editors, ASIACRYPT 2014, Part II, volume 8874 of LNCS, pages 466-485. Springer, Heidelberg, December 2014. URL: https://doi.org/10.1007/978-3-662-45608-8_25.
  18. Ronald Cramer, Ivan Bjerre Damgård, and Jesper Buus Nielsen. Secure Multiparty Computation and Secret Sharing. Cambridge University Press, 2015. URL: https://doi.org/10.1017/CBO9781107337756.
  19. Ivan Damgård and Yuval Ishai. Scalable secure multiparty computation. In Cynthia Dwork, editor, CRYPTO 2006, volume 4117 of LNCS, pages 501-520. Springer, Heidelberg, August 2006. URL: https://doi.org/10.1007/11818175_30.
  20. Ivan Damgård, Yuval Ishai, and Mikkel Krøigaard. Perfectly secure multiparty computation and the computational overhead of cryptography. In Henri Gilbert, editor, EUROCRYPT 2010, volume 6110 of LNCS, pages 445-465. Springer, Heidelberg, May / June 2010. URL: https://doi.org/10.1007/978-3-642-13190-5_23.
  21. Ivan Damgard, Marcel Keller, Enrique Larraia, Valerio Pastro, Peter Scholl, and Nigel P. Smart. Practical covertly secure MPC for dishonest majority - or: Breaking the SPDZ limits. In Jason Crampton, Sushil Jajodia, and Keith Mayes, editors, ESORICS 2013, volume 8134 of LNCS, pages 1-18. Springer, Heidelberg, September 2013. URL: https://doi.org/10.1007/978-3-642-40203-6_1.
  22. Ivan Damgård and Jesper Buus Nielsen. Scalable and unconditionally secure multiparty computation. In Alfred Menezes, editor, CRYPTO 2007, volume 4622 of LNCS, pages 572-590. Springer, Heidelberg, August 2007. URL: https://doi.org/10.1007/978-3-540-74143-5_32.
  23. Ivan Damgard, Jesper Buus Nielsen, Antigoni Polychroniadou, and Michael Raskin. On the communication required for unconditionally secure multiplication. In Matthew Robshaw and Jonathan Katz, editors, CRYPTO 2016, Part II, volume 9815 of LNCS, pages 459-488. Springer, Heidelberg, August 2016. URL: https://doi.org/10.1007/978-3-662-53008-5_16.
  24. Ivan Damgård, Valerio Pastro, Nigel P. Smart, and Sarah Zakarias. Multiparty computation from somewhat homomorphic encryption. In Reihaneh Safavi-Naini and Ran Canetti, editors, CRYPTO 2012, volume 7417 of LNCS, pages 643-662. Springer, Heidelberg, August 2012. URL: https://doi.org/10.1007/978-3-642-32009-5_38.
  25. Danny Dolev, Cynthia Dwork, Orli Waarts, and Moti Yung. Perfectly secure message transmission. Journal of the ACM, 40(1):17-47, January 1993. Google Scholar
  26. Matthias Fitzi, Martin Hirt, and Ueli M. Maurer. Trading correctness for privacy in unconditional multi-party computation (extended abstract). In Hugo Krawczyk, editor, CRYPTO'98, volume 1462 of LNCS, pages 121-136. Springer, Heidelberg, August 1998. URL: https://doi.org/10.1007/BFb0055724.
  27. Juan A. Garay and Kenneth J. Perry. A continuum of failure models for distributed computing. In Adrian Segall and Shmuel Zaks, editors, Distributed Algorithms: 6th International Workshop, WDAG '92 Haifa, Israel, pages 153-165, Berlin, Heidelberg, 1992. Springer Berlin Heidelberg. Google Scholar
  28. Daniel Genkin, Yuval Ishai, and Antigoni Polychroniadou. Efficient multi-party computation: From passive to active security via secure SIMD circuits. In Rosario Gennaro and Matthew J. B. Robshaw, editors, CRYPTO 2015, Part II, volume 9216 of LNCS, pages 721-741. Springer, Heidelberg, August 2015. URL: https://doi.org/10.1007/978-3-662-48000-7_35.
  29. Daniel Genkin, Yuval Ishai, Manoj Prabhakaran, Amit Sahai, and Eran Tromer. Circuits resilient to additive attacks with applications to secure computation. In David B. Shmoys, editor, 46th ACM STOC, pages 495-504. ACM Press, May / June 2014. URL: https://doi.org/10.1145/2591796.2591861.
  30. Hossein Ghodosi and Josef Pieprzyk. Multi-party computation with omnipresent adversary. In Stanislaw Jarecki and Gene Tsudik, editors, PKC 2009, volume 5443 of LNCS, pages 180-195. Springer, Heidelberg, March 2009. URL: https://doi.org/10.1007/978-3-642-00468-1_11.
  31. Oded Goldreich. Foundations of Cryptography: Basic Applications, volume 2. Cambridge University Press, Cambridge, UK, 2004. Google Scholar
  32. Oded Goldreich, Silvio Micali, and Avi Wigderson. How to play any mental game or A completeness theorem for protocols with honest majority. In Alfred Aho, editor, 19th ACM STOC, pages 218-229. ACM Press, May 1987. URL: https://doi.org/10.1145/28395.28420.
  33. Vipul Goyal, Yanyi Liu, and Yifan Song. Communication-efficient unconditional MPC with guaranteed output delivery. In Alexandra Boldyreva and Daniele Micciancio, editors, CRYPTO 2019, Part II, volume 11693 of LNCS, pages 85-114. Springer, Heidelberg, August 2019. URL: https://doi.org/10.1007/978-3-030-26951-7_4.
  34. Martin Hirt, Christoph Lucas, Ueli Maurer, and Dominik Raub. Graceful degradation in multi-party computation (extended abstract). In Serge Fehr, editor, ICITS 11, volume 6673 of LNCS, pages 163-180. Springer, Heidelberg, May 2011. URL: https://doi.org/10.1007/978-3-642-20728-0_15.
  35. Martin Hirt, Ueli M. Maurer, and Bartosz Przydatek. Efficient secure multi-party computation. In Tatsuaki Okamoto, editor, ASIACRYPT 2000, volume 1976 of LNCS, pages 143-161. Springer, Heidelberg, December 2000. URL: https://doi.org/10.1007/3-540-44448-3_12.
  36. Martin Hirt, Ueli M. Maurer, and Vassilis Zikas. MPC vs. SFE: Unconditional and computational security. In Josef Pieprzyk, editor, ASIACRYPT 2008, volume 5350 of LNCS, pages 1-18. Springer, Heidelberg, December 2008. URL: https://doi.org/10.1007/978-3-540-89255-7_1.
  37. Martin Hirt and Marta Mularczyk. Efficient MPC with a Mixed Adversary. Cryptology ePrint Archive, Report 2020/356, 2020. (full version of this paper). URL: https://eprint.iacr.org/2020/356.
  38. Martin Hirt and Jesper Buus Nielsen. Robust multiparty computation with linear communication complexity. In Cynthia Dwork, editor, CRYPTO 2006, volume 4117 of LNCS, pages 463-482. Springer, Heidelberg, August 2006. URL: https://doi.org/10.1007/11818175_28.
  39. Yuval Ishai, Eyal Kushilevitz, Yehuda Lindell, and Erez Petrank. On combining privacy with guaranteed output delivery in secure multiparty computation. In Cynthia Dwork, editor, CRYPTO 2006, volume 4117 of LNCS, pages 483-500. Springer, Heidelberg, August 2006. URL: https://doi.org/10.1007/11818175_29.
  40. Jonathan Katz. On achieving the "best of both worlds" in secure multiparty computation. In David S. Johnson and Uriel Feige, editors, 39th ACM STOC, pages 11-20. ACM Press, June 2007. URL: https://doi.org/10.1145/1250790.1250793.
  41. Jonathan Katz, Ueli Maurer, Björn Tackmann, and Vassilis Zikas. Universally composable synchronous computation. In Amit Sahai, editor, TCC 2013, volume 7785 of LNCS, pages 477-498. Springer, Heidelberg, March 2013. URL: https://doi.org/10.1007/978-3-642-36594-2_27.
  42. Marcel Keller, Emmanuela Orsini, and Peter Scholl. MASCOT: Faster malicious arithmetic secure computation with oblivious transfer. In Edgar R. Weippl, Stefan Katzenbeisser, Christopher Kruegel, Andrew C. Myers, and Shai Halevi, editors, ACM CCS 2016, pages 830-842. ACM Press, October 2016. URL: https://doi.org/10.1145/2976749.2978357.
  43. Tal Rabin and Michael Ben-Or. Verifiable secret sharing and multiparty protocols with honest majority (extended abstract). In 21st ACM STOC, pages 73-85. ACM Press, May 1989. URL: https://doi.org/10.1145/73007.73014.
  44. Adi Shamir. How to share a secret. Communications of the Association for Computing Machinery, 22(11):612-613, November 1979. Google Scholar
  45. Andrew Chi-Chih Yao. Protocols for secure computations (extended abstract). In 23rd FOCS, pages 160-164. IEEE Computer Society Press, November 1982. URL: https://doi.org/10.1109/SFCS.1982.38.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact