Private Information Retrieval in Distributed Storage Systems Using an Arbitrary Linear Code

Understand

We propose an information-theoretic private information retrieval (PIR) scheme for distributed storage systems where data is stored using a linear systematic code of rate $R > 1/2$.

• The proposed scheme generalizes the PIR scheme for data stored using maximum distance separable codes recently proposed by Tajeddine and El Rouayheb for the scenario of a single spy node.
• We further propose an algorithm to optimize the communication price of privacy (cPoP) using the structure of the underlying linear code.
• As an example, we apply the proposed algorithm to several distributed storage codes, showing that the cPoP can be significantly reduced by exploiting the structure of the distributed storage code.