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 both the computational and the information-theoretic setting.
comment:
In
Proceedings of Seventeenth Annual ACM Symposium on
Principles of Distributed Computing (PODC-98)91-100. Journal version: Universal Service-Providers for Private Information Retrieval.
Journal of Cryptology 14(1): 37-74 (2001).
[Journal]
Fetch PostScript file of the paper
Fetch PDF file of the paper