Tight Bounds on the Randomness Complexity of Secure Multiparty Computation

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 Ω(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 Ω(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 = Ω(n)). We also obtain an explicit protocol that uses O(t 2 • log 2 n) 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.