Anzeige
Erschienen in:
2009 | OriginalPaper | Buchkapitel
Merkle Puzzles Are Optimal — An O(n2)-Query Attack on Any Key Exchange from a Random Oracle
verfasst von : Boaz Barak, Mohammad Mahmoody-Ghidary
Erschienen in: Advances in Cryptology - CRYPTO 2009
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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
(
n
2
) queries to the oracle. This improves on the previous
$\Tilde{\Omega}(n^6)$
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 a key exchange protocol that can easily be implemented in this model with
n
queries and cannot be broken by an adversary making
o
(
n
2
) queries.