Paper 2017/1056

Round-Optimal Secure Multi-Party Computation

Shai Halevi, Carmit Hazay, Antigoni Polychroniadou, and Muthuramakrishnan Venkitasubramaniam

Abstract

Secure multi-party computation (MPC) is a central cryptographic task that allows a set of mutually distrustful parties to jointly compute some function of their private inputs where security should hold in the presence of a malicious adversary that can corrupt any number of parties. Despite extensive research, the precise round complexity of this "standard-bearer'' cryptographic primitive is unknown. Recently, Garg, Mukherjee, Pandey and Polychroniadou, in EUROCRYPT 2016 demonstrated that the round complexity of any MPC protocol relying on black-box proofs of security in the plain model must be at least four. Following this work, independently Ananth, Choudhuri and Jain, CRYPTO 2017 and Brakerski, Halevi, and Polychroniadou, TCC 2017 made progress towards solving this question and constructed four-round protocols based on non-polynomial time assumptions. More recently, Ciampi, Ostrovsky, Siniscalchi and Visconti in TCC 2017 closed the gap for two-party protocols by constructing a four-round protocol from polynomial-time assumptions. In another work, Ciampi, Ostrovsky, Siniscalchi and Visconti TCC 2017 showed how to design a four-round multi-party protocol for the specific case of multi-party coin-tossing. In this work, we resolve this question by designing a four-round actively secure multi-party (two or more parties) protocol for general functionalities under standard polynomial-time hardness assumptions with a black-box proof of security.

Note: Significant revision to the presentation, and an additional instantiation based on DCR.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A minor revision of an IACR publication in CRYPTO 2018
Keywords
Secure Multi-Party ComputationGarbled CircuitsRound ComplexityAdditive Errors
Contact author(s)
carmit hazay @ biu ac il
History
2018-09-11: last of 2 revisions
2017-10-31: received
See all versions
Short URL
https://ia.cr/2017/1056
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/1056,
      author = {Shai Halevi and Carmit Hazay and Antigoni Polychroniadou and Muthuramakrishnan Venkitasubramaniam},
      title = {Round-Optimal Secure Multi-Party Computation},
      howpublished = {Cryptology ePrint Archive, Paper 2017/1056},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/1056}},
      url = {https://eprint.iacr.org/2017/1056}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.