ROM ⇒ Merkle puzzles

Random oracle model · Mer78

Statement

In the random oracle model, Merkle’s puzzles is a key-agreement protocol in which the honest parties make $O(n)$ oracle queries, while any eavesdropper recovering the key with constant probability makes $\Omega (n^2)$ queries — Mer78.

Notes

• The quadratic gap is optimal: every random-oracle key agreement whose honest parties make $n$ queries falls to an eavesdropper making $O(n^2)$ queries — BM09 (No reduction from ROM to KE).