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
- Probabilistic encryption
- Personal Communication
- The Knowledge Complexity of Interactive Proof Systems
- How to play ANY mental game
- A Randomized Protocol for Signing Contracts
- A Simple Unpredictable Pseudo-Random Number Generator
- Software protection and simulation on oblivious RAMs
- Private information retrieval
- Non-transitive transfer of confidence: A perfect zero-knowledge interactive protocol for SAT and beyond
- Personal communication