  In the classical model for (information theoretically secure) Private
Information Retrieval (PIR), a user wishes to retrieve one bit of a database
that is stored on a set of $n$ servers, in such a way that no individual server
gains information about which bit the user is interested in. The aim is to
design schemes that minimise communication between the user and the servers.
More recently, there have been moves to consider more realistic models where
the total storage of the set of servers, or the per server storage, should be
minimised (possibly using techniques from distributed storage), and where the
database is divided into $R$-bit records with $R>1$, and the user wishes to
retrieve one record rather than one bit. When $R$ is large, downloads from the
servers to the user dominate the communication complexity and so the aim is to
minimise the total number of downloaded bits. Shah, Rashmi and Ramchandran show
that at least $R+1$ bits must be downloaded from servers in the worst case, and
provide PIR schemes meeting this bound. Sun and Jafar determine the best
asymptotic download cost of a PIR scheme (as $R\rightarrow\infty$), where this
cost is defined as the ratio of the message length $R$ and the total number of
bits downloaded.
  This paper provides various bounds on the download complexity of a PIR
scheme, generalising those of Shah et al. to the case when the number $n$ of
servers is bounded, and providing links with classical techniques due to Chor
et al. The paper also provides a range of constructions for PIR schemes that
are either simpler or perform better than previously known schemes, including
explicit schemes that achieve the best asymptotic download complexity of Sun
and Jafar with significantly lower upload complexity, and general techniques
for constructing a scheme with good worst case download complexity from a
scheme with good download complexity on average.
