Journal
STOC'15: PROCEEDINGS OF THE 2015 ACM SYMPOSIUM ON THEORY OF COMPUTING
Volume -, Issue -, Pages 577-584Publisher
ASSOC COMPUTING MACHINERY
DOI: 10.1145/2746539.2746546
Keywords
Private Information Retrieval; Locally Decodable Codes
Categories
Funding
- NSF [CCF-1217416]
- Sloan fellowship
Ask authors/readers for more resources
A 2-server Private Information Retrieval (PIR) scheme allows a user to retrieve the ith bit of an n-bit database replicated among two non-communicating servers, while not revealing any information about i to either server. In this work we construct a 2-server PIR scheme with total comog log rt. munication cost n(O)(root log log n/log n). This improves over current 2-server protocols which all require Omega(n(1/3)) communication. Our construction circumvents the n(1/3) barrier of Razborov and Yekhanin [21] which holds for the restricted model of bilinear group-based schemes (covering all previous 2-server schemes). The improvement comes from reducing the number of servers in existing protocols, based on Matching Vector Codes, from 3 or 4 servers to 2. This is achieved by viewing these protocols in an algebraic way (using polynomial interpolation) and extending them using partial derivatives.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available