On Monday, Valsorda finally channeled years’ price of frustration, fueled by the widely held misunderstanding, right into a blog post titled “Quantum Computers Are Not a Threat to 128-bit Symmetric Keys.”
“There’s a standard misconception that quantum computers will ‘halve’ the safety of symmetric keys, requiring 256-bit keys for 128 bits of security,” he wrote. “That isn’t an accurate interpretation of the speedup offered by quantum algorithms, it’s not reflected in any compliance mandate, and risks diverting energy and a spotlight from actually crucial post-quantum transition work.”
That’s the simple a part of the argument. The much harder part is the maths and physics that designate it. At its highest level, it comes all the way down to a fundamental difference in the best way a brute-force search works on classical computers versus the best way it really works using Grover’s algorithm. Classical computers can perform multiple searches concurrently, a capability that enables large tasks to be broken into smaller pieces to finish the general job faster. Grover’s algorithm, in contrast, requires a long-running serial computation, where each search is completed separately.
“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 mixtures to a lock, A traditional attack would take 256 tries. You choose it’s too long, so that you get three friends and also you each do 64 tries. “That’s the classical parallelization. With Grover you would in theory do √256)=16 tries in a row, but when that’s still too long and also you again search for help from three friends. Each has to do √256/4)=8 tries.
So in total you do 8*4=32 tries, which is greater than the 16 you’d have done alone! Asking for help to parallelize the attack made the attack slower overall. Which isn’t the case for classical attacks.
After all the numbers are way larger, but when we apply any reasonable constraint on the attacker (like having to complete a run in 10 years), the full work becomes so rather more than 264.
Also, 264 was never the correct number, because that pretends you’ll be able to do AES as a single operation on a single qubit. That is somewhat orthogonal. The mix of those two observations turn the actual cost into 2104 give or take, which is well beyond the edge for security.
Sophie Schmieg, a senior cryptography engineer at Google, explained it this fashion: