A Randomness-Rounds Tradeoff in Private Computation
Eyal Kushilevitz, Adi Rosén · SIAM Journal on Discrete Mathematics · 1998
We study the role of randomness in multiparty private computations. In particular, we give several results that prove the existence of a randomness-rounds tradeoff in multiparty private computation of $\fxor$. We show that with a single random bit, $\Theta(n)$ rounds are necessary and sufficient to privately compute $\fxor$ of n input bits. With $d\ge 2$ random bits, $\Omega(\log n/ d)$ rounds are necessary, and $O(\log n/ \log d)$ are sufficient. More generally, we show that the private computation of a boolean function f, using $d\ge 2 $ random bits, requires $\Omega(\log S(f)/ d)$ rounds, where S(f) is the sensitivity of f. Using a single random bit, $\Omega(S(f))$ rounds are necessary.