Can two strangers agree on a secret while everyone is listening? Can you lock a message with a padlock anyone can close but only you can open? This box assumes yes, which needs more than one-way functions.
The idea: A plain one-way function lets you lock something that only you can open later, but not something a stranger can lock for you, or a secret two strangers can agree on in public. For that the problem needs extra structure: a hidden shortcut (a trapdoor, as in RSA), or a way for two secrets to combine (as in Diffie-Hellman). The second needs less: Diffie-Hellman gives encryption without any trapdoor. Impagliazzo and Rudich showed that no straightforward ("black-box") construction gets this from a one-way function alone, which is why it's a separate, stronger bet.
Why it matters: It's how your browser sets up a private connection to a site it has never talked to before.
On the map: needs more than one-way functions (Cryptomania). Quantum computers don't change that for classical keys (no black-box construction, Li-Li-Li-Liu 2026). Only QKD sidesteps it, with a quantum channel. If it were impossible, every assumption tagged KE would fall, with everything built on it. Untagged ones (ECDLP, isogeny paths, SIS, standard-noise LPN) are only known to give signatures, hashes or OT extension
The assumption that you can encrypt to someone's public key, or equivalently that two strangers can agree on a secret in two messages over a public channel: Alice's message works as her public key, which is exactly how Diffie-Hellman becomes ElGamal encryption[1]. Key agreement with more messages might exist even without public-key encryption: Rudich built oracle worlds where k messages suffice but k-1 don't[2]. Every assumption on the map that gives key exchange gives the two-message kind.
Public-key encryption is strictly more than one-way functions: Impagliazzo and Rudich showed it can't be built from one-way functions in a black-box way[3], and Li, Li, Li and Liu (published 2026, preprint 2025)[4] showed quantum computers don't change that for classical keys. Impagliazzo called this world "Cryptomania"[5].
Every assumption tagged KE on the map gives key exchange on its own. So if public-key encryption turned out to be impossible, all of them would fall, and with them RSA, Diffie-Hellman, ML-KEM and McEliece. Untagged ones such as ECDLP, isogeny paths, SIS and standard-noise LPN are only known to give signatures, hashes or OT extension.
A trapdoor function, the hidden shortcut behind RSA, gives public-key encryption but is a stronger bet: see the trapdoor box beside this one.
The only known way around it uses physics instead of hardness: quantum key distribution[6].
If any of these breaks, this breaks too.
If this breaks, these break with it.