International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Universal Service Providers for Database Private Information Retrieval

Authors:
Giovanni Di-Crescenzo
Yuval Ishai
Rafail Ostrovsky
Download:
URL: http://eprint.iacr.org/1998/004
Search ePrint
Search Google
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
}