Sizes, Speed And Security Levels: What PQC Does To Keys And Handshakes

Switching to post-quantum cryptography changes the numbers your systems handle. An X25519 public key is 32 bytes. Its post-quantum counterpart in FIPS 203, an ML-KEM-768 encapsulation key, is 1,184 bytes. Signatures grow even more. For most applications the extra computing work is small; the extra bytes are what break things.

This article sets out the security categories NIST uses to compare algorithms, the sizes of the standardised schemes, and where those sizes cause practical trouble. It is written for architects and engineers who need to estimate the impact on their own protocols, devices and certificate chains before a migration starts.

The Five Security Categories

Post-quantum algorithms are not rated with a single “bits of security” number. NIST instead asks whether breaking an algorithm takes at least as much effort as breaking a well-understood reference. It defines five categories.¹

Higher categories mean larger keys and slower operations. FIPS 203 recommends ML-KEM-768, a category 3 parameter set, as the default, describing it as a large security margin at a reasonable cost.² The NSA’s CNSA 2.0 suite for US national security systems requires the category 5 options, ML-KEM-1024 and ML-DSA-87.³

How Big Are The New Keys

The table below compares the standardised schemes with the classical algorithms they replace. For key establishment it shows what each side sends; for signatures it shows the public key and the signature, which are what travel in certificates and protocols.

All three ML-KEM parameter sets produce a 32-byte shared secret, the same size as today’s key agreement output.² The ML-DSA figures come from FIPS 204⁴ and the SLH-DSA figures from FIPS 205, where the “s” variants are tuned for smaller signatures and the “f” variants for faster signing.⁵ Falcon’s figures come from its submission team; the final FN-DSA standard could differ in detail.⁶ Classical sizes follow from RFC 7748 for X25519 and from the key lengths in FIPS 186-5.⁷⁸

Three patterns stand out. ML-KEM adds roughly a kilobyte in each direction. ML-DSA signatures are roughly 38 to 72 times the size of a 64-byte ECDSA P-256 signature. SLH-DSA has tiny public keys but signatures measured in tens of kilobytes.

Speed Is Usually Not The Problem

Lattice key establishment is cheap to compute. Cloudflare, in its own benchmarks published in 2024, reported that ML-KEM is typically faster than X25519, although results vary by platform.⁹ The OpenSSH project described its new default, mlkem768x25519-sha256, as considerably faster than the previous default, the hybrid sntrup761x25519 method.¹⁰

Signatures involve more trade-offs. Falcon, the basis of FN-DSA, was designed around floating-point arithmetic, which NIST says creates challenges for validation and side-channel protection.¹¹ In September 2026 NIST proposed specifying fixed-point arithmetic in FIPS 206 instead, so that every implementation of signing can be checked against exact test results.¹² SLH-DSA makes the trade-off explicit: its “f” variants sign faster but produce larger signatures, and its “s” variants do the reverse.⁵

Where Size Starts To Hurt

The clearest example is the TLS handshake used by every HTTPS connection. With the hybrid group X25519MLKEM768, now standardised in RFC 10024, the client’s key share is 1,216 bytes and the server’s is 1,120 bytes, against 32 bytes each for X25519 alone.¹³ Most networks handle that without trouble, and Google announced in 2024 that Chrome would offer it from version 131.¹⁴

Certificates are harder. A typical TLS connection carries several signatures and public keys across the server’s certificate chain and handshake. Cloudflare estimated that moving all of them to ML-DSA-44 would add about 17 kilobytes to the handshake. It also reported that some clients or middleboxes break once certificate chains grow by more than about 10 kilobytes.⁹ That is why post-quantum authentication on the web is moving more slowly than post-quantum key establishment.

Planning For The Extra Bytes

The sizes suggest a sensible order of work. Post-quantum key establishment is already practical almost everywhere, so most organisations can enable hybrid ML-KEM in TLS, SSH and VPNs once their software supports it, then watch for failures in older network equipment. This is also where the urgency lies, because recorded traffic can be decrypted later.

Signatures need more design work. Choosing between ML-DSA, SLH-DSA and the coming FN-DSA is partly a question of where the bytes travel. A firmware image signed once and verified at boot can absorb a large signature. A certificate chain sent on every connection, or a constrained device on a slow radio link, may not. Measuring message sizes and storage limits in your own systems is the only reliable way to know which option fits.