Abstract
Remote servers need search terms from the user to complete retrieval requests. However, keeping the search terms private or confidential without undermining the server’s ability to retrieve the desired information is a problem that private information retrieval (PIR) schemes are designed to address. A study of the computational practicality of PIR by Sion and Carbunar in 2007 concluded that no existing construction is as efficient as the trivial PIR scheme — the server transferring its entire database to the client. While often cited as evidence that PIR is impractical, that paper did not examine multi-server information-theoretic PIR schemes or recent single-server lattice-based PIR schemes. In this paper, we report on a performance analysis of a single-server lattice-based scheme by Aguilar-Melchor and Gaborit, as well as two multi-server information-theoretic PIR schemes by Chor et al. and by Goldberg. Using analytical and experimental techniques, we find the end-to-end response times of these schemes to be one to three orders of magnitude (10–1000 times) smaller than the trivial scheme for realistic computation power and network bandwidth. Our results extend and clarify the conclusions of Sion and Carbunar for multi-server PIR schemes and single-server PIR schemes that do not rely heavily on number theory.
An extended version of this paper is available [25].
Access provided by Autonomous University of Puebla. Download to read the full chapter text
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
Aguilar Melchor, C., Crespin, B., Gaborit, P., Jolivet, V., Rousseau, P.: High-Speed Private Information Retrieval Computation on GPU. In: SECURWARE 2008, pp. 263–272 (2008)
Aguilar-Melchor, C., Gaborit, P.: A Lattice-Based Computationally-Efficient Private Information Retrieval Protocol. In: WEWORC 2007 (July 2007)
Asonov, D. (ed.): Querying Databases Privately. LNCS, vol. 3128. Springer, Heidelberg (2004)
Beimel, A., Ishai, Y., Malkin, T.: Reducing the Servers’ Computation in Private Information Retrieval: PIR with Preprocessing. J. Cryptol. 17(2), 125–151 (2004)
Boneh, D., Kushilevitz, E., Ostrovsky, R., Skeith III, W.E.: Public Key Encryption that Allows PIR Queries. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol. 4622, pp. 50–67. Springer, Heidelberg (2007)
Cachin, C., Micali, S., Stadler, M.A.: Computationally Private Information Retrieval with Polylogarithmic Communication. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 402–414. Springer, Heidelberg (1999)
Chor, B., Goldreich, O., Kushilevitz, E., Sudan, M.: Private Information Retrieval. In: FOCS 1995: Proceedings of the 36th Annual Symposium on the Foundations of Computer Science, pp. 41–50 (October 1995)
Chor, B., Gilboa, N.: Computationally Private Information Retrieval (extended abstract). In: STOC 1997, pp. 304–313 (1997)
Danezis, G., Dingledine, R., Mathewson, N.: Mixminion: Design of a Type III Anonymous Remailer Protocol. In: IEEE S&P, pp. 2–15 ( May 2003)
Di Crescenzo, G., et al.: Towards Practical Private Information Retrieval. Achieving Practical Private Information Retrieval Panel. In: SecureComm 2006 (August 2006), http://www.cs.sunysb.edu/~sion/research/PIR.Panel.Securecomm.2006/giovanni.pdf
Dingledine, R., Mathewson, N., Syverson, P.: Tor: The Second-Generation Onion Router. In: Proceedings of the 13th USENIX Security Symposium (August 2004)
Gentry, C., Ramzan, Z.: Single-Database Private Information Retrieval with Constant Communication Rate. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol. 3580, pp. 803–815. Springer, Heidelberg (2005)
Gertner, Y., Ishai, Y., Kushilevitz, E., Malkin, T.: Protecting Data Privacy in Private Information Retrieval Schemes. In: STOC 1998, pp. 151–160 (1998)
Ghinita, G., Kalnis, P., Khoshgozaran, A., Shahabi, C., Tan, K.L.: Private Queries in Location Based Services: Anonymizers are not Necessary. In: SIGMOD 2008, pp. 121–132 (2008)
Goldberg, I.: Percy++ project on SourceForge, http://percy.sourceforge.net/
Goldberg, I.: Improving the Robustness of Private Information Retrieval. In: Proceedings of the IEEE Symposium on Security and Privacy, pp. 131–148 (2007)
GPGPU Team: High-speed PIR computation on GPU on Assembla, http://www.assembla.com/spaces/pir_gpgpu/
Juels, A.: Targeted Advertising... And Privacy Too. In: Naccache, D. (ed.) CT-RSA 2001. LNCS, vol. 2020, pp. 408–424. Springer, Heidelberg (2001)
Kushilevitz, E., Ostrovsky, R.: Replication is not needed: single database, computationally-private information retrieval. In: FOCS 1997, p. 364 (1997)
Lipmaa, H.: An Oblivious Transfer Protocol with Log-Squared Communication. In: Zhou, J., López, J., Deng, R.H., Bao, F. (eds.) ISC 2005. LNCS, vol. 3650, pp. 314–328. Springer, Heidelberg (2005)
Moore, G.E.: Cramming More Components Onto Integrated Circuits. Electronics Magazine 38(8) (1965)
National Institute of Standards and Technology: Key Management Guideline (2007), http://csrc.nist.gov/groups/ST/toolkit/index.html
Nielsen, J.: Nielsen’s Law of Internet Bandwidth (April 1988), http://www.useit.com/alertbox/980405.html
Olumofin, F., Goldberg, I.: Privacy-Preserving Queries over Relational Databases. In: Atallah, M.J., Hopper, N.J. (eds.) PETS 2010. LNCS, vol. 6205, pp. 75–92. Springer, Heidelberg (2010)
Olumofin, F., Goldberg, I.: Revisiting the Computational Practicality of Private Information Retrieval. Tech. rep., CACR 2010-17, University of Waterloo (2010), http://www.cacr.math.uwaterloo.ca/techreports/2010/cacr2010-17.pdf
Ookla: Canada and US Source Data, http://www.netindex.com/source-data/
Shamir, A.: How to Share a Secret. Commun. ACM 22(11), 612–613 (1979)
Sion, R., Carbunar, B.: On the Computational Practicality of Private Information Retrieval. In: NDSS 2007 (2007)
Trostle, J., Parrish, A.: Efficient Computationally Private Information Retrieval From Anonymity or Trapdoor Groups. ePrint 2007/392 (2007)
Weiss, A.R.: Dhrystone Benchmark: History, Analysis, Scores and Recommendations. EEMBC White Paper (2002)
Wieschebrink, C.: Two NP-complete Problems in Coding Theory with an Application in Code Based Cryptography. In: ISIT 2006, pp. 1733–1737 (July 2006)
Yoshida, R., Shigetomi, Y.C., Imai, R., The Practicality, H.: of the Keyword Search Using PIR. In: ISITA 2008, pp. 1–6 (December 2008)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Olumofin, F., Goldberg, I. (2012). Revisiting the Computational Practicality of Private Information Retrieval. In: Danezis, G. (eds) Financial Cryptography and Data Security. FC 2011. Lecture Notes in Computer Science, vol 7035. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-27576-0_13
Download citation
DOI: https://doi.org/10.1007/978-3-642-27576-0_13
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-27575-3
Online ISBN: 978-3-642-27576-0
eBook Packages: Computer ScienceComputer Science (R0)