A geometric approach to information-theoretic private information retrieval

A t-private private information retrieval (PIR) scheme allows a user to retrieve the ith bit of an n-bit string x replicated among k servers, while any coalition of up to t servers learns no information about i. We present a new geometric approach to PIR and obtain the following: (1) A t-private k-server protocol with communication O(k(2)/t logk n(1/[(2k-1)/t])), removing the kt term of previous schemes. This answers an open question of [Y. Ishai and E. Kushilevitz, in Proceedings of the 31st ACM Symposium on Theory of Computing, 1999, pp. 79-88]. (2) A 2-server protocol with O(n1/3) communication, polynomial preprocessing, and online work O(n/log(r) n) for any constant r. This improves the O(n/log(2) n) work of [A. Beimel, Y. Ishai, and T. Malkin, J. Cryptology, 17 (2004), pp. 125-151]. (3) Smaller communication for instance hiding [D. Beaver, J. Feigenbaum, J. Kilian, and P. Rogaway, J. Cryptology, 10 (1997), pp. 17-36; Y. Ishai and E. Kushilevitz, in Proceedings of the 31st ACM Symposium on Theory of Computing, 1999, pp. 79-88], PIR with a polylogarithmic number of servers, and robust PIR [A. Beimel and Y. Stahl, in Proceedings of the 3rd Conference on Security in Communications Networks (SCN 2002), Lecture Notes in Comput. Sci. 2576, Springer, Berlin, 2003, pp. 326-341].