1994 | OriginalPaper | Chapter
A Randomness-Rounds Tradeoff in Private Computation
Authors : Eyal Kushilevitz, Adi Rosén
Published in: Advances in Cryptology — CRYPTO ’94
Publisher: Springer Berlin Heidelberg
Included in: Professional Book Archive
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We study the role of randomness in multi-party private computations. In particular, we give several results that prove the existence of a randomness-rounds tradeoff in multi-party private computation of xor. We show that with a single random bit, Θ(n) rounds are necessary and sufficient to privately compute xor of n input bits. With d ≥ 2 random bits, Ω(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 ≥ 2 random bits, requires Ω(log S(f)/d) rounds, where S(f) is the sensitivity of f. Using a single random bit, Ω(S(f)) rounds are necessary.