Quantum Computers Are Not a Threat to 128-bit Symmetric Keys
Quality: 4/5
Key Message: AES-128 is safe against quantum computers. SHA-256 is safe against quantum computers. No symmetric key sizes have to change as part of the post-quantum transition.
The Misconception
There's a common misconception that quantum computers will "halve" the security of symmetric keys, requiring 256-bit keys for 128 bits of security. This is not accurate.
This misconception is based on a misunderstanding of Grover's algorithm's applicability.
Why Grover's Doesn't Work
Grover's algorithm allows searching an unstructured function for the "right answer" in π/4 × √N invocations. However:
- The function oracle must be implemented as part of the quantum circuit
- Oracle invocations must happen one after the other in series
- There is no better way to parallelize than partitioning the search space (Zalka, 1997)
The Math
Breaking AES-128 with Grover requires:
- 140 trillion quantum circuits of 724 logical qubits each
- Operating in parallel for 10 years
- Using hypothetical fast and perfect quantum computers
Comparison: Breaking AES-128 with Grover is 430,000,000,000,000,000,000,000 times harder than breaking 256-bit elliptic curves with Shor's algorithm.
What Needs to Change
The post-quantum transition does require replacing:
- ECDH (Elliptic Curve Diffie-Hellman) - key exchange
- RSA, ECDSA, EdDSA - digital signatures
These are vulnerable to Shor's quantum algorithm.
Conclusion
128-bit symmetric keys remain secure. This is a near-consensus opinion amongst experts and standardization bodies. The IT community needs to understand this to focus energy on actually necessary post-quantum transition work.