# The Capacity of Symmetric Private Information Retrieval

arXiv: https://arxiv.org/abs/1606.08828 · HTML: https://mlsanity.com/paper/1606.08828/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Jun 2016.

## Built on by (most cited first, 5 of 5)

- [Information Theoretic Secure Aggregation with User Dropouts](https://mlsanity.com/paper/2101.07750/) (2021)
- [Private Counterfactual Retrieval](https://mlsanity.com/paper/2410.13812/) (2024)
- [Private Federated Submodel Learning with Sparsification](https://mlsanity.com/paper/2205.15992/) (2022)
- [Private Counterfactual Retrieval With Immutable Features](https://mlsanity.com/paper/2411.10429/) (2024)
- [What If, But Privately: Private Counterfactual Retrieval](https://mlsanity.com/paper/2508.03681/) (2025)

## Abstract (arXiv)

Private information retrieval (PIR) is the problem of retrieving as efficiently as possible, one out of K messages from N non-communicating replicated databases (each holds all K messages) while keeping the identity of the desired message index a secret from each individual database. Symmetric PIR (SPIR) is a generalization of PIR to include the requirement that beyond the desired message, the user learns nothing about the other K-1 messages. The information theoretic capacity of SPIR (equivalently, the reciprocal of minimum download cost) is the maximum number of bits of desired information that can be privately retrieved per bit of downloaded information. We show that the capacity of SPIR is 1-1/N regardless of the number of messages K, if the databases have access to common randomness (not available to the user) that is independent of the messages, in the amount that is at least 1/(N-1) bits per desired message bit, and zero otherwise. Extensions to the capacity region of SPIR and the capacity of finite length SPIR are provided.