Necessary and Sufficient Conditions for Capacity-Achieving Private Information Retrieval and Its Construction Method
Atsushi Miki, Yusuke Morishita, Toshiyasu Matsushima · 2024
Private Information Retrieval (PIR) is a mechanism for efficiently downloading messages while keeping the index secret. The information-theoretic upper bound on efficiency has been proved in previous studies; PIR properties and the proofs of capacity were notated in terms of entropy and probability. However, in order to construct a linear PIR, it is necessary to clarify the properties of the query matrix. In this study, we prove the necessary and sufficient conditions for PIR properties, and represent them in matrix form. We also show a PIR construction method that satisfies the conditions.