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.

Technically, we extend and relax the notion of randomized encoding to specifically address multi-party functionalities. 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$.

Category / Keywords:

Date: received 22 Sep 2018

Contact author: zvika brakerski at weizmann ac il

Available format(s): PDF | BibTeX Citation

Version: 20180923:193908 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]