No relativizing reduction from KE to PKE

Unconditional · against relativizing reductions · Rud91

Statement

For every $k$ there is an oracle relative to which $k$-message key agreement exists and $(k-1)$-message key agreement does not — Rud91. Two-message key agreement and PKE imply each other by constructions that relativize — folklore — so the oracle for $k=3$ rules out every relativizing, and in particular every fully-black-box, construction of PKE from key agreement.

Sketch

PKE gives two-message key agreement: Alice sends a public key and Bob an encryption of a uniform key. Conversely, the first message of a two-message protocol serves as a public key, and Bob’s reply together with his key, used as a one-time pad, is a ciphertext — folklore.

Notes

• The same oracle separates key agreement from trapdoor functions: No relativizing reduction from KE to TDP — Rud91.