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 |