International Association for Cryptologic Research

International Association
for Cryptologic Research


Optimal Single-Server Private Information Retrieval

Mingxun Zhou , Carnegie Mellon University
Wei-Kai Lin , Northeastern University
Yiannis Tselekounis , Carnegie Mellon University
Elaine Shi , Carnegie Mellon University
DOI: 10.1007/978-3-031-30545-0_14 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: EUROCRYPT 2023
Abstract: We construct a single-server pre-processing Private Information Retrieval (PIR) scheme with optimal bandwidth and server computation (up to poly-logarithmic factors), assuming the hardness of the Learning With Errors (LWE) problem. Our scheme achieves amortized $\widetilde{O}_{\lambda}(\sqrt{n})$ server and client computation and $\widetilde{O}_\lambda(1)$ bandwidth per query, completes in a single roundtrip, and requires $\widetilde{O}_\lambda(\sqrt{n})$ client storage. In particular, we achieve a significant reduction in bandwidth over the state-of-the-art scheme by Corrigan-Gibbs, Henzinger, and Kogan (Eurocrypt'22): their scheme requires as much as $\widetilde{O}_{\lambda}(\sqrt{n})$ bandwidth per query, with comparable computational and storage overhead as ours.
  title={Optimal Single-Server Private Information Retrieval},
  author={Mingxun Zhou and Wei-Kai Lin and Yiannis Tselekounis and Elaine Shi},