Rafail Ostrovsky - Publications

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

Eyal Kushilevitz and Rafail Ostrovsky


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