Binary, shortened projective reed muller codes for coded private information retrieval

Abstract

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 = <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">ℓ</sup> Σ <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">i=0</inf> ( <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">m</sup> <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">i</inf> ), k = ( <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">m</sup> <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">i</inf> ) and τ = 2 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">ℓ</sup> for any integer m ≥ ℓ ≥ 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 τ = ∊ {2 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">ℓ</sup> , 2 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">ℓ</sup> − 1 | ℓ ∊ Z, ℓ ≥ 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, τ) <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">B</inf> batch codes for τ = 3,4. The PIR code constructions presented here also yield upper bounds on the generahzed Hamming weights of binary PRM codes.