International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: Tight Bounds on the Randomness Complexity of Secure Multiparty Computation

Authors:
Vipul Goyal , CMU and NTT Research
Yuval Ishai , Technion
Yifan Song , Carnegie Mellon University
Download:
Search ePrint
Search Google
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
}