PIR schemes with small download complexity and low storage requirements

Simon R. Blackburn, Tuvi Etzion, Maura B. Paterson

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$ se…