Forward: Private Information Retrieval Talk friday

[Robert Hettinga]

--- begin forwarded text


Mime-Version: 1.0
Date: Thu, 25 Sep 1997 19:11:39 -0400
To: dcsb at ai.mit.edu
From: Kent Borg <kentborg at borg.org>
Subject: Forward: Private Information Retrieval Talk friday
Sender: bounce-dcsb at ai.mit.edu
Precedence: bulk
Reply-To: Kent Borg <kentborg at borg.org>

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: rivest at theory.lcs.mit.edu (Ron Rivest)
 ** Date: Thu, 25 Sep 97 10:31:48 EDT
 ** To: cis-reading-group at theory.lcs.mit.edu, cis-seminars at theory.lcs.mit.edu
 ** 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
kentborg at borg.org                       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
"dcsb-request at ai.mit.edu" with one line of text: "help".

--- end forwarded text



-----------------
Robert Hettinga (rah at shipwright.com), 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/