Introduction

Publicly accessible databases are an indispensable resource for retrieving up to date information. But they also pose a significant risk to the privacy of the user, since a curious database operator can follow the users queries and infer what the user is after. Indeed, in cases where the users' intensions are to be kept secret, users are often cautious about accessing the database.

The problem of protecting the privacy of the user accessing a public database was formalized in [4]. The database is represented by a binary vector x of length n. It is assumed that the user wants to learn the value of a certain bit x_i. Note that this problem allows a trivial solution: the user may request the value of every bit of the database. Clearly, in such a protocol the user's privacy is perfectly protected. However, there is a huge increase in the amount of communication needed for such a protocol. The user needs to communicate O(n) bits instead of O(log n) in the usual (non-private) scheme. In [4] it is shown that for a user accessing a single database, the trivial approach described above is the best possible. In order to reduce the communication complexity of private information retrieval (PIR) schemes, the authors of [4] propose to consider the scenario where the user is able to access k>1 replicated copies of the same database, and privately retrieve information. This means that every individual server (holding a replicated copy of the database) gets no information about the identity of the item retrieved by the user. Surprisingly even considering the case k=2, allows to decrease the communication complexity of PIR protocols from O(n) to O(n^{1/3}).

The initial work of [4] has drawn a lot of attention from other researchers in the fields of cryptography, complexity theory and the theory of error-correcting codes. The extensive online bibliography is available at [3].

Progress

The main problem of the PIR related research is to reduce the communication complexity of PIR protocols. Following the seminal work of [4] a sequence of improvements had been obtained. The most important improvements appeared in [1] and [2]. In [5] we introduce a new unifying approach to PIR. Our approach allows simpler and more intuitive proofs of many of the previously known bounds. We also obtain improvements (by polynomial factors) for various generalized settings of the PIR problem.

Future

In spite of the large amount of work done by many researchers in the field of private information retrieval, the most important questions that have been raised in [4] are still far from resolution. The burning problem is to understand whether PIR protocols involving constant number of servers require polynomial (or poly-logarithmic) amount of communication. In our future work we plan to focus on improving the parameters of the PIR protocols. One route that we believe promising is to improve the understanding of a relation between an exceptionally good class of error-correcting codes (known as algebraic-geometry codes) and locally decodable codes. Better understanding of this relation may allow us to use powerful tools of algebra and algebraic geometry in designing the PIR protocols.

Research Support

This project was supported in part by NTT Award MIT 2001-2004 and NSF grant CCR 0219218.

References

[1] A. Ambainis. Upper bound on the communication complexity of private information retrieval. In The Proceedings of the 24th International Colloquium on Automata, Languages and Programming (ICALP), LNCS 1256, pp. 401--407, 1997.

[2] A. Beimel, Y. Ishai, E. Kushelevitz and J. F. Raymond. Breaking the O(n^{1/(2k-1)}) barrier for information-theoretic private information retrieval. In The Proceedings of the 43rd IEEE Symposium on Foundations of Computer Science (FOCS), pp. 261--270, 2002.

[3] W. Gasarch. A web-page on private information retrieval, http://www.cs.umd.edu/gasarch/pir/pir.html

[4] B. Chor, O. Goldreich, E. Kushelevitz and M. Sudan. Private information retrieval. In The Proceedings of the 36th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 41--50, 1995. Also in the Journal of the ACM, 45, 1998.

[5] D. Woodruff and S. Yekhanin. A geometric approach to information theoretic private information retrieval. In The Proceedings of IEEE Conference on Computational Complexity 2005, to appear.