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 }$.

arXiv commentThis is a full version of the paper submitted to ISIT 2020

References in corpus (14)

• Private Information Retrieval from MDS Coded Databases with Colluding Servers under Several Variant Models
• Private Information Retrieval from Storage Constrained Databases -- Coded Caching meets PIR
• Towards the Capacity of Private Information Retrieval from Coded and Colluding Servers
• Private Set Intersection: A Multi-Message Symmetric Private Information Retrieval Perspective
• Private Information Retrieval from Transversal Designs
• 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 Information Leakage in Private Information Retrieval Systems
• On the Capacity of Single-Server Multi-Message Private Information Retrieval with Side Information
• On the Storage Cost of Private Information Retrieval
• A Capacity-Achieving $T$-PIR Scheme Based On MDS Array Codes
• Weakly-Private Information Retrieval
• Robust low-delay Streaming PIR using convolutional codes
• On the Access Complexity of PIR Schemes