# Robust Multiparty Computation with Linear Communication Complexity

## Martin Hirt and Jesper Buus Nielsen

```
```We present a robust multiparty computation protocol. The protocol is
for the cryptographic model with open channels and a poly-time
adversary, and allows $n$ parties to actively securely evaluate any
poly-sized circuit with resilience $t < n/2$. The total
communication complexity in bits over the point-to-point channels is
$\O(S n \kappa + n \BC)$, where $S$ is the size of the circuit being
securely evaluated, $\kappa$ is the security parameter and $\BC$ is
the communication complexity of one broadcast of a $\kappa$-bit
value. This means the average number of bits sent and received by a
single party is $\O(S \kappa + \BC)$, which is almost independent of
the number of participating parties. This is the first robust
multiparty computation protocol with this property.