|The Capacity of Private Information Retrieval Under Arbitrary Collusion Patterns
|Xinyu Yao, Wei Kang, Nan Liu, Southeast University, China
|P.9: Private Information Retrieval II
|Cryptography, Security and Privacy
|Click here to download the manuscript
|Click here to watch in the Virtual Symposium
|We study the private information retrieval (PIR) problem under arbitrary collusion patterns 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^*$.