PIR schemes with small download complexity and low storage requirements

Shah, Rashmi and Ramchandran recently considered a model for Private Information Retrieval (PIR) where a user wishes to retrieve one of several $R$-bit messages from a set of $n$ non-colluding servers. Their security model is information-theoretic. Their paper is the first to consider a model for PIR in which the database is not necessarily replicated, so allowing distributed storage techniques to be used. Shah et al. show that at least $R+1$ bits must be downloaded from servers, and describe a scheme with linear total storage (in $R$) that downloads between $2R$ and $3R$ bits. For any positive $\epsilon$, we provide a construction with the same storage property, that requires at most $(1+\epsilon)R$ bits to be downloaded; moreover one variant of our scheme only requires each server to store a bounded number of bits (in the sense of being bounded by a function that is independent of $R$). We also provide variants of a scheme of Shah et al which downloads exactly $R+1$ bits and has quadratic total storage. Finally, we simplify and generalise a lower bound due to Shah et al. on the download complexity a PIR scheme. In a natural model, we show that an $n$-server PIR scheme requires at least $nR/(n-1)$ download bits in many cases, and provide a scheme that meets this bound.