# The Capacity of T-Private Information Retrieval with Private Side Information

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Sep 2017.

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

- [Single-Server Private Linear Transformation: The Joint Privacy Case](https://mlsanity.com/paper/2106.05220/) (2021)

## Abstract (arXiv)

We consider the problem of T-Private Information Retrieval with private side information (TPIR-PSI). In this problem, N replicated databases store K independent messages, and a user, equipped with a local cache that holds M messages as side information, wishes to retrieve one of the other K-M messages. The desired message index and the side information must remain jointly private even if any T of the N databases collude. We show that the capacity of TPIR-PSI is left(1+fracTN+cdots+left(fracTNright)K-M-1right)-1. As a special case obtained by setting T=1, this result settles the capacity of PIR-PSI, an open problem previously noted by Kadhe et al. We also consider the problem of symmetric-TPIR with private side information (STPIR-PSI), where the answers from all N databases reveal no information about any other message besides the desired message. We show that the capacity of STPIR-PSI is 1-fracTN if the databases have access to common randomness (not available to the user) that is independent of the messages, in an amount that is at least fracTN-T bits per desired message bit. Otherwise, the capacity of STPIR-PSI is zero.