loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
20th Annual IEEE Conference on Computational Complexity (CCC'05)
A Geometric Approach to Information-Theoretic Private Information Retrieval
San Jose, CA
June 11-June 15
ISBN: 0-7695-2364-1
ASCII Text
x 
 
David Woodruff, Sergey Yekhanin, "A Geometric Approach to Information-Theoretic Private Information Retrieval," Computational Complexity, Annual IEEE Conference on, pp. 275-284, 20th Annual IEEE Conference on Computational Complexity (CCC'05), 2005.
 
 
BibTex
x
 
@article{ 10.1109/CCC.2005.2,
author = {David Woodruff and Sergey Yekhanin},
title = {A Geometric Approach to Information-Theoretic Private Information Retrieval},
journal ={Computational Complexity, Annual IEEE Conference on},
volume = {0},
year = {2005},
issn = {1093-0159},
pages = {275-284},
doi = {http://doi.ieeecomputersociety.org/10.1109/CCC.2005.2},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Computational Complexity, Annual IEEE Conference on
TI - A Geometric Approach to Information-Theoretic Private Information Retrieval
SN - 1093-0159
SP275
EP284
A1 - David Woodruff,
A1 - Sergey Yekhanin,
PY - 2005
KW - null
VL - 0
JA - Computational Complexity, Annual IEEE Conference on
ER -
 
David Woodruff, Massachusetts Institute of Technology
Sergey Yekhanin, Massachusetts Institute of Technology

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 0(\frac{{k^2 }}{t}\log kn^{{1 \mathord{\left/ {\vphantom {1 {\left\lfloor {(2k - 1)/t} \right\rfloor }}} \right. \kern-\nulldelimiterspace} {\left\lfloor {(2k - 1)/t} \right\rfloor }}}), removing the (\begin{array}{*{20}c}k \\t \\\end{array}) term of previous schemes. This answers an open question of [14].
  • A 2-server protocol with O(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 1-private upper bounds from [7].

    Citation:
    David Woodruff, Sergey Yekhanin, "A Geometric Approach to Information-Theoretic Private Information Retrieval," ccc, pp.275-284, 20th Annual IEEE Conference on Computational Complexity (CCC'05), 2005
    Usage of this product signifies your acceptance of the Terms of Use.