**
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 |