text: 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.
  @cite_10: 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 k-server PIR, the database is replicated among k 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. However, another important cost parameter is the 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 2 (or k, in the case of k-server PIR). In this work, we show that information-theoretic PIR can be achieved with storage overhead arbitrarily close to the optimal value of 1, without sacrificing the communication complexity. Specifically, we prove that all known k-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 n bits of the database among s + r servers, each storing n s coded bits (rather than replicas). Notably, our coding scheme remains the same, regardless of the specific k-server PIR protocol being emulated. For every fixed k, the resulting storage overhead (s +r) s approaches 1 as s grows; explicitly we have equation. Moreover, in the special case k = 2, the storage overhead is only 1 + 1 s. In order to achieve these results, we introduce and study a new kind of binary linear codes, called here k-server PIR codes. Finally, we show how such codes can be constructed from multidimensional cubic, from Steiner systems, and from one-step majority-logic decodable codes.
  @cite_3: The notion of a Private Information Retrieval (PIR) code was recently introduced by Fazeli, Vardy and Yaakobi [1] who showed that this class of codes permit PIR at reduced levels of storage overhead in comparison with rephcated-server PIR. In the present paper, the construction of an (n, k) τ-server binary linear PIR code having parameters n = lΣ i=0 (m i ), k = (m i ) and τ = 2l for any integer m ≥ l ≥ 0 is presented. These codes are obtained through homogeneous-polynomial evaluation and correspond to the binary. Projective Reed Muller (PRM) code. The construction can be extended to yield PIR codes for any τ = ∊ 2l, 2l − 1 | l ∊ Z, l ≥ 0 and any value of k, through a combination of single-symbol puncturing and shortening of the PRM code. Each of these code constructions above, have smaller storage overhead in comparison with known short block length codes in [1]. For the particular case of τ = 3,4, we show that the codes constructed here are optimal, systematic PIR codes by providing an improved lower bound on the block length n k, τ) of a systematic PIR code. It follows from a result by Vardy and Yaakobi [2], that these codes also yield optimal, systematic primitive multi-set n, k, τ) B batch codes for τ = 3,4. The PIR code constructions presented here also yield upper bounds on the generahzed Hamming weights of binary PRM codes.
summary: RM codes have previously been considered for PIR in other settings @cite_3 . There, the system model is different from the present paper, in that the coding is between different files and the primary goal is to minimize storage overhead for a given PIR scheme, along the same lines as in @cite_10 . In our work, coding is between different blocks of the same file, and the goal is to minimize the download overhead for fixed storage codes.