Cryptology ePrint Archive: Report 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).

Category / Keywords: foundations / secure multiparty computation, lower bound, communication complexity

Date: received 24 Feb 2020

Contact author: ivan at cs au dk,nis@cs au dk

Available format(s): PDF | BibTeX Citation

Version: 20200225:204111 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]