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 264.
Also, 264 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 2104 give or take, which is well beyond the threshold for security.
Sophie Schmieg, a senior cryptography engineer at Google, explained it this way: