Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR05-009 | 14th December 2004 00:00

A Geometric Approach to Information-Theoretic Private Information Retrieval


Authors: David P. Woodruff, Sergey Yekhanin
Publication: 18th January 2005 19:48
Downloads: 1986


A t-private private information retrieval (PIR) scheme allows a user to retrieve the i-th 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 smaller communication complexity, answering an open question of [IK99], (2) A 2-server protocol with n^{1/3} communication, polynomial preprocessing, and online work O(n/log^r n) for any constant r, improving the O(n/log^2 n ) work of Beimel et al [BIM00], and (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 of [BIKR02].

ISSN 1433-8092 | Imprint