Welcome to the resource topic for 2022/799
Title:
Tight Bounds on the Randomness Complexity of Secure Multiparty Computation
Authors: Vipul Goyal, Yuval Ishai, and Yifan Song
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.
ePrint: https://eprint.iacr.org/2022/799
Talk: https://www.youtube.com/watch?v=XMFjAp31Zag
Slides: https://iacr.org/submit/files/slides/2022/crypto/crypto2022/365/slides.pptx
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .