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.
While explicit PIR schemes which achieve capacity are constructed in @cite_4 , @cite_14 , and @cite_12 , they require the base field to be large. If @math is the number of servers and @math is the number of files, the capacity-achieving schemes of @cite_14 require a field size of @math , since they rely on the existence of MDS codes of high lengths. Realistic storage systems, however, may operate over fields of small size to keep the complexity of the involved operations manageable. One would naturally then like to construct explicit PIR schemes over small base fields.
@cite_14 @cite_4 @cite_12
2768218911 2599749253 2524023279
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. This paper presents an explicit construction for an @math regenerating code over a field @math operating at the Minimum Storage Regeneration (MSR) point. The MSR code can be constructed to have rate @math as close to @math as desired, sub-packetization given by @math , for @math , field size no larger than @math and where all code symbols can be repaired with the same minimum data download. The construction modifies a prior construction by Sasidharan et. al. which required far larger field-size. A building block appearing in the construction is a scalar MDS code of block length @math . The code has a simple layered structure with coupling across layers, that allows both node repair and data recovery to be carried out by making multiple calls to a decoder for the scalar MDS code. While this work was carried out independently, there is considerable overlap with a prior construction by Ye and Barg. It is shown here that essentially the same architecture can be employed to construct MSR codes using vector binary MDS codes as building blocks in place of scalar MDS codes. The advantage here is that computations can now be carried out over a field of smaller size potentially even over the binary field as we demonstrate in an example. Further, we show how the construction can be extended to handle the case of @math under a mild restriction on the choice of helper nodes. Two widely studied models of multiple-node repair in distributed storage systems are centralized repair and cooperative repair. The centralized model assumes that all the failed nodes are recreated in one location, while the cooperative one stipulates that the failed nodes may communicate but are distinct, and the amount of data exchanged between them is included in the repair bandwidth. We show that cooperative model is stronger than the centralized one, in the sense that MDS codes with optimal repair bandwidth under the former model have the same property under the latter one. In this paper we present explicit constructions of MDS codes with optimal cooperative repair for all possible parameters. More precisely, given any @math such that @math we construct explicit @math MDS codes over the field @math of size @math that can optimally repair any @math erasures from any @math helper nodes. The repair scheme of our codes involves two rounds of communication. In the first round, each failed node downloads information from the helper nodes, and in the second one, each failed node downloads additional information from the other failed nodes. This shows that two rounds of communication in cooperative repair always suffice, and that the proposed codes achieve the optimal repair bandwidth using the smallest possible number of rounds. 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.