{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,13]],"date-time":"2026-08-13T16:26:34Z","timestamp":1786638394220,"version":"build-2736575974"},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540679073","type":"print"},{"value":"9783540445982","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-44598-6_4","type":"book-chapter","created":{"date-parts":[[2007,5,1]],"date-time":"2007-05-01T10:15:21Z","timestamp":1178014521000},"page":"55-73","source":"Crossref","is-referenced-by-count":93,"title":["Reducing the Servers Computation in Private Information Retrieval: PIR with Preprocessing"],"prefix":"10.1007","author":[{"given":"Amos","family":"Beimel","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yuval","family":"Ishai","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tal","family":"Malkin","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2000,8,11]]},"reference":[{"key":"4_CR1","doi-asserted-by":"crossref","unstructured":"W. Aiello, S. Bhatt, R. Ostrovsky, and S. Rajagopalan. Fast Verification of Any Remote Procedure Call: Short Witness-Indistinguishable One-Round Proofs for NP. In ICALP 2000.","DOI":"10.1007\/3-540-45022-X_39"},{"key":"4_CR2","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"401","DOI":"10.1007\/3-540-63165-8_196","volume-title":"24th ICALP","author":"A. Ambainis","year":"1997","unstructured":"A. Ambainis. Upper bound on the communication complexity of private information retrieval. In 24th ICALP, volume 1256 of LNCS, pages 401\u2013407, 1997."},{"key":"4_CR3","doi-asserted-by":"crossref","unstructured":"A. Ambainis and S. Lokam. Improved upper bounds on the simultaneous messages complexity of the generalized addressing function. In LATIN 2000.","DOI":"10.1007\/10719839_21"},{"key":"4_CR4","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1007\/3-540-59042-0_88","volume-title":"12th STACS","author":"L. Babai","year":"1995","unstructured":"L. Babai, P. Kimmel, and S. Lokam. Simultaneous messages vs. communication. In 12th STACS, volume 900 of LNCS, pages 361\u2013372, 1995."},{"key":"4_CR5","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1007\/3-540-52282-4_30","volume-title":"7th STACS","author":"D. Beaver","year":"1990","unstructured":"D. Beaver and J. Feigenbaum. Hiding instances in multioracle queries. In 7th STACS, volume 415 of LNCS, pages 37\u201348. Springer-Verlag, 1990."},{"key":"4_CR6","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1007\/s001459900017","volume":"10","author":"D. Beaver","year":"1997","unstructured":"D. Beaver, J. Feigenbaum, J. Kilian, and P. Rogaway. Locally random reductions: Improvements and applications. J. of Cryptology, 10:17\u201336, 1997. Early version: Security with small communication overhead, CRYPTO\u2019 90.","journal-title":"J. of Cryptology"},{"key":"4_CR7","unstructured":"A. Beimel and Y. Ishai. On private information retrieval and low-degree polynomials. Manuscript, 2000."},{"key":"4_CR8","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 31th STOC, pages 89\u201398, 1999.","DOI":"10.1145\/301250.301277"},{"key":"4_CR9","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"402","DOI":"10.1007\/3-540-48910-X_28","volume-title":"EUROCRYPT\u2019 99","author":"C. Cachin","year":"1999","unstructured":"C. Cachin, S. Micali, and M. Stadler. Computationally private information retrieval with polylogarithmic communication. In EUROCRYPT\u2019 99, volume 1592 of LNCS, pages 402\u2013414. Springer, 1999."},{"key":"4_CR10","doi-asserted-by":"crossref","unstructured":"B. Chor and N. Gilboa. Computationally private information retrieval. In 29th STOC, pages 304\u2013313, 1997.","DOI":"10.1145\/258533.258609"},{"key":"4_CR11","doi-asserted-by":"crossref","unstructured":"B. Chor, O. Goldreich, E. Kushilevitz, and M. Sudan. Private information retrieval. In 36th FOCS, pages 41\u201351, 1995. Journal version: JACM, 45:965\u2013981, 1998.","DOI":"10.1145\/293347.293350"},{"key":"4_CR12","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":"4_CR13","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/S0747-7171(08)80013-2","volume":"9","author":"D. Coppersmith","year":"1990","unstructured":"D. Coppersmith and S. Winograd. Matrix multiplication via arithmetic progressions. J. Symbolic Comput., 9:251\u2013280, 1990.","journal-title":"J. Symbolic Comput."},{"key":"4_CR14","doi-asserted-by":"crossref","unstructured":"G. Di-Crescenzo, Y. Ishai, and R. Ostrovsky. Universal service-providers for database private information retrieval. In 17th PODC, pages 91\u2013100, 1998.","DOI":"10.1145\/277697.277713"},{"key":"4_CR15","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1007\/3-540-45539-6_10","volume-title":"EUROCRYPT 2000","author":"G. Di-Crescenzo","year":"2000","unstructured":"G. Di-Crescenzo, T. Malkin, and R. Ostrovsky. Single-database private information retrieval implies oblivious transfer. In EUROCRYPT 2000, volume 1807 of LNCS, pages 122\u2013138, 2000."},{"key":"4_CR16","doi-asserted-by":"crossref","unstructured":"Y. Dodis. Space-Time Tradeoffs for Graph Properties. Master\u2019s thesis, Massachusetts Institute of Technology, 1998.","DOI":"10.1007\/3-540-48523-6_26"},{"key":"4_CR17","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 Workshop on Randomization and Approximation Techniques in CS","author":"Y. Gertner","year":"1998","unstructured":"Y. Gertner, S. Goldwasser, and T. Malkin. A random server model for private information retrieval. In RANDOM\u2019 98, 2nd Workshop on Randomization and Approximation Techniques in CS, vol. 1518 of LNCS, pages 200\u2013217. 1998."},{"key":"4_CR18","doi-asserted-by":"crossref","unstructured":"Y. Gertner, Y. Ishai, E. Kushilevitz, and T. Malkin. Protecting data privacy in private information retrieval schemes. In 30th STOC, pages 151\u2013160, 1998.","DOI":"10.1145\/276698.276723"},{"key":"4_CR19","doi-asserted-by":"crossref","unstructured":"Y. Ishai and E. Kushilevitz. Improved upper bounds on information theoretic private information retrieval. In 31th STOC, pages 79\u201388, 1999.","DOI":"10.1145\/301250.301275"},{"key":"4_CR20","doi-asserted-by":"crossref","unstructured":"E. Kushilevitz and R. Ostrovsky. Replication is not needed: Single database, computationally-private information retrieval. In 38th FOCS, pages 364\u2013373, 1997.","DOI":"10.1109\/SFCS.1997.646125"},{"key":"4_CR21","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1007\/3-540-45539-6_9","volume-title":"EUROCRYPT 2000","author":"E. Kushilevitz","year":"2000","unstructured":"E. Kushilevitz and R. Ostrovsky. One-way trapdoor permutations are sufficient for non-trivial single-server private information retrieval. In EUROCRYPT 2000, volume 1807 of LNCS, pages 104\u2013121, 2000."},{"key":"4_CR22","doi-asserted-by":"crossref","unstructured":"J. H. van Lint. Introduction to Coding Theory. Springer-Verlag, 1982.","DOI":"10.1007\/978-3-662-07998-0"},{"key":"4_CR23","unstructured":"T. Malkin. A Study of Secure Database Access and General Two-Party Computation. PhD thesis, MIT, 2000. http:\/\/theory.lcs.mit.edu\/~cis\/cis-theses.html ."},{"key":"4_CR24","volume-title":"Master\u2019s thesis","author":"E. Mann","year":"1998","unstructured":"E. Mann. Private access to distributed information. Master\u2019s thesis, Technion-Israel Institute of Technology, Haifa, 1998."},{"key":"4_CR25","doi-asserted-by":"crossref","unstructured":"R. Ostrovsky and V. Shoup. Private information storage. In 29th STOC, pages 294\u2013303, 1997.","DOI":"10.1145\/258533.258606"},{"key":"4_CR26","doi-asserted-by":"crossref","unstructured":"P. Pudl\u00e1k and V. R\u00f6dl. Modified Ranks of Tensors and the Size of Circuits. In 25th STOC, pages 523\u2013531, 1993.","DOI":"10.1145\/167088.167228"},{"key":"4_CR27","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1007\/3-540-49649-1_28","volume-title":"ASIACRYPT\u2019 98","author":"J. P. Stern","year":"1998","unstructured":"J. P. Stern. A new and efficient all-or-nothing disclosure of secrets protocol. In ASIACRYPT\u2019 98, volume 1514 of LNCS, pages 357\u2013371. Springer, 1998."},{"key":"4_CR28","doi-asserted-by":"publisher","first-page":"615","DOI":"10.1145\/322261.322274","volume":"28","author":"A.C. Yao","year":"1981","unstructured":"A.C. Yao. Should tables be sorted? JACM, 28:615\u2013628, 1981.","journal-title":"JACM"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2014 CRYPTO 2000"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44598-6_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,16]],"date-time":"2025-01-16T00:06:19Z","timestamp":1736985979000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44598-6_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540679073","9783540445982"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/3-540-44598-6_4","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[2000]]}}}