Undecidable Encryption

This article is part of the Quantum Snake Oil Dictionary — a series examining terms used in quantum technology marketing. The series is divided into Red Flag Terms (terms with no established technical meaning that almost always signal hype or fraud) and Misused Terms (legitimate concepts routinely stripped of context in marketing). This entry is a Misused Term.

“Undecidable Encryption”

A note before we begin. This entry examines “undecidable encryption” and the broader pitch that a cipher is secure because it is built on an undecidable problem. I am not writing about any specific company or product. Undecidability is real and precise mathematics, which is exactly why it makes effective marketing, and also why the claim deserves careful handling rather than a reflexive dismissal.

What Undecidability Actually Means

A problem is undecidable when no single algorithm can correctly answer it for every possible input. The original example is Alan Turing’s halting problem: there is no general procedure that decides, for an arbitrary program and input, whether the program eventually stops. The example that drives most “undecidable encryption” pitches is Hilbert’s tenth problem, which asks for a general method to decide whether an arbitrary Diophantine equation — a polynomial equation solved in integers — has a solution. In 1970, Yuri Matiyasevich completed a proof that no such method exists. Solving Diophantine equations in general is undecidable.

This is a deep and genuinely beautiful result. It is also a precise one, and the precision matters, because three specific features of it are what the marketing quietly drops.

Undecidability is a statement about a single algorithm working for every instance, across an infinite family of problems, answering a yes-or-no question about whether a solution exists. Each of those features is load-bearing, and a cipher needs the opposite of each.

The Three Gaps Between Undecidability and Security

First, undecidability is a worst-case, whole-family property. It says no algorithm handles all equations. A cipher does not emit all equations; it emits a specific, narrow distribution of them, generated by its own construction. “No method works for every possible equation” tells you nothing about whether the particular equations your cipher produces are hard. Most amateur cryptosystems die in this gap between a worst-case guarantee and the average case the system actually runs in.

Second, undecidability is about decision, but an attacker faces a search problem. Hilbert’s tenth problem asks whether a solution exists. The attacker against a cipher is not wondering whether a solution exists. They know it does, because the legitimate recipient decrypts with it, which means the message is itself a solution by construction. The attacker’s task is to find a solution that is known in advance to be there. That is a different and usually far easier problem than the undecidable one.

Third, undecidability is about arbitrary instances, but a working cipher needs structured ones. To let the right recipient decrypt, the scheme has to build equations with a planted, recoverable solution and a usable trapdoor. That structure is not incidental. It is mandatory, and it is precisely the foothold an attacker uses. The undecidable general problem is never touched, because the attacker goes after the scaffolding the designer was forced to add.

Thirty Years of the Same Failure

This is not a theoretical worry. The pattern has repeated for three decades, and it always breaks the same way.

In 1995, Lin, Chang, and Lee proposed a public-key cipher whose security was meant to rest on the difficulty of solving certain Diophantine equations. Thomas Cusick broke it almost immediately, and the manner of the break is the whole lesson: he recovered messages in polynomial time without solving any Diophantine equation at all, by solving linear congruences derived from the public key and ciphertext. The hard problem the scheme advertised was simply bypassed.

The idea was revived as a post-quantum candidate two decades later. A scheme known as DEC, based on Diophantine equations of a special “degree increasing” type, was proposed as offering strong security with unusually small keys. It was broken in polynomial time using lattice reduction, with one of the original designers among the authors of the attack. Once again the attack did not solve the general undecidable problem. It exploited the structure the construction required.

Even the narrower claim that specific Diophantine equations are practically unsolvable has not held. Researchers have shown that particular families yield to A* search, genetic algorithms, and other heuristic and AI-based solvers, even though the general problem has no decision procedure. The general impossibility result and the practical solvability of the instances a cipher needs are not in tension. They coexist comfortably, which is the entire problem.

Why the Pitch Keeps Coming Back

The argument is seductive because every step sounds rigorous on its own. Hilbert’s tenth problem really is undecidable. Matiyasevich’s theorem really is a landmark. The word “undecidable” carries more mathematical weight than “hard,” and weight reads as security. The chain only fails at the joints, where a worst-case impossibility over an infinite family gets quietly swapped for a hardness claim about the specific, structured, solvable instances a usable cipher must generate. That swap is the error, and it has been the error every time.

Questions to Ask a Vendor

“Is the security a worst-case statement about all instances, or a claim about the specific instances your cipher actually generates?” Undecidability is the former. Security needs the latter, and the two are not the same.

“The attacker knows a solution exists, because the recipient decrypts. What makes finding that planted solution hard?” This reframes the question from decision to search, which is the question that actually matters.

“Has the scheme been published and attacked, given that every prior Diophantine cipher fell to its construction rather than to the hard problem?” If the design is not public and cryptanalyzed, the historical base rate is not encouraging.

The Bottom Line

Undecidability is real mathematics, and Hilbert’s tenth problem is genuinely undecidable. None of that transfers to a cipher. The undecidable result is a worst-case statement about whether arbitrary equations have solutions, while a cipher must generate specific, structured equations whose solutions are planted and recoverable. Attackers have spent thirty years breaking exactly those structured instances without ever engaging the hard general problem. When a product’s security rests on the word “undecidable,” the burden is on it to explain why its instances escape a pattern that has caught every predecessor. That explanation has not yet been written.