A Geometric Approach to Information-Theoretic Private Information Retrieval

San Jose, CA June 11-June 15

DOI Bookmark:

http://doi.ieeecomputersociety.org/10.1109/CCC.2005.2

20th Annual IEEE Conference on Comput ...

	This Article
	PURCHASE ARTICLE: $19 PDF HTML IEEE Xplore Subscribers
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan/Endnote
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by David Woodruff Articles by Sergey Yekhanin

	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

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.