In some recent conversations with practitioners about their transition to post-quantum cryptography, I found that people are unsure whether they need to double the key lengths of symmetric-key (and hash-based) cryptographic systems to be post-quantum secure. The short answer is: you don’t.
On searching for secret keys of AES-128
Yes, Grover’s algorithm speeds up unstructured search. To brute-force an n-bit secret key, Grover reduces the cost from \(O(2^n)\) classical operations to \(O(2^{n/2})\) quantum operations. But this is only if the operations are sequential and coherent. In 1997 it was already shown that parallel unstructured search over \(p\) quantum processors cannot achieve a per-processor runtime better than \(\Omega(2^{n/2}/\sqrt{p})\)—so in parallel the total work becomes \(\Omega(2^{n/2} \sqrt{p})\). There is an embarrassingly parallel algorithm (meaning it requires no communication between processors)1 that saturates this bound, so we should really think of these as \(p\) runs—you could do some of them sequentially if you want, resetting the quantum computer between each one to clear out noise. Let’s explore how this affects the quantum cost in practice.
Consider a future quantum computer that can perform 230 logical Toffoli gates before being overwhelmed by noise (and/or runtime)—which is more than sufficient to break ECDSA via Shor’s algorithm, assuming the machine also has enough logical qubits.
Let’s also take the following, both of which are extremely generous:
- Ignoring the fact that one AES-128 evaluation involves many Toffoli gates, let’s just suppose we can do 230 Grover iterations per run.
- Supposing an absurdly fast 1ns cycle time2, runs of circuit depth 230 would take ~1 second each.
Then how much work would it take to successfully break AES-128?
\[ \text{iters. per run} \sim 2^{30} \sim \frac{2^{128/2}}{\sqrt{p}} \; \Longrightarrow \; p \sim 2^{68} \text{ 1-second runs} \]
Even with 1,000 quantum processors working through these runs in parallel, the runtime would be 1010 years—roughly the age of the universe. And this was with extremely generous assumptions!
Don’t just take it from me
I was going to write a longer blog post working through more numbers, but several people have already done that:
- Check out Filippo Valsorda’s very nice April 2026 blog post working this out in detail.
- In that post, Filippo observes that Samuel Jaques worked out these numbers back in 2024 too!
- NIST agrees too!
- This paper argues that in general, we shouldn’t expect to see practical quantum advantage from algorithms with only a quadratic quantum speedup.
What about finding hash collisions?
The above analysis is for brute-forcing a key—what if we’re doing, say, collision finding for a hash function?
Classically, collision finding for a random function with \(n\)-bit outputs can be achieved in \(O(2^{n/2})\) queries via the birthday paradox, while a lower bound of \(\Omega(2^{n/3})\) quantum queries has been shown. This is already less of a speedup than generic search, but making things worse, the best algorithms we know that satisfy this query lower bound have large computational overheads, so the number of queries underrepresents their actual cost in practice.
Overall, there is even less of a speedup in the collision-finding case than for key search; if brute-forcing a key is not feasible quantumly, a collision finding problem with equivalent classical hardness is not going to be feasible either.
What about structural attacks?
Everything in this blog post so far considers block ciphers and hash functions as black boxes without structure. Of course, it’s possible that by leveraging the inherent structure of AES or SHA, one could come up with a better attack. However that’s also true for classical attacks; I don’t feel any more nervous relying on the difficulty of finding quantum structural attacks than I do classical ones.
(There are known quantum attacks using Simon’s algorithm that are wildly more efficient than Grover search, but they rely on an unrealistic attack model where one can make quantum queries to encryption under the secret key).
Thanks to Martin Ekerå for feedback and thoughts on this post!
Footnotes
You literally just take the original size-\(2^n\) search space and split it into \(p\) smaller search spaces of size \(2^n/p\), and then search each of them separately.↩︎
Source: I asked Craig Gidney, and he said “I normally assume 1μs surface code cycle time (with fault tolerant gates taking tens of cycles), but for a Grover estimate you might as well assume 1ns, it won’t matter.” Note that here I’m being even more extreme and assuming 1ns per Grover iteration.↩︎