Performance of post-quantum cryptography

I've written extensively about the impact of post-quantum cryptography on networking performance (links below). Still, I thought it would be a good idea to write another blog post to summarise the current situation, provide additional information and references, and perhaps draw some conclusions.

In a nutshell, while post-quantum primitives like ML-KEM and ML-DSA come with manageable CPU overheads, their significantly larger public-key and signature sizes pose a major payload problem for real-world networks. Pushing these larger byte footprints through transport protocols forces fragmentation, exceeds standard initial congestion windows, and triggers additional round trips that directly degrade connection speed.

This blog post is part of a series. Although you don't have to have read all the previous installments, you should read these two for the relevant background they provide:

• Effect of post-quantum algorithms on networking performance
• Why post-quantum signatures are breaking TLS handshake limits

These two blog posts focus on theory, but you'll notice they don't provide much evidence. What are the industry and academia saying?

Chrome was the first browser to deploy X25519MLKEM768 (a new, hybrid, quantum-safe key establishment), so it makes sense to start with them. What are they seeing in practice?

"Chrome saw a 4% increase in TLS handshake latency when they deployed ML-KEM, which takes up approximate 1K of additional space in the ClientHello. This pushed the size of the ClientHello greater than the standard maximum transmission unit (MTU) of packets on the Internet, ~1400 bytes, causing the ClientHello to be fragmented over two underlying transport layer (TCP or UDP) packets."

— David Adrian, from Post-quantum cryptography is too damn big

On the same topic, Cloudflare has published several interesting blog posts on post-quantum cryptography. Rather than try to find the best resource, here's a link to their entire category. To save you some time, their findings are consistent with Google's: larger payloads lead to TCP fragmentation, increased probability of packet loss, and measurable connection delays on real-world networks.

When you introduce new cryptographic payloads and protocol extensions to the wild, you run straight into middlebox ossification, network appliances, and security inspection devices that drop connections simply because they encounter data shapes or sizes they weren't programmed to expect.

As Google, Cloudflare, Meta, and AWS expanded post-quantum key agreement deployment, a distinct set of operational issues emerged:

• Middlebox and firewall failures: Network appliances and security gateways frequently drop fragmented multi-packet ClientHello messages or reject unknown TLS extensions. Sophos firewall instances running web protection inspect modes have historically struggled with post-quantum client handshakes. At the same time, AWS Network Firewall users have experienced rule-matching bugs when handling OpenSSL 3.5.1 PQC handshakes.
• Large-scale deployment discrepancies: In Meta's real-world TLS deployment (TLS-PQR), even minuscule intolerance rates translated into millions of impacted user connections. Similarly, Cloudflare's broader PQC rollouts (pqc-to-origin and post-quantum for all) highlighted that edge-to-origin and client-to-edge paths encounter vastly different middlebox environments.
• Extreme fragmentation edge cases: When network path MTUs fall below typical standards or when UDP/QUIC handshakes hit strict amplification limits, large PQC messages trigger drop loops; a phenomenon documented in detail by research projects like tldr.fail.

Clients who want to speak with servers that don't offer X25519 or X25519MLKEM768 will need to issue a HelloRetryRequest. In the future, this may affect clients who wish to use a pure ML-KEM key establishment, forcing an extra network round trip whenever the client's predicted key share misses the server's capabilities.

In the meantime, we're seeing similar problems with CDN origins: if an origin doesn't support mainstream key exchange methods, an additional round trip is required to complete the handshake. Cloudflare does have some interesting information that's not available elsewhere about what origins prefer for key establishment. In their Automatic Key Exchange for Origins research, they demonstrate how auto-negotiating key-exchange preferences dynamically prevent performance-killing HelloRetryRequest round trips between edge nodes and upstream origins.

We're not seeing this problem yet, because post-quantum certificate chains are rare. Where they're used, they're used over (faster) private networks, and among clients that have greater control over the network settings and can tune their TCP stacks.

However, academic research provides a clear preview of what might happen when post-quantum authentication reaches the public Web PKI:

• Certificate chains and handshake throughput: A comprehensive performance study by Sikeridis et al. (NDSS 2020) benchmarked NIST PQC signature candidates inside TLS 1.3 certificate chains. They discovered that using a single large PQC signature scheme across an entire chain severely degrades server throughput and latency. To mitigate this, they proposed mixed certificate chains (combining fast, larger algorithms like Falcon with smaller, slower ones like Dilithium or SPHINCS+), which significantly speeds up handshake times and restores connection rates.
• Network latency vs. CPU bottlenecks: Benchmarking post-quantum cryptography in TLS by Paquin, Stebila, and Tam (Microsoft Research) using a network emulation framework proved that CPU computation times are rarely the primary bottleneck in PQC TLS. Instead, network latency and packet loss dominate total page-load times due to the sheer size of post-quantum public keys and ciphertexts.
• TTFB and TTLB under real network conditions: Research by Kampanakis and Childs-Klein (MADWeb 2024) evaluated the full connection lifecycle, Time-To-First-Byte (TTFB), and Time-To-Last-Byte (TTLB). They found that while data-heavy PQC certificate chains increase initial handshake latency by 20–30% on clean links, their relative impact is heavily amortized when transferring large data payloads or operating over already impaired/lossy connections.
• White-box and black-box microbenchmarks: Sosnowski et al. (ACM CoNEXT '23) demonstrated that while lattice-based key exchange execution speed outpaces classical algorithms on the CPU, increased key and certificate chain sizes drive network-layer latency on lossy network paths.

When moving away from desktop browsers and powerful edge servers toward hardware security modules (HSMs), IoT microcontrollers, and embedded systems, the large memory footprints and packet sizes of PQC impose severe physical constraints.

Standard IoT protocols (such as CoAP, DTLS, and EDHOC) operate over lossy low-power wireless networks where packet buffers are measured in kilobytes. Storing and reassembling multi-kilobyte PQC public keys or signatures quickly leads to buffer exhaustion, fragment-loss loops, and severe battery drain. Furthermore, HSMs and smart cards face tight non-volatile storage limits and restricted internal bus bandwidths when managing PQC key material and processing heavy OTA (Over-The-Air) firmware signatures.

The IETF is actively developing engineering workarounds to adapt constrained environments to post-quantum requirements:

• RFC 9958: Post-Quantum Cryptography for Engineers: Published by the PQUIP working group, this document outlines operational guidance, performance trade-offs, and algorithm selection criteria for constrained network stacks.
• draft-ietf-pquip-pqc-hsm-constrained: Addresses physical hardware resource limits, detailing how state, RAM, and NVRAM constraints in HSMs, smart cards, and embedded microcontrollers impact PQC key storage, processing times, and firmware updates.
• draft-rfcxml-pqc-key-fragmentation: Analyzes network-layer reassembly risks and provides recommendations to prevent buffer exhaustion and packet loss loops when transmitting fragmented PQC keys over low-power wireless networks (CoAP, DTLS, EDHOC, OSCORE).
• Compact and stateful signatures: Guidance on adopting stateful hash-based signature schemes (like LMS and XMSS defined in RFC 8554 / RFC 8708) to keep verification code and signature verification overhead lightweight enough for embedded bootloaders.

We have many problems, but actual computing performance isn't one of them. The modern lattice-based PQC algorithms, specifically ML-KEM and ML-DSA, are computationally fast. On modern x86 and ARM processors, lattice-based key generation, encapsulation, and decapsulation often execute in fewer CPU cycles than traditional ECDH or RSA exchanges. It's fortunate that we at least don't have to worry about this, except if we decide to switch to some other algorithms in the future.

Despite these structural hurdles, several empirical benchmarks argue that post-quantum TLS won't bring down the internet, and may even improve performance in places we least expect:

• Computational superiority cancels out bytes: Sosnowski et al. (ACM CoNEXT '23) demonstrated that because lattice-based primitives (ML-KEM) require drastically fewer CPU cycles than high-security classical curves or RSA, overall server throughput can actually increase under normal network conditions.
• Microcontrollers can actually run faster with PQC: Gillot, Buchanan, and Turino (arXiv:2610.27766) directly challenged the assumption that IoT hardware will buckle under PQC payloads. Testing dozens of TLS 1.3 configurations on constrained microcontrollers (such as the Raspberry Pi Pico W), they discovered that ML-KEM's low-cycle mathematical operations allowed post-quantum TLS handshakes to complete significantly faster (up to ~41% faster in benchmarks) than traditional classical handshakes, proving that embedded devices can comfortably run quantum-safe key exchange without collapsing.
• Payload amortization in real-world traffic: Research by Kampanakis & Childs-Klein (MADWeb '24) highlights that while PQC handshake latency grows in isolation, it becomes statistically negligible when evaluated against real-world Time-to-Last-Byte (TTLB) and typical HTTP payloads (>40 KB).
• Architectural fixes like KEMTLS: Research from Schwabe, Stebila, and Wiggers (ACM CCS '20) proves that authentication doesn't necessarily need multi-kilobyte signatures; replacing handshake signatures with KEMs (AuthKEM) keeps handshake byte footprints well within standard TCP window limits.