International Association for Cryptologic Research

International Association
for Cryptologic Research


Communication Lower Bounds for Statistically Secure MPC, With or Without Preprocessing

Ivan Damgård
Kasper Green Larsen
Jesper Buus Nielsen
DOI: 10.1007/978-3-030-26951-7_3 (login may be required)
Search ePrint
Search Google
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 $$\varOmega (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 $$\lg n$$ off for Boolean circuits).
Video from CRYPTO 2019
  title={Communication Lower Bounds for Statistically Secure MPC, With or Without Preprocessing},
  booktitle={Advances in Cryptology – CRYPTO 2019},
  series={Lecture Notes in Computer Science},
  author={Ivan Damgård and Kasper Green Larsen and Jesper Buus Nielsen},