# The Capacity of Robust Private Information Retrieval with Colluding Databases

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

## Key facts

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

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

- [Adversarial Attacks on Online Learning to Rank with Stochastic Click Models](https://mlsanity.com/paper/2305.19218/) (2023)
- [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)
- [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. The information theoretic capacity of PIR (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. T-private PIR is a generalization of PIR to include the requirement that even if any T of the N databases collude, the identity of the retrieved message remains completely unknown to them. Robust PIR is another generalization that refers to the scenario where we have M ≥ N databases, out of which any M - N may fail to respond. For K messages and M≥ N databases out of which at least some N must respond, we show that the capacity of T-private and Robust PIR is left(1+T/N+T2/N2+cdots+TK-1/NK-1right)-1. The result includes as special cases the capacity of PIR without robustness (M=N) or T-privacy constraints (T=1).