Welcome to the resource topic for 2018/894
Title:
Perfect Secure Computation in Two Rounds
Authors: Benny Applebaum, Zvika Brakerski, 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.
ePrint: https://eprint.iacr.org/2018/894
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .