Grover's Algorithm & Symmetric Keys
While Shor's algorithm completely breaks RSA and ECC, Grover's algorithm is the quantum threat to symmetric encryption. It doesn't break AES — but it halves its effective security. Understanding Grover's algorithm and how to respond to it is essential for quantum-safe design.
What is Grover's Algorithm?
Grover's algorithm, published by Lov Grover in 1996, is a quantum algorithm for searching an unstructured database of N items. A classical computer needs N/2 steps on average to find the right item. Grover's algorithm finds it in roughly √N steps.
How Grover's Algorithm Works
Grover's uses a technique called amplitude amplification. Here's the intuition:
- Superposition: Put all possible keys into quantum superposition — the computer "considers" all 2¹²⁸ possible AES keys simultaneously.
- Oracle: Apply a quantum function that flips the sign of the amplitude of the correct key (the one that produces the known plaintext-ciphertext pair). This marks the right answer without identifying it directly.
- Diffusion: Apply a mathematical transformation that amplifies the marked item's amplitude relative to all others — like turning up the volume on the right answer.
- Repeat: Steps 2–3 repeated ~√N times increase the probability of measuring the correct key to nearly 100%.
- Measure: Collapse the superposition and read out the correct key.
What Does This Mean for Symmetric Encryption?
Grover's algorithm halves the effective security level of any symmetric cipher or hash function:
The Fix: Double Your Key Size
The good news: unlike Shor's algorithm (which requires replacing the mathematical problem entirely), Grover's algorithm has a simple countermeasure — use larger keys.
- Replace AES-128 with AES-256
- Use SHA-384 or SHA-512 where SHA-256 is currently used for security-critical operations
- For digital signatures, this doesn't help (they use RSA/ECC which Shor's breaks) — use post-quantum signatures instead
Grover's vs. Shor's: Comparing the Threats
Grover's Algorithm
- Quadratic speedup (√N)
- Weakens symmetric crypto
- Fix: use 256-bit keys
- No new algorithms needed
- Lower qubit requirement
- Less urgent (but matters)
Shor's Algorithm
- Exponential speedup (polynomial time)
- Completely breaks RSA, ECC, DH
- Fix: replace the algorithm entirely
- Requires new post-quantum algorithms
- Higher qubit requirement (but decreasing)
- The primary motivation for PQC
Frequently Asked Questions
Can Grover's algorithm break any hash function?
Grover's algorithm speeds up preimage attacks (finding an input that hashes to a given output), reducing a 256-bit hash's preimage resistance from 2²⁵⁶ to 2¹²⁸ operations. It also speeds up collision searches via a quantum variant of birthday attacks, but the speedup there is less dramatic. SHA-256 is considered at marginal risk for some applications; SHA-384 or SHA-512 is recommended for post-quantum security.
Is Grover's algorithm already running on real quantum hardware?
In toy versions, yes — small databases with a handful of items have been demonstrated on quantum hardware. But running Grover's against real AES key sizes (128 or 256 bits) would require millions of error-corrected logical qubits. This is even more challenging than running Shor's against real RSA keys, because Grover's requires the quantum computer to evaluate the AES function as an oracle — a complex quantum circuit in itself.
Frequently Asked Questions
What will I learn here?
This page covers the core concepts and techniques you need to understand the topic and progress confidently to the next lesson.
How should I use this page?
Start with the overview, then follow the section links to deepen your understanding. Use the table of contents on the right to jump to specific sections.
What should I read next?
Use the navigation below to continue to the next lesson or explore related topics.