The Capacity of Private Information Retrieval Under Arbitrary Collusion Patterns

2020/01/12 by Yao, Xinyu, Liu, Nan, Kang, Wei
#FOS: Computer and information sciences #Information Theory (cs.IT)

paper · doi:10.48550/arxiv.2001.03843

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^*. The number S^* 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^*.

Related

• The Capacity of Symmetric Private Information Retrieval under Arbitrary Collusion and Eavesdropping Patterns
• The Capacity of Robust Private Information Retrieval with Colluding Databases
• Towards the Capacity of Private Information Retrieval from Coded and\n Colluding Servers
• Private Information Retrieval Schemes for Coded Data with Arbitrary Collusion Patterns
• Necessary and Sufficient Conditions for Capacity-Achieving Private Information Retrieval with Non-Colluding and Colluding Servers