**
One-way Trapdoor Permutations Are Sufficient for
Non-Trivial Single-Server Private Information Retrieval
**

*
Eyal Kushilevitz, Rafail Ostrovsky
*

**
Abstract:
**

We show that general one-way trapdoor permutations are sufficient to
privately retrieve an entry from a database of size n with total
communication complexity strictly less than n. More specifically,
we present a protocol in which the user sends O(K^{2}) bits and the
server sends n-cn ^{K} bits (for any constant c), where K
is the security parameter of the trapdoor permutations. Thus, for
sufficiently large databases (e.g., when K=n^{∈} for some small
∈ our construction breaks the information-theoretic
lower-bound (of at least n bits). This demonstrates the feasibility
of basing single-server private information retrieval on general
complexity assumptions.

An important implication of our result is that we can implement a 1-out-of-n Oblivious Transfer protocol with communication complexity strictly less than n based on any one-way trapdoor permutation.

**comment:**
Appeared In Proceedings of Advances in Cryptology
B. Prneel (ED.): EUROCRYPT 2000,
LNCS 1807, pp. 104-121, 2000. Springer-Verlag.

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

Back to Publications List |