{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,5]],"date-time":"2026-03-05T19:24:09Z","timestamp":1772738649715,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":40,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540675174","type":"print"},{"value":"9783540455394","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-45539-6_9","type":"book-chapter","created":{"date-parts":[[2007,7,16]],"date-time":"2007-07-16T16:26:08Z","timestamp":1184603168000},"page":"104-121","source":"Crossref","is-referenced-by-count":61,"title":["One-Way Trapdoor Permutations Are Sufficient for Non-trivial Single-Server Private Information Retrieval"],"prefix":"10.1007","author":[{"given":"Eyal","family":"Kushilevitz","sequence":"first","affiliation":[]},{"given":"Rafail","family":"Ostrovsky","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2000,5,12]]},"reference":[{"key":"9_CR1","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"401","DOI":"10.1007\/3-540-63165-8_196","volume-title":"Proc. of 24th ICALP","author":"A. Ambainis","year":"1997","unstructured":"A. Ambainis. Upper bound on the communication complexity of private information retrieval. In Proc. of 24th ICALP, volume 1256 of Lecture Notes in Computer Science, pages 401\u2013407, 1997."},{"key":"9_CR2","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 the 31th Annu. ACM Symp. on the Theory of Computing, 1999.","DOI":"10.1145\/301250.301277"},{"key":"9_CR3","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1007\/BFb0055735","volume-title":"Advances in Cryptology-CRYPTO\u2019 98","author":"M. Bellare","year":"1998","unstructured":"M. Bellare, S. Halevi, A. Sahai, and S. Vadhan. Many-to-one trapdoor functions and their relation to public-key cryptosystems. In H. Krawczyk, editor, Advances in Cryptology-CRYPTO\u2019 98, volume 1462 of Lecture Notes in Computer Science, pages 283\u2013298. Springer-Verlag, 1998."},{"key":"9_CR4","doi-asserted-by":"crossref","unstructured":"G. Brassard, C. Crepeau and J.-M. Robert All-or-nothing disclosure of secrets In Advances in Cryptology: Proceedings of Crypto\u2019 86 Springer-Verlag, 1987, pp. 234\u2013238.","DOI":"10.1007\/3-540-47721-7_17"},{"key":"9_CR5","doi-asserted-by":"crossref","unstructured":"C. Cr\u00e9peau. Equivalence between two flavors of oblivious transfers. In Proc. of CRYPTO\u2019 87, pages 350\u2013354, 1988.","DOI":"10.1007\/3-540-48184-2_30"},{"key":"9_CR6","doi-asserted-by":"crossref","unstructured":"C. Cachin, C. Crepeau, and J. Marcil. Oblivious transfer with a memory-bounded receiver. In Proc. 39th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 493\u2013502, 1998.","DOI":"10.1109\/SFCS.1998.743500"},{"key":"9_CR7","doi-asserted-by":"crossref","unstructured":"C. Cachin, S. Micali, and M. Stadler. Computationally private information retrieval with polylogarithmic communication. In Advances in Cryptology-EUROCRYPT\u2019 99, 1999.","DOI":"10.1007\/3-540-48910-X_28"},{"key":"9_CR8","doi-asserted-by":"crossref","unstructured":"B. Chor and N. Gilboa. Computationally private information retrieval. In Proc. of the 29th Annu. ACM Symp. on the Theory of Computing, pages 304\u2013313, 1997.","DOI":"10.1145\/258533.258609"},{"key":"9_CR9","doi-asserted-by":"crossref","unstructured":"B. Chor, O. Goldreich, E. Kushilevitz, and M. Sudan. Private information retrieval. In Proc. of the 36th Annu. IEEE Symp. on Foundations of Computer Science, pages 41\u201351, 1995. Journal version in JACM, Vol. 45(6), 1998, pp. 965\u2013981.","DOI":"10.1145\/293347.293350"},{"key":"9_CR10","series-title":"Lect Notes Comput Sci","volume-title":"Advances in Cryptology-CRYPTO\u2019 93","author":"I. Damgard","year":"1994","unstructured":"I. Damgard. Interactive hashing can simplify zero-knowledge protocol design without computational assumptions. In D. R. Stinson, editor, Advances in Cryptology-CRYPTO\u2019 93, volume 773 of Lecture Notes in Computer Science. Springer-Verlag, 1994."},{"key":"9_CR11","doi-asserted-by":"crossref","unstructured":"G. Di Crescenzo, Y. Ishai, and R. Ostrovsky. Universal service-providers for database private information retrieval. In Proc. of the 17th Annu. ACM Symp. on Principles of Distributed Computing, pages 91\u2013100, 1998.","DOI":"10.1145\/277697.277713"},{"key":"9_CR12","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1007\/3-540-45539-6_10","volume-title":"Advances in Cryptology-EUROCRYPT 2000","author":"G. Crescenzo Di","year":"2000","unstructured":"G. Di Crescenzo, T. Malkin, and R. Ostrovsky. Single-database private information retrieval implies oblivious transfer. In Advances in Cryptology-EUROCRYPT 2000, Lecture Notes in Computer Science, volume 1807, Springer-Verlag, 2000, pp. 122\u2013139 (this volume)."},{"key":"9_CR13","first-page":"637","volume":"28","author":"S. Even","year":"1985","unstructured":"S. Even, O. Goldreich and A. Lempel A Randomized Protocol for Signing Contracts Communications of the ACM, Vol 28, 1985, pp. 637\u2013447.","journal-title":"A Randomized Protocol for Signing Contracts Communications of the ACM"},{"key":"9_CR14","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"352","DOI":"10.1007\/3-540-57332-1_30","volume-title":"Advances in Cryptology \u2014 Asiacrypt\u201991","author":"J. Feigenbaum","year":"1993","unstructured":"J. Feigenbaum and R. Ostrovsky A note on one-prover, instance-hiding zero-knowledge proof systems In Advances in Cryptology \u2014 Asiacrypt\u201991, Lecture Notes in Computer Science, volume 739, Springer, Berlin, 1993, pp. 352\u2013359."},{"key":"9_CR15","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1007\/3-540-49543-6_17","volume-title":"RANDOM\u2019 98, 2nd International Workshop on Randomization and Approximation Techniques in Computer Science","author":"Y. Gertner","year":"1998","unstructured":"Y. Gertner, S. Goldwasser, and T. Malkin. A random server model for private information retrieval. In M. Luby, J. Rolim, and M. Serna, editors, RANDOM\u2019 98, 2nd International Workshop on Randomization and Approximation Techniques in Computer Science, volume 1518 of Lecture Notes in Computer Science, pages 200\u2013217. Springer, 1998."},{"key":"9_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 the 30th Annu. ACM Symp. on the Theory of Computing, pages 151\u2013160, 1998.","DOI":"10.1145\/276698.276723"},{"key":"9_CR17","unstructured":"O. Goldreich. Foundations of Cryptography (fragments of a book). Electronic Colloquium on Computational Complexity, 1995. Electronic publication: http:\/\/www.eccc.uni-trier.de\/eccc-local\/ECCC-Books\/eccc-books.html ."},{"key":"9_CR18","doi-asserted-by":"crossref","unstructured":"O. Goldreich, S. Goldwasser, and N. Linial. Fault-tolerant computation in the full information model: the Two-party Case In Proc. of the 32nd Annu. IEEE Symp. on Foundations of Computer Science, pages 447\u2013457, 1991. Journal Version in SIAM J. on Computing, Vol. 27(3), 1998, pp. 505\u2013544.","DOI":"10.1109\/SFCS.1991.185405"},{"key":"9_CR19","doi-asserted-by":"crossref","unstructured":"O. Goldreich and L. Levin. A hard predicate for all one-way functions. In Proc. of the 21st Annu. ACM Symp. on the Theory of Computing, pages 25\u201332, 1989.","DOI":"10.1145\/73007.73010"},{"key":"9_CR20","doi-asserted-by":"crossref","unstructured":"O. Goldreich, S. Micali, and A. Wigderson. How to play any mental game or a completeness theorem for protocols with honest majority. In Proc. of the 19th Annu. ACM Symp. on the Theory of Computing, pages 218\u2013229, 1987.","DOI":"10.1145\/28395.28420"},{"key":"9_CR21","unstructured":"J. Hastad, R. Impagliazzo, L. A. Levin, and M. Luby. Construction of a pseudo-random generator from any one-way function. Technical Report TR-91-068, International Computer Science Institute, 1991."},{"key":"9_CR22","doi-asserted-by":"crossref","unstructured":"R. Impagliazzo and M. Luby. One-way functions are essential for complexity based cryptography. In Proc. of the 30th Annu. IEEE Symp. on Foundations of Computer Science, pages 230\u2013235, 1989.","DOI":"10.1109\/SFCS.1989.63483"},{"key":"9_CR23","doi-asserted-by":"crossref","unstructured":"R. Impagliazzo and S. Rudich. Limits on the provable consequences of one-way permutations. In Proc. of the 21st Annu. ACM Symp. on the Theory of Computing, pages 44\u201361, 1989.","DOI":"10.1145\/73007.73012"},{"key":"9_CR24","doi-asserted-by":"crossref","unstructured":"Y. Ishai and E. Kushilevitz. Improved upper bounds on information theoretic private information retrieval. In Proc. of the 31th Annu. ACM Symp. on the Theory of Computing, 1999.","DOI":"10.1145\/301250.301275"},{"key":"9_CR25","doi-asserted-by":"crossref","unstructured":"J. Kilian. Basing cryptography on oblivious transfer. In Proc. of the 20th Annu. ACM Symp. on the Theory of Computing, pages 20\u201331, 1988.","DOI":"10.1145\/62212.62215"},{"key":"9_CR26","doi-asserted-by":"crossref","unstructured":"J. Kilian. A general completeness theorem for two-party games. In Proc. of the 23th Annu. ACM Symp. on the Theory of Computing, pages 553\u2013560, 1991.","DOI":"10.1145\/103418.103475"},{"key":"9_CR27","doi-asserted-by":"crossref","unstructured":"E. Kushilevitz and R. Ostrovsky. Replication is not needed: Single database, computationally-private information retrieval. In Proc. of the 38th Annu. IEEE Symp. on Foundations of Computer Science, pages 364\u2013373, 1997.","DOI":"10.1109\/SFCS.1997.646125"},{"key":"9_CR28","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":"9_CR29","series-title":"Lect Notes Comput Sci","volume-title":"Advances in Cryptology-CRYPTO\u2019 92","author":"M. Naor","year":"1992","unstructured":"M. Naor, R. Ostrovsky, R. Venkatesan, and M. Yung. Perfect zero-knowledge arguments for NP can be based on general complexity assumptions. In E. F. Brickell, editor, Advances in Cryptology-CRYPTO\u2019 92, volume 740 of Lecture Notes in Computer Science. Springer-Verlag, 1992. Final version in J. Cryptology, 11(2):87\u2013108, 1998."},{"key":"9_CR30","doi-asserted-by":"crossref","unstructured":"M. Naor and B. Pinkas. Oblivious transfer and polynomial evaluation. In Proc. of the 31th Annu. ACM Symp. on the Theory of Computing, pages 245\u2013254, 1999.","DOI":"10.1145\/301250.301312"},{"key":"9_CR31","doi-asserted-by":"crossref","unstructured":"M. Naor and M. Yung. Universal one-way functions and their cryptographic applications. In Proc. of the 21st Annu. ACM Symp. on the Theory of Computing, pages 33\u201343, 1989.","DOI":"10.1145\/73007.73011"},{"key":"9_CR32","doi-asserted-by":"crossref","unstructured":"R. Ostrovsky and V. Shoup. Private information storage. In Proc. of the 29th Annu. ACM Symp. on the Theory of Computing, pages 294\u2013303, 1997.","DOI":"10.1145\/258533.258606"},{"key":"9_CR33","doi-asserted-by":"crossref","unstructured":"R. Ostrovsky, R. Venkatesan, and M. Yung. Fair games against an all-powerful adversary. Presented at DIMACS Complexity and Cryptography workshop, October 1990, Princeton. Prelim. version in Proc. of the Sequences II workshop 1991, Springer-Verlag, pp. 418\u2013429. Final version in AMS DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 13 Distributed Computing and Cryptography, Jin-Yi Cai, editor, pp. 155\u2013169. AMS, 1993.","DOI":"10.1090\/dimacs\/013\/09"},{"key":"9_CR34","series-title":"Lect Notes Comput Sci","first-page":"439","volume-title":"Proceedings of 9th Symposium on Theoretical Aspects of Computer Science (STACS-92)","author":"R. Ostrovsky","year":"1992","unstructured":"R. Ostrovsky, R. Venkatesan, and M. Yung. Secure Commitment Against Powerful Adversary: A Security Primitive based on Average Intractability. In Proceedings of 9th Symposium on Theoretical Aspects of Computer Science (STACS-92) (LNCS 577 Springer Verlag Ed. A. Finkel and M. Jantzen) pp. 439\u2013448 February 13\u201315 1992, Paris, France."},{"key":"9_CR35","series-title":"Lect Notes Comput Sci","volume-title":"Advances in Cryptology-EUROCRYPT\u2019 93","author":"R. Ostrovsky","year":"1993","unstructured":"R. Ostrovsky, R. Venkatesan, and M. Yung. Interactive hashing simplifies zero-knowledge protocol design. In Advances in Cryptology-EUROCRYPT\u2019 93, Lecture Notes in Computer Science. Springer-Verlag, 1993."},{"key":"9_CR36","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":"9_CR37","unstructured":"M. O. Rabin How to exchange secrets by oblivious transfer Technical Memo TR-81, Aiken Computation Laboratory, Harvard University, 1981."},{"key":"9_CR38","doi-asserted-by":"crossref","unstructured":"J. Rompel. One-way functions are necessary and sufficient for secure signatures. In Proc. of the 22nd Annu. ACM Symp. on the Theory of Computing, pages 387\u2013394, 1990.","DOI":"10.1145\/100216.100269"},{"key":"9_CR39","doi-asserted-by":"crossref","unstructured":"J. P. Stern. A new and efficient all-or-nothing disclosure of secrets protocol. In ASIACRYPT\u2019 98, 1998.","DOI":"10.1007\/3-540-49649-1_28"},{"key":"9_CR40","doi-asserted-by":"crossref","unstructured":"A. C. Yao. Theory and application of trapdoor functions. In Proc. of the 23th Annu. IEEE Symp. on Foundations of Computer Science, pages 80\u201391, 1982.","DOI":"10.1109\/SFCS.1982.45"}],"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_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,19]],"date-time":"2025-01-19T11:59:10Z","timestamp":1737287950000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45539-6_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540675174","9783540455394"],"references-count":40,"URL":"https:\/\/doi.org\/10.1007\/3-540-45539-6_9","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[2000]]}}}