2017/09/10 by Zhen Chen, Zhiying Wang, Chen, Zhen +3
Computer Science · #Complexity and Algorithms in Graphs #Cryptography and Data Security #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #Information Theory (cs.IT) #Privacy-Preserving Technologies in Data
paper · pdf · doi:10.48550/arxiv.1709.03022
openalex publication_date 2017/09/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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))K-M-1)-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-(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.