Welcome to the resource topic for 2019/220
Title:
Communication Lower Bounds for Statistically Secure MPC, with or without Preprocessing
Authors: Ivan Damgård, Kasper Green Larsen, 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).
ePrint: https://eprint.iacr.org/2019/220
Talk: https://www.youtube.com/watch?v=x5W1Ce29tHc
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .