Can Quantum Computers Break 128-bit Symmetric Keys? Analyzing the Real Threat

The Overhyped Quantum Threat: Getting the Basics Straight

"Quantum computers are about to break all encryption"—headlines like this are all too common on social media. Yet within the tech community, a more sober assessment circulates: quantum computers pose no substantial threat to 128-bit symmetric keys.

This claim may seem counterintuitive, but it rests on solid theoretical grounds. Understanding the logic hinges on distinguishing between two fundamentally different cryptographic systems and how quantum algorithms actually affect each.

Asymmetric vs. Symmetric Encryption: Different Targets for the Quantum Threat

The Real Target of the Quantum Threat: Asymmetric Encryption

The true target of quantum computing is asymmetric encryption algorithms, such as RSA and Elliptic Curve Cryptography (ECC). The security of these algorithms is built on the computational difficulty of factoring large integers or solving discrete logarithm problems.

In 1994, mathematician Peter Shor proposed Shor's algorithm, which can theoretically solve these problems in polynomial time. This means a sufficiently powerful quantum computer could break mainstream asymmetric encryption schemes like RSA-2048 within a reasonable timeframe—which is precisely why research into "post-quantum cryptography" (PQC) continues to heat up.

The reason Shor's algorithm poses an exponential threat to RSA lies in the natural suitability of the Quantum Fourier Transform (QFT) for periodic problems. RSA's security depends on factoring large integers, and the factoring problem can be transformed into finding the period of a modular exponentiation function—which is exactly where quantum computers excel. Classical computers require sub-exponential time to solve for this period (as in the General Number Field Sieve), whereas Shor's algorithm accomplishes it in polynomial time using the QFT, achieving a fundamental leap from "hard" to "easy" rather than just a constant-factor speedup. This stands in stark contrast, in terms of order of magnitude, to the mere square-root speedup that Grover's algorithm provides against symmetric encryption—and it is the fundamental reason the two have such vastly different impacts on the cryptographic security landscape.

The Defense Logic of Symmetric Encryption Is Entirely Different

Symmetric encryption like AES does not rely on mathematical hard problems, but rather on the sheer size of the key space to resist brute-force attacks. For a 128-bit key, the number of possible combinations reaches 2^128 (about 3.4×10^38), making exhaustive search fundamentally infeasible on classical computers.

Screenshot of discussion on quantum computing and symmetric encryption threats

Grover's Algorithm: The Real Limits of Square-Root Speedup

The Theoretical Threat: Halving the Security Strength

For symmetric encryption, the most relevant quantum algorithm is Grover's algorithm—it provides a "square-root level" speedup for unstructured search problems.

Applied to key cracking: Grover's algorithm can reduce the complexity of brute-forcing a 128-bit key from 2^128 to 2^64, theoretically halving the security strength. At first glance, this appears to be a catastrophic weakening.

The Triple Constraint in Reality: Why 2^64 Remains Secure

However, translating this theoretical speedup into an actual attack faces numerous obstacles:

Serialized operations, no arbitrary parallelization: Grover's algorithm requires the quantum computer to perform 2^64 serial quantum operations, unlike classical computing which can simply scale out horizontally.
Extremely high quantum error correction overhead: Real quantum computers require a large number of physical qubits to construct a small number of reliable logical qubits, and the cost of error correction makes 2^64 reliable operations unattainable.
Unbearable time cost: Even under optimistic estimates of quantum gate speeds, completing 2^64 serial operations could take hundreds of years.

The serialized nature of Grover's algorithm stems from its core mechanism—quantum amplitude amplification: each iteration requires phase flipping and mean inversion based on the quantum state from the previous iteration, and intermediate states cannot be split for parallel processing. This is fundamentally different from classical brute-forcing, which can distribute the key space across thousands of machines searching simultaneously. Moreover, quantum error correction codes (such as the currently most promising surface code) typically require hundreds to thousands of physical qubits to maintain a single logical qubit, meaning the scale of physical resources needed to perform 2^64 reliable gate operations far exceeds the engineering capabilities foreseeable now or even in the coming decades.

In other words, the "halving" from Grover's algorithm remains at the level of asymptotic complexity, and its engineering feasibility is far lower than the threat Shor's algorithm poses to asymmetric encryption.

The Response Strategy: Doubling the Key, Done in One Step

Migrating to AES-256 Provides Quantum Resistance

Faced with the theoretical challenge of Grover's algorithm, the cryptographic community offers a surprisingly simple response: double the symmetric key length.

After migrating from AES-128 to AES-256, the best complexity Grover's algorithm can achieve is 2^128—exactly equal to the security level at which current classical computers are helpless against a 128-bit key. For this reason, AES-256 is widely regarded by the cryptographic community as "quantum-resistant."

Compared to Asymmetric Encryption: A World of Difference in Migration Difficulty

This stands in stark contrast to the situation with asymmetric encryption. For RSA, simply increasing the key length cannot resist the exponential speedup brought by Shor's algorithm. The entire industry has been forced to turn to post-quantum algorithms based on entirely new mathematical structures such as lattice-based cryptography and hash-based signatures—a systemic transformation involving protocols, software, and hardware, with migration costs and complexity that are simply incomparable.

Notably, the post-quantum cryptography standardization project launched by NIST (National Institute of Standards and Technology) in 2016 officially released its first batch of standards in 2024: ML-KEM (derived from CRYSTALS-Kyber, for key encapsulation), ML-DSA (derived from CRYSTALS-Dilithium, for digital signatures), and SLH-DSA (derived from SPHINCS+, a hash-based signature scheme). The security of these algorithms is respectively built on the Module Learning With Errors problem (Module-LWE) over module lattices and on weighted hash tree structures, and they are considered to offer sufficient resistance against both quantum and classical computers. For enterprises and system designers, this means the migration path for asymmetric encryption has moved from the "research phase" to the "standard implementation phase," and the window for delaying deployment is narrowing.

Conclusion: Focus Your Energy on the Real Risks

The narrative that "quantum computing will destroy all encryption" is clearly an oversimplification. A more accurate picture is:

Asymmetric encryption faces a real and urgent quantum threat, and post-quantum cryptography migration is imperative;
Symmetric encryption (especially AES-256) is fundamentally secure, and the square-root speedup of Grover's algorithm is far from sufficient to undermine its security;
Although the theoretical strength of 128-bit symmetric keys is halved, the actual cracking cost of 2^64 remains unattainable for the foreseeable future.

For system designers, the pragmatic strategy is: use 256-bit keys at the symmetric encryption layer, while directing your primary resources toward the post-quantum migration of asymmetric encryption. Understanding the true boundaries of the quantum threat is what allows you to avoid unnecessary panic and spend your limited security budget where it is truly needed.