# Perfectly-Secure {MPC} with Linear Communication Complexity

## Zuzana {Beerliova-Trubiniova} and Martin Hirt

```
```Secure multi-party computation (MPC) allows a set of $n$ players to
securely compute an agreed function, even when up to $t$ players are
under the control of an adversary.
Known *perfectly secure* MPC protocols require communication of at
least $\Omega(n^3)$ field elements per multiplication, whereas
cryptographic or unconditional security is possible with communication
linear in the number of players.
We present a perfectly secure MPC protocol communicating $\O(n)$ field
elements per multiplication. Our protocol provides perfect security
against an active, adaptive adversary corrupting $t<n/3$ players, which
is optimal.
Thus our protocol improves the security of the most efficient
information-theoretically secure protocol at no extra costs,
respectively improves the efficiency of perfectly secure MPC protocols by
a factor of $\Omega(n^2)$.
To achieve this, we introduce a novel technique – constructing
detectable protocols with the help of so-called hyper-invertible
matrices, which we believe to be of independent interest.
Hyper-invertible matrices allow (among other things) to perform efficient
correctness checks of many instances in parallel, which was until now
possible only if error-probability was allowed.