  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 $\widetilde{\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.
