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. We consider the problem of private information retrieval (PIR) over a distributed storage system. The storage system consists of N non-colluding databases, each storing an MDS-coded version of M messages. In the PIR problem, the user wishes to retrieve one of the available messages without revealing the message identity to any individual database. We derive the information-theoretic capacity of this problem, which is defined as the maximum number of bits of the desired message that can be privately retrieved per one bit of downloaded information. We show that the PIR capacity in this case is C = (1 + K N + K2 N2 + ··· + KM−1 NN−1)−1 = (1 + R c + R2 c + ··· + RM c −1)−1 = 1−R c R c M, where R c is the rate of the (N, K) code used. The capacity is a function of the code rate and the number of messages only regardless of the explicit structure of the storage code. The result implies a fundamental tradeoff between the optimal retrieval cost and the storage cost. The result generalizes the achievability and converse results for the classical PIR with replicating databases to the case of coded databases. We consider the problem of private information retrieval (PIR) over a distributed storage system. The storage system consists of @math non-colluding databases, each storing a coded version of @math messages. In the PIR problem, the user wishes to retrieve one of the available messages without revealing the message identity to any individual database. We derive the information-theoretic capacity of this problem, which is defined as the maximum number of bits of the desired message that can be privately retrieved per one bit of downloaded information. We show that the PIR capacity in this case is @math , where @math is the rate of the @math code used. The capacity is a function of the code rate and the number of messages only regardless of the explicit structure of the storage code. The result implies a fundamental tradeoff between the optimal retrieval cost and the storage cost. The result generalizes the achievability and converse results for the classical PIR with replicating databases to the case of coded databases. Private information retrieval (PIR) protocols allow a user to retrieve a data item from a database without revealing any information about the identity of the item being retrieved. Specifically, in information-theoretic @math -server PIR, the database is replicated among @math non-communicating servers, and each server learns nothing about the item retrieved by the user. The cost of PIR protocols is usually measured in terms of their communication complexity, which is the total number of bits exchanged between the user and the servers, and storage overhead, which is the ratio between the total number of bits stored on all the servers and the number of bits in the database. Since single-server information-theoretic PIR is impossible, the storage overhead of all existing PIR protocols is at least @math . In this work, we show that information-theoretic PIR can be achieved with storage overhead arbitrarily close to the optimal value of @math , without sacrificing the communication complexity. Specifically, we prove that all known @math -server PIR protocols can be efficiently emulated, while preserving both privacy and communication complexity but significantly reducing the storage overhead. To this end, we distribute the @math bits of the database among @math servers, each storing @math coded bits (rather than replicas). For every fixed @math , the resulting storage overhead @math approaches @math as @math grows; explicitly we have @math . Moreover, in the special case @math , the storage overhead is only @math . In order to achieve these results, we introduce and study a new kind of binary linear codes, called here @math -server PIR codes. We then show how such codes can be constructed, and we establish several bounds on the parameters of @math -server PIR codes. Finally, we briefly discuss extensions of our results to nonbinary alphabets, to robust PIR, and to @math -private PIR.