Paper 2018/894

Perfect Secure Computation in Two Rounds

Benny Applebaum, 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 $N{C}^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 $$ is an encoding of the functionality $$, then for any (permitted) coalition of players, their respective outputs and inputs in $$ allow them to simulate their respective inputs and outputs in $$, without learning anything else, including the other outputs of $$. We further introduce a new notion of effective algebraic degree, and show that the round complexity of a functionality $$ 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.