  In this paper we study one-round key-agreement protocols analogous to
Merkle's puzzles in the random oracle model. The players Alice and Bob are
allowed to query a random permutation oracle $n$ times and upon their queries
and communication, they both output the same key with high probability. We
prove that Eve can always break such a protocol by querying the oracle $O(n^2)$
times. The long-time unproven optimality of the quadratic bound in the fully
general, multi-round scenario has been shown recently by Barak and
Mahmoody-Ghidary. The results in this paper have been found independently of
their work.
