Name
Abstract | ||
|---|---|---|
A 2-server Private Information Retrieval (PIR) scheme allows a user to retrieve the ith bit of an n-bit database replicated among two noncommunicating servers, while not revealing any information about i to either server. In this work, we construct a 2-server PIR scheme with total communication cost nO(&sqrt;&frac;log log n log n). This improves over current 2-server protocols, which all require Ω(n1/3) communication. Our construction circumvents the n1/3 barrier of Razborov and Yekhanin [2007], 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. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1145/2968443 | Journal of the ACM (JACM) |
Keywords | DocType | Volume |
private information retrieval | Journal | 63 |
Issue | ISSN | ISBN |
4 | 0004-5411 | 978-1-4503-3536-2 |
Citations | PageRank | References |
14 | 0.99 | 21 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Zeev Dvir | 1 | 437 | 30.85 |
| Sivakanth Gopi | 2 | 25 | 5.63 |