• DocumentCode
    3328686
  • Title

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

  • Author

    Kushilevitz, Eyal ; Ostrovsky, Rafail

  • Author_Institution
    Technion-Israel Inst. of Technol., Haifa, Israel
  • fYear
    1997
  • fDate
    20-22 Oct 1997
  • Firstpage
    364
  • Lastpage
    373
  • 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
  • Keywords
    communication complexity; database management systems; information retrieval; communication complexity; computational private information retrieval problem; computationally private information retrieval; data replication; quadratic residuosity assumption; Complexity theory; Computer science; Data privacy; Databases; History; Indexes; Information retrieval; Polynomials; Postal services; Upper bound;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Foundations of Computer Science, 1997. Proceedings., 38th Annual Symposium on
  • Conference_Location
    Miami Beach, FL
  • ISSN
    0272-5428
  • Print_ISBN
    0-8186-8197-7
  • Type

    conf

  • DOI
    10.1109/SFCS.1997.646125
  • Filename
    646125
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=3328686