The bet that a disguised easy puzzle (picking numbers that add up to a target) stays hard. Shamir undid the disguise in 1982.
The idea: An easy knapsack has each number bigger than all the previous ones combined, so you can solve it greedily from the largest down. Merkle and Hellman multiplied every number by a secret value modulo a secret number to make the list look random. Shamir showed that the disguised numbers still betray a multiplier and modulus that turn the puzzle back into an easy one.
Why it matters: Proof that building on an NP-hard problem isn't enough: the specific puzzles a scheme produces must be hard too.
On the map: ✗ broken 1982 (Shamir): subset sum is NP-hard, these instances weren't
Subset sum: given some numbers and a target, find the ones that add up to the target. It is NP-hard in general, which made it look like a perfect foundation. Merkle and Hellman started from an easy instance (each number bigger than the sum of all the smaller ones, solvable greedily) and disguised it with a secret modular multiplication[1].
In 1982 Shamir showed[2] how to undo the disguise in polynomial time. Iterated versions fell to Brickell (1985)[3], and lattice reduction (Lagarias and Odlyzko, 1985)[4] breaks most low-density knapsacks outright. The lesson connects to P ≠ NP: a problem being NP-hard in the worst case says nothing about the specific, structured instances a cryptosystem produces.
If any of these breaks, this breaks too.
If this breaks, these break with it.