$\Omega(\log n)$ Lower Bounds on the Amount of Randomness in 2-Private Computation
Anna Gál, Adi Rosén · SIAM Journal on Computing · 2005
We consider the amount of randomness necessary in information-theoretic private protocols. We prove that at least $\Omega(\log n)$ random bits are necessary for the t-private computation of the function {\tt xor} by n players for any $t \geq 2$. In view of the upper bound of O(t 2 log(n/t)) [E. Kushilevitz and Y. Mansour, SIAM J. Discrete Math., 10 (1997), pp. 647--661], this bound is tight, up to constant factors, for any fixed t. For a class of protocols obeying certain restrictions, we give a stronger lower bound of $\Omega(t \log(n/t))$. We note that all known randomness efficient private protocols designed specifically for {\tt xor} belong to this class. In fact we prove slightly stronger statements: we prove that on every input there is a run where the number of random bits used is large, rather than proving only that on some input there is a run where the number of random bits used is large. All our lower bounds hold for the "trusted dealer" model as well, and the $\Omega(t \log(n/t))$ lower bound for restricted protocols is tight, up to constant factors, for any $t \geq 2$ in this model. In comparison, the previous lower bounds on the amount of randomness required by t-private computation of explicit functions did not grow with n for constant values of t, and our results improve the previous lower bounds for {\tt xor} for any $2 \leq t = o(\log n)$. Our results also show that already for t=2$, $\Omega(\log n)$ random bits are necessary, while it is known that for the case of t=1$ a single random bit is sufficient for privately computing {\tt xor} for any number of players. Our proofs use novel techniques by which we extract random variables from a t-private protocol, and then use the t-privacy property of the protocol to prove properties of these random variables. These properties in turn imply that the number of random bits used by the players is large.