Quantum computing discussions tend to follow a familiar script. Shor’s algorithm threatens RSA and elliptic curve cryptography (ECC). Grover’s algorithm threatens symmetric encryption. Therefore, AES-128 loses half its security, and everyone needs to move to AES-256 immediately.
That story is simple, widely repeated, and only partly right.
The mathematics behind Grover’s algorithm is valid and undisputed. It does provide a theoretical quadratic speedup against brute-force key search, and no serious researcher argues otherwise. What has changed is our understanding of what running Grover against AES at a meaningful scale would actually require. When engineering reality enters the picture, the threat model shifts dramatically.
The question is no longer whether Grover reduces a 2128 search space to roughly 264 operations. The question is whether any realistic quantum system could execute those operations at the required cost, on any practical timeline. That distinction is where the debate lives in 2026.
In this blog, we look at why Grover falls short of the threat it appears to pose, how it compares to Shor’s algorithm, where AES-256 still earns its place, and what security teams should actually prioritize first.
The Grover Misconception and Why MAXDEPTH Changes Everything
This is the part that most coverage gets wrong, and getting it right changes how you think about the urgency and the risk.
The popular statement is: “Grover’s algorithm halves the bit security of symmetric cryptography. AES-128 drops to 64-bit security. AES-256 drops to 128-bit. So just double your key sizes.” This is technically true in one narrow sense and practically misleading in almost every sense that matters.
Grover’s algorithm can be parallelized, but only in the most straightforward way: by dividing the search space equally among independent quantum computers, each running its own search. No cleverer approach exists that reduces the total number of oracle queries. The overall query cost stays the same regardless of how many machines you use, which means parallelization offers no advantage beyond what you would expect from simply splitting the work. This is what makes the circuit depth constraint practically significant: you cannot use more hardware to run the algorithm faster in the way classical computation allows.
NIST captures this through a parameter called MAXDEPTH, which is defined as the realistic maximum number of sequential quantum gate operations a quantum computer can execute in one computation before decoherence, errors, or practical constraints force a stop.
Plausible values range from 240, roughly what near-future quantum architectures could execute serially in a year based on the hardware architectures studied when NIST wrote the evaluation criteria, through 264 and up to a theoretical ceiling of 296.
With this constraint, attacking AES-128 via Grover requires 2170 / MAXDEPTH quantum gates. At MAXDEPTH 240, that is 2130. At MAXDEPTH 264, it is 2106. Neither of those numbers is 264. Both are far beyond any realistic quantum attack.
For AES-256, the estimate is 2298 / MAXDEPTH. At MAXDEPTH 264, that is 2234, a number that does not get meaningfully threatened even if quantum hardware improves by many orders of magnitude beyond current projections.
Plausible values range from 240, roughly what near-future quantum architectures could execute serially in a year based on the hardware architectures studied when NIST wrote the evaluation criteria, through 264 and up to a theoretical ceiling of 296.
With this constraint, attacking AES-128 via Grover requires 2170 / MAXDEPTH quantum gates. At MAXDEPTH 240, that is 2130. At MAXDEPTH 264, it is 2106. Neither of those numbers is 264. Both are far beyond any realistic quantum attack.
For AES-256, the estimate is 2298 / MAXDEPTH. At MAXDEPTH 264, that is 2234, a number that does not get meaningfully threatened even if quantum hardware improves by many orders of magnitude beyond current projections.
So when NIST says a Category 1 algorithm must resist attacks as costly as AES-128 key search, they are not saying it has 64-bit quantum security. They are saying it has something closer to 106 to 130 bits of quantum security, depending on hardware assumptions.
Security cost models used in NIST’s PQC evaluation assume a quantum gate costs somewhere between 109 and 1012 times more than a classical gate. This is a modeling assumption used to explore different economic scenarios, not a measured physical ratio. A quantum attack on Category 1 that requires 2106 quantum gates, where each gate costs a trillion times what a classical gate costs, may still be economically less viable than a classical brute-force attack for a long time.
NIST accounts for this by allowing security evaluations to weight quantum gates more expensively than classical gates in cost models. And importantly, for the highest security categories, NIST recommends assuming this cost disparity eventually disappears, that future quantum hardware becomes as inexpensive to run as classical hardware. Category 5 is designed to survive that scenario.
NIST’s own FAQ puts it plainly: “It is quite likely that Grover’s algorithm will provide little or no advantage in attacking AES, and AES-128 will remain secure for decades to come.” Current applications can continue to use AES with 128, 192, or 256-bit keys.
Once the real cost of a Grover attack is understood, the gap between it and Shor becomes impossible to ignore, and that gap is what determines where migration effort should actually go.
Three Reality Checks on Grover’s Algorithm
The MAXDEPTH picture gives theoretical framing. Three engineering constraints make the practical situation even worse for any attacker trying to run Grover at scale.
1. Parallelization Barely Helps
Classical brute-force attacks scale almost perfectly with additional hardware. Double the machines, and you roughly halve the time. Grover does not work that way. The more you parallelize Grover across quantum processors, the less efficient it becomes. The total computational effort does not decrease as parallelization increases.
Even with the most optimized AES-128 quantum circuit designs available today, and assuming highly optimistic quantum hardware running continuously for a decade, breaking AES-128 would still require approximately 247 parallel qu antum circuits running simultaneously, roughly 140 trillion of them (Valsorda, 2026, citing Liao and Luo, 2025). The total cost of that attack is approximately 278. Five times larger than breaking 256-bit elliptic curves using Shor’s algorithm, roughly 4 x 1023 times more expensive.
2. Error Correction Overhead Dominates
Real quantum hardware experiences noise and qubit instability. Any large-scale reliable computation requires quantum error correction, which dramatically multiplies resource consumption.
Google Quantum AI research has established that quadratic speedups will not enable quantum advantage on early fault-tolerant devices, with the important qualifier that this conclusion holds unless there is a significant improvement in how quantum error correction is realized. That is not a permanent statement about what quantum computers can never do. It is an honest assessment of where things stand today, and it is the basis on which practical risk decisions should be made.
When a quantum algorithm offers only a quadratic speedup, the constant overhead of error correction is so large that even classical hardware can outperform it under realistic assumptions, making Grover-based attacks impractical by any near-term measure.
3. The AES Oracle Is Expensive
Grover does not search a key space directly. It repeatedly evaluates an oracle, and for AES key search, that oracle is a full reversible quantum implementation of AES itself. Even the most optimized designs known today require several hundred to a few thousand logical qubits (circuit width), depending on the circuit design and which cost metric is being optimized. The textbook description hides this cost behind a constant factor. In practice, that constant contains the entire complexity of implementing AES in a quantum circuit, and it contributes substantially to the overall infeasibility of the attack.
These three constraints, taken together with the MAXDEPTH analysis, transform what looks like a clean theoretical speedup into an engineering challenge that no plausible near-term quantum system can address. That makes the contrast with Shor’s algorithm all the more striking.
Grover vs Shor: Not the Same Threat
The most significant mistake in quantum security planning is treating these two algorithms as equivalent risks. They are not, and the difference has direct implications for where migration resources should go.
| Algorithm | What It Targets | Quantum Impact | Migration Priority |
|---|---|---|---|
| Shor’s Algorithm | RSA, ECDH, ECDSA | Expected to completely break the underlying hard problems | High: begin migration now |
| Grover’s Algorithm | AES, symmetric key search | Quadratic speedup, with major practical constraints | Lower: upgrade key sizes when practical |
| Grover’s Algorithm | Hash preimage search | Quadratic speedup only | Manageable with larger output sizes |
Shor’s algorithm is expected to fundamentally break the hard mathematical problems that underpin RSA, ECDH, and ECDSA. A sufficiently large quantum computer running Shor’s algorithm does not merely weaken these systems. It renders them broken. Grover does not break AES. It reduces brute-force query complexity from N to approximately sqrt(N), while carrying all the practical constraints described above.
That distinction is exactly why NIST’s post-quantum migration guidance focuses on replacing vulnerable public-key systems. NIST’s finalized post-quantum standards, published August 13, 2024, reflect this priority directly:
- ML-KEM (FIPS 203): Key encapsulation, replacing RSA and ECDH in key exchange
- ML-DSA (FIPS 204): Digital signatures, replacing ECDSA and RSA-PSS
- SLH-DSA (FIPS 205): Backup hash-based signature scheme
In March 2025, NIST selected HQC as a backup code-based KEM, providing mathematical diversity alongside ML-KEM. FN-DSA (FIPS 206), based on FALCON, is in draft with finalization expected in late 2026 or early 2027. None of these additions changes the AES picture.
None of these replaces AES. NIST IR 8547 (Initial Public Draft, November 2024) sets the deprecation of RSA-2048 and ECC P-256 by 2030, with full disallowance of all quantum-vulnerable public-key algorithms by 2035. These deadlines cover algorithms threatened by Shor, not Grover. The urgency in post-quantum migration belongs to key establishment and digital signatures.
That said, it does not mean symmetric cryptography warrants no attention.
Where AES-256 Still Makes Sense
If Grover’s algorithm is unlikely to become a practical threat anytime soon, should organizations ignore AES-256 entirely? Not quite.
The strongest argument for AES-256 is not that AES-128 is broken. It is that upgrading symmetric key sizes is often inexpensive, and the margin it provides is real even when the near-term threat is low. NSA CNSA 2.0 (v2.1, December 2024) mandates AES-256 for symmetric encryption in National Security Systems. Not because AES-128 is quantum-vulnerable in any practical sense, but because the additional margin carries no meaningful operational cost in those environments.
AES-256 makes the most sense in the following situations:
- Long-lived sensitive data with multi-decade retention requirements
- National security systems where CNSA 2.0 already mandates AES-256
- Healthcare records subject to extended confidentiality obligations
- Critical infrastructure systems undergoing broader cryptographic modernization
- Any environment where moving to longer keys costs little operationally
The important limitation is this: replacing RSA and ECC with ML-KEM and ML-DSA provides a far larger security improvement than upgrading AES key sizes. Security teams that prioritize AES-256 upgrades while deferring post-quantum migration of public-key infrastructure (PKI) are solving the smaller problem first. That is one of the most common misallocations of migration resources, and an accurate read of the evidence helps to avoid it.
Before closing on priorities, one honest uncertainty deserves acknowledgment.
One Wildcard To Acknowledge
Most resource estimates assume AES behaves as an ideal unstructured search target, where Grover represents the best-known quantum attack. AES contains algebraic structure, and researchers continue exploring whether future quantum algorithms might exploit that structure more effectively than Grover’s generic approach.
Current evidence does not point toward any near-term breakthrough in this direction. But the possibility cannot be dismissed entirely. This uncertainty cuts both ways: it prevents confident claims that AES will face a dramatically better quantum attack, but it also prevents confident claims that Grover is the permanent final word on quantum symmetric cryptanalysis.
The responsible approach is to make decisions based on known evidence rather than speculation. That evidence consistently points in one direction: symmetric encryption is not where the most urgent quantum risk lives, and migration resources should reflect that.
What Security Leaders Should Do
A clear prioritization framework follows from the evidence.
Start with public-key exposure: Systems relying on RSA and ECC carry the clearest quantum risk and the most binding regulatory deadlines. NSA CNSA 2.0 (v2.1, December 2024) requires all new National Security System acquisitions to support CNSA 2.0 algorithms by January 1, 2027. PQC implementations must also be FIPS 140-3 validated through the Cryptographic Module Validation Program (CMVP); FIPS 140-2 module certificates move to Historical status on September 21, 2026, after which only FIPS 140-3 validated modules are accepted for new federal procurement.
Adopt NIST-standardized post-quantum algorithms: Migrate to ML-KEM (FIPS 203) for key exchange, ML-DSA (FIPS 204) for digital signatures, and SLH-DSA (FIPS 205) for stateless hash-based signatures. During the transition, deploy these alongside existing classical algorithms in a hybrid configuration so that if an implementation issue surfaces in the new PQC code, the classical layer still holds. These algorithms directly address the Shor algorithm threat.
Upgrade symmetric key sizes where the cost is low: Use AES-256 when operational disruption is minimal and data sensitivity justifies additional margin. Do not let this work delay the migration of public-key systems.
Build crypto-agility from the start: Design systems so cryptographic algorithms can be swapped without re-architecting the platform. The current NIST standards reflect the best current assessment, not a permanent answer.
Run a cryptographic inventory before anything else: You cannot migrate what you have not mapped. Every TLS certificate, key, algorithm, library, and signing key needs to be documented before a meaningful migration plan can be built.
How Encryption Consulting Can Help
Encryption Consulting helps organizations translate the quantum risk picture into a practical, sequenced migration program grounded in verified evidence. Whether the immediate concern is public-key infrastructure, symmetric key upgrades, or building crypto-agility into new systems, we bring the expertise to move from risk assessment to deployment without creating new vulnerabilities in the process through our PQC Advisory Services.
- Cryptographic Discovery and Inventory: Full-environment scanning to identify every certificate, key, algorithm, and protocol across endpoints, applications, APIs, and infrastructure before migration planning begins.
- PQC Assessment: Systematic evaluation of exposure to Shor-algorithm threats across RSA and ECC-dependent systems, with a prioritized roadmap and risk severity ratings.
- PQC Strategy and Roadmap: Phased migration planning aligned to regulatory deadlines and risk appetite, including crypto-agility design so systems can adapt as standards evolve.
- Vendor Evaluation and Pilot Testing: Selection of libraries and tools with documented audit histories, proof-of-concept deployments, and interoperability validation before full-scale rollout.
- Full Implementation: Deployment of ML-KEM and ML-DSA across your PKI and signing infrastructure, with ongoing monitoring that treats post-deployment vulnerability discovery as planned operational work.
CBOM Secure
Encryption Consulting’s CBOM Secure gives security teams a centralized, continuously updated view of every cryptographic algorithm, library version, and key across the organization. For teams working through Grover-versus-Shor prioritization, CBOM Secure identifies exactly which systems depend on quantum-vulnerable public-key algorithms and which use symmetric encryption, so migration effort goes where the actual risk lives.
If your organization is ready to build a quantum readiness program grounded in evidence rather than alarm, we encourage you to reach out.
Conclusion
The real cost of a Grover attack on AES-128, once you account for MAXDEPTH constraints, error correction overhead, and parallelization limits, sits between 2106 and 2130 equivalent quantum gates, not 264. NIST’s own guidance confirms this: Grover is likely to provide “little or no advantage” against AES, and AES-128 should remain secure for decades to come.
The migration that cannot wait is not symmetric encryption. It is public-key infrastructure. Shor’s algorithm does not merely weaken RSA and ECC. It breaks them. The deadlines that follow are binding: NIST IR 8547, currently in Initial Public Draft, proposes full disallowance of quantum-vulnerable public-key algorithms by 2035, with earlier milestones already counting down. Security teams that lead with AES-256 upgrades while deferring PKI migration are sequencing their risk response in the wrong order.
AES-256 is a sensible choice wherever the upgrade carries little operational cost and data longevity justifies the margin. But it is maintenance, not transformation. The real transformation is migrating to ML-KEM and ML-DSA, building crypto-agility into new systems, and mapping every cryptographic dependency before the window closes. That is where the effort belongs.
