Universal service-providers for database private information retrieval (extended abstract)

We consider the question of private information retrieval in the so-called "commodity-based" model. This model was recently proposed by Beaver for practically-oriented service-provider internet applications. In this paper, we show the following, somewhat surprising, results regarding this model for the problem of private information retrieval: (1) the service-provider model allows to dramatically reduce the overall communication involving the user, using off-line pre-processing messages from "service-providers" to databases, where the service-providers need not know the database contents, nor the future user's requests; (2) our service-provider solutions are resilient against more than a majority (in fact, all-but-one) coalitions of serviceproviders; and (3) these results hold for bath the computational and the information-theoretic setting.