No reduction from ROM to KE

Unconditional · against free reductions · IR89, BM09

Statement

No reduction of any kind from the random oracle model to key agreement exists. In the random oracle model every key-agreement protocol whose honest parties make $\ell$ oracle queries is broken by an eavesdropper making $\tilde{O}({\ell }^6)$ queries — IR89 — and by one making $O({\ell }^2)$ queries, matching the quadratic gap of Merkle’s puzzles — BM09. Hence no random-oracle key agreement is secure against eavesdroppers making polynomially many queries; both eavesdroppers are bounded in oracle queries, not in computation.

Notes

• Merkle’s puzzles (ROM ⇒ Merkle puzzles) is consistent with the barrier: its gap between $O(n)$ honest and $\Omega (n^2)$ eavesdropper queries is polynomial — Mer78.
• For protocols whose honest parties’ queries are uniformly random, or which run in two rounds with non-adaptive queries, secrecy against an eavesdropper making roughly ${\ell }^2$ queries requires $\Omega (\ell )$ bits of communication, as in Merkle’s puzzles; the first case is proved by reduction from two-party set disjointness, the second by an information-theoretic argument — HMO+19.