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
2591083178 2963413537 2100816365 2005598127
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. 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. In this letter, we propose a novel forward error correction (FEC) coding method using a modified Reed-Muller (RM) code for providing accurate dimming control in on-off keying (OOK) based visible light communication (VLC) systems. The proposed FEC scheme has a property that produces exactly same occurrence probability of 1's and 0's. Therefore, it can contain minimal compensation symbols in supporting multiple dimming target values. Moreover, VLC with our proposed scheme provides more coding gain than VLC scheme with the conventional FEC codes [the first-order RM and Reed-Solomon (RS) codes]. Simulation results for various dimming target values show that the proposed scheme leads to at least 2 dB or more signal-to-noise ratio (SNR) gain in 1 bit error rate (BER) than two FEC codes. In this letter, we propose a new forward error correction (FEC) coding method using a coset constructed from a bent function and a Reed-Muller (RM) code for providing accurate dimming control in on-off keying-based visible light communication (VLC) systems. By partitioning the coset made from bent function and the first-order RM codes, the new FEC scheme can be made to be suitable for dimming close to 0 or 100 . Therefore, it can contain minimal compensation symbols in supporting multiple dimming target values, which causes improved coding gain when the total amount of frame data is fixed. Simulation results for various dimming target values show that the proposed scheme leads to about 1-dB signal-to-noise ratio gain in 10-2 bit error rate compared with other three FEC codes.