Ranjit Kumaresan: Secure Computation with Minimal Interaction, Revisited

Friday, September 11, 2015 - 10:30am to 12:00pm
Hewlett G882
Ranjit Kumaresan

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

When $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 $\mathrm{NC}^1$. The concrete efficiency of this protocol is comparable to the efficiency of secure two-party computation protocols for {\em semi-honest} parties based on garbled circuits. 
When $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 {\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$. 
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. 
This is joint work with Yuval Ishai, Eyal Kushilevitz, and Anat Paskin-Cherniavsky