--- begin forwarded text Mime-Version: 1.0 Date: Thu, 25 Sep 1997 19:11:39 -0400 To: dcsb@ai.mit.edu From: Kent Borg <kentborg@borg.org> Subject: Forward: Private Information Retrieval Talk friday Sender: bounce-dcsb@ai.mit.edu Precedence: bulk Reply-To: Kent Borg <kentborg@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@theory.lcs.mit.edu (Ron Rivest) ** Date: Thu, 25 Sep 97 10:31:48 EDT ** To: cis-reading-group@theory.lcs.mit.edu, cis-seminars@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@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@ai.mit.edu" with one line of text: "help". --- end forwarded text ----------------- Robert Hettinga (rah@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/