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-\frac{c n}{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^\epsilon$ for some small $\epsilon$) 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 |