Replication is NOT Needed: SINGLE Database, Computationally-Private Information Retrieval

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.

Authors

• Eyal Kushilevitz
• Rafail Ostrovsky

Keywords

• Databases
• Information retrieval
• Complexity theory
• Data privacy
• Upper bound
• History
• Indexes
• Computer science
• Postal services
• Polynomials
• Replication Data
• Complex Communication
• One-way Function
• Information Theory
• Regulon
• Basic Scheme
• Hash Function
• Binary String
• Security Protocols
• Most Significant Bit
• User Requests
• String Length
• Security Parameter
• Recursive Scheme
• Probabilistic Polynomial Time