Why Larger Keys Do Not Answer the Quantum Threat

The three classical public-key families — RSA, finite-field Diffie-Hellman, and elliptic curves — rest on two problems that are believed hard for classical computers. Both problems have a structure that a quantum computer can exploit, and the exploitation is not a matter of trying more keys. Shor’s algorithm solves integer factorization and discrete logarithm in polynomial time. The consequence for a system designer is that the key-size table in Key Size Equivalence Across RSA, Diffie-Hellman, and Curves stops being a dial that can be turned.

The structure that Shor’s algorithm exploits

Every classical public-key scheme reduces to arithmetic in a finite abelian group. RSA computes $m^e \bmod n$ in the multiplicative group modulo $n$, and its hard problem is factoring $n$; Diffie-Hellman and the curve schemes compute $g^x$ or $xP$ in a cyclic group, and their hard problem is the discrete logarithm. Classically, the best algorithms cost about $\sqrt{q}$ group operations for a prime-order group $q$, or subexponential for the special-purpose algorithms against finite fields and factoring.

Shor’s algorithm ignores the group’s size and attacks the periodicity of the group operation itself. Quantum period finding — the quantum Fourier transform applied to a superposition of group elements — extracts the order of $g$, and once the order is known the discrete logarithm follows by classical post-processing. For factoring, the reduction is to order finding modulo $n$, which yields a nontrivial square root of unity and hence a factor. Both reductions are polynomial in the bit length.

The important point for design is what the algorithm depends on: the abelian group structure and the existence of an efficient quantum circuit for the group operation. It does not depend on the size of the modulus, the choice of curve, the choice of generator, or any parameter the implementer controls. A 15360-bit RSA key and a 512-bit curve are both solved in polynomial time; the polynomial has a larger constant for the bigger key, and that is the entire difference.

This is why “just use bigger keys” fails as a strategy. The classical table encodes a race between key growth and algorithm improvement, and it can be run indefinitely because each added bit genuinely costs the attacker more. Shor’s algorithm changes the complexity class, and a complexity class is not outrun by a constant factor.

What survives and what does not

The split is by primitive, not by scheme name.

Symmetric encryption and hash functions lose part of their margin, not all of it. Grover’s algorithm gives a quadratic speedup for unstructured search, so a $b$-bit key offers roughly $b/2$ bits of security against a quantum adversary. Doubling the key length restores the original level: AES-256 against Grover is about as hard as AES-128 against a classical attacker. The cost is a larger key and more rounds, both of which are affordable. The quadratic speedup is also harder to realise in practice than the counting argument suggests, because the search must be run as a single long circuit rather than iterated, but the conservative assumption is that it applies.

Public-key encryption and key agreement do not survive. RSA, finite-field Diffie-Hellman, ECIES, and ECDH all fall to Shor’s algorithm. No parameter change rescues them, because the attack targets the algebraic structure that makes them work.

Signatures fall for the same reason. RSA signatures, DSA, ECDSA, and EdDSA all depend on the hardness of a discrete logarithm or a factorization. A forged signature requires the private key, and the quantum algorithm recovers the private key from the public one.

The asymmetry between these cases is the reason migration is urgent for key establishment even where signatures seem less exposed. Symmetric keys are cheap to lengthen; public-key groups cannot be lengthened into safety.

The threat that arrives before the hardware

A cryptographically relevant quantum computer does not exist, and published resource estimates for factoring a 2048-bit modulus put the requirement in the millions of physical qubits once error correction is accounted for, with the exact figure depending heavily on assumptions about gate error rates and circuit depth. Those estimates have fallen over time, which is the reason the timeline is treated as uncertain rather than distant.

The exposure does not begin when the machine is built. An adversary can record encrypted traffic now and decrypt it later, once the capability exists. For data that must remain confidential for a decade or more — long-lived credentials, archival records, private keys transported under a hybrid scheme — the confidentiality requirement overlaps the arrival window. This is the harvest-now-decrypt-later argument, and it is why key establishment is migrated ahead of signatures: a signature forged in the future does not retroactively compromise a session that has already ended, but a recorded session does become readable.

Forward secrecy reduces but does not eliminate the exposure. An ephemeral exchange whose secrets were erased cannot be decrypted later even with a quantum computer, as described in Ephemeral Diffie-Hellman and What Forward Secrecy Actually Buys, because the attack needs the ephemeral public value and the private exponent that produced it, and the latter no longer exists. The problem is that the long-term authentication key is still a classical signature, so an adversary who records the handshake and later forges the authentication can mount an active attack on new sessions. Forward secrecy protects the past; it does nothing for the future.

What a replacement has to provide

A post-quantum key establishment primitive must supply the same interface as the classical one: two parties, no prior shared secret, a shared key at the end, and public values small enough to fit in a handshake. The standardised answer is a key encapsulation mechanism, the interface described in Hybrid Encryption and the Cost of Encrypting Long Messages: the recipient publishes a public key, the sender encapsulates to produce a ciphertext and a key, and the recipient decapsulates.

The lattice-based schemes standardised as ML-KEM and ML-DSA are built on module learning-with-errors, a problem for which no efficient quantum algorithm is known. The security argument is a reduction to a lattice problem, and the parameters are chosen so that the best known classical and quantum algorithms both cost more than the target level. The public keys and ciphertexts are measured in hundreds of bytes to a few kilobytes depending on the parameter set — an ML-KEM public key is 800 bytes at the smallest set and 1568 at the largest — which is the operational cost that shows up in every protocol that adopts them.

That size is the reason hybrid construction is the transitional design rather than a post-quantum-only one. A hybrid exchange carries both a classical and a post-quantum public value, derives the key from the concatenation, and is secure if either component holds. It defends against the quantum threat and against the possibility that a new lattice scheme has a classical weakness nobody has found yet. The cost is the sum of both sizes plus the extra computation, paid once per connection.

Signatures migrate more slowly because the sizes are worse and because the verification cost is on the critical path for every certificate in a chain. A hybrid certificate chain doubles or triples the bytes that must be transmitted and parsed before a connection can start.

Where the migration actually costs

The primitive swap is the easy part. The expensive part is everything that assumed the old primitive’s shape.

Fixed-size fields. Protocols, file formats, and hardware tokens often encode keys and signatures in fixed-size buffers sized for a 256-bit curve or a 2048-bit modulus. A post-quantum public key does not fit, so every such buffer is a format change, and format changes propagate through parsers, databases, and stored credentials.

Certificate chains and trust anchors. A signature algorithm is named in a certificate, and a verifier must understand the name. Adding a new algorithm means every verifier in the chain — including embedded devices that will never be updated — must either understand it or be bypassed. The practical approach is to run parallel chains during the transition, which doubles the size and the number of signatures to verify.

Protocol negotiation and downgrade. A protocol that lets the peer choose between classical and post-quantum must resist an attacker who strips the post-quantum option. The defence is to bind the negotiation into the authenticated transcript, so a downgrade is detectable. The same requirement applies to parameter negotiation in classical key exchange: a peer that can strip the stronger option must be detected, which means the negotiation has to be inside the authenticated transcript.

Long-lived keys and stored data. A private key generated today under a classical scheme is compromised the day the quantum computer arrives, and re-keying does not help if the old key signed something that must remain trusted. Signature schemes with long validity periods need to be migrated before the data they protect expires, not before the hardware exists.

Where the classical schemes remain

Migration is not deletion. RSA and elliptic curves remain correct and remain the right choice for systems whose data lifetime is short and whose threat model does not include a future quantum adversary. They also remain necessary as the classical half of hybrid constructions, where their well-understood failure modes serve as the fallback.

What changes is the assumption that the choice is permanent. A protocol designed now should treat the key exchange algorithm as a replaceable component with a defined interface, because the interface is what makes the next migration possible. The classical schemes were designed without that assumption — RSA’s key format embeds the algorithm in the key, and a certificate names its algorithm in a field that verifiers must parse — and that is the design constraint the next generation is trying to avoid.