# A Randomness-Rounds Tradeoff in Private Computation

Conference paper

First Online:

- 4 Citations
- 2.1k Downloads

## Abstract

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.

## Keywords

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.

Download
to read the full conference paper text

## References

- [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 - [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
- [B89]D. Beaver, “Perfect Privacy for Two-Party Protocols”, TR-11-89, Harvard University, 1989.Google Scholar
- [BFKR91]D. Beaver, J. Feigenbaum, J. Kilian, and P. Rogaway, “Security with Low Communication Overhead”, 1991.Google Scholar
- [BGG90]M. Bellare, O. Goldreich, and S. Goldwasser, “Randomness in Interactive Proofs”, Proc. of 31st FOCS, 1990, pp. 563–571.Google Scholar
- [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
- [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 - [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 - [BSV94]C. Blundo, A. De-Santis, and U. Vaccaro, “Randomness in Distribution Protocols”, To appear in
*Proc. of 21st ICALP*, 1994.Google Scholar - [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 - [CCD88]D. Chaum, C. Crepeau, and I. Damgard, “Multiparty Unconditionally Secure Protocols”, Proc. of 20th STOC, 1988, pp. 11–19.Google Scholar
- [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 - [CK92]B. Chor, and E. Kushilevitz, “A Communication-Privacy Tradeoff for Modular Addition”,
*Information Processing Letters*, Vol. 45, 1993, pp. 205–210.zbMATHCrossRefMathSciNetGoogle Scholar - [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
- [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 - [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 - [CW89]A. Cohen, and A. Wigderson, “Dispersers, Deterministic Amplification, and Weak Random Sources”, Proc. of 30th FOCS, 1989, pp. 14–19.Google Scholar
- [FY92]M. Franklin, and M. Yung, “Communication complexity of secure computation”, Proc. of 24th STOC, 1992, pp. 699–710.Google Scholar
- [IZ89]R. Impagliazzo, and D. Zuckerman, “How to Recycle Random Bits”, Proc. of 30th FOCS, 1989, pp. 248–253.Google Scholar
- [KM93]D. Koller, and N. Megiddo, “Constructing Small Sample Spaces Satisfying Given Constraints”, Proc. of 25th STOC, 1993, pp. 268–277.Google Scholar
- [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
- [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
- [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 - [N90]N. Nisan, “Pseudorandom Generator for Space Bounded Computation”, Proc. of 22nd STOC, 1990, pp. 204–212.Google Scholar
- [RS89]P. Raghavan, and M. Snir, “Memory vs. Randomization in On-Line Algorithms”, Proc. of 16th ICALP, 1989, pp. 687–703.Google Scholar
- [S92]L. J. Schulman, “Sample Spaces Uniform on Neighborhoods”, Proc. of 24th STOC, 1992, pp. 17–25.Google Scholar
- [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
- [Y82]A. C. Yao, “Theory and Applications of Trapdoor Functions” Proc. of 23rd FOCS, 1982, pp. 80–91.Google Scholar
- [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