Universal Service-Providers for Database Private Information Retrieval
Giovanni DiCrescenzo, Yuval Ishai, Rafail Ostrovsky
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 service-providers; and (3) these results hold for {\em both} the computational and the information-theoretic setting.
comment: Appeared In Proceedings of Seventeenth Annual ACM Symposium on Principles of Distributed Computing (PODC-98) Journal version appears in Journal of Cryptology 14(1): 37-74 (2001).
Fetch PostScript file of the paper