CryptoDB
Paper: Tight Bounds on the Randomness Complexity of Secure Multiparty Computation
| Authors: |
|
|---|---|
| Download: | |
| Presentation: | Slides |
| Conference: | CRYPTO 2022 |
| 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 * \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 * \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. |
Video from CRYPTO 2022
BibTeX
@inproceedings{crypto-2022-32166,
title={Tight Bounds on the Randomness Complexity of Secure Multiparty Computation},
publisher={Springer-Verlag},
author={Vipul Goyal and Yuval Ishai and Yifan Song},
year=2022
}