[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Private Information Retrieval
This work looks like it might be of interest to readers of this list.
--- On Tue, 24 Sep 1996 14:52:08 -0700 (PDT) Scott Dakins
<[email protected]> wrote:
UNIVERSITY OF WASHINGTON
Seattle, Washington 98195
Department of Computer Science and Engineering
SPEAKER: Benny Chor,
Technion, Haifa, Israel
TITLE: Private Information Retrieval
DATE: Wednesday, September 25, 1996
TIME: 3:30 pm
PLACE: 422 Sieg Hall
HOST: Richard Karp
Publicly accessible databases are an indispensable resource for retrieving
up to date information. But they also pose a significant risk to the
privacy of the user, since a curious database operator can follow the user's
queries and infer what the user is after. Indeed, in cases where the
users' intentions are to be kept secret, users are often cautious about
accessing the database. It can be shown that when accessing a single
database, to completely guarantee the privacy of the user, the whole database
should be downloaded , namely $n$ bits should be communicated (where $n$ is
the number of bits in the database).
In this work, we investigate whether by replicating the database, more
efficient solutions to the private retrieval problem can be obtained.
We describe schemes that enable a user to access $k$ replicated copies of
a database ($k\geq 2$) and privately retrieve information stored in the
database. This means that each individual database gets no information on
the identity of the item retrieved by the user. These schemes use the
replication to gain substantial saving.
In the talk, I will describe the original work on this topic (joint work
with Oded Goldreich, Eyal Kushilevitz, and Madhu Sudan), as well as recent
developments in this area.
Refreshments to follow.
Email: [email protected]
---------------End of Original Message-----------------