Perfectly-Secure MPC with Linear Communication Complexity

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

Ω

(

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

$\mathcal{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

Ω

(

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.