From: Ravi Pandya <rpandya@netcom.com>
Date: Wed, 25 Sep 1996 13:21:17 +0800
To: cypherpunks@toad.com
Subject: Private Information Retrieval
Message-ID: <2.2.32.19960924222443.006964e8@netcom7.netcom.com>
MIME-Version: 1.0
Content-Type: text/plain


This work looks like it might be of interest to readers of this list.

Ravi
--- On Tue, 24 Sep 1996 14:52:08 -0700 (PDT)  Scott Dakins
<sjdakins@cs.washington.edu> wrote:
UNIVERSITY OF WASHINGTON
Seattle, Washington 98195

Department of Computer Science and Engineering
Box 352350
(206) 543-1695

COLLOQUIUM

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

ABSTRACT:

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: talk-info@cs.washington.edu

Info: http://www.cs.washington.edu




---------------End of Original Message-----------------