International Association
for Cryptologic Research

We study the question of how much interaction is needed for unconditionally secure multiparty computation. We first consider the number of messages that need to be sent to compute a non-trivial function (such as the AND of several input bits), assuming that all players have input and get output. We show that for $n$ players and $t$ corruptions,

$n(t+3)/2$ messages is necessary, this holds already for semi-honest and static corruption. Note that for functions that can be securely computed in constant round, this bound is tight up to a constant factor. For the case $t=1$ and semi-honest security, we show that $2 n$ messages is also sufficient to compute a rich class of functions efficiently, showing that the bound is exact for $t=1$.

Next, we consider round complexity.

It is a long-standing open problem to determine whether all efficiently computable functions can also be efficiently computed in constant-round with {\\em unconditional} security. Providing a positive answer seems to require completely new ideas for protocol design. Motivated by this, we consider the question of whether we can compute any function securely, while minimizing the interaction of {\\em some of} the players? And if so, how many players can this apply to? Note that we still want the standard security guarantees (correctness, privacy, termination) and we consider the standard communication model with secure point-to-point channels. We answer the questions as follows: for passive security, with $n=2t+1$ players and $t$ corruptions, up to $t$ players can have minimal interaction, i.e., they send 1 message in the first round to each of the $t+1$ remaining players and receive one message from each of them in the last round. Using our result on message complexity, we show that this is (unconditionally) optimal. For malicious security with $n=3t+1$ players and $t$ corruptions, up to $t$ players can have minimal interaction, also this is shown to be optimal.