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|