Technical Report CS0962

Title: One-way Trapdoor Permutations Are Sufficient for Single-Server Private Information Retrieval
Authors: Eyal Kushilevitz and 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, if $K$ is the security parameter of the trapdoor permutations, we show a protocol where the user sends $O(K^2)$ bits and the server sends $n-\frac{cn\log n}{K}$ bits (for any constant $c$). Thus, for sufficiently large databases (e.g., when $K=n^\epsilon$ for some small $\epsilon$) our construction breaks the information-theoretic lower-bound (of $n$ bits); this demonstrates the feasibility of basing private information retrieval on general assumptions, resolving a major open problem in this area.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1999
To the main CS technical reports page

Computer science department, Technion