# Technical Report CS0906

 TR#: CS0906 Class: CS Title: Replication Is NOT Needed: A SINGLE Database, Computational PIR Authors: E. Kushilevitz and R. Ostrovsky PDF Not Available Abstract: We establish the following, quite unexpected, result: replication of data for the computational Private Information Retrieval (PIR) problem is not necessary! More specifically, based on the quadratic residuosity assumption, we present a {\em single database}, computationally-private information-retrieval scheme with $O(n^\epsilon)$ communication complexity for any $\epsilon >0$. 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/1997/CS/CS0906), rather than to the URL of the PDF files directly. The latter URLs may change without notice.