Grover's Attack on Symmetric Cryptography

Implement Grover's search to understand its impact on symmetric key sizes.

Grover's Attack on Symmetric Cryptography

Quantum computers do not break symmetric cryptography the way they break RSA and ECC: but they do weaken it. Grover's algorithm provides a quadratic speedup for searching unsorted databases, which translates into a halving of effective key security.

Grover's Algorithm: The Core Idea

Grover's algorithm solves the unstructured search problem: given a function f(x) that returns 1 for exactly one input and 0 for all others, find that input. Classically, the best strategy is random search with O(N) queries. Grover's achieves O(√N) queries.

For symmetric key search:

•AES-128 has $2^{128}$ possible keys
•Classical brute force: $\sim 2^{128}$ operations
•Grover's attack: $\sim 2^{64}$ operations (quadratic speedup)

The implication: AES-128 should be upgraded to AES-256 in a post-quantum world, and NIST recommends this. AES-256 provides $\sim 2^{128}$ effective security even against Grover's algorithm.

The Algorithm Structure

Grover's algorithm works by amplitude amplification. Starting from a uniform superposition over all N states, it applies a sequence of two operations:

Oracle: Marks the target state by flipping its phase:

•|target⟩ → −|target⟩
•All other states unchanged

Diffuser (inversion about average): Amplifies marked states:

1.Apply H to all qubits
2.Apply a phase flip to |0...0⟩
3.Apply H to all qubits

After approximately π/4 × √N iterations of (oracle + diffuser), the amplitude of the target state is close to 1. Measuring the system yields the target with high probability.

2-Qubit Example

For a 2-qubit search (N=4 states), only 1 iteration is needed. Let's search for the state |11⟩:

1.Initialize: H⊗H|00⟩ = (|00⟩+|01⟩+|10⟩+|11⟩)/2
2.Oracle: Flip phase of |11⟩ using CZ gate
3.Diffuser: Invert about average
4.Measure: |11⟩ with probability 1

Impact on Cryptography

Algorithm	Classical Security	Quantum Security (Grover)	Post-Quantum Recommendation
AES-128	128 bits	64 bits	Upgrade to AES-256
AES-256	256 bits	128 bits	Safe
SHA-256	256 bits	128 bits (collision)	Safe
SHA-3-256	256 bits	128 bits	Safe

This is the opening of the lesson. The full walkthrough, the interactive circuit, and the graded challenge continue inside myqubit.

How this lesson works

A hands-on coding challenge. You write Qiskit-compatible Python in the browser editor, run it instantly via WebAssembly, watch the circuit and Bloch sphere react, and pass automatic output checks. The AI tutor Qubitus gives Socratic hints if you get stuck.

Part of: Quantum Cryptography

Master quantum key distribution, the threat quantum computers pose to classical cryptography, and post-quantum cryptographic standards.

Previous lessonWhy Quantum Computers Threaten Cryptography Next lessonShor's Algorithm and RSA

This lesson is part of Pro

Unlock Quantum Cryptography and all 10 tracks with Pro: $12.99/month, $79/year, or $97 lifetime. Start with the free track first if you are new.

Create account Try the Playground