PQC Impacts: Key Sizes, Handshakes and Network Performance

What post-quantum algorithms cost in size and latency

Post-quantum algorithms are larger, not slower. ML-KEM and ML-DSA compute at speeds comparable to the algorithms they replace, but their keys and signatures are one to two orders of magnitude bigger. The cost appears in handshake size, certificate chains and packet behaviour, not in processor load.

How much larger are post-quantum algorithms?

The size difference is the central engineering fact of the migration.

Key establishment is the cheaper of the two problems. A hybrid ML-KEM and X25519 exchange adds roughly 1 to 2 kilobytes to a handshake, which most networks absorb without difficulty. That is why post-quantum key exchange has deployed rapidly across browsers, content delivery networks and cloud services.

Signatures are the harder problem, because they appear repeatedly in a certificate chain rather than once.

Where post-quantum algorithms cost network performance

Certificate chains multiply the signature cost

A typical TLS chain contains a leaf certificate, one or two intermediates and a signature from the certificate authority, plus signed certificate timestamps and OCSP material. Each signature and each public key grows by the factors above.

Cloudflare has reported that a median certificate chain today, after compression, is around 3.2 kilobytes, and that on more than half of non-resumed QUIC connections almost 40 per cent of all server-to-client data is the certificates alone. Their assessment is that using ML-DSA-44 as a drop-in replacement for classical signatures would more than double the bytes transmitted over the lifetime of the majority of QUIC connections.

The initial congestion window

The constraint that produces measurable latency is TCP's initial congestion window, conventionally ten packets or roughly fourteen kilobytes. A handshake that fits inside it completes without waiting. A handshake that exceeds it requires an additional round trip before the remaining data can be sent.

On a low-latency connection an extra round trip is negligible. On a satellite link, a congested mobile network or a long international path, it is the difference between a fast page load and a slow one, and it applies to every new connection rather than to a single transfer.

MTU, fragmentation and middleboxes

A hybrid ML-KEM ClientHello pushes the first packet close to or past a typical 1,500 byte maximum transmission unit. Fragmentation follows, and a proportion of deployed middleboxes handle large or fragmented ClientHello messages incorrectly, dropping the connection rather than passing it on.

Cloudflare found in origin testing that the faster of two available approaches would break approximately 0.05 per cent of connections, which they judged too high to enable by default. That figure is small in percentage terms and large in absolute terms at internet scale, and it illustrates the real risk: not slower connections, but connections that fail entirely on a minority of paths.

QUIC amplification limits

QUIC restricts a server to sending no more than three times the bytes it has received before the client's address is validated. Larger certificate chains can exceed that budget, forcing additional round trips at exactly the point in the connection where latency is most visible.

Constrained links and protocols

On narrowband cellular, LoRaWAN, industrial serial links and satellite backhaul, the payload limits are measured in hundreds of bytes. A post-quantum certificate chain does not fit, and no amount of tuning changes that. These environments require a different approach, covered in our article on quantum risk in embedded and operational technology.

Processor cost is not the constraint

Contrary to a common assumption, the lattice-based algorithms are computationally efficient. ML-KEM key generation, encapsulation and decapsulation are fast, often faster than the elliptic curve operations they replace. ML-DSA signing and verification are likewise competitive.

Cloudflare has published a useful figure on aggregate cost: around 18 million TLS connections per second are established with their network, and upgrading each of those to ML-DSA would consume approximately 2.1 terabits per second, or about 0.5 per cent of their total network capacity. The cost is expressed in bandwidth, not in processor time.

The exception is SLH-DSA. Its signing operation is slow, in the hundreds of milliseconds for the small-signature parameter sets, which restricts it to infrequent operations such as root certificate authority signing. Verification remains cheap.

What this means in different environments

How to reduce post-quantum algorithm overhead

Several measures reduce the cost materially, and most are configuration rather than engineering.

Session resumption avoids retransmitting certificates entirely on subsequent connections. Cloudflare reports that 27 per cent of QUIC connections carrying at least one HTTP request are resumptions, and on those the certificate cost does not arise at all. Maximising resumption rates is the single highest-value mitigation for high-volume services.

Shortening certificate chains removes whole signatures. Every intermediate eliminated removes both a signature and a public key from the chain, so hierarchy design has a direct and multiplied effect on handshake size once post-quantum signatures are in use.

Certificate compression is already widely deployed and should be confirmed as enabled, since its benefit increases with chain size.

Parameter selection matters. ML-DSA-44 rather than ML-DSA-65 saves roughly 900 bytes per signature where the security category is appropriate, though category 5 remains mandatory under CNSA 2.0 for national security systems.

Applying hybrid key exchange broadly while deferring post-quantum signatures is the sequencing most large providers have adopted. It addresses harvest now, decrypt later exposure at low cost, while the more expensive authentication change follows as trust anchor negotiation and chain optimisation mature.

Common mistakes

The first is assuming the problem is processor capacity and sizing hardware accordingly. The cost is bandwidth and round trips, and additional compute does not address it.

The second is testing only on a low-latency local network, where the extra round trip is invisible. Performance testing must include the paths users actually traverse, particularly mobile, satellite and international links.

The third is treating failure as slowness. The significant risk is a minority of connection paths failing outright because of fragmentation or middlebox behaviour, which appears as an intermittent connectivity fault rather than a performance issue and is correspondingly hard to diagnose.

The fourth is ignoring storage limits on credentials. Smartcards, tokens and embedded secure elements have fixed capacity, and a post-quantum credential may simply not fit, which is a procurement problem rather than a tuning problem.

How Unsung helps

Unsung is a UK-based, vendor-neutral consultancy specialising exclusively in public key infrastructure and cryptographic systems, working across central government, defence, healthcare, financial services, nuclear and transport.

We design certificate hierarchies that minimise chain length and handshake size, assess where fragmentation and MTU behaviour will cause failures before rollout, and configure the issuance and certificate lifecycle management infrastructure to support the resulting design. Our PKI design and build work takes post-quantum sizing into account at the architecture stage, where hierarchy decisions are cheap, rather than after deployment, where they are not.

For algorithm selection itself, see our comparison of the NIST post-quantum algorithms.