### 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.

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
See all versions
Short URL
https://ia.cr/2022/799

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},
note = {\url{https://eprint.iacr.org/2022/799}},
url = {https://eprint.iacr.org/2022/799}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.