Paper 1996/006

Upper bound on the communication complexity of private information retrieval

Andris Ambainis

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.

Metadata
Available format(s)
PS
Publication info
Published elsewhere. Appeared in the THEORY OF CRYPTOGRAPHY LIBRARY and has been included in the ePrint Archive.
Contact author(s)
ambainis @ cclu lv
History
1996-05-23: received
Short URL
https://ia.cr/1996/006
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:1996/006,
      author = {Andris Ambainis},
      title = {Upper bound on the communication complexity of private information retrieval},
      howpublished = {Cryptology ePrint Archive, Paper 1996/006},
      year = {1996},
      note = {\url{https://eprint.iacr.org/1996/006}},
      url = {https://eprint.iacr.org/1996/006}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.