A Geometric Approach to Information-Theoretic Private Information Retrieval
David P. Woodruff, Sergey Yekhanin · 2005
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/sup 2//t) log k n/sup 1//spl lfloor//(2k - 1)/spl rfloor/) 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/sup 1/3/) communication, polynomial preprocessing, and online work O(n/log/sup r/ n) for any constant r. This improves the O(n/log/sup 2/ 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.