CISOOnline

Do AI’s mathematical advances put PKI under threat?

Warnings by a leading cryptographer that industry-wide public-key cryptography could fail because of advances in AI has sparked a debate in the security community.

In a series of post on X, Johns Hopkins cryptographer Matthew Green warned that existing public-key cryptography systems were at risk because machines have begun outperforming humans in their ability to address some mathematical problems.

“I think there is a 1% chance we live in Minicrypt, and a 15% chance we functionally lose confidence in our existing public-key encryption algorithms,” Green wrote last month.

Green’s initial warning and follow-up comments offered a warning about the cryptographic foundations beneath public key infrastructure (PKI), rather than an obituary for PKI, the system of certificates, keys, and certificate authorities that secures Transport Layer Security (TLS), code signing, and many other information security functions.

“I’m worried about standardized public-key encryption (and some signatures) and specifically the fact that most of it is based on a small number of hard problems,” Green added.

These hard mathematical problems have been extensively analyzed by humans for years but any comforting notion that this means they are safe is now being undermined because machines have begun outperforming humans in solving some mathematical problems.

Green warns that a disruptive loss of confidence in internet security systems would arise if a major cryptanalytic surprise arrives faster than standards and deployments can adapt — so the industry needs to focus on improved cryptographic agility.

The comments sparked a discussions on LinkedIn and elsewhere about how public-key crypto could fail. Green is yet to respond to CSO’s request for comment on the debate he sparked.

Markku-Juhani O. Saarinen, a cryptographer and professor at Finland’s Tampere University who has looked closely at AI-powered crypto-analysis, told CSO that he takes Green’s warning seriously but urges caution, saying there is no need to rip and replace established industry cryptographic standards.

“We really can’t entirely rule out surprises, but I’d also definitely not recommend some hasty moves, because those are sure to cause problems,” Saarinen said. “Cryptography has good standards, best practices, and active modernization paths (the ‘PQC transition’) — just following those is the most sensible approach from information security perspective.”

The math at stake

Saarinen explained that there are two kinds of “hard problems” in mathematics:

  1. Numerical problems for which a solution is thought to be hard to compute (for computers)
  2. Analytic problems that are open and have been expected to be settled by a human with pencil and paper via a proof, counterexample, new theory, etc.

“What has happened in 2026 is that mathematics had its ‘Lee Sedol moment’ (after the ‘last Go grandmaster’) and [analytical] problems previously thought to be in the human domain (2) are now being solved by computers,” Saarinen told CSO.

Cryptography uses numerical problems in class — traditional ones like factoring the products of large prime numbers and discrete logarithm, and newer ones like learning with errors (LWE). Analyzing those algorithms and their complexity is part of theoretical computer science.

“The fear in cryptography is that AI will find a shortcut for some hard computational problems and make them easy,” Saarinen said. “While AI is very good at optimizing computation, we don’t expect it to turn all hard computational problems into trivial ones.”

2026: Breaking HAWK and McEliece

Cryptographic problems involving set (1) above are typically “sub-exponential”; solving them requires an almost exponential number of operations relative to the problem size or distance.

“A cryptographically relevant break can be exponential but might halve the number of bits; such an analytic break has happened to some relatively new schemes, such as HAWK by AI in 2026, and to numerous older proposals by humans,” Saarinen explained.

AI also played a significant role in finding a significant shortcut to the parameters of the McEliece cryptosystem (one of the earliest public-key schemes, designed in 1978).

“The German cyber agency had been recommending a variant called ‘Classic McEliece’ for quantum security since 2020, but withdrew its recommendation at the end of September,” Saarinen added.

Saarinen clarified that, in both cases, the schemes could still be “considered secure if security parameters were adjusted, but that would have doubled public and secret keys, signatures, and ciphertexts.”

Meanwhile, SA and Elliptic-Curve cryptosystems are already “broken” from a computational-complexity viewpoint because “polynomial-time quantum algorithms for them have been known since 1994, and building quantum computers is ‘just an engineering problem,’” according to Saarinen.

The main post-quantum alternatives, ML-KEM, ML-DSA, and SLH-DSA, have received more than a decade of intense analysis.

Looking for a ‘mathematical shortcut’

Another question that cryptographers are asking is whether public-key cryptography or symmetric cryptography is more vulnerable to AI cryptanalysis.

Saarinen suggested a “mathematical shortcut” is more likely to exist in public-key cryptography given that it, by definition, requires mathematical structure for the “trapdoor” (a secret key that opens a public-key encrypted message or creates a signature that the public key can verify). “Symmetric-key cryptography (hashes and keyed ciphers) has simply more design freedom in this sense,” Saarinen concluded.

Q-Day and LLMs

Professor Alan Woodward, a computer scientist at the University of Surrey, said that LLMs are yet to make a huge dent on cryptography.

“We’ve seen some inroads and erosion of the security guarantees, but what’s actually happening as far as I can see is that the LLMs are acting as a great tool for mathematicians, cryptographers, and computer scientists to speed up their research: that leap of intuition needed to find the fatal flaw still seems to need humans,” Prof. Woodward said. “LLMs are very effective at finding flaws in those implementations rather than the underlying mathematics.”

Prof. Woodward compared the threat posed by AI in breaking encryption schemes to the danger to legacy encryption schemes posed by quantum computers. Both problems highlight the need for improved agility in the cryptographic schemes in use.

“We’ve already seen people migrating in preparation for ‘Q-Day’ so in some ways that should already be addressing the risks posed, if they’re real, by LLMs,” according to Prof. Woodward, referring to the hypothetical future time when quantum computers are powerful enough to break public-key encryption. “The most effective route so far seems to be a hybrid route where we have a mix of cryptographic schemes that, whilst one or two might fall away, leaves us with others we can rely upon. Any found to be flawed for whatever reason can be deprecated rapidly and the intact schemes used instead.”



Source link