Brief IA
›

AI and Cryptography: Matthew Green Estimates the Risk at 15%

Use Cases·Tom Levy·

AI and Cryptography: Matthew Green Estimates the Risk at 15%

AI and Cryptography: Matthew Green Estimates the Risk at 15%
Key Takeaways
1Matthew Green estimates a 15% probability of a significant loss of trust in current public key encryption algorithms.
2Saarinen cites advancements involving AI against HAWK and on McEliece parameters.
3Woodward considers the models particularly useful for accelerating research and detecting implementation flaws.
Why it matters : a cryptanalytic breakthrough could, according to Green, outpace the speed of standards adaptation and deployments.

Matthew Green, a cryptographer at Johns Hopkins, estimates a 15% probability of a significant loss of trust in current public key encryption algorithms due to mathematical advancements in AI. Other experts take this threat seriously but do not recommend hastily abandoning established standards.

Saarinen cites an attack on HAWK in 2026

Markku-Juhani O. Saarinen, a cryptographer and professor at the University of Tampere in Finland, who has studied AI-assisted cryptanalysis, cites an advancement achieved by AI against HAWK in 2026. According to him, an attack can remain exponential while halving the number of bits; humans had already achieved comparable results on many older proposals. He describes the numerical problems involved as generally sub-exponential, with an almost exponential volume of operations relative to their size or distance.

Saarinen also highlights a significant contribution from AI in discovering a shortcut on McEliece parameters, a scheme designed in 1978 among the first public key systems. According to the cryptographer, the German cybersecurity agency stopped recommending Classic McEliece for quantum security at the end of September, after advocating it since 2020. In the cases mentioned, he believes that adjusting the parameters could preserve security but would have doubled the sizes of public and secret keys, signatures, and ciphertexts.

Alan Woodward, a computer science professor at the University of Surrey, does not yet see a major impact from large language models on cryptography. He notes advancements and weakened guarantees but primarily views these models as tools that accelerate the research of mathematicians, cryptographers, and computer scientists. He believes that decisive intuition still seems to be human. In his view, the models mainly identify implementation errors rather than weaknesses in the mathematical foundations.

Two types of mathematical problems

Saarinen distinguishes between the difficulty of performing a numerical calculation and that of solving an open analytical question. The latter may require a proof, a counterexample, or a new theory, work that was previously expected from a human. He anticipates that by 2026, computers will cross this boundary on certain problems, drawing a parallel to Lee Sedol's previous experience in Go.

Cryptography, on the other hand, involves numerical problems: factoring products of large prime numbers, calculating a discrete logarithm, or solving learning with errors, known as LWE. The analysis of the associated algorithms and their complexity falls under theoretical computer science. Saarinen expresses concern that AI might discover a method that makes some of these calculations easy, although he does not expect it to simplify all difficult problems. He does, however, acknowledge its effectiveness in optimizing calculations.

La lettre du soirGratuit · 19 h

Le brief IA que les pros lisent chaque soir

Les 7 actus IA du jour, décryptées en 5 min. Gratuit.

Inclus dès l'inscription : notre sélection des meilleurs guides & comparatifs IA.

Choisissez votre rythme

Gratuit · Pas de spam · Désabonnement en 1 clic

Cryptographers are also questioning the relative vulnerability of public key systems and symmetric cryptography to AI-assisted cryptanalysis. Saarinen considers it more likely that a shortcut exists in public key systems, which require a mathematical structure for a secret trapdoor. This allows for decrypting a message or producing a signature verifiable by the public key. He attributes more design freedom to hash functions and symmetric encryptions.

Green fears a slow adaptation

In his messages published last month, Matthew Green also assigns a 1% probability to the scenario he calls Minicrypt. His concern particularly revolves around the concentration of standardized public key cryptography and certain signatures on a limited set of difficult problems. These problems have been examined for years by humans, but Green fears that advancements in machines on certain mathematical questions could undermine the trust placed in this long analysis.

The focus of his warning is the cryptographic foundation of public key infrastructure, or PKI, rather than an imminent disappearance of it. This infrastructure encompasses certificates, keys, and certification authorities; it secures protocols such as Transport Layer Security, or TLS, as well as code signing. Green envisions a disruption of trust if a major cryptanalytic discovery outpaces the ability of standards and deployments to adapt. His warning has sparked discussions within the security community, particularly on LinkedIn. He calls for greater cryptographic agility.

Standards and migration to post-quantum cryptography

Saarinen takes the alert seriously without calling for the replacement of current standards. While he does not rule out a surprise, he believes that hasty decisions would cause problems and recommends following best practices as well as transitioning to post-quantum cryptography, or PQC. The ML-KEM, ML-DSA, and SLH-DSA solutions have already undergone more than a decade of intensive analysis.

The quantum risk provides another point of comparison. Saarinen considers the designated SA and Elliptic-Curve systems to be broken in terms of computational complexity: he reminds us that polynomial-time quantum algorithms have been known for them since 1994. He describes the construction of the necessary computers as an engineering problem.

Woodward also draws parallels between the threats of AI and quantum computing, which he believes call for a better capacity to change cryptographic schemes. He notes migrations preparing for Q-Day, this hypothetical horizon where quantum machines could break public key encryption, and believes they should also cover potential risks from language models. At this stage, he favors a combination of schemes: if some fail, others would remain usable. Recognized defective mechanisms could then be quickly abandoned in favor of those that withstand scrutiny.

Brief IA — L'actualité IA en français

L'essentiel de l'actualité de l'intelligence artificielle, décrypté et expliqué chaque jour.