Paper 2020/1592

Puncturable Pseudorandom Sets and Private Information Retrieval with Polylogarithmic Bandwidth and Sublinear Time

Elaine Shi and Waqar Aqeel and Balakrishnan Chandrasekaran and Bruce Maggs

Abstract

Imagine that one or more non-colluding servers each holds 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 deal breaker with respect to practical adoption. Several recent works have shown, however, that by introducing a one-time, per-client, off-line preprocessing phase, an \emph{unbounded} number of client queries can be subsequently served with sublinear on-line computation time per query (and the cost of the preprocessing can be amortized over the unboundedly many queries). Unfortunately, existing preprocessing PIRs make undesirable tradeoffs to achieve sublinear online computation: they either require $\sqrt{n}$ or more bandwidth per query, which is asymptotically worse than classical PIR schemes, or they require the servers to store a linear amount 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 $\widetilde{O}(\sqrt{n})$ online computation per query, while preserving the polylogarithmic online bandwidth of classical PIR schemes. 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.