Paper 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
- 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
-
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},
url = {https://eprint.iacr.org/2022/609}
}
