We propose three private information retrieval (PIR) protocols fordistributed storage systems (DSSs) where data is stored using an arbitrarylinear code. The first two protocols, named Protocol 1 and Protocol 2, achieveprivacy for the scenario with noncolluding nodes. Protocol 1 requires a filesize that is exponential in the number of files in the system, while the filesize required for Protocol 2 is independent of the number of files and is hencesimpler. We prove that, for certain linear codes, Protocol 1 achieves the PIRcapacity, i.e., its PIR rate (the ratio of the amount of retrieved stored dataper unit of downloaded data) is the maximum possible for any given (finite andinfinite) number of files, and Protocol 2 achieves the asymptotic PIR capacity(with infinitely large number of files in the DSS). In particular, we provide asufficient and a necessary condition for a code to be PIR capacity-achievingand prove that cyclic codes, Reed-Muller (RM) codes, and optimal informationlocality local reconstruction codes achieve both the finite PIR capacity (i.e.,with any given number of files) and the asymptotic PIR capacity with Protocols1 and 2, respectively. Furthermore, we present a third protocol, Protocol 3,for the scenario with multiple colluding nodes, which can be seen as animprovement of a protocol recently introduced by Freij-Hollanti et al. We alsopresent an algorithm to optimize the PIR rate of the proposed protocol.Finally, we provide a particular class of codes that is suitable for thisprotocol and show that RM codes achieve the maximum possible PIR rate for theprotocol.
展开▼
