# Forward: Private Information Retrieval Talk friday


--- begin forwarded text

Mime-Version: 1.0
Date: Thu, 25 Sep 1997 19:11:39 -0400
To: [email protected]
From: Kent Borg <[email protected]>
Subject: Forward: Private Information Retrieval Talk friday
Sender: [email protected]
Precedence: bulk
Reply-To: Kent Borg <[email protected]>

This isn't strictly commerce, but it is anonymity related, and that can be
important for electronic commerce.  It is also likely to be nice and
techie, for those who need an occasional does of substance.

Finally, I forward this to the Digital Commerce Society of Boston list
because it is damn close to Boston.

-kb, the Kent who is enjoying a good news in digital land day.

<< start of forwarded material >>

** From: [email protected] (Ron Rivest)
** Date: Thu, 25 Sep 97 10:31:48 EDT
** To: [email protected], [email protected]
** Subject: Talk friday
**
**
** There will be a CIS seminar this Friday.  All are welcome!
**
** Title:	Protecting Data Privacy in Private Information Retrieval
Schemes.
** Speaker: Tal Malkin
** When:	1:30--3:30 (talk starts at 2PM) Friday, September 26, 1997
** Where:	NE43-518
**
** Abstract:
**
** Private Information Retrieval (PIR) schemes allow a user to retrieve
** the i-th bit of a data string x, replicated in k>=2 databases (in the
** information-theoretic setting) or k>=1 databases (in the computational
** setting), while keeping the value of i private. The main cost measure
** for such a scheme is its communication complexity.
**
** We study PIR schemes where in addition to the user's privacy we
** require {\em data privacy}. That is, in every invocation of the
** retrieval protocol the user learns exactly a single (physical) bit of
** x and no other information about the data. All currently known PIR
** schemes fail to meet this requirement, which is essential for
** real-world'' applications. Solutions to this problem also yield
** efficient distributed implementations of the cryptographic 1 out of n
** oblivious transfer primitive.
**
** We present transformations that allow translating PIR schemes into
** ones that respect data privacy as well, with a small penalty in the
** communication and randomness complexity. In particular we get:
** a k-database scheme of complexity $O(\log n\cdot n^{1/(2k-1)})$ for
** every k>=2; an $O(\log n)$-database scheme of poly-logarithmic
** complexity; and a 2-database computational PIR scheme of complexity
** $O(n^c)$, for every constant $c>0$.  All these schemes require only a
** single round of interaction. A {\em single} database computational
** scheme can also be achieved, based on the hardness of deciding
** quadratic residuosity and using a multi-round protocol.
**
** Joint work with Yael Gertner, Yuval Ishai, and Eyal Kushilevitz.
**

<< end of forwarded material >>

--
Kent Borg                               H: +1-617-776-6899
[email protected]                       W:
"Then with daybreak not quite risen into dawn,
the night and day still deadlocked, round the pyre
a work brigade of picked Achaeans grouped."
- Homer's Illiad (7-500, Fagles tr.)

For help on using this list (especially unsubscribing), send a message to
"[email protected]" with one line of text: "help".

--- end forwarded text

-----------------
Robert Hettinga ([email protected]), Philodox
e$, 44 Farquhar Street, Boston, MA 02131 USA "... however it may deserve respect for its usefulness and antiquity, [predicting the end of the world] has not been found agreeable to experience." -- Edward Gibbon, 'Decline and Fall of the Roman Empire' The e$ Home Page: http://www.shipwright.com/