Paper 1998/004

Universal Service Providers for Database Private Information Retrieval

Giovanni Di-Crescenzo, Yuval Ishai, and Rafail Ostrovsky


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}.

Available format(s)
Publication info
Published elsewhere. Appeared in the THEORY OF CRYPTOGRAPHY LIBRARY and has been included in the ePrint Archive.
Private information retrievalCommodity-based cryptography.
Contact author(s)
yuvali @ cs technion ac il
1998-02-22: received
Short URL
Creative Commons Attribution


      author = {Giovanni Di-Crescenzo and Yuval Ishai and Rafail Ostrovsky},
      title = {Universal Service Providers for Database Private Information Retrieval},
      howpublished = {Cryptology ePrint Archive, Paper 1998/004},
      year = {1998},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.