Contrary to popular superstition, AES 128 is just fine in a post-quantum world

With growing focus on the existential threat quantum computing poses to some of the most crucial and widely used forms of encryption, cryptography engineer Filippo Valsorda wants to make one thing absolutely clear: Contrary to popular mythology that refuses to die, AES 128 is perfectly fine in a post-quantum world.

AES 128 is the most widely used variety of the Advanced Encryption Standard, a block cipher suite formally adopted by NIST in 2001. While the specification allows 192- and 256-bit key sizes, AES 128 was widely considered to be the preferred one because it meets the sweet spot between computational resources required to use it and the security it offers. With no known vulnerabilities in its 30-year history, a brute-force attack is the only known way to break it. With 2¹²⁸ or 3.4 x 10³⁸ possible key combinations, such an attack would take about 9 billion years using the entire bitcoin mining resources as of 2026.

It boils down to parallelization

Over the past decade, something interesting happened to all that public confidence. Amateur cryptographers and mathematicians twisted a series of equations known as Grover’s algorithm to declare the death of AES 128 once a cryptographically relevant quantum computer (CRQC) came into being. They said a CRQC would halve the effective strength to just 2⁶⁴, a small enough supply that—if true—would allow the same bitcoin mining resources to brute force it in less than a second (the comparison is purely for illustration purposes; a CRQC almost certainly couldn’t run like clusters of bitcoin ASICs and more importantly couldn’t parallelize the workload as the amateurs assume).

On Monday, Valsorda finally channeled years’ worth of frustration, fueled by the widely held misunderstanding, into a blog post titled “Quantum Computers Are Not a Threat to 128-bit Symmetric Keys.”

“There’s a common misconception that quantum computers will ‘halve’ the security of symmetric keys, requiring 256-bit keys for 128 bits of security,” he wrote. “That is not an accurate interpretation of the speedup offered by quantum algorithms, it’s not reflected in any compliance mandate, and risks diverting energy and attention from actually necessary post-quantum transition work.”

That’s the easy part of the argument. The much harder part is the math and physics that explain it. At its highest level, it comes down to a fundamental difference in the way a brute-force search works on classical computers versus the way it works using Grover’s algorithm. Classical computers can perform multiple searches simultaneously, a capability that allows large tasks to be broken into smaller pieces to complete the overall job faster. Grover’s algorithm, by contrast, requires a long-running serial computation, where each search is done one at a time.

“What makes Grover special is that as you parallelize it, its advantage over non-quantum algorithms gets smaller,” Valsorda said in an interview. He continued:

Imagine it with small numbers, let’s say there are 256 possible combinations to a lock, A normal attack would take 256 tries. You decide it’s too long, so you get three friends and you each do 64 tries. “That’s the classical parallelization. With Grover you could in theory do √256)=16 tries in a row, but if that’s still too long and you again look for help from three friends. Each has to do √256/4)=8 tries.

So in total you do 8*4=32 tries, which is more than the 16 you would have done alone! Asking for help to parallelize the attack made the attack slower overall. Which is not the case for classical attacks.

Of course the numbers are way larger, but if we apply any reasonable constraint on the attacker (like having to finish a run in 10 years), the total work becomes so much more than 2⁶⁴.

Also, 2⁶⁴ was never the right number, because that pretends you can do AES as a single operation on a single qubit. This is somewhat orthogonal. The combination of these two observations turn the actual cost into 2¹⁰⁴ give or take, which is well beyond the threshold for security.

Sophie Schmieg, a senior cryptography engineer at Google, explained it this way:

With a normal brute force search, if I interrupt it halfway through, I have roughly a 50% chance of it already being successful. So I can have two computers doing the search, each over 50% of the keys, and be done in half the time. But with Grover’s, if I interrupt halfway through, the probability of getting the correct answer is only 25%. So instead of using two computers on half of the search space, I now need four.

So if you look at coreseconds, the classical algorithms cost what they cost, independent of how many computers you use in parallel. You can increase cores and your time goes down by the corresponding amount. But with the quantum algorithm, coreseconds are not independent of the parallelization strategy. Having more cores does not reduce the time by the same amount, to the point that if you went to the maximally parallel instance where each QC has to check only a single key, you need 2¹²⁸ QCs, and not 2⁶⁴, i.e. you’re no better than classical.

Valsorda’s post provides a more mathematically detailed explanation, as does this video.

Valsorda listed a litany of sources that support the assertion that AES is perfectly acceptable in a post-quantum world, including from the National Institute of Standards and Technology (here, here, and here), the German Federal Office for Information Security (here), and Samuel Jaques, an assistant professor in the Department of Combinatorics and Optimization at the University of Waterloo (here).

The exception to these recommendations is spelled out in the NSA’s version 2 of the Commercial National Security Algorithm Suite, which mandates AES 256. Valsorda said requirements for 256-level security were in place even in the predecessor algorithm suite, and weren’t specific to quantum readiness. “As far as I can tell, its intention is to avoid the very same fragmentation introduced by security levels by picking one oversized primitive for all settings.”