Paper 2022/609 Original: eprint.iacr.org/2022/609 ↗
Optimal Single-Server Private Information Retrieval
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
- Preprint.
- History
- 2023-02-27: last updated
- 2022-05-23: published
- Short URL
- https://ia.cr/2022/609
- License
- https://creativecommons.org/licenses/by/4.0/
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},
url = {https://eprint.iacr.org/2022/609}
}