Paper 2024/930
Information-Theoretic Single-Server PIR in the Shuffle Model
Abstract
We revisit the problem of private information retrieval (PIR) in the shuffle model, where queries can be made anonymously by multiple clients. We present the first single-server PIR protocol in this model that has sublinear per-client communication and information-theoretic security. Moreover, following one-time preprocessing on the server side, our protocol only requires sublinear per-client computation. Concretely, for every $\gamma>0$, the protocol has $O(n^{\gamma})$ communication and computation costs per (stateless) client, with $1/\text{poly}(n)$ statistical security, assuming that a size-$n$ database is simultaneously accessed by $\text{poly}(n)$ clients. This should be contrasted with the recent breakthrough result of Lin, Mook, and Wichs (STOC 2023) on doubly efficient PIR in the standard model, which is (inherently) limited to computational security.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Published elsewhere. Major revision. ITC 2024
- Keywords
- shuffle modelprivate information retrieval
- Contact author(s)
-
yuvali @ cs technion ac il
mahimna @ cs cornell edu
lee_d @ mit edu
yipingma @ seas upenn edu - History
- 2024-06-12: approved
- 2024-06-10: received
- See all versions
- Short URL
- https://ia.cr/2024/930
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/930,
author = {Yuval Ishai and Mahimna Kelkar and Daniel Lee and Yiping Ma},
title = {Information-Theoretic Single-Server {PIR} in the Shuffle Model},
howpublished = {Cryptology ePrint Archive, Paper 2024/930},
year = {2024},
note = {\url{https://eprint.iacr.org/2024/930}},
url = {https://eprint.iacr.org/2024/930}
}
