Welcome to the resource topic for 2008/032
Title:
Merkle’s Key Agreement Protocol is Optimal: An O(n^2) Attack on any Key Agreement from Random Oracles
Authors: Boaz Barak, Mohammad Mahmoody
Abstract:We prove that every key agreement 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 who makes O(n^2) queries to the oracle. This improves on the previous \Omega(n^6) query attack given by Impagliazzo and Rudich (STOC '89) and resolves an open question posed by them. Our bound is optimal up to a constant factor since Merkle proposed a key agreement protocol in 1974 that can be easily implemented with n queries to a random oracle and cannot be broken by any adversary who asks o(n^2) queries.
ePrint: https://eprint.iacr.org/2008/032
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .