New YorkGödel’s undecidability is now a cryptographic primitive.
Existing post-quantum schemes rely on computationally hard problems; undecidability is absolute — no algorithm can ever resolve it.
Whether undecidability-based primitives can run fast enough for practical deployment remains unproven.
Sources: Quanta Magazine
THE HALTING PROBLEM
In 1936, Alan Turing proved no algorithm can decide in general whether an arbitrary program will eventually halt or run forever. This was the first proven undecidable problem — a question no computer, however powerful, can answer in finite time.
GÖDEL'S SHADOW
Kurt Gödel's 1931 incompleteness theorems showed that any consistent formal system rich enough to express arithmetic contains true statements it cannot prove. Undecidability is the computational shadow of this result — some questions have no mechanical procedure to settle them.
HARD VS IMPOSSIBLE
RSA rests on factoring being slow; lattice schemes rest on shortest-vector problems being slow. Slow is not the same as impossible — a faster algorithm or a quantum computer can collapse the gap. Undecidability has no such gap to collapse.
SHOR'S GUILLOTINE
Shor's algorithm (1994) factors integers and computes discrete logarithms in polynomial time on a quantum computer. This is why intelligence agencies are presumed to be recording encrypted traffic today — harvest now, decrypt later — and why NIST spent a decade selecting quantum-resistant replacements.
THE CATCH
Cryptography needs two things from a hard problem: that the attacker cannot solve it, and that the legitimate user can. Undecidable problems block everyone — including the person trying to decrypt their own message. Building a usable scheme requires carving out a decidable trapdoor inside an undecidable structure, which is where the engineering bleeds.
AES SURVIVES
Symmetric ciphers like AES-256 are not threatened by Shor. Grover's algorithm halves their effective key length, so AES-256 behaves like AES-128 under quantum attack — still secure. The quantum threat is to public-key cryptography, which is how two strangers establish a shared symmetric key in the first place.