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

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

We prove a lower bound on the communication complexity of unconditionally secure multiparty computation, both in the standard model with (formula presented) parties of which t are corrupted, and in the preprocessing model with n=t+1. In both cases, we show that for any (formula presented) there exists a Boolean circuit C with g gates, where any secure protocol implementing C must communicate (formula presented) 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 (formula presented) 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 (formula presented) off for Boolean circuits).

Original languageEnglish
Title of host publicationAdvances in Cryptology – CRYPTO 2019 - 39th Annual International Cryptology Conference, Proceedings
EditorsAlexandra Boldyreva, Daniele Micciancio
Number of pages24
Publication year2019
ISBN (print)9783030269500
Publication statusPublished - 2019
Event39th Annual International Cryptology Conference, CRYPTO 2019 - Santa Barbara, United States
Duration: 18 Aug 201922 Aug 2019


Conference39th Annual International Cryptology Conference, CRYPTO 2019
LandUnited States
BySanta Barbara
SponsorCalibra, Cloudflare, Concordium, Conflux, et al, Fujitsu
SeriesLecture Notes in Computer Science

See relations at Aarhus University Citationformats

ID: 175971753