Rafail Ostrovsky - Publications

A Survey of Single-Database Private Information Retrieval: Techniques and Applications.

Rafail Ostrovsky, William Skeith


In this paper we survey the notion of Single-Database Private Information Retrieval (PIR). The first Single-Database PIR was constructed in 1997 by Kushilevitz and Ostrovsky and since then Single-Database PIR has emerged as an important cryptographic primitive. For example, Single-Database PIR turned out to be intimately connected to collision-resistant hash functions, oblivious transfer and public-key encryptions with additional properties. In this survey, we give an overview of many of the constructions for Single-Database PIR (including an abstract construction based upon homomorphic encryption) and describe some of the connections of PIR to other primitives.

comment: In Proceedings of the Public Key Cryptography 2007 conference, pp. 393-411. (PKC-2007). Full version appeared as a book chapter in "Homeland Security Technology Challenges From Sensing and Encrypting to Mining and Modeling" Franceschetti, Giorgio and Grossi, Marina (EDT), Artec-House publishers.

Fetch PostScript file of the paper     Fetch PDF file of the paper

Back to Publications List