Some puzzles are easy to check but seem very hard to solve, like a sudoku: checking a filled grid takes seconds, filling it in can take hours. P ≠ NP says that gap is real. Nobody has proven it, but all of cryptography bets on it.
The idea: Every scheme is arranged so that honest users only ever check things (is this signature valid? does this key open the file?), while an attacker has to find things (which key? which signature?). P ≠ NP is the bet that finding can be fundamentally harder than checking. Even that isn't enough on its own: cryptography needs puzzles that are hard almost every time you pick one at random, not just in rare worst cases, so the other boxes on the map are stronger, more specific bets.
Why it matters: If it were false, computers could find secret keys about as fast as they check them.
The details
On the map: necessary for classical crypto, not known to be sufficient. Quantum caveat: pseudorandom quantum states exist in an oracle world where P = NP (Kretschmer et al. 2023)
P is the set of problems a computer can solve quickly. NP is the set of problems whose answers can be checked quickly. P ≠ NP says some problems are easy to check but hard to solve.
Cryptography lives in that gap: checking a key or a signature is easy, finding the key must be infeasible. If P = NP, an attacker could find secret keys about as fast as you can verify them, and every scheme that relies on computational hardness would collapse.
It is necessary, and not known to be enough. Cryptography needs problems that are hard for typical, randomly chosen instances, not just for a few worst cases, and P ≠ NP alone isn't known to provide them: Impagliazzo's worlds include ones where P ≠ NP holds and cryptography still fails[1]. The Merkle-Hellman knapsack is the classic warning: built on an NP-hard problem in 1978, broken in 1982[2, 3]. Nobody has proven P ≠ NP. It is one of the Clay Millennium Prize problems[4].
Quantum caveat: some quantum primitives (pseudorandom quantum states) can exist even in an oracle world where P = NP (Kretschmer et al. 2023)[5], so the "necessary" part is a statement about classical cryptography.
Rests on
If any of these breaks, this breaks too.
Nothing below it on the map: this is a starting point that the rest builds on.
R. Impagliazzo. A personal view of average-case complexity. Proceedings of Structure in Complexity Theory. Tenth Annual IEEE Conference, 1995. doi:10.1109/sct.1995.514853
R. Merkle and M. Hellman. Hiding information and signatures in trapdoor knapsacks. IEEE Transactions on Information Theory, 1978. doi:10.1109/tit.1978.1055927
Adi Shamir. A Polynomial Time Algorithm for Breaking the Basic Merkle-Hellman Cryptosystem. Advances in Cryptology, 1983. doi:10.1007/978-1-4757-0602-4_27
William Kretschmer, Luowen Qian, Makrand Sinha and Avishay Tal. Quantum Cryptography in Algorithmica. Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023. doi:10.1145/3564246.3585225