No relativizing reduction from OWF to PKE

Unconditional · against relativizing reductions · IR89

Statement

No relativizing construction of PKE from a one-way function exists. Relative to a random permutation together with a $\mathbf{PSPACE}$-complete oracle, one-way permutations exist and no key-agreement protocol is secure — IR89 (OWP ⇏ KE). A one-way permutation is a one-way function and PKE gives two-message key agreement, so relative to the same oracle one-way functions exist and PKE does not.

Sketch

Against a key-agreement protocol whose parties make $q$ queries to the random permutation $\pi$, the eavesdropper repeatedly queries the points that are likely to have been queried given the transcript and its own queries; after $\mathrm{poly}(q)$ queries it holds, with high probability, every query asked by both parties, and it recovers the key by sampling a view of one party consistent with the transcript and its own queries. The $\mathbf{PSPACE}$-complete oracle makes the sampling efficient, while $\pi$, being random, stays one-way against every adversary making polynomially many queries.

Notes

• An eavesdropper making $O(q^2)$ queries breaks any key-agreement protocol whose parties make $q$ random-oracle queries, so Merkle’s quadratic query gap is optimal and the separation is quantitatively tight — BM09.
• The separation restricts the proof technique only; whether one-way functions imply PKE is open — folklore.
• Collision-resistant hash functions also exist relative to the IR89 oracle, so no relativizing construction of PKE from them exists either — standard.