Symmetric vs Asymmetric Encryption: Which One Quantum Breaks and Which Survives

The Two Halves of Modern Cryptography

Every real-world encryption system uses both symmetric and asymmetric cryptography. Asymmetric (public-key) algorithms like RSA and ECDH negotiate a shared secret between parties who have never met. Symmetric algorithms like AES then use that secret to encrypt the bulk of the data. Quantum computers affect these two halves completely differently.

Asymmetric: Broken

Shor's algorithm (1994) solves integer factorization and discrete logarithms in polynomial time on a quantum computer. This breaks:

• RSA (any key size)
• Diffie-Hellman (any modulus size)
• ECDH (any curve)
• ECDSA (any curve)
• EdDSA including Ed25519 and Ed448
• DSA (classical)
• Paillier, ElGamal, and other discrete-log systems
• Pairing-based cryptography (including BLS signatures)

There is no key size that saves these algorithms. You must migrate to Post Quantum Cryptography alternatives.

Symmetric: Weakened but Survivable

Grover's algorithm (1996) provides a quadratic speedup for unstructured search. For a symmetric cipher with k-bit key, the quantum attack cost drops from 2^k to 2^(k/2). This halves the effective security.

Algorithm	Classical security	Post-Grover	Status
AES-128	128 bits	64 bits	Deprecate for long-term data
AES-192	192 bits	96 bits	Borderline; prefer AES-256
AES-256	256 bits	128 bits	Quantum-safe
ChaCha20-Poly1305	256 bits	128 bits	Quantum-safe
3DES	112 bits	56 bits	Deprecated, do not use

AES-256 at effective 128-bit post-quantum security is still astronomically secure. A Grover attack on 2^128 would take longer than the age of the universe on any plausible quantum computer.

Hash Functions: Similar to Symmetric

Hash functions like SHA-256, SHA-384, SHA-512, SHA3-256, and BLAKE3 are affected by Grover too. Preimage resistance halves (an n-bit hash has 2^(n/2) post-Grover preimage resistance). Collision resistance, already 2^(n/2) classically via birthday, does not get faster under Grover.

For post-quantum use, prefer hash output sizes of 384 bits or more when you need provable long-term security. SHA-384, SHA-512, SHA3-384, and SHA3-512 are all fine. BLAKE3 at 256-bit output is fine for most uses but can be configured to 512 bits.

The Shape of a Post-Quantum Protocol

A TLS 1.3 session using hybrid Post Quantum Cryptography looks like this after Q-Day:

1. Key exchange: X25519 + ML-KEM-768. X25519 is broken, but ML-KEM-768 is not. The derived shared secret is still secret.
2. Signing: ML-DSA-65 (certificate signature). Classical ECDSA is broken. PQC signature holds.
3. Symmetric cipher: AES-256-GCM or ChaCha20-Poly1305 (still 256-bit key). Grover reduces to 128-bit post-quantum security. Still safe.
4. Hash / MAC / KDF: HKDF over SHA-384. Grover reduces preimage to 192-bit. Still safe.

Every link in the chain holds under quantum attack, because the weakest link (key exchange) has been replaced with a PQC algorithm.

Implications for Your Migration Plan

1. Replace asymmetric first. RSA, ECDH, ECDSA, Ed25519 are emergencies on any long-lived data.
2. Upgrade symmetric key sizes if you still run AES-128. Move to AES-256 or ChaCha20-Poly1305.
3. Prefer larger hash outputs for long-lived artifacts. Code-signing certificates that must remain valid for 10 years should use SHA-384 or higher.
4. Do not overspend on symmetric side. AES-256 is already enough. You do not need "AES-512" (which does not exist).

Hybrid Is Not Just for Paranoia

Some operators wonder why the world is deploying hybrid (classical + PQC) rather than pure PQC. Three reasons:

1. Lattice cryptography is young. ML-KEM has been analyzed since roughly 2012 in its various forms. RSA has been studied since 1977. If a surprise attack on lattices appeared, the classical half of the hybrid would still protect everything encrypted so far.
2. Implementation bugs. A bug in an early ML-KEM library would not immediately expose data if the classical half still works.
3. Regulatory acceptance. Agencies that have not yet accepted pure PQC can accept hybrid immediately because the classical half remains in place.

Frequently Asked Questions

Is AES quantum-safe?

AES-256 is quantum-safe at the effective 128-bit post-Grover security level, which is still cryptographically unreachable. AES-128 is borderline and should be upgraded for long-term data.

Are hash functions broken by quantum?

No, only weakened. Grover gives a quadratic speedup for preimage attacks, halving the effective security. Collision attacks do not benefit. For long-term security, use 384-bit or larger hash outputs.

Which do I migrate first, symmetric or asymmetric?

Asymmetric. Shor's algorithm breaks it completely. Symmetric can be addressed by moving from AES-128 to AES-256, which is typically a configuration change.

Does Grover speed up all quantum attacks on symmetric crypto?

Grover is the best known generic quantum attack. Other structured attacks may exist for specific ciphers, but AES has resisted structured attacks for decades, classical or quantum.

Sources

1. Grover (1996)
2. Shor (1994)
3. NSA CNSA 2.0
4. FIPS 203 (ML-KEM)

Related Articles

• Shor's Algorithm
• Grover's Algorithm
• AES-256-GCM
• Hybrid Encryption
• Why RSA-2048 Will Break