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

Authors: Eyal Kushilevitz, Rafail Ostrovsky | Venue: FOCS 1997 | Source

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^{ϵ})$ communication complexity for any $ϵ>0$.