Rafail Ostrovsky - Publications

Replication Is Not Needed: Single Database, Computationally-Private Information Retrieval

Eyal Kushilevitz and Rafail Ostrovsky

Abstract: We establish the following, quite unexpected, result: replication of data for the computational Private Information Retrieval problem is not necessary. More specifically, based on the quadratic residuosity assumption, we present a single database, computationally-private information-retrieval scheme with $O(n^\epsilon)$ communication complexity for any $\epsilon >0$.

comment: Appeared In Proceedings of Thirty-eigth Annual IEEE Symposium on the Foundations of Computer Science (FOCS-97)

Fetch PostScript file of the paper     Fetch PDF file of the paper

Back to Publications List