Secure Computation with Minimal Interaction, Revisited

Yuval Ishai; Ranjit Kumaresan; Eyal Kushilevitz; Anat Paskin-Cherniavsky

Secure Computation with Minimal Interaction, Revisited

Yuval Ishai ,
Ranjit Kumaresan ,
Eyal Kushilevitz ,
Anat Paskin-Cherniavsky

Advances in Cryptology - CRYPTO 2015 | August 2015

Published by Springer, Berlin, Heidelberg

Publication | Publication

Download BibTex

Motivated by the goal of improving the concrete efficiency of secure multiparty computation (MPC), we revisit the question of MPC with only two rounds of interaction. We consider a minimal setting in which parties can communicate over secure point-to-point channels and where no broadcast channel or other form of setup is available.

Katz and Ostrovsky (Crypto 2004) obtained negative results for such protocols with $n = 2 "> n = 2$ parties. Ishai et al. (Crypto 2010) showed that if only one party may be corrupted, then $n \geq 5 "> n \geq 5$ parties can securely compute any function in this setting, with guaranteed output delivery, assuming one-way functions exist. In this work, we complement the above results by presenting positive and negative results for the cases where $n = 3 "> n = 3$ or $n = 4 "> n = 4$ and where there is a single malicious party.

When $n = 3 "> n = 3$ , we show a 2-round protocol which is secure with “selective abort” against a single malicious party. The protocol makes a black-box use of a pseudorandom generator or alternatively can offer unconditional security for functionalities in $N C 1 "> N C 1$ . The concrete efficiency of this protocol is comparable to the efficiency of secure two-party computation protocols for semi-honest parties based on garbled circuits.

When $n = 4 "> n = 4$ in the setting described above, we show the following:

A statistical VSS protocol that has a 1-round sharing phase and 1-round reconstruction phase. This improves over the state-of-the-art result of Patra et al. (Crypto 2009) whose VSS protocol required 2 rounds in the reconstruction phase.
A 2-round statistically secure protocol for linear functionalities with guaranteed output delivery. This implies a 2-round 4-party fair coin tossing protocol. We complement this by a negative result, showing that there is a (nonlinear) function for which there is no 2-round statistically secure protocol.
A 2-round computationally secure protocol for general functionalities with guaranteed output delivery, under the assumption that injective (one-to-one) one-way functions exist.
A 2-round protocol for general functionalities with guaranteed output delivery in the preprocessing model, whose correlated randomness complexity is proportional to the length of the inputs. This protocol makes a black-box use of a pseudorandom generator or alternatively can offer unconditional security for functionalities in $N C 1 "> N C 1$ .

Prior to our work, the feasibility results implied by our positive results were not known to hold even in the stronger MPC model considered by Gennaro et al. (Crypto 2002), where a broadcast channel is available.