  Private information retrieval (PIR) protocols allow a user to retrieve a data
item from a database without revealing any information about the identity of
the item being retrieved. Specifically, in information-theoretic $k$-server
PIR, the database is replicated among $k$ non-communicating servers, and each
server learns nothing about the item retrieved by the user. The cost of PIR
protocols is usually measured in terms of their communication complexity, which
is the total number of bits exchanged between the user and the servers, and
storage overhead, which is the ratio between the total number of bits stored on
all the servers and the number of bits in the database. Since single-server
information-theoretic PIR is impossible, the storage overhead of all existing
PIR protocols is at least $2$.
  In this work, we show that information-theoretic PIR can be achieved with
storage overhead arbitrarily close to the optimal value of $1$, without
sacrificing the communication complexity. Specifically, we prove that all known
$k$-server PIR protocols can be efficiently emulated, while preserving both
privacy and communication complexity but significantly reducing the storage
overhead. To this end, we distribute the $n$ bits of the database among $s+r$
servers, each storing $n/s$ coded bits (rather than replicas). For every fixed
$k$, the resulting storage overhead $(s+r)/s$ approaches $1$ as $s$ grows;
explicitly we have $r\le k\sqrt{s}(1+o(1))$. Moreover, in the special case $k =
2$, the storage overhead is only $1 + \frac{1}{s}$. In order to achieve these
results, we introduce and study a new kind of binary linear codes, called here
$k$-server PIR codes. We then show how such codes can be constructed, and we
establish several bounds on the parameters of $k$-server PIR codes. Finally, we
briefly discuss extensions of our results to nonbinary alphabets, to robust
PIR, and to $t$-private PIR.
