CryptoDB
Universal Service Providers for Database Private Information Retrieval
Authors: | |
---|---|
Download: | |
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 do not need to 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. More specifically, we exhibit a service-provider algorithm which can ``sell'' (i.e., generate and send) ``commodities'' to users and databases, that subsequently allow users to retrieve database contents in a way which hides from the database which particular item the user retrieves. The service-providers need not know anything about the contents of the databases nor the nature of the user's requests in order to generate commodities. Our commodity-based solution significantly improves communication complexity of the users (i.e., counting both the size of commodities bought by the user from the service-providers and the subsequent communication with the databases) compared to all previously known on-line private information retrieval protocols (i.e., without the help of the service-providers). Moreover, we show how commodities from different service-providers can be {\em combined} in such a way that even if ``all-but-one'' of the service-providers collude with the database, the user's privacy remains intact. Finally, we show how to re-use commodities in case of multiple requests (i.e., in the amortized sense), how to ``check'' commodity-correctness, and how some of the solutions can be extended to the related problem of {\em Private Information Storage}. |
BibTeX
@misc{eprint-1998-11301, title={Universal Service Providers for Database Private Information Retrieval}, booktitle={IACR Eprint archive}, keywords={Private information retrieval, Commodity-based cryptography.}, url={http://eprint.iacr.org/1998/004}, note={Appeared in the THEORY OF CRYPTOGRAPHY LIBRARY and has been included in the ePrint Archive. yuvali@cs.technion.ac.il 10500 received Feb 22, 1998.}, author={Giovanni Di-Crescenzo and Yuval Ishai and Rafail Ostrovsky}, year=1998 }