[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$.

BibTeX

Copy

@Inproceedings{FOCS:KusOst97,
  author = {Eyal Kushilevitz and Rafail Ostrovsky},
  title = {Replication is {NOT} Needed: {SINGLE} Database, Computationally-Private Information Retrieval},
  pages = {364--373},
  booktitle = {38th Annual Symposium on Foundations of Computer Science},
  address = {Miami Beach, Florida},
  month = {oct~19--22},
  publisher = {{IEEE} Computer Society Press},
  year = {1997},
  doi = {10.1109/SFCS.1997.646125},
}