[Resource Topic] 2024/930: Information-Theoretic Single-Server PIR in the Shuffle Model

Welcome to the resource topic for 2024/930

Information-Theoretic Single-Server PIR in the Shuffle Model

Authors: Yuval Ishai, Mahimna Kelkar, Daniel Lee, Yiping Ma


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.

ePrint: https://eprint.iacr.org/2024/930

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .