Abstract

It was recently shown by Fazeli et al. that the storage overhead of a traditional t-server private information retrieval (PIR) protocol can be significantly reduced using the concept of a t-server PIR code. In this work, we show that a family of t-server PIR codes (with increasing dimensions and blocklengths) can be constructed from an existing t-server PIR code through lengthening by a single information symbol and code extension by at most \(\lceil t/2\rceil\) code symbols. Furthermore, by extending a code construction notion from Steiner systems by Fazeli et al., we obtain a specific family of t-server PIR codes. Based on a code construction technique that lengthens and extends a t-server PIR code simultaneously, a basic algorithm to find good (i.e., small blocklength) t-server PIR codes is proposed. For the special case of \(t=5\), we find provably optimal PIR codes for code dimensions \(k \leq 6\), while for all \(5 \leq k \leq 32\) we find codes of smaller blocklength than the best known codes from the literature. Furthermore, in the case of \(t = 8\), we also find better codes for \(k=5,6,11,12\). Numerical results show that most of the best found 5-server PIR codes can be constructed from the proposed family of codes connected to Steiner systems.