The Capacity of <i>T</i>-Private Information Retrieval With Private Side Information
Zhen Chen, Zhiying Wang, Syed A. Jafar
Abstract
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 (1+ T/N + ⋯ +(T/N) <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">K-M</sup> <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">-1</sup> ) <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">-1</sup> . 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 - T/N 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 T/N -T bits per desired message bit. Otherwise, the capacity of STPIR-PSI is zero.