CryptoDB
Near-Optimal Private Information Retrieval with Preprocessing
| Authors: |
|
|---|---|
| Download: | |
| Presentation: | Slides |
| Conference: | TCC 2023 |
| Abstract: | In Private Information Retrieval (PIR), a client wishes to access an index $i$ from a public $n$-bit database without revealing any information about $i$. Recently, a series of works starting with the seminal paper of Corrigan-Gibbs and Kogan (EUROCRYPT 2020) considered PIR with \emph{client preprocessing} and \emph{no additional server storage}. In this setting, we now have protocols that achieve $\stackrel{\sim}{\smash{O}\rule{0pt}{1.0ex}}$$(\sqrt{n})$ (amortized) server time and $\stackrel{\sim}{\smash{O}\rule{0pt}{1.0ex}}$$(1)$ (amortized) bandwidth in the two-server model (Shi et al., CRYPTO 2021) as well as $\stackrel{\sim}{\smash{O}\rule{0pt}{1.0ex}}$$(\sqrt{n})$ server time and $\stackrel{\sim}{\smash{O}\rule{0pt}{1.0ex}}$$(\sqrt{n})$ bandwidth in the single-server model (Corrigan-Gibbs et al., EUROCRYPT 2022). Given existing lower bounds, a single-server PIR scheme with $\stackrel{\sim}{\smash{O}\rule{0pt}{1.0ex}}$$(\sqrt{n})$ (amortized) server time and $\stackrel{\sim}{\smash{O}\rule{0pt}{1.0ex}}$$(1)$ (amortized) bandwidth is still feasible, however, to date, no known protocol achieves such complexities. In this paper we fill this gap by constructing the first single-server PIR scheme with $\stackrel{\sim}{\smash{O}\rule{0pt}{1.0ex}}$$(\sqrt{n})$ (amortized) server time and $\stackrel{\sim}{\smash{O}\rule{0pt}{1.0ex}}$$(1)$ (amortized) bandwidth. Our scheme achieves near-optimal (optimal up to polylogarithmic factors) asymptotics in every relevant dimension. Central to our approach is a new cryptographic primitive that we call an \emph{adaptable pseudorandom set}: With an adaptable pseudorandom set, one can represent a large pseudorandom set with a succinct fixed-size key $k$, and can both add to and remove from the set a constant number of elements by manipulating the key $k$, while maintaining its concise description as well as its pseudorandomness (under a certain security definition). |
BibTeX
@inproceedings{tcc-2023-33651,
title={Near-Optimal Private Information Retrieval with Preprocessing},
publisher={Springer-Verlag},
author={Arthur Lazzaretti and Charalampos Papamanthou},
year=2023
}