Rafail Ostrovsky - Publications

Single Database Private Information Retrieval Implies Oblivious Transfer

Giovanni Di Crescenzo, Tal Malkin and Rafail Ostrovsky

Abstract: A Single-Database Private Information Retrieval (PIR, for short) is a protocol that allows a user to privately retrieve from a database an entry with as small as possible communication complexity. We call any PIR protocol non-trivial if its total communication complexity is strictly less than the total size of the database (i.e., a PIR protocol is non-trivial even if the total communication is just one bit less then the total size of the database). Non-trivial PIR is an important cryptographic primitive with many applications. Thus, understanding which assumptions are necessary for implementing such a primitive is an important task, although (so far) not a well-understood one. In this paper we show that any non-trivial PIR implies Oblivious Transfer, a far better understood primitive. Our result not only significantly clarifies our understanding of any non-trivial PIR protocol, but also yields the following consequences:

-- Any non-trivial PIR is complete for all two-party and multi-party secure computations.

-- There exists a communication-efficient reduction from any PIR protocol to a $1$-out-of-$n$ Oblivious Transfer protocol (also called SPIR).

-- There is a strong evidence that the assumption of the existence of a one-way function is necessary but not sufficient for any non-trivial PIR implementation.

comment: Appeared in Proceedings of Advances in Cryptology B. Preneel (ED.): EUROCRYPT 2000, LNCS 1807, pp. 122-138, 2000. Springer-Verlag.

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

Back to Publications List