Paper 2018/894

Perfect Secure Computation in Two Rounds

Benny Applebaum, Zvika Brakerski, and Rotem Tsabary


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.

Available format(s)
Publication info
A major revision of an IACR publication in TCC 2018
Contact author(s)
zvika brakerski @ weizmann ac il
2020-05-02: last of 2 revisions
2018-09-23: received
See all versions
Short URL
Creative Commons Attribution


      author = {Benny Applebaum and Zvika Brakerski and Rotem Tsabary},
      title = {Perfect Secure Computation in Two Rounds},
      howpublished = {Cryptology ePrint Archive, Paper 2018/894},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.