Part 3: It's Not Just Shor's — Why Grover's Algorithm Quietly Doubles Your Key-Length Bill

This is Part 3 of a 10-part series on Post-Quantum Cryptography for enterprise leaders.

Shor’s algorithm gets the headlines. It breaks RSA and ECC entirely, and as we covered in Part 2, it does so by transforming the problem — not by being faster at the same search. That’s dramatic. That’s existential for public-key cryptography.

But there’s a quieter quantum algorithm that most enterprise security teams haven’t fully reckoned with — one that doesn’t break your symmetric cryptography, but silently weakens it. And because it “only” weakens rather than destroys, it gets dangerously dismissed.

Meet Grover’s algorithm. And the reason your AES-128 deployment may already be insufficient for a post-quantum world.

What Grover’s algorithm does

Where Shor’s targets specific mathematical structures (factoring, discrete logarithms), Grover’s is general-purpose. Published by Lov Grover, it provides a quantum speedup for any unstructured search problem — searching through an unsorted database, or more relevant to us, searching through a keyspace.

The speedup is quadratic. A classical computer searching through N possibilities needs, on average, N/2 attempts. Grover’s algorithm does it in roughly √N.

In raw numbers: searching a keyspace of 2¹²⁸ possibilities classically takes about 2¹²⁷ operations. With Grover’s, it takes about 2⁶⁴. That’s not twice as fast. That’s a reduction from an astronomically hard problem to a merely very expensive one — one that sits within reach of a well-resourced adversary with sufficient quantum hardware.

In practical terms, Grover’s algorithm effectively halves your key length. AES-128 becomes AES-64 in quantum security terms. AES-256 becomes AES-128. Your symmetric key infrastructure doesn’t break — but it downgrades by an entire security tier overnight.

“It’s a parameter problem, not an algorithm problem”

This is the line I keep coming back to when discussing Grover’s with enterprise security teams, because it reframes the entire response.

Shor’s is an algorithm problem. It fundamentally breaks the mathematical assumptions behind RSA and ECC. No key length increase saves you — a bigger RSA key just means Shor’s takes slightly longer, but it still runs in polynomial time. The algorithm must be replaced entirely. That’s why we need PQC.

Grover’s is different. The algorithm (AES, for instance) isn’t broken. The math still holds. What changes is the minimum parameter — the key length — needed to maintain your target security level. You don’t need a new algorithm. You need bigger keys.

That distinction matters enormously for how enterprises plan their migrations. The Shor’s response is: replace RSA/ECC with ML-KEM, ML-DSA and other post-quantum algorithms. The Grover’s response is: audit every symmetric key deployment and ensure you’re at AES-256 or equivalent. Different threat, different remediation, different program workstream.

Why this gets underestimated

Three reasons.

First, the “quadratic vs. exponential” framing makes Grover’s sound tame compared to Shor’s. In academic discussions, that’s technically accurate — Grover’s gives a polynomial speedup, not an exponential one. But translating “your 128-bit keys now offer 64-bit security” into enterprise risk language makes the impact immediately concrete. 64-bit security hasn’t been considered acceptable since the 1990s.

Second, most organizations assume they’re already on AES-256 everywhere. They’re often wrong. Legacy systems, embedded devices, IoT endpoints, older TLS configurations, VPN tunnels and hardware security modules frequently still run AES-128 or even 3DES. The assumption that “we’re fine on symmetric” breaks down the moment you audit what’s actually deployed rather than what’s specified in the policy document.

Third, Grover’s impact extends beyond encryption keys. It applies to hash functions as well. A 256-bit hash (SHA-256) drops to 128-bit quantum security. That affects digital signatures, integrity verification, blockchain constructs, certificate fingerprints and password hashing. The surface area is broader than most initial assessments capture.

The connection to key generation and randomness

There’s a subtler dimension here worth flagging. When your symmetric key lengths need to increase, the quality of your key generation becomes more critical. Longer keys generated from weak or predictable random sources don’t actually deliver the security their length promises. The randomness behind the key matters as much as its size — which is precisely why quantum random number generation (QRNG) enters the conversation as a complementary technology, not a competing one.

The quantum properties that create the threat (superposition enabling Grover’s search) are the same properties that can strengthen the defense (superposition-based true randomness). That symmetry is one of the more elegant aspects of the entire PQC landscape.

What to do about it — the short version

The Grover’s response is more tractable than the Shor’s response, but it’s not trivial. It requires:

• A comprehensive audit of every symmetric key deployment — not just what policy says, but what’s actually running across production systems, legacy infrastructure, and third-party integrations.
• Migration from AES-128 to AES-256 wherever 128-bit deployments persist — and there will be more than you expect.
• Review of hash function usage to ensure minimum 256-bit outputs for any security-critical application (with recognition that SHA-256 drops to 128-bit quantum security, which may or may not meet your risk threshold).
• Integration of these findings into the same cryptographic inventory that your Shor’s/PQC migration program will need anyway.

That last point is key. The Grover’s remediation and the Shor’s remediation converge on the same foundational requirement: you need to know where your cryptography actually lives. Different threats, same starting point — a complete cryptographic inventory.

We’ll get deeper into that convergence in Part 5, when we talk about why your biggest PQC risk isn’t algorithms — it’s your certificate inventory.

Coming up next

Parts 2 and 3 covered the quantum algorithms that create the threat. Part 4 flips the lens: we’ll look at the mathematics that defends against them. Specifically, Regev’s lattice-based constructions — the theoretical foundation behind ML-KEM and ML-DSA and why their security guarantee is a proof of hardness, not just a track record.

---

Col Gaurav Kumar Upadhyay (Retd) — published researcher in quantum random number generation (IEEE RTEICT 2016) and Shor’s algorithm (Springer ICACCT 2015). 21+ years in enterprise cryptographic infrastructure, PKI, and certificate lifecycle management.