PIR Codes with Short Block Length

Abstract

In this work private information retrieval (PIR) codes are studied. In a $k$-PIR code, $s$ information bits are encoded in such a way that every information bit has $k$ mutually disjoint recovery sets. The main problem under this paradigm is to minimize the number of encoded bits given the values of $s$ and $k$, where this value is denoted by $P(s,k)$. The main focus of this work is to analyze $P(s,k)$ for a large range of parameters of $s$ and $k$. In particular, we improve upon several of the existing results on this value.

10 pages, 1 table

References in corpus (4)

• PIR with Low Storage Overhead: Coding instead of Replication
• Lengthening and Extending Binary Private Information Retrieval Codes
• LinCode -- computer classification of linear codes
• Notes on Reed-Muller Codes