The Performance Cost of PQC: Key Sizes and Network Latency

TL;DR

Post-quantum primitives are not a drop-in size replacement for classical ones: ML-KEM-768's public key is $1{,}184$ bytes against X25519's $32$, and ML-DSA-65's signature is $3{,}309$ bytes against Ed25519's $64$ — roughly a $37\times$ and $52\times$ increase respectively. A hybrid X25519MLKEM768 key exchange alone adds about 1.1 KB per direction; a full ML-DSA-65 certificate chain adds tens of kilobytes to the server's first flight. That flight can now exceed the RFC 6928 initial TCP congestion window ($\text{IW} = \min(10 \cdot \text{MSS},\ \max(2 \cdot \text{MSS},\ 14{,}600\text{ bytes}))$), forcing a congestion-driven wait or exposing more of the handshake to loss-triggered retransmission. Over UDP-based transports (QUIC, DTLS 1.3), the same growth collides with the mandatory anti-amplification limit ($B_{\text{server}} \le 3 \times B_{\text{client}}$ before address validation) — a hybrid/PQC ServerHello and certificate chain routinely exceeds that budget, which effectively makes Retry-based address validation mandatory rather than an edge-case defense. None of this is fatal to PQC deployment, but it means the migration is a network-engineering problem as much as a cryptographic one.

Byte-Level Comparison

The ratios matter more than the absolute numbers:

A single hybrid key exchange is a modest addition: X25519's 32 bytes plus ML-KEM-768's 1,184-byte encapsulation key brings a ClientHello key_share to 1,216 bytes, and the server's response (X25519's 32 bytes plus a 1,088-byte ML-KEM ciphertext) to 1,120 bytes — each well under 1.5 KB. The larger cost sits in certificate signatures, and it compounds: a typical chain carries a leaf and an intermediate certificate, each holding a public key and an issuer signature. Under ML-DSA-65, one certificate's cryptographic payload alone (public key + signature) is roughly $1{,}952 + 3{,}309 = 5{,}261$ bytes, before X.509 boilerplate (names, extensions, OIDs — typically 300–500 bytes regardless of algorithm). A two-certificate chain pushes the server's Certificate message past 11 KB on cryptographic material alone.

TCP Congestion Window Pressure

RFC 6928 sets the initial TCP congestion window — how much a server can send in its first flight before waiting for an ACK — as:

With a standard 1,460-byte MSS (1500-byte Ethernet MTU minus IP/TCP headers), this caps the first flight at roughly 14.6 KB. A classical TLS 1.3 server flight — ServerHello, EncryptedExtensions, Certificate, CertificateVerify, Finished — typically totals a few kilobytes and clears this window without incident, one reason the classical handshake reliably completes in a single round trip.

A server flight carrying a hybrid ML-KEM key share plus a full ML-DSA-65 certificate chain can reach 15–17 KB — past the default initial window on stacks that haven't tuned it upward. Two consequences follow. First, on a connection that hasn't otherwise validated a larger window, the excess bytes wait for the window to grow via normal slow-start, adding latency the classical handshake never incurred. Second, and more consistently costly: more packets in flight means a proportionally higher chance that at least one segment is lost on any given connection, and TCP's retransmission timeout for a lost segment costs at minimum a full RTT — a cost that scales with how many additional segments the larger PQC flight requires, not with the connection's underlying loss rate changing.

Fragmentation and UDP-Based Transports

TLS 1.3 over TCP doesn't fragment at the IP layer under normal conditions — TCP simply segments the payload into multiple MSS-sized packets, and the transport layer handles reassembly transparently. The sharper fragmentation risk shows up in TLS's UDP-based relatives, QUIC (RFC 9001) and DTLS 1.3 (RFC 9147), where a datagram exceeding the path MTU can be IP-fragmented, and fragmented UDP datagrams are dropped by a meaningful fraction of middleboxes and firewalls in practice — particularly over IPv6, where only the originating host fragments and path MTU discovery failures silently blackhole the connection instead of triggering a retry. QUIC mitigates this partly by requiring Initial packets to pad to at least 1,200 bytes and by coalescing multiple QUIC packets into a single UDP datagram up to the path MTU, but a hybrid/PQC handshake that no longer fits in one datagram's worth of coalesced packets must be split across several sends — each an independent point of loss exposure in a transport that, unlike TCP, does not benefit from decades of kernel-level congestion and retransmission tuning applied uniformly across the fleet.

Amplification: The Anti-Amplification Limit Under Pressure

TLS-over-TCP is structurally resistant to reflection amplification: an attacker spoofing a victim's source IP cannot complete the TCP three-way handshake, since the SYN-ACK goes to the victim, not the attacker — no TLS byte is ever sent to an unvalidated address. QUIC and DTLS 1.3, running over UDP, have no equivalent handshake gate, so both specify an explicit anti-amplification limit instead: before a client's address is validated, a server must not send more than three times what it has received from that address.

QUIC's mandatory 1,200-byte minimum Initial packet size sets a starting budget of about 3,600 bytes before validation — sized with classical certificate chains in mind. A hybrid ServerHello plus an ML-DSA-65 certificate chain of 15+ KB overruns that budget by roughly $4$–$5\times$ regardless of whether the requesting client is legitimate. The server cannot simply send the oversized flight: it must either coalesce as much as the budget allows and wait for the client's response (which, by proving receipt, incrementally validates the address and unlocks more send budget) or issue a Retry token up front to force explicit address validation before attempting the full flight. In practice, PQC-sized certificate chains make Retry-based validation the default path for first-time QUIC connections rather than a fallback reserved for suspected abuse — a direct, quantifiable operational cost of the larger payloads, independent of whether any attack is actually underway.

Mitigation Strategies

• Enable TLS certificate compression (RFC 8879), with adjusted expectations. Compression helps most against the redundant ASN.1/X.509 boilerplate in a certificate, not against the key and signature material itself — ML-DSA public keys and signatures are high-entropy, lattice-derived values that don't compress meaningfully. The relative benefit of certificate compression shrinks as PQC material becomes a larger fraction of the certificate's total bytes.
• Amortize cost via session resumption. TLS 1.3's PSK-based resumption (including 0-RTT) skips the full certificate exchange on repeat connections entirely — the large payload cost is paid once per session lifetime, not per connection, and resumption's key schedule stays PSK-derived and small regardless of which KEM established the original session.
• Tune the initial congestion window deliberately. Raising initcwnd to fit a hybrid/PQC first flight avoids a slow-start-induced wait, but should be sized to the deployment's actual flight size and network conditions — an unconditionally maximized window trades handshake latency for bufferbloat and fairness risk elsewhere on shared links.
• Treat Retry/cookie-based address validation as standard, not exceptional, for QUIC and DTLS deployments serving hybrid or full-PQC handshakes. Given the anti-amplification math above, planning capacity and latency budgets around a mandatory validation round trip is more accurate than treating it as a rare mitigation path.
• Phase the migration by payload weight, not uniformly. Hybrid KEM-only deployment (X25519MLKEM768) adds roughly 1 KB per direction and rarely causes the problems described here. Full ML-DSA certificate chains are the dominant cost — deferring signature-layer migration behind the crypto-agile abstraction boundary until network paths are tuned for the larger flight size is a reasonable sequencing, not a security compromise, since the key exchange is what Harvest Now, Decrypt Later actually threatens.
• Match parameter set to required security category. Defaulting every deployment to the largest available parameter set (ML-DSA-87 over ML-DSA-65, for instance) multiplies this cost without a corresponding security requirement in most web-facing contexts — size the algorithm to the actual threat model, not to the ceiling.