{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,18]],"date-time":"2025-12-18T13:49:10Z","timestamp":1766065750593},"publisher-location":"Berlin, Heidelberg","reference-count":37,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540675174"},{"type":"electronic","value":"9783540455394"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-45539-6_10","type":"book-chapter","created":{"date-parts":[[2007,7,16]],"date-time":"2007-07-16T16:26:08Z","timestamp":1184603168000},"page":"122-138","source":"Crossref","is-referenced-by-count":82,"title":["Single Database Private Information Retrieval Implies Oblivious Transfer"],"prefix":"10.1007","author":[{"given":"Giovanni","family":"Di Crescenzo","sequence":"first","affiliation":[]},{"given":"Tal","family":"Malkin","sequence":"additional","affiliation":[]},{"given":"Rafail","family":"Ostrovsky","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2000,5,12]]},"reference":[{"key":"10_CR1","doi-asserted-by":"crossref","unstructured":"A. Ambainis. Upper Bound on the Communication Complexity of Private Information Retrieval. In Proc. of 24th ICALP, 1997.","DOI":"10.1007\/3-540-63165-8_196"},{"key":"10_CR2","doi-asserted-by":"crossref","unstructured":"G. Brassard, C. Crepeau and J.-M. Robert All-or-Nothing Disclosure of Secrets In Crypto\u2019 86 Springer-Verlag, 1987, pp. 234\u2013238.","DOI":"10.1007\/3-540-47721-7_17"},{"key":"10_CR3","doi-asserted-by":"crossref","unstructured":"A. Beimel, Y. Ishai, E. Kushilevitz, and T. Malkin. One-Way Functions are Essential for Single-Server Private Information Retrieval. In Proc. of 31st STOC, 1999.","DOI":"10.1145\/301250.301277"},{"key":"10_CR4","doi-asserted-by":"crossref","unstructured":"A. Beimel, T. Malkin, S. Micali. The All-or-Nothing Nature of Two-Party Secure Computation. In Proc. of CRYPTO 99, 1999.","DOI":"10.1007\/3-540-48405-1_6"},{"key":"10_CR5","doi-asserted-by":"crossref","unstructured":"C. Cachin, C. Crepeau, and S. Marcil. Oblivious Transfer with a Memory Bounded Receiver. In Proc. of 39th FOCS, 1998.","DOI":"10.1109\/SFCS.1998.743500"},{"key":"10_CR6","doi-asserted-by":"crossref","unstructured":"C. Cachin, S. Micali, and M. Stadler. Computationally Private Information Retrieval with Polylogarithmic Communication. In Proc. of EUROCRYPT 99, 1999.","DOI":"10.1007\/3-540-48910-X_28"},{"key":"10_CR7","doi-asserted-by":"crossref","unstructured":"B. Chor and N. Gilboa. Computationally Private Information Retrieval. In Proc. of 29th STOC, 1997.","DOI":"10.1145\/258533.258609"},{"key":"10_CR8","doi-asserted-by":"crossref","unstructured":"B. Chor, O. Goldreich, E. Kushilevitz, and M. Sudan. Private Information Retrieval. In Proc. of 36th FOCS, 1995.","DOI":"10.1109\/SFCS.1995.492461"},{"key":"10_CR9","doi-asserted-by":"crossref","unstructured":"T. M. Cover and J. A. Thomas. Elements of Information Theory. John Wiley & Sons, 1991.","DOI":"10.1002\/0471200611"},{"key":"10_CR10","doi-asserted-by":"crossref","unstructured":"C. Cr\u00e9peau. Equivalence Between Two Flavors of Oblivious Transfers. In Proc. of CRYPTO\u2019 87, 1987.","DOI":"10.1007\/3-540-48184-2_30"},{"key":"10_CR11","doi-asserted-by":"crossref","unstructured":"A. De Santis and P. Persiano, Zero-Knowledge Proofs of Knowledge without Interaction, In Proc. of 33rd FOCS, 1992.","DOI":"10.1109\/SFCS.1992.267809"},{"key":"10_CR12","doi-asserted-by":"crossref","unstructured":"G. Di Crescenzo, Y. Ishai, and R. Ostrovsky. Universal Service-Providers for Database Private Information Retrieval. In Proc. of 17th PODC, 1998.","DOI":"10.1145\/277697.277713"},{"key":"10_CR13","doi-asserted-by":"publisher","first-page":"637","DOI":"10.1145\/3812.3818","volume":"28","author":"S. Even","year":"1985","unstructured":"S. Even, O. Goldreich, and A. Lempel. A Randomized Protocol for Signing Contracts. Comm. of ACM, 28:637\u2013647, 1985.","journal-title":"Comm. of ACM"},{"key":"10_CR14","doi-asserted-by":"crossref","unstructured":"U. Feige and A. Shamir, Witness Indistinguishable and Witness Hiding Protocols. In Proc. of 23rd STOC, 1990.","DOI":"10.1145\/100216.100272"},{"key":"10_CR15","doi-asserted-by":"crossref","unstructured":"Y. Gertner, S. Goldwasser, and T. Malkin. A Random Server Model for Private Information Retrieval. In Proc. of 2nd RANDOM, 1998.","DOI":"10.1007\/3-540-49543-6_17"},{"key":"10_CR16","doi-asserted-by":"crossref","unstructured":"Y. Gertner, Y. Ishai, E. Kushilevitz, and T. Malkin. Protecting Data Privacy in Private Information Retrieval Schemes. In Proc. of 30th STOC, 1998.","DOI":"10.1145\/276698.276723"},{"key":"10_CR17","doi-asserted-by":"publisher","first-page":"792","DOI":"10.1145\/116825.116852","volume":"38","author":"O. Goldreich","year":"1991","unstructured":"O. Goldreich, S. Goldwasser, and S. Micali. How to Construct Random Functions. In Journal of the ACM, vol. 38, 1991, pages 792\u2013807, 1986.","journal-title":"Journal of the ACM"},{"key":"10_CR18","doi-asserted-by":"publisher","first-page":"691","DOI":"10.1145\/116825.116852","volume":"38","author":"O. Goldreich","year":"1991","unstructured":"O. Goldreich, S. Micali, and A. Wigderson. Proofs that Yield Nothing but Their Validity, and a Methodology of Cryptographic Protocol Design. In Journal of the ACM, vol. 38, 1991, pages 691\u2013729.","journal-title":"Journal of the ACM"},{"key":"10_CR19","doi-asserted-by":"crossref","unstructured":"O. Goldreich, S. Micali, and A. Wigderson. How to Play Any Mental Game. In Proc. of 19th STOC, 1987.","DOI":"10.1145\/28395.28420"},{"key":"10_CR20","doi-asserted-by":"crossref","unstructured":"J. Hastad, R. Impagliazzo, L. Levin, and M. Luby. A Pseudorandom Generator From Any One-Way Function. SIAM J. on Computing, 1999, vol. 28, n. 4.","DOI":"10.1137\/S0097539793244708"},{"key":"10_CR21","doi-asserted-by":"crossref","unstructured":"R. Impagliazzo and M. Luby, \u201cOne-Way Functions are Essential for Complexity-Based Cryptography\u201d In Proc. of FOCS 89.","DOI":"10.1109\/SFCS.1989.63483"},{"key":"10_CR22","doi-asserted-by":"crossref","unstructured":"R. Impagliazzo and S. Rudich. Limits on the Provable Consequences of One-Way Permutations. In Proc. of 21st STOC, 1989.","DOI":"10.1145\/73007.73012"},{"key":"10_CR23","doi-asserted-by":"crossref","unstructured":"Y. Ishai and E. Kushilevitz. Improved Upper Bounds on Information-Theoretic Private Information Retrieval. In Proc. of 31st STOC, 1999.","DOI":"10.1145\/301250.301275"},{"key":"10_CR24","doi-asserted-by":"crossref","unstructured":"J. Kilian. Founding Cryptography on Oblivious Transfer. In Proc. of 20th STOC, 1988.","DOI":"10.1145\/62212.62215"},{"key":"10_CR25","unstructured":"J. Kilian, E. Kushilevitz, S. Micali, and R. Ostrovsky. Reducibility and Completness In Private Computations. In SIAM J. on Computing, includes [26]."},{"key":"10_CR26","unstructured":"E. Kushilevitz, S. Micali, and R. Ostrovsky. Reducibility and Completness in Multi-party Private Computations. In Proc. of 35th FOCS 94, 1994."},{"key":"10_CR27","doi-asserted-by":"crossref","unstructured":"E. Kushilevitz and R. Ostrovsky. Replication is Not Needed: Single-Database Computationally Private Information Retrieval. In Proc. of 38th FOCS, 1997.","DOI":"10.1109\/SFCS.1997.646125"},{"key":"10_CR28","doi-asserted-by":"crossref","unstructured":"E. Kushilevitz and R. Ostrovsky. One-Way Trapdoor Permutations are Sufficient for Single-database Computationally-Private Information Retrieval. In Proc. of EUROCRYPT\u2019 00, 2000.","DOI":"10.1007\/3-540-45539-6_9"},{"key":"10_CR29","volume-title":"Private Access to Distributed Information","author":"E. Mann","year":"1998","unstructured":"E. Mann. Private Access to Distributed Information. Master\u2019s thesis, Technion-Israel Institute of Technology, Haifa, 1998."},{"key":"10_CR30","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1007\/BF00196774","volume":"4","author":"M. Naor","year":"1991","unstructured":"M. Naor. Bit Commitment Using Pseudorandom Generators. Journal of Cryptology, 4:151\u2013158, 1991.","journal-title":"Journal of Cryptology"},{"key":"10_CR31","doi-asserted-by":"crossref","unstructured":"M. Naor and B. Pinkas. Oblivious Transfer and Polynomial Evaluation. In Proc. of 31st STOC, 1999.","DOI":"10.1145\/301250.301312"},{"key":"10_CR32","doi-asserted-by":"crossref","unstructured":"M. Naor and M. Yung. Universal One-Way Hash Functions and their Cryptographic Applications. In Proc. of 21st STOC, 1989.","DOI":"10.1145\/73007.73011"},{"key":"10_CR33","unstructured":"R. Ostrovsky and V. Shoup. Private Information Storage. In Proc. of 29th STOC, 1997."},{"key":"10_CR34","unstructured":"R. Ostrovsky and A. Wigderson One-Way Functions are Essential for Non-Trivial Zero-Knowledge. In Proceedings of the Second Israel Symposium on Theory of Computing and Systems (ISTCS-93) pp. 1\u201310., IEEE 1993."},{"key":"10_CR35","unstructured":"M. O. Rabin. How to Exchange Secrets by Oblivious Transfer. Technical Report TR-81, Harvard University, 1981."},{"key":"10_CR36","doi-asserted-by":"crossref","unstructured":"J. Rompel. One-Way Functions are Necessary and Sufficient for Secure Signatures. In Proc. of 22nd STOC, 1990.","DOI":"10.1145\/100216.100269"},{"key":"10_CR37","doi-asserted-by":"crossref","unstructured":"J. P. Stern. A New and Efficient All-or-Nothing Disclosure of Secrets Protocol. In Proc. of ASIACRYPT\u2019 98, 1998.","DOI":"10.1007\/3-540-49649-1_28"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2014 EUROCRYPT 2000"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45539-6_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,1]],"date-time":"2019-05-01T03:36:50Z","timestamp":1556681810000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45539-6_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540675174","9783540455394"],"references-count":37,"URL":"https:\/\/doi.org\/10.1007\/3-540-45539-6_10","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]}}}