BEGIN:VCALENDAR
VERSION:2.0
X-WR-CALNAME:CIS/Microsoft Seminars 2008/2009 Events
BEGIN:VEVENT
DTSTART;TZID=US/Eastern:20090109T103000
DTEND;TZID=US/Eastern:20090109T120000
URL;VALUE=URI:http://www.csail.mit.edu/events/eventcalendar/calendar.php?show=event&id=2072
SUMMARY:Merkle Puzzles are Optimal --- an O(n2)-query attack on key exchange from a random oracle
LOCATION:32-G449
DESCRIPTION:Series: CIS/Microsoft Seminars 2008/2009\nSpeaker:  Boaz Barak\, Princeton University \nHost: \, \nContact: be\, 3-6098\, imbe\nRefreshment Time: \nRelevant URL: \nWe prove that every key exchange protocol in the random oracle model\nin which the honest users make at most n queries to the oracle can be\nbroken by an adversary making O(n2) queries to the oracle. This\nimproves on the previous O~(n6) query attack given by Impagliazzo and\nRudich (STOC '89)\, and answers an open question posed by them. Our\nbound is optimal up to a constant factor since Merkle (CACM '78) gave\nan n-query key exchange protocol in this model that cannot be broken\nby an adversary making o(n2) queries.\n\nJoint work with Mohammad Mahmoody-Ghidary. 
END:VEVENT
END:VCALENDAR