Paper 2022/799
Tight Bounds on the Randomness Complexity of Secure Multiparty Computation
Abstract
We revisit the question of minimizing the randomness complexity of protocols for secure multiparty computation (MPC) in the setting of perfect information-theoretic security. Kushilevitz and Mansour (SIAM J. Discret. Math., 1997) studied the case of $n$-party semi-honest MPC for the XOR function with security threshold $t<n$, showing that $O(t^2\log(n/t))$ random bits are sufficient and $\Omega(t)$ random bits are necessary. Their positive result was obtained via a non-explicit protocol, whose existence was proved using the probabilistic method. We essentially close the question by proving an $\Omega(t^2)$ lower bound on the randomness complexity of XOR, matching the previous upper bound up to a logarithmic factor (or constant factor when $t=\Omega(n)$). We also obtain an explicit protocol that uses $O(t^2\cdot\log^2n)$ random bits, matching our lower bound up to a polylogarithmic factor. We extend these results from XOR to general symmetric Boolean functions and to addition over a finite Abelian group, showing how to amortize the randomness complexity over multiple additions. Finally, combining our techniques with recent randomness-efficient constructions of private circuits, we obtain an explicit protocol for evaluating a general circuit $C$ using only $O(t^2\cdot\log |C|)$ random bits, by employing additional ``helper parties'' who do not contribute any inputs. This upper bound too matches our lower bound up to a logarithmic factor.
Metadata
- Available format(s)
- Category
- Foundations
- Publication info
- A major revision of an IACR publication in CRYPTO 2022
- Keywords
- Information-theoretic Security Randomness Complexity Multiparty Computation
- Contact author(s)
-
vipul @ cmu edu
yuvali @ cs technion ac il
yifans2 @ andrew cmu edu - History
- 2022-06-22: revised
- 2022-06-20: received
- See all versions
- Short URL
- https://ia.cr/2022/799
- License
-
CC BY-NC
BibTeX
@misc{cryptoeprint:2022/799, author = {Vipul Goyal and Yuval Ishai and Yifan Song}, title = {Tight Bounds on the Randomness Complexity of Secure Multiparty Computation}, howpublished = {Cryptology {ePrint} Archive, Paper 2022/799}, year = {2022}, url = {https://eprint.iacr.org/2022/799} }