Abstract
Imagine one or more non-colluding servers each holding a large public database, e.g., the repository of DNS entries. Clients would like to access entries in this database without disclosing their queries to the servers. Classical private information retrieval (PIR) schemes achieve polylogarithmic bandwidth per query, but require the server to perform linear computation per query, which is a significant barrier towards deployment. Several recent works showed, however, that by introducing a one-time, per-client, off-line preprocessing phase, an unbounded number of client queries can be subsequently served with sublinear online computation time per query (and the cost of the preprocessing can be amortized over the unboundedly many queries). Existing preprocessing PIR schemes (supporting unbounded queries), unfortunately, make undesirable tradeoffs to achieve sublinear online computation: they are either significantly non-optimal in online time or bandwidth, or require the servers to store a linear amount of state per client or even per query, or require polylogarithmically many non-colluding servers. We propose a novel 2-server preprocessing PIR scheme that achieves O~(n) online computation per query and O~(n) client storage, while preserving the polylogarithmic online bandwidth of classical PIR schemes. Both the online bandwidth and computation are optimal up to a poly-logarithmic factor. In our construction, each server stores only the original database and nothing extra, and each online query is served within a single round trip. Our construction relies on the standard LWE assumption. As an important stepping stone, we propose new, more generalized definitions for a cryptographic object called a Privately Puncturable Pseudorandom Set, and give novel constructions that depart significantly from prior approaches.
| Original language | English |
|---|---|
| Title of host publication | Advances in Cryptology – CRYPTO 2021 |
| Subtitle of host publication | 41st Annual International Cryptology Conference, CRYPTO 2021, Virtual Event, August 16–20, 2021, Proceedings, Part IV |
| Editors | Tal Malkin, Chris Peikert |
| Publisher | Springer Science and Business Media Deutschland GmbH |
| Pages | 641-669 |
| Number of pages | 29 |
| Volume | 4 |
| ISBN (Electronic) | 9783030842598 |
| ISBN (Print) | 9783030842581 |
| DOIs | |
| Publication status | Published - 2021 |
| Event | 41st Annual International Cryptology Conference, CRYPTO 2021 - Virtual, Online Duration: 16 Aug 2021 → 20 Aug 2021 |
Publication series
| Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
|---|---|
| Volume | 12828 LNCS |
| ISSN (Print) | 0302-9743 |
| ISSN (Electronic) | 1611-3349 |
Conference
| Conference | 41st Annual International Cryptology Conference, CRYPTO 2021 |
|---|---|
| City | Virtual, Online |
| Period | 16/08/21 → 20/08/21 |
Bibliographical note
Funding Information:Acknowledgment. This work is in part supported by a DARPA SIEVE grant under a subcontract from SRI, an ONR YIP award, a Packard Fellowship, a JP Morgan Award, and NSF grants under the award numbers 2001026, 1901047, and 1763742. The authors would like to acknowledge Dima Kogan and Feng-Hao Liu for helpful discussions, and thank the anonymous reviewers for the detailed and throughtful comments.
Publisher Copyright:
© 2021, International Association for Cryptologic Research.
Funding
Acknowledgment. This work is in part supported by a DARPA SIEVE grant under a subcontract from SRI, an ONR YIP award, a Packard Fellowship, a JP Morgan Award, and NSF grants under the award numbers 2001026, 1901047, and 1763742. The authors would like to acknowledge Dima Kogan and Feng-Hao Liu for helpful discussions, and thank the anonymous reviewers for the detailed and throughtful comments.