Abstract
A private information retrieval (PIR) protocol allows a user to retrieve one of N records from a database while hiding the identity of the record from the database server.
With the initially proposed PIR protocols to process a query, the server has to process the entire database, resulting in an unacceptable response time for large databases. Later solutions make use of some preprocessing and offline communication, such that only O(1) online computation and communication are performed to execute a query. The major drawback of these solutions is offline communication, comparable to the size of the entire database.
Using a secure coprocessor we construct a PIR scheme that eliminates both drawbacks. Our protocol requires O(1) online computation and communication, periodical preprocessing, and zero offline communication. The protocol is almost optimal. The only parameter left to improve is the server’s preprocessing complexity - the least important one.
This research was supported by the German Research Society, Berlin-Brandenburg Graduate School in Distributed Information Systems (DFG grant no. GRK 316.)
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
D. Asonov and J.-C. Freytag. Almost optimal private information retrieval. Tech. Report HUB-IB-156, Humboldt University Berlin, November 2001.
D. Asonov and J.-C. Freytag. Private information retrieval, optimal for users and secure coprocessors. Tech. Report HUB-IB-159, Humboldt University Berlin, May 2001.
A. Ambainis. Upper bound on the communication complexity of private information retrieval. In Proceedings of 24th ICALP, 1997.
D. Asonov. Private information retrieval-an overview and current trends. In Proceedings of the ECDPvA Workshop, Informatik 2001, Vienna, Austria, September 2001.
F. Bao, R. H. Deng, and P. Feng. An efficient and practical scheme for privacy protection in the e-commerce of digital goods. In Proc. of the 3rd Intl. Conference on Information Security and Cryptology, December 2000.
A. Beimel and Y. Ishai. Information-theoretic private information retrieval: A unified construction. ECCC Report TR01-015, February 2001.
A. Beimel, Y. Ishai, and T. Malkin. Reducing the servers computation in private information retrieval: PIR with preprocessing. In Proceedings of CRYPTO’00, 2000.
B. Chor and N. Gilboa. Computationally private information retrieval. In Proceedings of 29th STOC, 1997.
B. Chor, O. Goldreich, E. Kushilevitz, and M. Sudan. Private information retrieval. In Proceedings of 36th FOCS, 1995.
G. D. Crescenzo, Y. Ishai, and R. Ostrovsky. Universal service-providers for database private information retrieval. In Proceedings of 17th PODC, 1998.
C. Cachin, S. Micali, and M. Stadler. Computationally private information retrieval with polylogarithmic communication. In Proceedings of EURO-CRYPT’99, 1999.
J. G. Dyer, M. Lindemann, R. Perez, R. Sailer, L. Doorn, S. Smith, and S. Weingart. Building the IBM 4758 Secure Coprocessor. In IEEE Computer, 43(10), October 2001.
Y. Gertner, S. Goldwasser, and T. Malkin. A random server model for private information retrieval. In Proceedings of 2nd RANDOM, 1998.
E. T. Jaynes. Probability theory: the logic of science. http://omega.math.albany.edu:8008/JaynesBook.html, 1994.
D. E. Knuth. The art of computer programming, volume 2. Addison-Wesley, second edition, Jan 1981.
E. Kushilevitz and R. Ostrovsky. Replication is NOT needed: Single-database computationally private information retrieval. In Proceedings of 38th FOCS, 1997.
A. Kiayias and M. Yung. Secure games with polynomial expressions. In Proceedings of 28th ICALP, 2001.
B. Schneier. Applied Cryptography. Wiley, New York, 2nd edition, 1996.
Shannon. A mathematical theory of communication. Bell Systems Technical Journal, 27, 1948.
C. P. Schnorr and M. Jakobsson. Security of signed elgamal encryption. In Proceedings of ASIACRYPT’00, LNCS 1976, December 2000.
S. W. Smith, E. R. Palmer, and S. H. Weingart. Using a high-performance, programmable secure coprocessor. In Proceedings of the 2nd International Conference on Financial Cryptography, February 1998.
S. W. Smith and D. Safford. Practical private information retrieval with secure coprocessors. Technical report, IBM Research Division, T.J. Watson Research Center, July 2000.
S. W. Smith and D. Safford. Practical server privacy with secure coprocessors. IBM Systems Journal, 40(3), September 2001.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Asonov, D., Freytag, JC. (2003). Almost Optimal Private Information Retrieval. In: Dingledine, R., Syverson, P. (eds) Privacy Enhancing Technologies. PET 2002. Lecture Notes in Computer Science, vol 2482. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-36467-6_16
Download citation
DOI: https://doi.org/10.1007/3-540-36467-6_16
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-00565-0
Online ISBN: 978-3-540-36467-2
eBook Packages: Springer Book Archive