Technical Program

Paper Detail

Paper IDP.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

Visit Website!