International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Upper bound on the communication complexity of private information retrieval

Authors:
Andris Ambainis
Download:
URL: http://eprint.iacr.org/1996/006
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-1996-11273,
  title={Upper bound on the communication complexity of private information retrieval},
  booktitle={IACR Eprint archive},
  keywords={},
  url={http://eprint.iacr.org/1996/006},
  note={Appeared in the THEORY OF CRYPTOGRAPHY LIBRARY and has been included in the ePrint Archive. ambainis@cclu.lv 10500 received May 23rd, 1996.},
  author={Andris Ambainis},
  year=1996
}