Universal service-providers for private information retrieval

A private information retrieval scheme allows a user to retrieve a data ite m of his choice from a remote database (or several copies of a database) wh ile hiding from the database owner which particular data item he is interes ted in. We consider the question of private information retrieval in the so -called "commodity-bases' model, recently proposed by Beaver for practicall y oriented service-provider Internet applications. We present simple and mo dular schemes allowing us to reduce dramatically the overall communication involving users, and substantially reduce their computation, using off-line messages sent from service-providers to databases and users. The service-p roviders do not need to know the database contents nor the future user's re quests; all they need to know is an upper bound on the data size. Our solut ions can be made resilient against collusions of databases with more than a majority tin fact, all-but-one) of the service-providers.