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: 1) a t-private k-server protocol with communication O((k²/t) log k n¹└/(2k - 1)┘) removing the (t) term of previous schemes. This answers an open question of Ishai and Kushilevitz (1999). 2) A 2-server protocol with O(n¹3/) communication, polynomial preprocessing, and online work O(n/log^r n) for any constant r. This improves the O(n/log² n) work of Beimel et al. (2000). 3) Smaller communication for instance hiding, PIR with a polylogarithmic number of servers, robust PIR, and PIR with fixed answer sizes. To illustrate the power of our approach, we also give alternative, geometric proofs of some of the best 1-private upper bounds.