TR#: | CS0962 |

Class: | CS |

Title: | One-way Trapdoor Permutations Are Sufficient for Single-Server Private Information Retrieval |

Authors: | Eyal Kushilevitz and Rafail Ostrovsky |

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.

To the list of the CS technical reports of 1999

To the main CS technical reports page