Cryptology ePrint Archive: Report 1996/006
Upper bound on the communication complexity of private information retrieval
Abstract: Private information retrieval was introduced
by Chor, Goldreich, Kushilevitz and Sudan.
It is the problem of reading a bit from the database so
that it remains secret which bit we need.
If the database exists in several identical copies,
it is possible to ask queries so that each of copies
alone does not get any information about the adress
of the needed bit.
We construct a scheme for private information retrieval
with k databases and O(n sup (1/(2k-1)) ) bits of communication.
Category / Keywords:
Publication Info: Appeared in the THEORY OF CRYPTOGRAPHY LIBRARY and has been included in the ePrint Archive.
Date: received May 23rd, 1996.
Contact author: ambainis at cclu lv
Available formats: Postscript (PS) | Compressed Postscript (PS.GZ) | BibTeX Citation
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]