New YorkA new construction roots cryptographic hardness in Gödelian undecidability — problems provably unsolvable under any axiom system.
Standard schemes rely on computational difficulty like factoring or lattices.
The result opens a third cryptographic foundation distinct from the 2 families dominating post-quantum proposals.
Sources: Quanta Magazine
THE TWO FAMILIES
Modern public-key crypto rests on two hardness assumptions: integer factorization (RSA) and discrete logarithms (Diffie-Hellman, ECC). Both crumble under a sufficiently large quantum computer running Shor's algorithm — which is why every standards body is racing toward a third foundation.
WHAT GÖDEL PROVED
In 1931 Kurt Gödel showed that any consistent formal system rich enough to express arithmetic contains statements that are true but unprovable within the system. Turing extended this in 1936: there exist problems no algorithm can ever decide, no matter how much time or memory it has.
THE HALTING PROBLEM
Turing's canonical example: given an arbitrary program, decide whether it eventually halts or runs forever. No general algorithm can answer this. Many undecidable problems reduce to halting — including word problems in group theory, Diophantine equations (Hilbert's 10th), and tiling questions.
WHY THIS MATTERS FOR CRYPTO
Conventional crypto assumes an attacker lacks enough computing power. An undecidability-rooted scheme assumes the attacker faces a mathematical wall no amount of computation — classical or quantum — can climb. Quantum speedups don't help: Shor's algorithm accelerates specific structured problems, not the general halting problem.
THE CATCH
Undecidability is a worst-case statement about the hardest instances. Cryptography needs average-case hardness — most instances must be hard, not just some. Translating an undecidable problem into a scheme where typical keys are unbreakable is the entire technical challenge, and where most past attempts have failed.
THE LINEAGE
Cryptographers have flirted with undecidability since the 1980s — Wagner and Magyarik proposed a public-key system based on the word problem for groups in 1985. It was broken. Subsequent attempts using Post correspondence problems and Diophantine equations met similar fates. A durable construction would be a genuine third pillar.