Next: Free Bits, PCPs and
Up: The First 1.5 Years
Previous: Incremental Cryptography and Application
This work introduced Private Information Retrieval,
which is a method to obtain information from a database that is
split between several (non-colluding) servers without revealing any
information about the specific record being retreived.
The main result is a two-server scheme of communication complexity
related to the third root of the length of the original database.
Comments:
Authored by B. Chor, O. Goldreich, E. Kushilevitz and M. Sudan. Appeared in
- Proc. of the 36th FOCS, pp. 41-50, 1995.
- Jour.
of the ACM, Vol. 45, No. 6, pages 965-982, November 1998.
Oded Goldreich
2003-07-30