{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,24]],"date-time":"2026-01-24T23:44:41Z","timestamp":1769298281103,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540583332","type":"print"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/3-540-48658-5_36","type":"book-chapter","created":{"date-parts":[[2007,8,9]],"date-time":"2007-08-09T20:50:39Z","timestamp":1186692639000},"page":"397-410","source":"Crossref","is-referenced-by-count":5,"title":["A Randomness-Rounds Tradeoff in Private Computation"],"prefix":"10.1007","author":[{"given":"Eyal","family":"Kushilevitz","sequence":"first","affiliation":[]},{"given":"Adi","family":"Ros\u00e9n","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"36_CR1","doi-asserted-by":"crossref","unstructured":"N. Alou, O. Goldreich, J. Hastad, and R. Peralta, \u201cSimple constructions of almost k-wise independent random variables\u201d, Proc. of 31st FOCS, 1990, pp. 544\u2013553.","DOI":"10.1109\/FSCS.1990.89575"},{"key":"36_CR2","doi-asserted-by":"crossref","unstructured":"J. Bar-Ilan, and D. Beaver, \u201cNon-Cryptographic Fault-Tolerant Computing in a Constant Number of Rounds\u201d, Proc. of 8th PODC, 1989, pp. 201\u2013209.","DOI":"10.1145\/72981.72995"},{"key":"36_CR3","unstructured":"D. Beaver, \u201cPerfect Privacy for Two-Party Protocols\u201d, TR-11-89, Harvard University, 1989."},{"key":"36_CR4","unstructured":"D. Beaver, J. Feigenbaum, J. Kilian, and P. Rogaway, \u201cSecurity with Low Communication Overhead\u201d, 1991."},{"key":"36_CR5","doi-asserted-by":"crossref","unstructured":"M. Bellare, O. Goldreich, and S. Goldwasser, \u201cRandomness in Interactive Proofs\u201d, Proc. of 31st FOCS, 1990, pp. 563\u2013571.","DOI":"10.1109\/FSCS.1990.89577"},{"key":"36_CR6","doi-asserted-by":"crossref","unstructured":"M. Ben-or, S. Goldwasser, and A. Wigderson, \u201cCompleteness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation\u201d, Proc. of 20th STOC, 1988, pp. 1\u201310.","DOI":"10.1145\/62212.62213"},{"key":"36_CR7","doi-asserted-by":"publisher","first-page":"850","DOI":"10.1137\/0213053","volume":"13","author":"M. Blum","year":"1984","unstructured":"M. Blum, and S. Micali \u201cHow to Generate Cryptographically Strong Sequences Of Pseudo-Random Bits\u201d, FOCS 82 and SIAM J. on Computing, Vol 13, 1984, pp. 850\u2013864.","journal-title":"FOCS 82 and SIAM J. on Computing"},{"key":"36_CR8","unstructured":"C. Blundo, A. Giorgio Gaggia, and D. R. Stinson, \u201cOn the Dealer\u2019s Randomness Required in Secret Sharing Schemes\u201d, Proc. of EuroCrypt94."},{"key":"36_CR9","doi-asserted-by":"crossref","unstructured":"C. Blundo, A. De-Santis, and U. Vaccaro, \u201cRandomness in Distribution Protocols\u201d, To appear in Proc. of 21st ICALP, 1994.","DOI":"10.1007\/3-540-58201-0_99"},{"key":"36_CR10","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1007\/BF01200118","volume":"3","author":"R. Canetti","year":"1993","unstructured":"R. Canetti, and O. Goldreich, \u201cBounds on Tradeoffs between Randomness and Communication Complexity\u201d, FOCS 90 and Computational Complexity Vol. 3, (1993), 141\u2013167.","journal-title":"FOCS 90 and Computational Complexity"},{"key":"36_CR11","doi-asserted-by":"crossref","unstructured":"D. Chaum, C. Crepeau, and I. Damgard, \u201cMultiparty Unconditionally Secure Protocols\u201d, Proc. of 20th STOC, 1988, pp. 11\u201319.","DOI":"10.1145\/62212.62214"},{"key":"36_CR12","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1137\/0404004","volume":"4","author":"B. Chor","year":"1991","unstructured":"B. Chor, and E. Kushilevitz, \u201cA Zero-One Law for Boolean Privacy\u201d, STOC 89 and SIAM J. Disc. Math. Vol. 4, (1991), 36\u201347.","journal-title":"STOC 89 and SIAM J. Disc. Math."},{"key":"36_CR13","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/0020-0190(93)90120-X","volume":"45","author":"B. Chor","year":"1993","unstructured":"B. Chor, and E. Kushilevitz, \u201cA Communication-Privacy Tradeoff for Modular Addition\u201d, Information Processing Letters, Vol. 45, 1993, pp. 205\u2013210.","journal-title":"Information Processing Letters"},{"key":"36_CR14","doi-asserted-by":"crossref","unstructured":"B. Chor, M. Ger\u00e9b-Graus, and E. Kushilevitz, \u201cPrivate Computations Over the Integers\u201d, Proc. of 31st FOCS, 1990, pp. 335\u2013344.","DOI":"10.1109\/FSCS.1990.89552"},{"issue":"1","key":"36_CR15","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1007\/BF00195209","volume":"7","author":"B. Chor","year":"1994","unstructured":"B. Chor, M. Ger\u00e9b-Graus, and E. Kushilevitz, \u201cOn the Structure of the Privacy Hierarchy\u201d, Journal of Cryptology, Vol. 7, No. 1, 1994, pp. 53\u201360.","journal-title":"Journal of Cryptology"},{"key":"36_CR16","doi-asserted-by":"publisher","first-page":"230","DOI":"10.1137\/0217015","volume":"17","author":"B. Chor","year":"1988","unstructured":"B. Chor, and O. Goldreich, \u201cUnbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity\u201d, FOCS 85 and SIAM J. Computing Vol. 17, (1988), 230\u2013261.","journal-title":"FOCS 85 and SIAM J. Computing"},{"key":"36_CR17","doi-asserted-by":"crossref","unstructured":"A. Cohen, and A. Wigderson, \u201cDispersers, Deterministic Amplification, and Weak Random Sources\u201d, Proc. of 30th FOCS, 1989, pp. 14\u201319.","DOI":"10.1109\/SFCS.1989.63449"},{"key":"36_CR18","doi-asserted-by":"crossref","unstructured":"M. Franklin, and M. Yung, \u201cCommunication complexity of secure computation\u201d, Proc. of 24th STOC, 1992, pp. 699\u2013710.","DOI":"10.1145\/129712.129780"},{"key":"36_CR19","doi-asserted-by":"crossref","unstructured":"R. Impagliazzo, and D. Zuckerman, \u201cHow to Recycle Random Bits\u201d, Proc. of 30th FOCS, 1989, pp. 248\u2013253.","DOI":"10.1109\/SFCS.1989.63486"},{"key":"36_CR20","doi-asserted-by":"crossref","unstructured":"D. Koller, and N. Megiddo, \u201cConstructing Small Sample Spaces Satisfying Given Constraints\u201d, Proc. of 25th STOC, 1993, pp. 268\u2013277.","DOI":"10.1145\/167088.167168"},{"key":"36_CR21","doi-asserted-by":"crossref","unstructured":"D. Krizanc, D. Peleg, and E. Upfal, \u201cA Time-Randomness Tradeoff for Oblivious Routing\u201d, Proc. of 20th STOC, 1988, pp. 93\u2013102.","DOI":"10.1145\/62212.62221"},{"key":"36_CR22","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1137\/0405021","volume":"5","author":"E. Kushilevitz","year":"1992","unstructured":"E. Kushilevitz, \u201cPrivacy and Communication Complexity\u201d, FOCS 89, and SIAM Jour. on Disc. Math., Vol. 5, No. 2, May 1992, pp. 273\u2013284.","journal-title":"FOCS 89, and SIAM Jour. on Disc. Math."},{"issue":"4","key":"36_CR23","doi-asserted-by":"publisher","first-page":"838","DOI":"10.1137\/0222053","volume":"22","author":"J. Naor","year":"1993","unstructured":"J. Naor, and M. Naor, \u201cSmall-Bias Probability Spaces: Efficient Constructions and Applications\u201d, STOC 90, and SIAM J. on Computing, Vol 22, No. 4, 1993, pp. 838\u2013856.","journal-title":"STOC 90, and SIAM J. on Computing"},{"key":"36_CR24","doi-asserted-by":"crossref","unstructured":"N. Nisan, \u201cPseudorandom Generator for Space Bounded Computation\u201d, Proc. of 22nd STOC, 1990, pp. 204\u2013212.","DOI":"10.1145\/100216.100242"},{"key":"36_CR25","doi-asserted-by":"crossref","unstructured":"P. Raghavan, and M. Snir, \u201cMemory vs. Randomization in On-Line Algorithms\u201d, Proc. of 16th ICALP, 1989, pp. 687\u2013703.","DOI":"10.1007\/BFb0035792"},{"key":"36_CR26","doi-asserted-by":"crossref","unstructured":"L. J. Schulman, \u201cSample Spaces Uniform on Neighborhoods\u201d, Proc. of 24th STOC, 1992, pp. 17\u201325.","DOI":"10.1145\/129712.129715"},{"key":"36_CR27","doi-asserted-by":"crossref","unstructured":"U. Vazirani, and V. Vazirani, \u201cRandom Polynomial Time is Equal to Slightly-Random Polynomial Time\u201d, Proc. of 26th FOCS, 1985, pp. 417\u2013428.","DOI":"10.1109\/SFCS.1985.45"},{"key":"36_CR28","doi-asserted-by":"crossref","unstructured":"A. C. Yao, \u201cTheory and Applications of Trapdoor Functions\u201d Proc. of 23rd FOCS, 1982, pp. 80\u201391.","DOI":"10.1109\/SFCS.1982.45"},{"key":"36_CR29","doi-asserted-by":"crossref","unstructured":"D. Zuckerman, \u201cSimulating BPP Using a General Weak Random Source\u201d Proc. of 32nd FOCS, 1991, pp. 79\u201389.","DOI":"10.1109\/SFCS.1991.185351"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2014 CRYPTO \u201994"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-48658-5_36.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,20]],"date-time":"2025-01-20T07:02:57Z","timestamp":1737356577000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-48658-5_36"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540583332"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/3-540-48658-5_36","relation":{},"subject":[]}}