@article{woodruff2007a,
author = {Woodruff, David and Yekhanin, Sergey},
title = {A geometric approach to information theoretic private information retrieval},
year = {2007},
month = {January},
abstract = {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].},
publisher = {Society for Industrial and Applied Mathematics},
url = {http://approjects.co.za/?big=en-us/research/publication/a-geometric-approach-to-information-theoretic-private-information-retrieval/},
pages = {1046-1056},
journal = {SIAM Journal on Computing},
volume = {47},
number = {4},
}