Paper 2022/609

Optimal Single-Server Private Information Retrieval

Mingxun Zhou
Wei-Kai Lin
Yiannis Tselekounis
Elaine Shi
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 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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A minor revision of an IACR publication in EUROCRYPT 2023
Keywords
Private information retrieval
Contact author(s)
mingxunz @ andrew cmu edu
weikaili @ andrew cmu edu
tselekounis @ sians org
runting @ gmail com
History
2023-02-27: last of 6 revisions
2022-05-23: received
See all versions
Short URL
https://ia.cr/2022/609
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/609,
      author = {Mingxun Zhou and Wei-Kai Lin and Yiannis Tselekounis and Elaine Shi},
      title = {Optimal Single-Server Private Information Retrieval},
      howpublished = {Cryptology ePrint Archive, Paper 2022/609},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/609}},
      url = {https://eprint.iacr.org/2022/609}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.