• Calendar

May 6, Wednesday
12:00 – 13:30

We revisit the question of secure multiparty computation (MPC) with two rounds of interaction. It was previously shown by Gennaro et al. (Crypto 2002) that three or more communication rounds are necessary for general MPC protocols which tolerate $tge 2$ corrupted parties, regardless of the total number of parties, and even if {em broadcast} messages are allowed in each round. We complement this negative result by presenting matching positive results. Our main result is that if only {em one} party can be corrupted, then $nge 5$ parties can securely compute any function of their inputs using only {em two} rounds of interaction over secure point-to-point channels (without broadcast or any additional setup). Our protocol provides computational security while making only a black-box use of a pseudorandom generator, or alternatively can provide unconditional security for ``computationally simple'' functions (e.g., functions in $NC^1$). We also prove a similar result in a client-server setting, where there are $mge 2$ clients who hold inputs and should receive outputs, and $n$ additional servers with no inputs and outputs. For this setting we obtain a general MPC protocol which requires a single message from each client to each server, followed by a single message from each server to each client. The protocol is secure against a single corrupted client and against coalitions of $t<n/3$ corrupted servers.