This paper presents private information retrieval (PIR) schemes for coded storage with colluding servers, which are not restricted to maximum distance separable (MDS) codes. PIR schemes for general linear codes are constructed and the resulting PIR rate is calculated explicitly. It is shown that codes with transitive automorphism groups yield the highest possible rates obtainable with the proposed scheme. This rate coincides with the known asymptotic PIR capacity for MDS-coded storage systems without collusion. While many PIR schemes in the literature require field sizes that grow with the number of servers and files in the system, we focus especially on the case of a binary base field, for which Reed- Muller codes serve as an important and explicit class of examples.
In this work we construct PIR schemes based on general linear codes, and concentrate in particular on binary Reed--Muller (RM) codes. The schemes described in @cite_8 employed Generalized Reed-Solomon (GRS) codes, and the resulting analysis of the achievable rate relied on the @math of two GRS codes @math and @math again being a GRS code. The class of RM codes is closed under the star product operation as well, and thus naturally lends itself to be employed using the PIR scheme of @cite_8 . However, RM codes have the advantage of being defined over the binary field @math . When comparing GRS and RM codes of equal length and dimension, it is shown here that the same PIR rates as with GRS codes can be achieved in the non-colluding case. For a fixed PIR rate, however, RM codes provide less protection against collusion due to their lower minimum distance. Nevertheless, it is shown that the @math -PIR RM schemes presented here still provide protection against a substantial fraction of colluding sets of sizes slightly bigger than @math . In more detail, the main contributions of this paper are:
@cite_8
2963413537
We present a general framework for private information retrieval (PIR) from arbitrary coded databases that allows one to adjust the rate of the scheme to the suspected number of colluding servers. If the storage code is a generalized Reed--Solomon code of length @math and dimension @math , we design PIR schemes that achieve a PIR rate of @math while protecting against any @math colluding servers, for any @math . This interpolates between the previously studied cases of @math and @math and achieves PIR capacity in both of these cases asymptotically as the number of files in the database grows.