Abstract
We study the communication complexity of single-server Private Information Retrieval (PIR) protocols that are based on fundamental cryptographic primitives in a black-box manner. In this setting, we establish a tight lower bound on the number of bits communicated by the server in any polynomially-preserving construction that relies on trapdoor permutations. More specifically, our main result states that in such constructions Ω(n) bits must be communicated by the server, where n is the size of the server’s database, and this improves the Ω(n / logn) lower bound due to Haitner, Hoch, Reingold and Segev (FOCS ’07). Therefore, in the setting under consideration, the naive solution in which the user downloads the entire database turns out to be optimal up to constant multiplicative factors. We note that the lower bound we establish holds for the most generic form of trapdoor permutations, including in particular enhanced trapdoor permutations.
Technically speaking, this paper consists of two main contributions from which our lower bound is obtained. First, we derive a tight lower bound on the number of bits communicated by the sender during the commit stage of any black-box construction of a statistically-hiding bit-commitment scheme from a family of trapdoor permutations. This lower bound asymptotically matches the upper bound provided by the scheme of Naor, Ostrovsky, Venkatesan and Yung (CRYPTO ’92). Second, we improve the efficiency of the reduction of statistically-hiding commitment schemes to low-communication single-server PIR, due to Beimel, Ishai, Kushilevitz and Malkin (STOC ’99). In particular, we present a reduction that essentially preserves the communication complexity of the underlying single-server PIR protocol.
Due to space limitations a more complete version is available as [19].
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Beimel, A., Ishai, Y., Kushilevitz, E., Malkin, T.: One-way functions are essential for single-server private information retrieval. In: 31st STOC, pp. 89–98 (1999)
Cachin, C., Micali, S., Stadler, M.: Computationally private information retrieval with polylogarithmic communication. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 402–414. Springer, Heidelberg (1999)
Chang, Y.: Single database private information retrieval with logarithmic communication. In: 9th ACISP, pp. 50–61 (2004)
Chor, B., Goldreich, O., Kushilevitz, E., Sudan, M.: Private information retrieval. In: 36th FOCS, pp. 41–50 (1995)
Di Crescenzo, G., Malkin, T., Ostrovsky, R.: Single database private information retrieval implies oblivious transfer. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 122–138. Springer, Heidelberg (2000)
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. 3027, pp. 126–137. Springer, Heidelberg (2004)
Fischlin, M.: On the impossibility of constructing non-interactive statistically-secret protocols from any trapdoor one-way function. In: CT-RSA, pp. 79–95 (2002)
Gennaro, R., Gertner, Y., Katz, J.: Lower bounds on the efficiency of encryption and digital signature schemes. In: 35th STOC, pp. 417–425 (2003)
Gennaro, R., Gertner, Y., Katz, J., Trevisan, L.: Bounds on the efficiency of generic cryptographic constructions. SIAM J. Comput. 35(1), 217–246 (2005)
Gennaro, R., Lindell, Y., Malkin, T.: Enhanced versus plain trapdoor permutations for non-interactive zero-knowledge and oblivious transfer. Manuscript (2006)
Gennaro, R., Trevisan, L.: Lower bounds on the efficiency of generic cryptographic constructions. In: 41st FOCS, pp. 305–313 (2000)
Gentry, C., Ramzan, Z.: Single-database private information retrieval with constant communication rate. In: 32nd ICALP, pp. 803–815 (2005)
Gertner, Y., Kannan, S., Malkin, T., Reingold, O., Viswanathan, M.: The relationship between public key encryption and oblivious transfer. In: 41st FOCS, pp. 325–335 (2000)
Gertner, Y., Malkin, T., Reingold, O.: On the impossibility of basing trapdoor functions on trapdoor predicates. In: 42nd FOCS, pp. 126–135 (2001)
Goldreich, O.: Foundations of Cryptography, Basic Tools, vol. 1. Cambridge University Press, Cambridge (2001)
Goldreich, O.: Foundations of Cryptography, Basic Applications, vol. 2. Cambridge University Press, Cambridge (2004)
Haitner, I.: Implementing oblivious transfer using collection of dense trapdoor permutations. In: 1st TCC, pp. 394–409 (2004)
Haitner, I., Hoch, J.J., Reingold, O., Segev, G.: Finding collisions in interactive protocols – A tight lower bound on the round complexity of statistically-hiding commitments. In: 48th FOCS, pp. 669–679 (2007)
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)
Harnik, D., Naor, M.: On the compressibility of NP instances and cryptographic applications. In: 47th FOCS, pp. 719–728 (2006)
Horvitz, O., Katz, J.: Bounds on the efficiency of “black-box” commitment schemes. In: 32nd ICALP, pp. 128–139 (2005)
Impagliazzo, R., Rudich, S.: Limits on the provable consequences of one-way permutations. In: 21st STOC, pp. 44–61 (1989)
Ishai, Y., Kushilevitz, E., Ostrovsky, R.: Sufficient conditions for collision-resistant hashing. In: 2nd TCC, pp. 445–456 (2005)
Kalai, Y.T., Raz, R.: Succinct non-interactive zero-knowledge proofs with preprocessing for LOGSNP. In: 47th FOCS, pp. 355–366 (2006)
Kim, J.H., Simon, D.R., Tetali, P.: Limits on the efficiency of one-way permutation-based hash functions. In: 40th FOCS, pp. 535–542 (1999)
Kushilevitz, E., Ostrovsky, R.: Replication is NOT needed: SINGLE database, computationally-private information retrieval. In: 38th FOCS, pp. 364–373 (1997)
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. 1807, pp. 104–121. Springer, Heidelberg (2000)
Lipmaa, H.: An oblivious transfer protocol with log-squared communication. In: 8th ISC, pp. 314–328 (2005)
Lu, C.-J.: Encryption against storage-bounded adversaries from on-line strong extractors. J. Cryptology 17(1), 27–42 (2004)
Luby, M.: Pseudorandomness and Cryptographic Applications. Princeton University Press, Princeton (1996)
Naor, M., Ostrovsky, R., Venkatesan, R., Yung, M.: Perfect zero-knowledge arguments for NP using any one-way permutation. J. Cryptology 11(2), 87–108 (1998)
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–14 (2006)
Nisan, N., Zuckerman, D.: Randomness is linear in space. Journal of Computer and System Sciences 52(1), 43–52 (1996)
Ostrovsky, R., Skeith, W.E.: Algebraic lower bounds for computing on encrypted data. Cryptology ePrint Archive, Report 2007/064 (2007)
Ostrovsky, R., Skeith, W.E.: A survey of single database PIR: Techniques and applications. Cryptology ePrint Archive, Report 2007/059 (2007)
Reingold, O., Trevisan, L., Vadhan, S.P.: Notions of reducibility between cryptographic primitives. In: 1st TCC, pp. 1–20 (2004)
Rudich, S.: Limits on the provable consequences of one-way functions. PhD thesis, EECS Department, University of California, Berkeley (1988)
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. 1403, pp. 334–345. Springer, Heidelberg (1998)
Srinivasan, A., Zuckerman, D.: Computing with very weak random sources. SIAM J. Comput. 28(4), 1433–1459 (1999)
Stern, J.P.: A new efficient all-or-nothing disclosure of secrets protocol. In: Ohta, K., Pei, D. (eds.) ASIACRYPT 1998. LNCS, vol. 1514, pp. 357–371. Springer, Heidelberg (1998)
Wee, H.: One-way permutations, interactive hashing and statistically hiding commitments. In: 4th TCC, pp. 419–433 (2007)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Haitner, I., Hoch, J.J., Segev, G. (2008). A Linear Lower Bound on the Communication Complexity of Single-Server Private Information Retrieval. In: Canetti, R. (eds) Theory of Cryptography. TCC 2008. Lecture Notes in Computer Science, vol 4948. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-78524-8_25
Download citation
DOI: https://doi.org/10.1007/978-3-540-78524-8_25
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-78523-1
Online ISBN: 978-3-540-78524-8
eBook Packages: Computer ScienceComputer Science (R0)