2020 IEEE International Symposium
on Information Theory
21-26 June 2020 • Los Angeles, California, USA
| Paper ID | P.9.1 | ||
| Paper Title | The Capacity of Private Information Retrieval Under Arbitrary Collusion Patterns | ||
| Authors | Xinyu Yao, Wei Kang, Nan Liu, Southeast University, China | ||
| Session | P.9: Private Information Retrieval II | ||
| Presentation | Lecture | ||
| Track | Cryptography, Security and Privacy | ||
| Manuscript | Click here to download the manuscript | ||
| Virtual Presentation | Click here to watch in the Virtual Symposium | ||
| Abstract | 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^*$. | ||
Plan Ahead
2021 IEEE International Symposium on Information Theory
11-16 July 2021 | Melbourne, Victoria, Australia
