A newer kind of puzzle, noisy equations with only a few unknowns each, that can also support public-key encryption.
The idea: Most public-key schemes come from algebra: factoring, curves, lattices, codes. This one shows a purely combinatorial route: equations that each involve only a few unknowns, some with wrong answers, wired together along a carefully chosen network (an expander graph). The trapdoor is a small hidden structure planted among the equations that only the key holder knows. It matters as insurance: if the algebraic families fell, ideas like this might still stand.
Why it matters: A backup family of assumptions, not used in products.
On the map: + expanders / local functions (Applebaum-Barak-Wigderson 2010): public-key encryption with no number theory or lattices, no deployed scheme
Applebaum, Barak and Wigderson (2010)[1] built public-key encryption from the hardness of sparse noisy linear equations combined with assumptions about expander graphs and simple local functions.
It shows public-key cryptography can come from purely combinatorial problems, not only number theory, lattices or codes. There is no deployed scheme, but it widens the pool of independent assumptions to fall back on.
If any of these breaks, this breaks too.
If this breaks, these break with it.
Nothing on the map depends on it: it is an end point, something people use directly.