Cryptology ePrint Archive: Report 2007/059

A Survey of Single Database PIR: Techniques and Applications

Rafail Ostrovsky and William E. Skeith III

Abstract: 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.

Category / Keywords: cryptographic protocols / private information retrieval, PIR, public key encryption

Publication Info: The material presented in this paper appeared in proc. PKC-2007 (invited plenary talk).

Date: received 17 Feb 2007

Contact author: wskeith at math ucla edu

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Version: 20070220:101921 (All versions of this report)

Short URL: ia.cr/2007/059

Discussion forum: Show discussion | Start new discussion