Paper 2020/251

Communication Lower Bounds for Perfect Maliciously Secure MPC

Ivan Damgård and Nikolaj I. Schwartzbach

Abstract

We prove a lower bound on the communication complexity of perfect maliciously secure multiparty computation, in the standard model with $n=3t+1$ parties of which $t$ are corrupted. We show that for any $n$ and all large enough $g \in \mathbb{N}$ there exists a Boolean circuit $C$ with $g$ gates, where any perfectly secure protocol implementing $C$ must communicate $\Omega(n g)$ bits. The results easily extends to constructing similar circuits over any fixed finite field. Our results also extend to the case where the threshold $t$ is suboptimal. Namely if $n= 3t+s$ the bound is $\Omega(ng/s)$, which corresponds to known optimizations via packed secret-sharing. Using known techniques, we also show an upper bound that matches the lower bound up to a constant factor (existing upper bounds are a factor $\log n$ off for Boolean circuits).