Tight Bounds on the Randomness Complexity of Secure Multiparty Computation

Vipul Goyal
Yuval Ishai
Yifan Song

Publication date

June 2022

Publisher

International Association for Cryptologic Research (IACR)

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 ...

Extracted data

We use cookies to provide a better user experience.

Data Protection

Tight Bounds on the Randomness Complexity of Secure Multiparty Computation

Abstract

Extracted data

Tight Bounds on the Randomness Complexity of Secure Multiparty Computation

Abstract

Extracted data

Related items

Related items