Cryptology ePrint Archive: Report 2018/894

Perfect Secure Computation in Two Rounds

Benny Applebaum and Zvika Brakerski and Rotem Tsabary

Abstract: We show that any multi-party functionality can be evaluated using a two-round protocol with perfect correctness and perfect semi-honest security, provided that the majority of parties are honest. This settles the round complexity of information-theoretic semi-honest MPC, resolving a longstanding open question (cf. Ishai and Kushilevitz, FOCS 2000). The protocol is efficient for $NC^1$ functionalities. Furthermore, given black-box access to a one-way function, the protocol can be made efficient for any polynomial functionality, at the cost of only guaranteeing computational security.

Our results are based on a new notion of \emph{multi-party randomized encoding} which extends and relaxes the standard notion of randomized encoding of functions (Ishai and Kushilevitz, FOCS 2000). The property of a multi-party randomized encoding (MPRE) is that if the functionality $g$ is an encoding of the functionality $f$, then for any (permitted) coalition of players, their respective outputs and inputs in $g$ allow them to simulate their respective inputs and outputs in $f$, without learning anything else, including the other outputs of $f$. We further introduce a new notion of effective algebraic degree, and show that the round complexity of a functionality $f$ is characterized by the degree of its MPRE. We construct degree-2 MPREs for general functionalities in several settings under different assumptions, and use these constructions to obtain two-round protocols. Our constructions also give rise to new protocols in the client-server model with optimal round complexity.

Category / Keywords:

Original Publication (with major differences): IACR-TCC-2018

Date: received 22 Sep 2018, last revised 2 May 2020

Contact author: zvika brakerski at weizmann ac il

Available format(s): PDF | BibTeX Citation

Version: 20200502:161556 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]