Symmetric vs Asymmetric Cryptography: How the Quantum Threat Maps Differently onto Each

Most technical coverage of quantum computing and cryptography treats the threat as uniform: quantum computers are coming, encryption is at risk, action is required. That framing is close enough to be quoted but imprecise enough to be misleading. The quantum threat does not map uniformly onto cryptography. It hits asymmetric cryptography with an algorithm that breaks it completely. It hits symmetric cryptography with an algorithm that weakens it. Those two outcomes require different responses, on different timescales, with different urgency. Understanding the distinction is the foundation for any honest migration plan.

How Symmetric and Asymmetric Cryptography Work

Symmetric cryptography uses the same key for encryption and decryption. Both communicating parties must share that key before secure communication can begin. AES (Advanced Encryption Standard, NIST FIPS 197) is the dominant symmetric standard, operating on 128-bit, 192-bit, or 256-bit keys. Its security rests on the computational difficulty of reversing the block cipher operations without the key.

Asymmetric cryptography uses a mathematically linked key pair: a public key that can be shared freely, and a private key known only to the owner. RSA (Rivest, Shamir, Adleman, 1977) and elliptic curve cryptography (ECC) are the dominant asymmetric standards. RSA's security rests on the difficulty of factoring large integers. ECC rests on the discrete logarithm problem over elliptic curves. Asymmetric cryptography solves a specific problem that symmetric cryptography cannot: two parties who have never previously met can establish a shared secret over a public channel.

In practice, modern secure communication protocols use both. TLS 1.3 (IETF RFC 8446) uses asymmetric key exchange to establish a session key, then switches to AES for bulk data encryption. Asymmetric is used for key exchange and digital signatures. Symmetric handles the actual data. This is the pattern to keep in mind when examining how quantum algorithms affect the two types.

Shor's Algorithm: RSA and ECC Are Broken, Not Weakened

Peter Shor published his algorithm in 1994. The 1997 paper in SIAM Journal on Computing remains the definitive reference. The result is precise: Shor's algorithm solves integer factorisation and discrete logarithm computation in polynomial time on a quantum computer. Classical algorithms for the same problems run in sub-exponential time. That is not a speed difference. It is a fundamentally different scaling relationship.

The practical consequence: RSA-2048, estimated to require 2^112 operations to break classically, would be broken in polynomial time on a cryptographically relevant quantum computer (CRQC). The same applies to ECDH and ECDSA over P-256 or P-384 curves. Shor's algorithm applies with equal force to integer factorisation (RSA) and discrete logarithm computation over elliptic curves (ECC).

A common question at this point is whether larger RSA keys offer protection. They do not. Shor's algorithm scales polynomially with key size. Doubling from RSA-2048 to RSA-4096 adds a modest polynomial factor to the breaking time, not an exponential one. The entire security model of RSA collapses against a CRQC regardless of key size. This is why NIST IR 8547 (November 2024) takes the position it does: RSA in all key sizes, ECDH, ECDSA, DSA, and finite-field Diffie-Hellman are deprecated for new systems by 2030, with full retirement by 2035. The deprecation is not gradual hardening. It is a judgement that these algorithms cannot be patched.

See our separate analysis of how Shor's algorithm breaks RSA and ECC for the algorithm mechanics in detail.

Grover's Algorithm: AES Is Weakened, Not Broken

Lov Grover published his algorithm in 1996 for unstructured database search. For a search space of N elements, Grover's algorithm finds the solution in O(sqrt(N)) quantum operations instead of O(N) classically. Applied to cryptography, this means a CRQC can search a symmetric key space in the square root of the classical time. For a symmetric cipher with a k-bit key, the effective post-Grover security is k/2 bits.

The numbers matter here. AES-128 has an effective key length of approximately 64 bits after a Grover attack. That is below any accepted security threshold and is not appropriate for data with long confidentiality requirements. AES-256 has an effective key length of approximately 128 bits, which NSA explicitly judges adequate in CNSA 2.0, and which NIST IR 8547 (November 2024) does not deprecate.

Grover's algorithm also applies to hash functions. SHA-256 retains approximately 128-bit post-Grover preimage resistance. SHA-384 retains 192 bits. SHA-512 retains 256 bits. NIST IR 8547 retains all three. SHA-1 and MD5, already classically deprecated, are not retained.

The critical distinction from the Shor case: Grover provides a quadratic speedup. Shor provides an exponential one. That difference is the difference between an algorithm being weakened and an algorithm being broken. The required response is different in each case.

Different Threats Require Different Responses

The response to the Shor threat requires algorithm replacement. RSA and ECC must be replaced with new mathematical constructions that have no known quantum speedup. ML-KEM (FIPS 203) is the NIST-standardised key encapsulation mechanism built on the Module Learning With Errors lattice problem. ML-DSA (FIPS 204) and SLH-DSA (FIPS 205) are the standardised signature replacements. These are not upgrades of RSA or ECC with larger parameters. They are different algorithms with different mathematical foundations. A system supporting RSA requires a new KEM implementation for ML-KEM, not a parameter change to the existing one.

The response to the Grover threat is a configuration change. AES-128 should be replaced with AES-256 for data with meaningful confidentiality requirements. AES-256 is already widely deployed and supported. No application rewrite is necessary, and no new cryptographic primitive needs to be integrated. The migration priority follows logically: asymmetric migration is urgent because Shor's algorithm would eliminate all protection. Symmetric migration from AES-128 to AES-256 matters for long-archive data, but it is a lower-complexity task and AES-128 leaves a non-trivial residual floor even post-Grover (64 bits is weak but not zero).

See our comparison of post-quantum cryptography and quantum cryptography for the algorithm replacement context in more detail.

TLS as a Worked Example

TLS 1.3 (IETF RFC 8446) combines both types of cryptography in a single protocol, which makes it a useful illustration of where each type of migration work falls.

A TLS 1.3 connection has three distinct cryptographic components:

• Key exchange: ECDH (X25519 or P-256) is used to establish the session's shared secret. This is asymmetric, and it is broken completely by Shor's algorithm on a CRQC. This is the component that must be replaced.
• Bulk data encryption: AES-128-GCM or AES-256-GCM encrypts the actual payload. AES-256-GCM is quantum-adequate. AES-256-GCM should be preferred over AES-128-GCM in high-value or long-retention connections: Grover's algorithm halves the effective key length, leaving AES-128 at approximately 64-bit post-quantum security, which falls below any accepted threshold.
• Certificate signatures: ECDSA or RSA authenticates the server identity. Asymmetric, Shor-vulnerable. Certificates must eventually migrate to ML-DSA.

The hybrid TLS approach addresses the key exchange component. IETF RFC 9496 specifies X-Wing, combining X25519 and ML-KEM-768 in a hybrid KEM. NSS environments require ECDH P-384 combined with ML-KEM-1024 rather than the ML-KEM-768 variant used in commercial TLS. The hybrid construction provides security so long as either component holds: if ML-KEM-768 has an undiscovered flaw, X25519 still provides protection; if X25519 is broken by a CRQC, ML-KEM-768 still holds.

OpenSSL 3.5, BoringSSL, and wolfSSL all added ML-KEM support in 2025. Updating cipher suite preference to favour AES-256-GCM is a server configuration change that requires no library update.

HNDL: The Asymmetric Threat Is Already Active

The quantum threat to asymmetric cryptography is not solely a future risk. Harvest-now, decrypt-later (HNDL) attacks collect encrypted traffic today for decryption once a CRQC is available. When an adversary captures a TLS session, they capture the ECDH public key material from the handshake. On a CRQC, Shor's algorithm solves the elliptic curve discrete logarithm problem to recover the ephemeral private key, reconstructing the session key and everything the session protected.

The Grover threat to AES-256 works differently. It is a brute-force threat that requires active computation against the ciphertext. An adversary with a CRQC must compute against each AES-256 ciphertext individually. That is a meaningful distinction: the HNDL model is passive collection followed by future CRQC decryption of the asymmetric key exchange. The Grover attack on AES-256 is active, computationally expensive, and session-specific. For data with a confidentiality lifetime that extends past the estimated CRQC availability window, the asymmetric threat is present now in a way the symmetric threat is not.

The category of data that faces HNDL risk is any data whose confidentiality requirement extends past the point at which a CRQC may be available. Michele Mosca's 2018 inequality (published in IEEE Security & Privacy) formalises this: if the time to complete migration (X) plus the required confidentiality lifetime of the data (Z) exceeds the time until a CRQC (Y), the data is at risk. For data categories with long retention requirements, that calculation runs in the negative direction for many organisations today.

For an assessment of which data categories carry the most immediate HNDL risk, see our analysis at which data is most at risk from HNDL today.

What This Means Practically

The asymmetric migration is the primary engineering task. ML-KEM, ML-DSA, and SLH-DSA are standardised, library support is arriving, and NIST IR 8547 November 2024 has set the deprecation timeline. The first step is a cryptographic inventory: identify every system using RSA or ECC for key establishment or signatures, classify those systems by migration difficulty, and sequence the work by exposure risk.

The symmetric migration is narrower in scope. AES-128 in active use for long-retention sensitive data should be moved to AES-256. This does not require PQC deployment and can be done now with classical infrastructure. For systems already using AES-256, no symmetric algorithm change is needed.

The combined position: Shor's algorithm breaks asymmetric cryptography. Grover's algorithm weakens symmetric cryptography. The first is an existential problem with a defined solution. The second is a manageable one with an available fix. Both require attention. They do not require the same response.