Cryptology ePrint Archive: Report 2017/1056

Round-Optimal Secure Multi-Party Computation

Shai Halevi and Carmit Hazay and 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.

Category / Keywords: cryptographic protocols / Secure Multi-Party Computation, Garbled Circuits, Round Complexity, Additive Errors

Date: received 29 Oct 2017, last revised 5 Mar 2018

Contact author: antigoni at cornell edu

Available format(s): PDF | BibTeX Citation

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

Version: 20180306:005451 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]