Merkle Puzzles are Optimal --- an O(n2)-query attack on key exchange from a random oracle
Speaker: Boaz Barak , Princeton University
Date: January 9 2009
Time: 10:30AM to 12:00PM
Location: 32-G449
Contact: be, 3-6098, imbe
Relevant URL:
We prove that every key exchange protocol in the random oracle model
in which the honest users make at most n queries to the oracle can be
broken by an adversary making O(n2) queries to the oracle. This
improves on the previous O~(n6) query attack given by Impagliazzo and
Rudich (STOC '89), and answers an open question posed by them. Our
bound is optimal up to a constant factor since Merkle (CACM '78) gave
an n-query key exchange protocol in this model that cannot be broken
by an adversary making o(n2) queries.
Joint work with Mohammad Mahmoody-Ghidary.
See other events that are part of CIS/Microsoft Seminars 2008/2009
See other events happening in January 2009
