# Multi-Message Private Information Retrieval: Capacity Results and Near-Optimal Schemes

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

## Key facts

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

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

- [Single-Server Private Linear Transformation: The Joint Privacy Case](https://mlsanity.com/paper/2106.05220/) (2021)
- [Single-Server Private Linear Transformation: The Individual Privacy Case](https://mlsanity.com/paper/2106.05222/) (2021)
- [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)

We consider the problem of multi-message private information retrieval (MPIR) from N non-communicating replicated databases. In MPIR, the user is interested in retrieving P messages out of M stored messages without leaking the identity of the retrieved messages. The information-theoretic sum capacity of MPIR CsP is the maximum number of desired message symbols that can be retrieved privately per downloaded symbol. For the case P ≥ fracM2, we determine the exact sum capacity of MPIR as CsP=frac11+fracM-PPN. The achievable scheme in this case is based on downloading MDS-coded mixtures of all messages. For P ≤ fracM2, we develop lower and upper bounds for all M,P,N. These bounds match if the total number of messages M is an integer multiple of the number of desired messages P, i.e., fracMP ∈ mathbbN. In this case, CsP=frac1-frac1N1-(frac1N)M/P. The achievable scheme in this case generalizes the single-message capacity achieving scheme to have unbalanced number of stages per round of download. For all the remaining cases, the difference between the lower and upper bound is at most 0.0082, which occurs for M=5, P=2, N=2. Our results indicate that joint retrieval of desired messages is more efficient than successive use of single-message retrieval schemes.