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 $\mathrm{\Omega }(ng)$ bits. The results easily extends to constructing similar circuits over any fixed finite field. Our results also extend to the case where the threshold $$ is suboptimal. Namely if $$ the bound is $$, 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 $$ off for Boolean circuits).