up:: Migration Architecture MOC

PQC Performance and Size Overhead

PQC performance and size overhead is the set of costs a system pays when it turns on post-quantum cryptography, and the load-bearing fact is that the cost is size rather than speed, because the new keys, ciphertexts, and signatures are far larger than the elliptic-curve artifacts they replace while the algorithms themselves run at competitive speed.

A single ML-DSA signature is 2,420 bytes where an ECDSA signature is about 64 bytes, and a hybrid TLS client’s first message jumps from 32 bytes of key material to over a kilobyte. Those bytes are what ripple through the real world, inflating handshakes past packet boundaries old middleboxes assumed would never move, growing certificates and stored keys, and stressing bandwidth on constrained links, which is why the honest framing of “what breaks in production” is a bandwidth-and-buffer problem rather than a compute one.

The short version:

1. The cost is size rather than speed. On modern hardware ML-KEM and ML-DSA are competitive with or faster than the elliptic-curve code they replace, so the binding limit is the size of the artifacts.
2. Post-quantum keys, ciphertexts, and signatures are one to two orders of magnitude larger than elliptic-curve ones, which is the root of every downstream effect.
3. In TLS the ML-KEM key pushes the ClientHello over a kilobyte, past the single-packet boundary decades of middleboxes assumed, and some old gear drops the larger handshake even when both endpoints support it.
4. Signatures are the hardest part, because they appear in every certificate and every signed message, and SLH-DSA signatures run from 7,856 bytes to 49,856 bytes.
5. The production symptoms are handshake failures on specific network paths, packet fragmentation, larger certificate chains, and buffer pressure on constrained devices, not slow cryptographic math.

Think of it like switching from mailing a single index card to mailing a thick booklet through a postal system built around thin envelopes. Writing the booklet takes about the same time as writing the card, so the desk clerk isn’t the bottleneck. The trouble starts at the sorting machines along the route, the ones with a slot sized for thin envelopes, because a few of them jam on anything fatter even though the sender and recipient are perfectly happy with the booklet. The pen was never the problem. The width of the mail, running through equipment that assumed mail stays thin, is the whole story, and post-quantum cryptography is the same shape.

Is post-quantum cryptography slow?

Usually no, and this is the most persistent wrong assumption about the transition. On modern processors the standardized lattice algorithms are competitive with or faster than the elliptic-curve operations they replace, so raw cryptographic speed is rarely what stops a deployment. NIST selected ML-KEM and ML-DSA partly for exactly this efficiency, and independent benchmarking on the community’s SUPERCOP suite confirms that key generation, encapsulation, and verification for these schemes run fast on general-purpose hardware.

Source: D. J. Bernstein and T. Lange, “eBACS: ECRYPT Benchmarking of Cryptographic Systems,” SUPERCOP, bench.cr.yp.to.

The place speed does show up is a narrow one: SLH-DSA signing is genuinely slow relative to lattice signatures, because it builds a signature from many hash computations, which is the tradeoff for its conservative hash-only security. But that’s a specific algorithm’s signing cost, not a property of the transition, and it’s chosen deliberately for roles that sign rarely. For the mainstream key-establishment and signature work, the reframe holds: the algorithms are fast, and what a system actually pays is the price of moving much larger artifacts.

Why are post-quantum keys and signatures so much bigger?

Because post-quantum security comes from mathematical structures whose hard problems need large objects to express, where elliptic-curve security packed enormous strength into tiny points on a curve. An elliptic-curve public key is a single point, representable in 32 bytes, and an ECDSA signature is about 64 bytes, which is why classical public-key artifacts fit in a single small network frame. Lattice keys and signatures are vectors and matrices over a modular ring, and hash-based signatures are trees of hash outputs, so both run from roughly a kilobyte to tens of kilobytes. The post-quantum size table below is drawn verbatim from the NIST standards; the classical baselines are the X25519 32-byte key from RFC 7748 and the ECDSA figures from FIPS 186-5, where a P-256 signature is 64 bytes (the pair r and s at 32 bytes each) and an uncompressed P-256 public-key point is 65 bytes.

Source: NIST, “Digital Signature Standard (DSS),” FIPS 186-5, February 2023, FIPS 186-5; X25519 key size per RFC 7748, RFC 7748.

Artifact	Classical	Post-quantum (NIST default)	Growth
KEM / key-exchange public key	X25519 public key, 32 bytes	ML-KEM-768 encapsulation key, 1,184 bytes	~37x
KEM ciphertext	(ECDH has no ciphertext, 32-byte share)	ML-KEM-768 ciphertext, 1,088 bytes	~34x vs the share
Signature (lattice)	ECDSA signature, ~64 bytes	ML-DSA-65 signature, 3,309 bytes	~52x
Signature (hash-based, smallest)	ECDSA signature, ~64 bytes	SLH-DSA-128s signature, 7,856 bytes	~123x
Signature (hash-based, largest)	ECDSA signature, ~64 bytes	SLH-DSA-256f signature, 49,856 bytes	~779x
Signature public key (lattice)	ECDSA public key, ~64 bytes	ML-DSA-65 public key, 1,952 bytes	~30x

Sources: NIST FIPS 203 Table 3, FIPS 204 Table 2, FIPS 205 Table 2, August 2024, FIPS 203, FIPS 204, FIPS 205.

Source: A. Langley, M. Hamburg, S. Turner, “Elliptic Curves for Security,” RFC 7748, January 2016 (Curve25519 public keys are 32 bytes), RFC 7748.

The pattern to hold onto is that key establishment is the manageable case and signatures are the hard case. ML-KEM artifacts are around a kilobyte, which most links carry, while signatures appear in every certificate and every signed message, so their larger sizes multiply across a certificate chain and a busy protocol. This is why so much of the applied migration effort concentrates on where signatures live.

What breaks in production when you turn on PQC?

What breaks is rarely the cryptography and usually the infrastructure around it, because the larger artifacts collide with assumptions old systems baked in about how big a handshake or a certificate could ever be. The failure modes are concrete and they cluster around size.

1. The oversized ClientHello. In hybrid TLS, the client’s X25519MLKEM768 key share is 1,216 bytes, made of the 1,184-byte ML-KEM-768 encapsulation key plus the 32-byte X25519 key, where a classical X25519 share was 32 bytes. That extra kilobyte lands in the very first message the client sends, pushing the ClientHello past the single-packet size that a long tail of middleboxes, load balancers, and inspection appliances assumed it would never exceed. Some of that older equipment mishandles or drops a ClientHello it can’t buffer, which surfaces as connection failures on specific network paths rather than a clean error.

Source: IETF, “Hybrid key exchange in TLS 1.3,” draft-ietf-tls-hybrid-design; the X25519MLKEM768 share sizes follow from the ML-KEM-768 encapsulation key (FIPS 203) plus a 32-byte X25519 key, TLS hybrid design draft.

2. Packet fragmentation. A message too large for one packet is split across two or more, and protocols or middleboxes that quietly relied on single-packet handshakes can mishandle the fragments. On datagram protocols this is sharper, because there’s no stream to reassemble transparently.

3. Certificate and chain growth. Post-quantum certificates carry a larger public key and a larger signature, and a chain stacks several of them, so the total handshake payload grows well beyond the key-exchange line. This is the size effect that most stresses TLS at scale, since every connection carries the chain.

4. Bandwidth and buffer pressure on constrained links. On a low-power radio where a physical frame carries only about a hundred bytes of payload (the IEEE 802.15.4 standard behind Zigbee and Thread caps a frame at 127 bytes, leaving roughly 100 usable after headers), a kilobyte-scale key spans a dozen frames and a multi-kilobyte signature spans dozens, and the receiver has to buffer the whole artifact in limited RAM before it can act on it. This is the constrained-device version of the same size problem, and it’s where a deployment most often runs out of room.

The common thread is that two perfectly configured post-quantum endpoints can still fail because of a third box on the path, or a buffer that was sized for the classical world. The load-bearing production lesson is that a protocol is only as quantum-safe as its largest artifact can travel, so the migration’s hardest engineering is making the bigger objects survive the whole network path.

How do you manage the size overhead?

You manage it by treating the size as a network-engineering problem and choosing algorithms and parameters for fit, rather than trying to make the artifacts small enough to pretend nothing changed. The moves that matter are educational to understand even where the specific tuning belongs to a given estate.

1. Choose the parameter set for the role. ML-KEM fits most key-establishment paths comfortably. For signatures the choice trades signature size against public-key size and implementation safety, so a rarely-signing firmware root can accept a large SLH-DSA signature for its 32-byte public key, while a high-volume protocol wants the compact lattice signatures instead.
2. Test the whole path end to end. Because the failures come from middleboxes and buffers between the endpoints, verification runs on real traffic across real network routes, which is why testing and interoperability carry more weight in a PQC migration than in a classical one.
3. Use the protocol’s escape hatches. Hybrid TLS allows a client to advertise a hybrid group with a small classical share and let the server request the full hybrid share on a second round trip, trading one round trip for surviving the middleboxes, which is a direct answer to the oversized-ClientHello problem.

The framing that keeps this tractable is that the overhead is real, bounded, and mostly a one-time integration cost. The bytes don’t get smaller, but a system engineered to carry them, with the right parameters for each role and a tested path end to end, absorbs the overhead and keeps running. The implementation pitfalls that actually sink deployments are usually the size effects going untested, not the cryptography being slow.

Common misconceptions

1. “Post-quantum cryptography is too slow to deploy.” On modern hardware the mainstream lattice schemes are competitive with or faster than elliptic-curve code. The binding cost is the size of the keys, ciphertexts, and signatures, so the challenge is bandwidth and buffers, not clock cycles.
2. “The overhead is a constant tax on every operation.” It’s mostly a one-time integration cost of making infrastructure carry larger artifacts. Once the path is engineered for the bigger objects, the ongoing cost is bandwidth, not a recurring slowdown in the math.
3. “If both endpoints support PQC, it’ll just work.” A third device on the path, a middlebox or load balancer sized for classical handshakes, can drop the larger message even when both endpoints are fine. The size problem lives in the network between the endpoints, not in the endpoints alone.
4. “Bigger keys make the algorithm stronger, so the size is the point.” The size comes from the mathematical structure the security rests on, not from a security dial you can turn down. You choose the parameter set for the security level and then engineer the path to carry whatever size that level requires.
5. “Signatures and key exchange have the same overhead.” Key establishment with ML-KEM is the manageable case at around a kilobyte. Signatures are the hard case, because they appear in every certificate and signed message, and the hash-based ones run to tens of kilobytes.

Questions people ask

Is post-quantum cryptography slower than what we use now? For mainstream key establishment and signatures, no. ML-KEM and ML-DSA run at competitive or better speed on modern hardware. The one slow spot is SLH-DSA signing, which is chosen deliberately for roles that sign rarely.

Why is the ClientHello suddenly too big? Because the hybrid key share carries an ML-KEM-768 encapsulation key of 1,184 bytes on top of the 32-byte X25519 key, so the client’s first message jumps from 32 bytes of key material to 1,216 and crosses the single-packet boundary that older middleboxes assumed it never would.

How much bigger are post-quantum signatures? A lot. An ECDSA signature is about 64 bytes, ML-DSA-65 is 3,309 bytes, and SLH-DSA runs from 7,856 bytes at its smallest to 49,856 at its largest. Signatures are where the size overhead bites hardest, because they appear in every certificate and signed message.

What actually fails in production? Handshakes on specific network paths where a middlebox can’t buffer the larger message, packet fragmentation, larger certificate chains, and buffer pressure on constrained devices. The cryptography works; the infrastructure sized for smaller artifacts is what breaks.

Can I make the post-quantum artifacts smaller? Not below what the security level requires, because the size comes from the underlying math. You choose the algorithm and parameter set that fit each role, use protocol escape hatches like the hybrid HelloRetryRequest, and engineer the network path to carry the size.

Do I need to worry about performance for internal, high-bandwidth links? Less so. On a fast wired network with modern gear, the extra kilobytes are easily absorbed and the fast algorithms keep latency low. The overhead bites hardest on constrained links, old middleboxes, and datagram protocols, so those are where testing concentrates.

Which is the bigger problem, ML-KEM’s size or ML-DSA’s? Both matter, but signatures usually dominate the total, because ML-DSA and the certificate signatures appear in every connection and stack across a chain, while an ML-KEM key appears once per handshake. Sizing the signature footprint is often the harder engineering call.

---

Everything here is the map, given freely. When your team needs its protocols and links profiled for the exact size overhead each will carry, the middlebox and constrained-device failure points found before rollout, and the parameter choices matched to each role, that’s the work I do. Request an alignment briefing.

Last verified 2026-07-14 · Maintained by Addie LaMarr, LaMarr Labs.