# Technical Report CS0962

 TR#: CS0962 Class: CS Title: One-way Trapdoor Permutations Are Sufficient for Single-Server Private Information Retrieval Authors: Eyal Kushilevitz and Rafail Ostrovsky PDF CS0962.pdf 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. Copyright The 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 (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/1999/CS/CS0962), rather than to the URL of the PDF files directly. The latter URLs may change without notice.