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

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.