# The Capacity of Private Information Retrieval

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Feb 2016.

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

- [Private Counterfactual Retrieval](https://mlsanity.com/paper/2410.13812/) (2024)
- [Single-Server Private Linear Transformation: The Joint Privacy Case](https://mlsanity.com/paper/2106.05220/) (2021)
- [Private Federated Submodel Learning with Sparsification](https://mlsanity.com/paper/2205.15992/) (2022)
- [Secure Embedding Aggregation for Federated Representation Learning](https://mlsanity.com/paper/2206.09097/) (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)

In the private information retrieval (PIR) problem a user wishes to retrieve, as efficiently as possible, one out of K messages from N non-communicating databases (each holds all K messages) while revealing nothing about the identity of the desired message index to any individual database. The information theoretic capacity of PIR is the maximum number of bits of desired information that can be privately retrieved per bit of downloaded information. For K messages and N databases, we show that the PIR capacity is (1+1/N+1/N2+cdots+1/NK-1)-1. A remarkable feature of the capacity achieving scheme is that if we eliminate any subset of messages (by setting the message symbols to zero), the resulting scheme also achieves the PIR capacity for the remaining subset of messages.