Ranjit Kumaresan: Secure Computation with Minimal Interaction, Revisited
Abstract: 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$ parties. Ishai et al. (Crypto 2010) showed that if only one party may be corrupted, then $n \ge 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$ or $n = 4$ and where there is a single malicious party.
- 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 {\em 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 {\em 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 {\em 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 $\mathrm{NC}^1$.