The Capacity of Private Information Retrieval Under Arbitrary Collusion Patterns

Abstract

We study the private information retrieval (PIR) problem under arbitrary collusion pattern for replicated databases. We find its capacity, which is the same as the capacity of the original PIR problem with the number of databases $N$ replaced by a number $S^{\ast }$. The number $S^{\ast }$ is the optimal solution to a linear programming problem that is a function of the collusion pattern. Hence, the collusion pattern affects the capacity of the PIR problem only through the number $S^{\ast }$.

This is a full version of the paper submitted to ISIT 2020

References in corpus (7)

• Private Information Retrieval from Storage Constrained Databases -- Coded Caching meets PIR
• On the Asymptotic Capacity of $X$-Secure $T$-Private Information Retrieval with Graph Based Replicated Storage
• Binary, Shortened Projective Reed Muller Codes for Coded Private Information Retrieval
• On the Storage Cost of Private Information Retrieval
• A Capacity-Achieving $T$-PIR Scheme Based On MDS Array Codes
• Robust low-delay Streaming PIR using convolutional codes
• Weakly-Private Information Retrieval