{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,29]],"date-time":"2025-01-29T05:49:50Z","timestamp":1738129790723,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":41,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540785231"},{"type":"electronic","value":"9783540785248"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-78524-8_25","type":"book-chapter","created":{"date-parts":[[2008,2,25]],"date-time":"2008-02-25T09:18:12Z","timestamp":1203931092000},"page":"445-464","source":"Crossref","is-referenced-by-count":4,"title":["A Linear Lower Bound on the Communication Complexity of Single-Server Private Information Retrieval"],"prefix":"10.1007","author":[{"given":"Iftach","family":"Haitner","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jonathan J.","family":"Hoch","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gil","family":"Segev","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"25_CR1","doi-asserted-by":"crossref","unstructured":"Beimel, A., Ishai, Y., Kushilevitz, E., Malkin, T.: One-way functions are essential for single-server private information retrieval. In: 31st STOC, pp. 89\u201398 (1999)","DOI":"10.1145\/301250.301277"},{"key":"25_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"402","DOI":"10.1007\/3-540-48910-X_28","volume-title":"Advances in Cryptology - EUROCRYPT 1999","author":"C. Cachin","year":"1999","unstructured":"Cachin, C., Micali, S., Stadler, M.: Computationally private information retrieval with polylogarithmic communication. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol.\u00a01592, pp. 402\u2013414. Springer, Heidelberg (1999)"},{"key":"25_CR3","doi-asserted-by":"crossref","unstructured":"Chang, Y.: Single database private information retrieval with logarithmic communication. In: 9th ACISP, pp. 50\u201361 (2004)","DOI":"10.1007\/978-3-540-27800-9_5"},{"key":"25_CR4","doi-asserted-by":"crossref","unstructured":"Chor, B., Goldreich, O., Kushilevitz, E., Sudan, M.: Private information retrieval. In: 36th FOCS, pp. 41\u201350 (1995)","DOI":"10.1109\/SFCS.1995.492461"},{"key":"25_CR5","series-title":"Lecture Notes in Computer Science","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":"Di Crescenzo, G., Malkin, T., Ostrovsky, R.: Single database private information retrieval implies oblivious transfer. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol.\u00a01807, pp. 122\u2013138. Springer, Heidelberg (2000)"},{"key":"25_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"126","DOI":"10.1007\/978-3-540-24676-3_8","volume-title":"Advances in Cryptology - EUROCRYPT 2004","author":"S. Dziembowski","year":"2004","unstructured":"Dziembowski, S., Maurer, U.M.: On generating the initial key in the bounded-storage model. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol.\u00a03027, pp. 126\u2013137. Springer, Heidelberg (2004)"},{"key":"25_CR7","doi-asserted-by":"crossref","unstructured":"Fischlin, M.: On the impossibility of constructing non-interactive statistically-secret protocols from any trapdoor one-way function. In: CT-RSA, pp. 79\u201395 (2002)","DOI":"10.1007\/3-540-45760-7_7"},{"key":"25_CR8","doi-asserted-by":"crossref","unstructured":"Gennaro, R., Gertner, Y., Katz, J.: Lower bounds on the efficiency of encryption and digital signature schemes. In: 35th STOC, pp. 417\u2013425 (2003)","DOI":"10.1145\/780542.780604"},{"issue":"1","key":"25_CR9","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1137\/S0097539704443276","volume":"35","author":"R. Gennaro","year":"2005","unstructured":"Gennaro, R., Gertner, Y., Katz, J., Trevisan, L.: Bounds on the efficiency of generic cryptographic constructions. SIAM J. Comput.\u00a035(1), 217\u2013246 (2005)","journal-title":"SIAM J. Comput."},{"key":"25_CR10","unstructured":"Gennaro, R., Lindell, Y., Malkin, T.: Enhanced versus plain trapdoor permutations for non-interactive zero-knowledge and oblivious transfer. Manuscript (2006)"},{"key":"25_CR11","doi-asserted-by":"crossref","unstructured":"Gennaro, R., Trevisan, L.: Lower bounds on the efficiency of generic cryptographic constructions. In: 41st FOCS, pp. 305\u2013313 (2000)","DOI":"10.1109\/SFCS.2000.892119"},{"key":"25_CR12","doi-asserted-by":"crossref","unstructured":"Gentry, C., Ramzan, Z.: Single-database private information retrieval with constant communication rate. In: 32nd ICALP, pp. 803\u2013815 (2005)","DOI":"10.1007\/11523468_65"},{"key":"25_CR13","doi-asserted-by":"crossref","unstructured":"Gertner, Y., Kannan, S., Malkin, T., Reingold, O., Viswanathan, M.: The relationship between public key encryption and oblivious transfer. In: 41st FOCS, pp. 325\u2013335 (2000)","DOI":"10.1109\/SFCS.2000.892121"},{"key":"25_CR14","doi-asserted-by":"crossref","unstructured":"Gertner, Y., Malkin, T., Reingold, O.: On the impossibility of basing trapdoor functions on trapdoor predicates. In: 42nd FOCS, pp. 126\u2013135 (2001)","DOI":"10.1109\/SFCS.2001.959887"},{"key":"25_CR15","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511546891","volume-title":"Foundations of Cryptography, Basic Tools","author":"O. Goldreich","year":"2001","unstructured":"Goldreich, O.: Foundations of Cryptography, Basic Tools, vol.\u00a01. Cambridge University Press, Cambridge (2001)"},{"key":"25_CR16","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511721656","volume-title":"Foundations of Cryptography, Basic Applications","author":"O. Goldreich","year":"2004","unstructured":"Goldreich, O.: Foundations of Cryptography, Basic Applications, vol.\u00a02. Cambridge University Press, Cambridge (2004)"},{"key":"25_CR17","doi-asserted-by":"crossref","unstructured":"Haitner, I.: Implementing oblivious transfer using collection of dense trapdoor permutations. In: 1st TCC, pp. 394\u2013409 (2004)","DOI":"10.1007\/978-3-540-24638-1_22"},{"key":"25_CR18","doi-asserted-by":"crossref","unstructured":"Haitner, I., Hoch, J.J., Reingold, O., Segev, G.: Finding collisions in interactive protocols \u2013 A tight lower bound on the round complexity of statistically-hiding commitments. In: 48th FOCS, pp. 669\u2013679 (2007)","DOI":"10.1109\/FOCS.2007.7"},{"key":"25_CR19","unstructured":"Haitner, I., Hoch, J.J., Segev, G.: A linear lower bound on the communication complexity of single-server private information retrieval. Cryptology ePrint Archive, Report 2007\/351 (2007)"},{"key":"25_CR20","doi-asserted-by":"crossref","unstructured":"Harnik, D., Naor, M.: On the compressibility of NP instances and cryptographic applications. In: 47th FOCS, pp. 719\u2013728 (2006)","DOI":"10.1109\/FOCS.2006.54"},{"key":"25_CR21","doi-asserted-by":"crossref","unstructured":"Horvitz, O., Katz, J.: Bounds on the efficiency of \u201cblack-box\u201d commitment schemes. In: 32nd ICALP, pp. 128\u2013139 (2005)","DOI":"10.1007\/11523468_11"},{"key":"25_CR22","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Rudich, S.: Limits on the provable consequences of one-way permutations. In: 21st STOC, pp. 44\u201361 (1989)","DOI":"10.1145\/73007.73012"},{"key":"25_CR23","doi-asserted-by":"crossref","unstructured":"Ishai, Y., Kushilevitz, E., Ostrovsky, R.: Sufficient conditions for collision-resistant hashing. In: 2nd TCC, pp. 445\u2013456 (2005)","DOI":"10.1007\/978-3-540-30576-7_24"},{"key":"25_CR24","doi-asserted-by":"crossref","unstructured":"Kalai, Y.T., Raz, R.: Succinct non-interactive zero-knowledge proofs with preprocessing for LOGSNP. In: 47th FOCS, pp. 355\u2013366 (2006)","DOI":"10.1109\/FOCS.2006.74"},{"key":"25_CR25","unstructured":"Kim, J.H., Simon, D.R., Tetali, P.: Limits on the efficiency of one-way permutation-based hash functions. In: 40th FOCS, pp. 535\u2013542 (1999)"},{"key":"25_CR26","doi-asserted-by":"crossref","unstructured":"Kushilevitz, E., Ostrovsky, R.: Replication is NOT needed: SINGLE database, computationally-private information retrieval. In: 38th FOCS, pp. 364\u2013373 (1997)","DOI":"10.1109\/SFCS.1997.646125"},{"key":"25_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1007\/3-540-45539-6_9","volume-title":"Advances in Cryptology - EUROCRYPT 2000","author":"E. Kushilevitz","year":"2000","unstructured":"Kushilevitz, E., Ostrovsky, R.: One-way trapdoor permutations are sufficient for non-trivial single-server private information retrieval. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol.\u00a01807, pp. 104\u2013121. Springer, Heidelberg (2000)"},{"key":"25_CR28","doi-asserted-by":"crossref","unstructured":"Lipmaa, H.: An oblivious transfer protocol with log-squared communication. In: 8th ISC, pp. 314\u2013328 (2005)","DOI":"10.1007\/11556992_23"},{"issue":"1","key":"25_CR29","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1007\/s00145-003-0217-1","volume":"17","author":"C.-J. Lu","year":"2004","unstructured":"Lu, C.-J.: Encryption against storage-bounded adversaries from on-line strong extractors. J. Cryptology\u00a017(1), 27\u201342 (2004)","journal-title":"J. Cryptology"},{"key":"25_CR30","doi-asserted-by":"crossref","DOI":"10.1515\/9780691206844","volume-title":"Pseudorandomness and Cryptographic Applications","author":"M. Luby","year":"1996","unstructured":"Luby, M.: Pseudorandomness and Cryptographic Applications. Princeton University Press, Princeton (1996)"},{"issue":"2","key":"25_CR31","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1007\/s001459900037","volume":"11","author":"M. Naor","year":"1998","unstructured":"Naor, M., Ostrovsky, R., Venkatesan, R., Yung, M.: Perfect zero-knowledge arguments for NP using any one-way permutation. J. Cryptology\u00a011(2), 87\u2013108 (1998)","journal-title":"J. Cryptology"},{"key":"25_CR32","doi-asserted-by":"crossref","unstructured":"Nguyen, M.-H., Ong, S.J., Vadhan, S.P.: Statistical zero-knowledge arguments for NP from any one-way function. In: 47th FOCS, pp. 3\u201314 (2006)","DOI":"10.1109\/FOCS.2006.71"},{"issue":"1","key":"25_CR33","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1006\/jcss.1996.0004","volume":"52","author":"N. Nisan","year":"1996","unstructured":"Nisan, N., Zuckerman, D.: Randomness is linear in space. Journal of Computer and System Sciences\u00a052(1), 43\u201352 (1996)","journal-title":"Journal of Computer and System Sciences"},{"key":"25_CR34","unstructured":"Ostrovsky, R., Skeith, W.E.: Algebraic lower bounds for computing on encrypted data. Cryptology ePrint Archive, Report 2007\/064 (2007)"},{"key":"25_CR35","unstructured":"Ostrovsky, R., Skeith, W.E.: A survey of single database PIR: Techniques and applications. Cryptology ePrint Archive, Report 2007\/059 (2007)"},{"key":"25_CR36","doi-asserted-by":"crossref","unstructured":"Reingold, O., Trevisan, L., Vadhan, S.P.: Notions of reducibility between cryptographic primitives. In: 1st TCC, pp. 1\u201320 (2004)","DOI":"10.1007\/978-3-540-24638-1_1"},{"key":"25_CR37","unstructured":"Rudich, S.: Limits on the provable consequences of one-way functions. PhD thesis, EECS Department, University of California, Berkeley (1988)"},{"key":"25_CR38","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"334","DOI":"10.1007\/BFb0054137","volume-title":"Advances in Cryptology - EUROCRYPT 1998","author":"D.R. Simon","year":"1998","unstructured":"Simon, D.R.: Finding collisions on a one-way street: Can secure hash functions be based on general assumptions? In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol.\u00a01403, pp. 334\u2013345. Springer, Heidelberg (1998)"},{"issue":"4","key":"25_CR39","doi-asserted-by":"publisher","first-page":"1433","DOI":"10.1137\/S009753979630091X","volume":"28","author":"A. Srinivasan","year":"1999","unstructured":"Srinivasan, A., Zuckerman, D.: Computing with very weak random sources. SIAM J. Comput.\u00a028(4), 1433\u20131459 (1999)","journal-title":"SIAM J. Comput."},{"key":"25_CR40","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1007\/3-540-49649-1_28","volume-title":"Advances in Cryptology - ASIACRYPT 1998","author":"J.P. Stern","year":"1998","unstructured":"Stern, J.P.: A new efficient all-or-nothing disclosure of secrets protocol. In: Ohta, K., Pei, D. (eds.) ASIACRYPT 1998. LNCS, vol.\u00a01514, pp. 357\u2013371. Springer, Heidelberg (1998)"},{"key":"25_CR41","doi-asserted-by":"crossref","unstructured":"Wee, H.: One-way permutations, interactive hashing and statistically hiding commitments. In: 4th TCC, pp. 419\u2013433 (2007)","DOI":"10.1007\/978-3-540-70936-7_23"}],"container-title":["Lecture Notes in Computer Science","Theory of Cryptography"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-78524-8_25.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,28]],"date-time":"2025-01-28T18:31:31Z","timestamp":1738089091000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-78524-8_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540785231","9783540785248"],"references-count":41,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-78524-8_25","relation":{},"subject":[]}}