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 • A t-private k-server protocol with communication Ok2 t logk n1/b(2k−1)/tc, removing the kt
term of previous schemes. This answers an open question of [14]. • A 2-server protocol with O(n1/3) communication, polynomial preprocessing, and online work O(n/logr n) for any constant r. This improves the O(n/log2 n) work of [8]. • Smaller communication for instance hiding [3, 14], PIR with a polylogarithmic number of servers, robust PIR [9], and PIR with fixed answer sizes [4]. To illustrate the power of our approach, we also give alternative, geometric proofs of some of the best 1-private upper bounds from [7].