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 O ( k(2)/t log k n(1)/ [(2k-I)/1t]), removing the ((k)(t)) term of previous schemes. This answers an open question of [14]. (.)A 2-server protocol with 0(n(1/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 [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 I-private upper bounds from [7].