Replication is not needed: single database, computationally-private information retrieval

Eyal Kushilevitz Z, Rafail Ostrovsky · Annual Symposium on Foundations of Computer Science · 2002

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/sup /spl epsiv//) communication complexity for any /spl epsiv/>0.

Cited by 932 works. doi:10.1109/sfcs.1997.646125

Authors

References