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.