# Upper Bounds on the Communication Complexity of Optimally Resilient Cryptographic Multiparty Computation

## Martin Hirt and Jesper Buus Nielsen

```
```We give improved upper bounds on the communication complexity of
optimally-resilient secure multiparty computation in the cryptographic
model. We consider evaluating an $n$-party randomized function and show
that if $f$ can be computed by a circuit of size $c$, then $\O(c n^2
\kappa)$ is an upper bound for active security with optimal
resilience $t < n/2$ and security parameter $\kappa$. This improves on
the communication complexity of previous protocols by a factor of at
least $n$. This improvement comes from the fact that in the new protocol,
only $\O(n)$ messages (of size $\O(\kappa)$ each) are broadcast during
the * whole\/*} protocol execution, in contrast to previous protocols
which require at least $\O(n)$ broadcasts * per gate*}.

Furthermore, we improve the upper bound on the communication complexity
of passive secure multiparty computation with resilience $t<n$ from
$\O(c n^2 \kappa)$ to $\O(c n \kappa)$. This improvement is mainly due to
a simple observation.