A Randomness-Rounds Tradeoff in Private Computation

  • Eyal Kushilevitz
  • Adi Rosén
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 839)


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.


Boolean Function External Agent Basic Protocol Privacy Requirement Coin Toss 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.


  1. [AGHP90]
    N. Alou, O. Goldreich, J. Hastad, and R. Peralta, “Simple constructions of almost k-wise independent random variables”, Proc. of 31st FOCS, 1990, pp. 544–553.Google Scholar
  2. [BB89]
    J. Bar-Ilan, and D. Beaver, “Non-Cryptographic Fault-Tolerant Computing in a Constant Number of Rounds”, Proc. of 8th PODC, 1989, pp. 201–209.Google Scholar
  3. [B89]
    D. Beaver, “Perfect Privacy for Two-Party Protocols”, TR-11-89, Harvard University, 1989.Google Scholar
  4. [BFKR91]
    D. Beaver, J. Feigenbaum, J. Kilian, and P. Rogaway, “Security with Low Communication Overhead”, 1991.Google Scholar
  5. [BGG90]
    M. Bellare, O. Goldreich, and S. Goldwasser, “Randomness in Interactive Proofs”, Proc. of 31st FOCS, 1990, pp. 563–571.Google Scholar
  6. [BGW88]
    M. Ben-or, S. Goldwasser, and A. Wigderson, “Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation”, Proc. of 20th STOC, 1988, pp. 1–10.Google Scholar
  7. [BM84]
    M. Blum, and S. Micali “How to Generate Cryptographically Strong Sequences Of Pseudo-Random Bits”, FOCS 82 and SIAM J. on Computing, Vol 13, 1984, pp. 850–864.zbMATHCrossRefMathSciNetGoogle Scholar
  8. [BGS94]
    C. Blundo, A. Giorgio Gaggia, and D. R. Stinson, “On the Dealer’s Randomness Required in Secret Sharing Schemes”, Proc. of EuroCrypt94.Google Scholar
  9. [BSV94]
    C. Blundo, A. De-Santis, and U. Vaccaro, “Randomness in Distribution Protocols”, To appear in Proc. of 21st ICALP, 1994.Google Scholar
  10. [CG90]
    R. Canetti, and O. Goldreich, “Bounds on Tradeoffs between Randomness and Communication Complexity”, FOCS 90 and Computational Complexity Vol. 3, (1993), 141–167.zbMATHCrossRefMathSciNetGoogle Scholar
  11. [CCD88]
    D. Chaum, C. Crepeau, and I. Damgard, “Multiparty Unconditionally Secure Protocols”, Proc. of 20th STOC, 1988, pp. 11–19.Google Scholar
  12. [CK89]
    B. Chor, and E. Kushilevitz, “A Zero-One Law for Boolean Privacy”, STOC 89 and SIAM J. Disc. Math. Vol. 4, (1991), 36–47.zbMATHCrossRefMathSciNetGoogle Scholar
  13. [CK92]
    B. Chor, and E. Kushilevitz, “A Communication-Privacy Tradeoff for Modular Addition”, Information Processing Letters, Vol. 45, 1993, pp. 205–210.zbMATHCrossRefMathSciNetGoogle Scholar
  14. [CGK90]
    B. Chor, M. Geréb-Graus, and E. Kushilevitz, “Private Computations Over the Integers”, Proc. of 31st FOCS, 1990, pp. 335–344.Google Scholar
  15. [CGK92]
    B. Chor, M. Geréb-Graus, and E. Kushilevitz, “On the Structure of the Privacy Hierarchy”, Journal of Cryptology, Vol. 7, No. 1, 1994, pp. 53–60.zbMATHCrossRefMathSciNetGoogle Scholar
  16. [CG88]
    B. Chor, and O. Goldreich, “Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity”, FOCS 85 and SIAM J. Computing Vol. 17, (1988), 230–261.zbMATHCrossRefMathSciNetGoogle Scholar
  17. [CW89]
    A. Cohen, and A. Wigderson, “Dispersers, Deterministic Amplification, and Weak Random Sources”, Proc. of 30th FOCS, 1989, pp. 14–19.Google Scholar
  18. [FY92]
    M. Franklin, and M. Yung, “Communication complexity of secure computation”, Proc. of 24th STOC, 1992, pp. 699–710.Google Scholar
  19. [IZ89]
    R. Impagliazzo, and D. Zuckerman, “How to Recycle Random Bits”, Proc. of 30th FOCS, 1989, pp. 248–253.Google Scholar
  20. [KM93]
    D. Koller, and N. Megiddo, “Constructing Small Sample Spaces Satisfying Given Constraints”, Proc. of 25th STOC, 1993, pp. 268–277.Google Scholar
  21. [KPU88]
    D. Krizanc, D. Peleg, and E. Upfal, “A Time-Randomness Tradeoff for Oblivious Routing”, Proc. of 20th STOC, 1988, pp. 93–102.Google Scholar
  22. [K89]
    E. Kushilevitz, “Privacy and Communication Complexity”, FOCS 89, and SIAM Jour. on Disc. Math., Vol. 5, No. 2, May 1992, pp. 273–284.zbMATHCrossRefMathSciNetGoogle Scholar
  23. [NN90]
    J. Naor, and M. Naor, “Small-Bias Probability Spaces: Efficient Constructions and Applications”, STOC 90, and SIAM J. on Computing, Vol 22, No. 4, 1993, pp. 838–856.zbMATHCrossRefMathSciNetGoogle Scholar
  24. [N90]
    N. Nisan, “Pseudorandom Generator for Space Bounded Computation”, Proc. of 22nd STOC, 1990, pp. 204–212.Google Scholar
  25. [RS89]
    P. Raghavan, and M. Snir, “Memory vs. Randomization in On-Line Algorithms”, Proc. of 16th ICALP, 1989, pp. 687–703.Google Scholar
  26. [S92]
    L. J. Schulman, “Sample Spaces Uniform on Neighborhoods”, Proc. of 24th STOC, 1992, pp. 17–25.Google Scholar
  27. [VV85]
    U. Vazirani, and V. Vazirani, “Random Polynomial Time is Equal to Slightly-Random Polynomial Time”, Proc. of 26th FOCS, 1985, pp. 417–428.Google Scholar
  28. [Y82]
    A. C. Yao, “Theory and Applications of Trapdoor Functions” Proc. of 23rd FOCS, 1982, pp. 80–91.Google Scholar
  29. [Z91]
    D. Zuckerman, “Simulating BPP Using a General Weak Random Source” Proc. of 32nd FOCS, 1991, pp. 79–89.Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 1994

Authors and Affiliations

  • Eyal Kushilevitz
    • 1
  • Adi Rosén
    • 2
  1. 1.Dept. of Computer ScienceTechnionHaifaIsrael
  2. 2.Dept. of Computer ScienceTel-Aviv UniversityTel-AvivIsrael

Personalised recommendations