Secure Multiparty Computation with Minimal Interaction

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 3 or more communication rounds are necessary for general MPC protocols with guaranteed output delivery, assuming that there may be

t

 ≥ 2 corrupted parties. This negative result holds regardless of the total number of parties, even if

broadcast

is allowed in each round, and even if only

fairness

is required. We complement this negative result by presenting matching positive results.

Our first main result is that if only

one

party may be corrupted, then

n

 ≥ 5 parties can securely compute any function of their inputs using only

two

rounds of interaction over secure point-to-point channels (without broadcast or any additional setup). The protocol makes a black-box use of a pseudorandom generator, or alternatively can offer unconditional security for functionalities in NC

1

.

We also prove a similar result in a client-server setting, where there are

m

 ≥ 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.

The above protocols guarantee output delivery and fairness. Our second main result shows that under a relaxed notion of security, allowing the adversary to selectively decide (after learning its own outputs) which honest parties will receive their (correct) output, there is a general 2-round MPC protocol which tolerates

t

 < 

n

/3 corrupted parties. This protocol relies on the existence of a pseudorandom generator in NC

1

(which is implied by standard cryptographic assumptions), or alternatively can offer unconditional security for functionalities in NC

1

.