Paper 2021/278
More Communication Lower Bounds for InformationTheoretic MPC
Ivan Damgård, Boyang Li, and Nikolaj I. Schwartzbach
Abstract
We prove two classes of lower bounds on the communication complexity of informationtheoretically secure multiparty computation. The first lower bound applies to perfect passive secure multiparty computation, in the standard model with $n=2t+1$ parties of which $t$ are corrupted. We show a lower bound that applies to secure evaluation of any function, assuming that each party can choose to learn to learn or not learn the output. Specifically, we show that there is a function $H^*$ such that for any protocol that evaluates $y_i=b_i \cdot f(x_1,...,x_n)$ with perfect passive security (where $b_i$ is a private boolean input), the total communication must be at least $\frac{1}{2} \sum_{i=1}^n H_f^*(x_i)$ bits of information. The second lower bound applies to the perfect maliciously secure setting with $n=3t+1$ parties. We show that for any $n$ and all large enough $S$, there exists a reactive functionality $F_S$ taking an $S$bit string as input (and with short output) such that any protocol implementing $F_S$ with perfect malicious security must communicate $\Omega(nS)$ bits. Since the functionalities we study can be implemented with linear size circuits, the result can equivalently be stated as follows: for any $n$ and all large enough $g \in \mathbb{N}$ there exists a reactive functionality $F_C$ doing computation specified by a Boolean circuit $C$ with $g$ gates, where any perfectly secure protocol implementing $F_C$ must communicate $\Omega(n g)$ bits. The results easily extends to constructing similar functionalities defined over any fixed finite field. 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). Both results also extend to the case where the threshold $t$ is suboptimal. Namely if $n=kt+s$ the bound is weakened by a factor $O(s)$, which corresponds to known optimizations via packed secretsharing.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Preprint. Minor revision.
 Keywords
 secure multiparty computationlower boundcommunication complexity
 Contact author(s)

ivan @ cs au dk
805864812 @ qq com
nis @ cs au dk  History
 20210304: received
 Short URL
 https://ia.cr/2021/278
 License

CC BY
BibTeX
@misc{cryptoeprint:2021/278, author = {Ivan Damgård and Boyang Li and Nikolaj I. Schwartzbach}, title = {More Communication Lower Bounds for InformationTheoretic MPC}, howpublished = {Cryptology ePrint Archive, Paper 2021/278}, year = {2021}, note = {\url{https://eprint.iacr.org/2021/278}}, url = {https://eprint.iacr.org/2021/278} }