Welcome to the resource topic for 2020/251
Title:
Communication Lower Bounds for Perfect Maliciously Secure MPC
Authors: Ivan Damgård, 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).
ePrint: https://eprint.iacr.org/2020/251
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 .