Universal Service Providers for Database Private Information Retrieval.
Giovanni Di Crescenzo, Yuval Ishai, Rafail Ostrovsky · 1998
A private information retrieval scheme allows a user to retrieve a data item of his choice from a remote database (or several copies of a database) while hiding from the database owner which particular data item he is interested in. We consider the question of private information retrieval in the so-called "commodity-based" model, recently proposed by Beaver for practically-oriented service-provider internet applications. We present simple and modular schemes allowing to dramatically reduce the overall communication involving users, and substantially reduce their computation, using off-line messages sent from service-providers to databases and users. The service-providers do not need to know neither the database contents nor the future user's requests; all they need to know is an upper bound on the data size. Our solutions can be made resilient against collusions of databases with more than a majority (in fact, all-but-one) of the service-providers.