Paper 2019/220

Communication Lower Bounds for Statistically Secure MPC, with or without Preprocessing

Ivan Damgård, Kasper Green Larsen, and Jesper Buus Nielsen

Abstract

We prove a lower bound on the communication complexity of unconditionally secure multiparty computation, both in the standard model with $n=2t+1$ parties of which $t$ are corrupted, and in the preprocessing model with $n=t+1$. In both cases, we show that for any $g \in \mathbb{N}$ there exists a Boolean circuit $C$ with $g$ gates, where any secure protocol implementing $C$ must communicate $\Omega(n g)$ bits, even if only passive and statistical security is required. The results easily extends to constructing similar circuits over any fixed finite field. This shows that for all sizes of circuits, the $O(n)$ overhead of all known protocols when $t$ is maximal is inherent. It also shows that security comes at a price: the circuit we consider could namely be computed among $n$ parties with communication only $O(g)$ bits if no security was required. Our results extend to the case where the threshold $t$ is suboptimal. For the honest majority case, this shows that the known optimizations via packed secret-sharing can only be obtained if one accepts that the threshold is $t= (1/2 - c)n$ for a constant $c$. For the honest majority case, 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).

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published by the IACR in CRYPTO 2019
Keywords
secure multiparty computationlower boundcommunication complexity
Contact author(s)
jbn @ cs au dk
ivan @ cs au dk
larsen @ cs au dk
History
2019-06-01: revised
2019-02-27: received
See all versions
Short URL
https://ia.cr/2019/220
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/220,
      author = {Ivan Damgård and Kasper Green Larsen and Jesper Buus Nielsen},
      title = {Communication Lower Bounds for Statistically Secure MPC, with or without Preprocessing},
      howpublished = {Cryptology ePrint Archive, Paper 2019/220},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/220}},
      url = {https://eprint.iacr.org/2019/220}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.