up:: Breaking Today’s Cryptography MOC

Symmetric vs Asymmetric Under Quantum Attack

A quantum computer treats the two halves of cryptography completely differently. Symmetric cryptography loses half its effective key strength to Grover’s algorithm, which a larger key restores. Asymmetric cryptography loses everything to Shor’s algorithm, which solves the exact mathematical problem it rests on.

That asymmetry is the single most useful fact in the whole subject, because it explains why the transition replaces RSA and elliptic-curve cryptography outright while AES-256 carries forward untouched.

The short version:

• The difference is structure. Public-key cryptography embeds a specific number-theoretic structure, factoring or the discrete logarithm, and Shor’s algorithm grabs that structure and solves it directly. Symmetric ciphers have no such structure, leaving only blind search.
• Grover halves, Shor collapses. Grover reduces a search of 2^n possibilities to about 2^(n/2), cutting bits of security in half. Shor solves the underlying problem in polynomial time, so no key size rescues it.
• The symmetric fix is a parameter change. AES-128 drops to about 64 bits of effective strength and AES-256 drops to about 128, which is why standardizing on AES-256 is the whole symmetric response.
• There is no new symmetric family to migrate to, which is why the post-quantum transition is overwhelmingly a public-key migration.
• Grover is weaker in practice than the halving suggests. It barely parallelizes, so 1,000 machines buy roughly a 31-fold speedup rather than a 1,000-fold one, and NIST bounds the real cost of breaking AES-128 at about 2^170 / MAXDEPTH quantum gates.

Picture a vault with a combination lock and a delivery van that brings the combination to authorized staff. The lock itself is sound, and a new tool halves the time an attacker needs to try every combination, which is answered by adding digits to the dial. The van is the problem: a different new tool reads the combination straight off the paperwork in transit, and no amount of extra digits on the dial helps, because the attacker never touches the lock. Replacing the van is the entire project, and adding digits to the dial is a settings change made the same afternoon.

What is the difference between how quantum affects symmetric and asymmetric cryptography?

The difference is whether there is a mathematical shortcut to find. Asymmetric algorithms are built on a hard problem with exploitable structure, and a quantum computer running Shor’s algorithm solves that problem in polynomial time, recovering the private key from the public one. The failure is structural and complete rather than a reduction in margin.

Symmetric algorithms have no equivalent structure. An attacker faces a key space to search, and the strongest general quantum tool against an unstructured search is Grover’s algorithm, whose advantage is provably limited to a quadratic speedup. Halving the effective bit strength is survivable, because doubling the key restores it.

What happens to symmetric cryptography?

A symmetric key with n bits has 2^n possible values, and a classical brute-force search takes on the order of 2^n tries. Grover reduces that to about 2^(n/2), which cuts the bits of security in half. That is the beginning and end of Grover’s effect: it exploits no structure in the cipher, recovers no key through a mathematical shortcut, and leaves the design of the algorithm untouched.

AES key size	Classical security	Effective strength under Grover (idealized)	Verdict
AES-128	128-bit	~64-bit	Retire for long-lived protection
AES-192	192-bit	~96-bit	Safe, and AES-256 is the cleaner target
AES-256	256-bit	~128-bit	The conservative quantum-safe choice

Hashes carry forward on the same logic. SHA-256 keeps roughly 128 bits of preimage strength under Grover, and its collision resistance is barely affected because the classical birthday bound already sat near 128 bits.

Source: NIST, “Report on Post-Quantum Cryptography,” NISTIR 8105, April 2016, csrc.nist.gov.

What happens to asymmetric cryptography?

Shor’s algorithm solves integer factorization and the discrete logarithm problem in polynomial time on a fault-tolerant quantum computer. RSA’s security is that factoring the modulus is infeasible, and ECC’s security is that recovering a scalar from a curve point is infeasible. Shor’s does exactly those recoveries, so a capable machine reads the private key off the public one.

No parameter change rescues it. Shor’s resource requirement grows only polynomially with bit length, so a larger key adds qubits and runtime to an attack that improving hardware keeps making cheaper. The response is to replace the algorithm: ML-KEM for key establishment and ML-DSA or SLH-DSA for signatures.

Symmetric vs asymmetric at a glance

Dimension	Symmetric	Asymmetric
What it does	Bulk encryption, integrity through MACs, key wrapping	Key establishment and digital signatures
Security basis	A large key space with no exploitable structure	A structured hard problem, factoring or the discrete logarithm
Relevant quantum algorithm	Grover’s	Shor’s
Effect of that algorithm	Quadratic speedup on blind search, halving effective bits	Polynomial-time solution of the underlying problem
Nature of the failure	A reduction in margin	A structural break, with the algorithm ceasing to work
Does a bigger key help	Yes. Doubling the key restores the original margin	No. Shor’s cost grows only polynomially with bit length
Required response	A parameter change to a larger key	Full algorithm replacement
Representative before and after	AES-128 to AES-256	RSA and ECC to ML-KEM, ML-DSA, SLH-DSA
New algorithm family needed	None exists or is needed	An entire standardization process was run to produce them
NIST retirement schedule	None for AES-256. AES-128 is a planning matter for long-lived data	Every quantum-vulnerable public-key algorithm disallowed after 2035
Where it sits in a TLS session	Encrypts every byte after the handshake	Agrees the shared secret during the handshake
HNDL exposure	Indirect. The cipher is not attacked; its key is recovered through the handshake	Direct. Recorded handshakes yield the session keys
Share of migration effort	Small, largely a configuration and policy question	The overwhelming majority of the work

How do they actually differ?

1. The presence of structure decides everything. Public-key cryptography buys its central capability, letting two strangers agree a secret over an open channel, by embedding a specific number-theoretic structure. That structure is what makes the mathematics work and is also precisely the handle Shor’s algorithm grabs. Symmetric cryptography never needed that structure and therefore never exposed the handle.

2. The failure curves have different shapes. Grover produces a smooth, predictable, fully quantified reduction that a key size absorbs. Shor produces a cliff: the algorithm works, and then on some future date it does not work at all, with nothing in between.

3. The remediation costs differ by orders of magnitude. Moving from AES-128 to AES-256 changes a key length and a round count within the same algorithm, and touches configuration rather than architecture. Replacing RSA and ECC means new key sizes, new certificate formats, new protocol negotiation, new hardware support and a multi-year program across an entire estate.

4. Only one of them is exposed retroactively through the handshake. A quantum attacker does not attack the symmetric cipher at all. They attack the public-key exchange that delivered its key, recover the session secret, and then read the symmetric traffic normally. The symmetric layer was never the weak link, and the public-key channel that keyed it is the exposure, which is the whole shape of harvest-now-decrypt-later.

5. Grover’s practical weakness has no equivalent on the Shor side. Grover’s speedup is fundamentally serial, so splitting the search across M machines gives each only a √(N/M) share, and 1,000 machines buy roughly a 31-fold speedup rather than a 1,000-fold one. Classical brute force parallelizes cleanly and Grover does not, which erases much of its apparent edge in any real deployment. NIST also bounds attack cost by a maximum circuit depth, under which breaking AES-128 costs on the order of 2^170 / MAXDEPTH quantum gates.

Where do they agree?

1. Both need a fault-tolerant quantum computer. Grover requires a long, deep, error-corrected computation just as Shor’s does, so today’s NISQ machines threaten neither.

2. Both appear in every real secure session. A TLS 1.3 connection runs a public-key exchange to agree a shared secret, derives keys from it, then switches to a fast symmetric AEAD cipher for the traffic. Neither half is optional.

3. Neither is helped by the other’s fix. Doubling a symmetric key does nothing for the handshake, and migrating the handshake to ML-KEM does nothing about an AES-128 configuration that should have moved to AES-256.

4. Both are covered by the same standards bodies and the same guidance. NISTIR 8105 addresses the symmetric response and the public-key replacement in the same document, treating them as two parts of one transition.

Why is the transition almost entirely a public-key migration?

Because the symmetric answer already exists and requires no new mathematics. NIST states the planning consequence directly in NISTIR 8105: Grover’s speedup “can have the effect of requiring larger key sizes, even in the symmetric key case,” and doubling the key size is sufficient to preserve security. There is no new symmetric family to standardize, no new format to negotiate and no ecosystem to rebuild.

The public-key side had none of those advantages. Replacing it required a multi-year international standardization process to produce entirely new algorithms on entirely different mathematical foundations, and it now requires every protocol, certificate format, hardware module and library in the world to learn them. That is why a post-quantum program is overwhelmingly an inventory-and-replace exercise aimed at key establishment and signatures.

What does this mean for reading claims about quantum breaking encryption?

The sentence “quantum computers will break encryption” is true of one half and false of the other, and the distinction is load-bearing rather than pedantic. A claim that a quantum computer breaks AES is wrong. A claim that AES-256 needs replacing is wrong. A claim that RSA and elliptic-curve cryptography survive with larger parameters is also wrong.

The precise version is that a cryptographically relevant quantum computer breaks the public-key algorithms that establish keys and sign data, and reduces the effective strength of symmetric algorithms by half, which AES-256 already absorbs. Anyone selling a new symmetric cipher as a quantum-safety product is solving a problem the field answered by doubling a key size.

Common misconceptions

1. “Quantum computers break all encryption.” They break public-key cryptography structurally and reduce symmetric strength by half. AES-256 carries forward with roughly 128 bits of effective security, which no foreseeable machine threatens.

2. “AES-256 needs to be replaced.” It does not. There is no post-quantum symmetric family because none is needed, and AES-256 is the standard answer for the symmetric side of the transition.

3. “Grover halves AES so it is half-broken.” The halving is a deliberately pessimistic idealization. Grover barely parallelizes and needs enormous circuit depth, so a real attack is far harder than the clean 2^(n/2) figure implies.

4. “We use AES-256, so we are quantum-safe.” The symmetric layer is fine and the key that unlocks it arrives through a public-key exchange. A quantum attacker recovers the session key from the recorded handshake and never attacks AES at all.

5. “Bigger RSA keys are the equivalent of moving to AES-256.” They are not equivalent. Doubling a symmetric key restores the full margin, and enlarging an RSA modulus raises the quantum attacker’s cost only polynomially while raising your own cost today.

6. “Hashes are broken by quantum too.” SHA-256 keeps roughly 128 bits of preimage strength under Grover, and its collision resistance is barely affected because the classical birthday bound already sat near 128 bits.

Questions people ask

Does a quantum computer break AES? No. Grover’s algorithm halves the effective key strength, so AES-256 retains roughly 128 bits of security, which is the level the industry already treats as safe against classical attackers. AES-128 falls to about 64 bits and is the size worth retiring for long-lived data.

Why is only public-key cryptography being replaced? Because Shor’s algorithm solves the structured mathematical problem public-key cryptography rests on, so no parameter change saves it. The symmetric side has no such structure, and its response is a larger key rather than a new algorithm.

Should I move from AES-128 to AES-256? For anything with a multi-year confidentiality lifetime, yes, and it is a parameter change within the same algorithm rather than a migration. The key length and round count differ while the AES structure is identical.

Is there a post-quantum replacement for AES? No, and none is needed. NIST’s guidance is that doubling the key size preserves security against Grover, which AES-256 already does.

If my data is encrypted with AES-256, is it safe from harvesting? Only if the key that protects it was not delivered by a quantum-vulnerable key exchange. Recorded traffic is exposed through the handshake rather than through the cipher, so the exposure follows the key establishment.

What about hashes and MACs? They carry forward. SHA-256 retains roughly 128 bits of preimage resistance under Grover with collision resistance barely affected, and HMAC inherits the strength of its underlying hash.

Why does NIST think Grover is less threatening than the halving suggests? Because Grover’s speedup is serial and barely parallelizes, so a thousand machines buy roughly a 31-fold gain, and because the circuits are enormous. Under NIST’s maximum-circuit-depth bound, breaking AES-128 costs on the order of 2^170 / MAXDEPTH quantum gates.

Does the symmetric side have a 2035 deadline? No. The 2035 disallowance applies to quantum-vulnerable public-key algorithms. AES-256 carries no retirement date, and moving off AES-128 for long-lived data is a planning judgment rather than a mandated deadline.

How much of a migration program is symmetric work? A small fraction. Most of a post-quantum program is finding and replacing key establishment and signatures, and the symmetric portion is largely a configuration and policy standardization on AES-256.

---

The map is free and I keep it that way. When the question becomes which half of this an actual estate is exposed on and in what order it comes out, that’s the work I do at LaMarr Labs.

Go deeper

• Symmetric-Key Cryptography and Post-Quantum Cryptography (PQC) for each half in full
• Shor vs Grover for both quantum algorithms compared directly
• Grover on AES for the symmetric case in depth
• What Can a Quantum Computer Actually Break for the complete breakage map
• Harvest Now, Decrypt Later (HNDL) for why the handshake is the exposure
• Quantum-Vulnerable Algorithm for what needs replacing
• Breaking Today’s Cryptography MOC for the whole picture

Last verified 2026-08-10 · Maintained by Addie LaMarr, LaMarr Labs.