International Association for Cryptologic Research

International Association
for Cryptologic Research


Near-Optimal Private Information Retrieval with Preprocessing

Arthur Lazzaretti , Yale University
Charalampos Papamanthou , Yale University
Search ePrint
Search Google
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).
  title={Near-Optimal Private Information Retrieval with Preprocessing},
  author={Arthur Lazzaretti and Charalampos Papamanthou},