Paper 2022/799

Tight Bounds on the Randomness Complexity of Secure Multiparty Computation

Vipul Goyal, Carnegie Mellon University, NTT Research
Yuval Ishai, Technion
Yifan Song, Carnegie Mellon University

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)
Publication info
A major revision of an IACR publication in CRYPTO 2022
Information-theoretic Security Randomness Complexity Multiparty Computation
Contact author(s)
vipul @ cmu edu
yuvali @ cs technion ac il
yifans2 @ andrew cmu edu
2022-06-22: revised
2022-06-20: received
See all versions
Short URL
Creative Commons Attribution-NonCommercial


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.