Welcome to the resource topic for 1996/006
Upper bound on the communication complexity of private information retrieval
Authors: Andris AmbainisAbstract:
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.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .