Explainer series 5 of 5: What is Grover's algorithm, what does it threaten, and how is it different from Shor's - the real question

[NightOwl94]

Fifth and final in the beginner series. If Shor's algorithm is the one that breaks the encryption protecting the internet, Grover's algorithm is its quieter sibling that weakens rather than breaks a different class of cryptography. Understanding both together gives you a complete picture of the quantum threat to security.

Grover's algorithm was published by Lov Grover in 1996, two years after Shor. Where Shor finds the prime factors of a number, Grover searches an unsorted list. Imagine you have a lock with a billion possible combinations and you have to try them one by one on a classical computer. Grover's algorithm lets a quantum computer search that same list in roughly the square root of a billion steps instead, which is about 31,623. That is a quadratic speedup rather than the exponential speedup Shor provides, which means it is significant but less devastating. The practical effect is that it halves the effective security of symmetric encryption. AES-128 encryption, which has 128 bit security classically, would have roughly 64 bit security against a quantum computer running Grover's algorithm. AES-256 drops to 128 bit security, which is still considered secure. The fix is straightforward: double your key lengths.

The reason Grover matters even though the fix is simple is that not every system can easily switch key lengths, and Grover also affects things like hash functions used in blockchain and digital signatures. Bitcoin uses SHA-256 as part of its security stack. A sufficiently powerful quantum computer running Grover's algorithm could not steal Bitcoin directly, but it could speed up the mining process in ways that could destabilise the network's economic assumptions. The more immediate threat remains Shor's algorithm against the elliptic curve cryptography that protects Bitcoin private keys, but Grover adds a separate dimension.

There is an important asymmetry between the two algorithms worth understanding. Shor's algorithm completely breaks the cryptography it targets, making the protection worthless. Grover's algorithm weakens its targets by a known and predictable amount. This means Grover's threat is manageable with preparation, while Shor's requires a complete change of cryptographic system. Post quantum cryptography standards published by NIST in 2024 address both threats. The algorithms chosen are designed to resist quantum computers running both Shor and Grover style attacks. If you have been following the series you now have the conceptual toolkit to understand most of what you will read about quantum computing and security for the foreseeable future

[WhatUQuant]

The distinction between breaks completely and weakens by a known amount is the clearest I have seen it put. That asymmetry matters enormously for how urgent the response needs to be

[Connor97]

I had no idea Grover's algorithm had implications for Bitcoin mining. Can you say more about what that means practically

[Anvil79]

It also explains why symmetric encryption like AES is not being replaced entirely under NIST post quantum standards, just recommending longer key lengths. The math supports that response

[Demi-Q]

In Bitcoin mining, computers are competing to find a number that produces a hash with certain properties. It is essentially a search problem and Grover provides a quadratic speedup on search problems. A quantum miner could find valid blocks roughly as the square root of classical effort faster, which gives it a disproportionate share of mining rewards and could centralise control of the network

[Phil95]

That is not immediate though right, given we are nowhere near having quantum computers powerful enough for that

[Hollow Tiger]

Correct. The threat to Bitcoin mining from Grover is further out than the threat to Bitcoin private keys from Shor. But the blockchain community has been slow to plan for it relative to how fast the hardware timeline is compressing

[SašaJelenič]

What is the difference between post quantum cryptography and quantum cryptography. I see both terms used and they seem different

[CosmicRay67]

Good question and an important distinction. Post quantum cryptography is classical algorithms running on normal computers that are mathematically hard for quantum computers to break. Quantum cryptography uses quantum physics itself, like entanglement and superposition, to provide security. Quantum key distribution is an example. They solve the same problem by completely different means

[CollapseState]

Which one is NIST recommending

[Cheugy89]

NIST standardised post quantum cryptography in 2024 because it can be deployed on existing hardware and internet infrastructure without rebuilding everything. Quantum cryptography requires new physical infrastructure like quantum networks which exist in limited deployments

[CMPunk02]

Having read all five threads I feel like I understand the field at a basic level for the first time. Thank you to whoever set this up

[GameChanger]

This is exactly the kind of content that makes a forum worth visiting. Pinning this series would be a good idea

[QuantumToken98]

The series has been genuinely excellent. One question to finish. Is there a quantum algorithm we do not know about yet that could be more dangerous than Shor

[TheGame_Fan]

Almost certainly yes. The history of the field includes surprises and there is no reason to think the known quantum algorithms are the complete picture. The unknown unknowns in quantum algorithm discovery are one of the things that keeps cryptographers honest about not being overconfident