Certificates and PKI Under Post-Quantum: Signature Bloat and Chain Strategies

The key-exchange article showed a handshake growing by about a kilobyte. The certificate story is worse, because a chain carries not one signature but several — the leaf signed by an intermediate, the intermediate by a root, plus the handshake signature that proves possession of the leaf key — and post-quantum signatures are tens of times larger than the classical ones they replace. Multiplying a large per-signature cost by several signatures makes the authentication half of the handshake the dominant bloat. Yet this migration carries a subtlety that softens the urgency: authentication is needed only at the moment of use, so it does not face the store-now-attack-later threat that makes key exchange pressing. This article quantifies the bloat and surveys the strategies for living with it.

Where signatures live

A TLS authentication involves a small hierarchy of signatures. At the top sits a root certificate authority whose public key is pre-distributed in trust stores, so its certificate need not be sent on the wire. Below it, one or more intermediate authorities each hold a certificate signed by the authority above, and these are transmitted. At the bottom is the leaf certificate identifying the server, signed by the intermediate. Finally, during the handshake the server produces a fresh signature over the transcript with its leaf private key, proving it actually holds the key the leaf certificate names.

So the wire carries, at minimum, the intermediate and leaf certificates — each containing a public key and the signature over it — plus the handshake signature. That is typically two to four signatures and their accompanying public keys transmitted per handshake, and additional signed objects such as certificate-transparency proofs or revocation staples can add more. Each of these is a place where a classical signature of tens of bytes becomes a post-quantum signature of kilobytes.

The root's exemption is the one structural relief: because trust anchors are pre-installed, their signatures and keys do not travel, so only the chain below the root contributes to handshake size. This is why strategies that shrink or eliminate the transmitted intermediates are so valuable, and why the leaf and the handshake signature, which cannot be pre-distributed, are the unavoidable core of the cost.

The bloat, quantified

The size gap is stark. A classical elliptic-curve signature is on the order of sixty-four bytes with a thirty-two-byte public key; the recommended post-quantum lattice signature is over three kilobytes with a roughly two-kilobyte public key, and the conservative hash-only signature is larger still. The table gathers representative figures. Multiplying across the two-to-four signatures and public keys in a transmitted chain, a certificate exchange that was around four kilobytes classically becomes tens of kilobytes post-quantum, and can reach the high tens of kilobytes with the hash-only scheme.

That size lands at a costly point in the connection. The certificate flight arrives early, when the congestion window is small, so a chain that no longer fits in the initial burst incurs extra network round trips before the handshake completes, adding latency on top of bytes. The bloat is therefore not merely a bandwidth line item but a latency multiplier, felt most on the first connection to a server and on high-latency paths where extra round trips hurt most.

Verification cost, by contrast, is not the bottleneck: post-quantum signature verification is fast, comparable to or better than the classical schemes. The problem is squarely the wire size of the signatures and public keys, which is why every mitigation targets bytes transmitted rather than computation. Naming the bottleneck precisely — transmitted signature bytes in the early flight — is what points at the right strategies.

The urgency asymmetry

A crucial insight reduces the pressure on this migration relative to key exchange: authentication is a here-and-now property. A signature verified during a handshake only needs the signature scheme to be unforgeable at that moment. An attacker who records the handshake and later, once a quantum computer exists, breaks the signature scheme gains nothing — the connection is long over, and a forged signature on an old transcript authenticates nothing. There is no store-now, attack-later value in a past authentication.

Key exchange is the opposite. A recorded encrypted session can be decrypted years later if the key exchange falls to a future quantum computer, so confidentiality must be protected today against tomorrow's attacker — the harvest-now-decrypt-later threat that makes the key-encapsulation migration genuinely urgent. This asymmetry means the two halves of the handshake have different clocks: confidentiality is racing the quantum timeline now, while authentication must be quantum-safe only before quantum computers actually arrive, not before they might be built.

The practical consequence is a sensible sequencing. Deploy hybrid post-quantum key exchange first, because it addresses the threat that is already accruing; migrate signatures and the public-key infrastructure on a more measured schedule, ahead of the arrival of quantum capability but without the same immediacy. The one exception is long-lived trust roots and any signature whose validity must be relied upon far into the future, which should move earlier because their unforgeability must hold across the quantum transition.

Strategies for the bloat

Several strategies cut the transmitted size. The most direct choice is between pure and composite certificates. A pure post-quantum certificate replaces every signature and key with a post-quantum one — simple but maximally large. A composite certificate carries both a classical and a post-quantum key and signature together, so it is even larger on the wire but provides assumption diversity and backward-compatible verification during the transition, letting old and new verifiers each use the algorithm they understand. The choice trades size against transitional compatibility and hedging.

Orthogonally, the number of transmitted signatures can be reduced. Suppressing intermediate certificates that the client already has cached avoids retransmitting them, and mechanisms that let a client signal which intermediates it holds turn a multi-certificate flight into a shorter one. More aggressively, the handshake signature itself can be eliminated by authenticating with a key-encapsulation mechanism instead of a signature — a design that proves key possession through decapsulation rather than a signature over the transcript, removing one large signature entirely. Newer certificate structures based on hash trees also compress the authority-signature overhead for large populations of certificates.

These are complementary rather than exclusive. A deployment might use composite certificates for diversity, suppress cached intermediates to shrink the flight, and adopt certificate-transparency and revocation mechanisms sized for the new reality. The unifying goal is to reduce transmitted signature bytes in the early flight, and each technique chips at that from a different angle.

Recommendations and the mutual-auth case

The pragmatic posture sequences the work by urgency and manages the bloat by strategy. Migrate key exchange to hybrid now; plan signature and public-key-infrastructure migration ahead of quantum arrival, moving long-lived trust roots earlier than short-lived leaf certificates. Prefer the recommended lattice signature for general certificate use because of its balanced size, reserve the conservative hash-only signature for durable trust anchors, and use composite certificates where transitional compatibility and assumption diversity justify the extra bytes. Reduce transmitted signatures wherever the ecosystem supports it.

The costs compound in mutual authentication, where both parties present certificate chains. A mutually authenticated connection carries two full chains and two handshake signatures, so the bloat roughly doubles, and the strategies above matter correspondingly more. Service-to-service communication that uses mutual authentication is therefore where certificate size pressure is most acute, and where suppressing cached intermediates and choosing balanced signatures pays off twice.

For autonomous AI systems this is precisely the common case. Agent service meshes typically use mutual authentication between services, so every connection carries two post-quantum chains, and agent-identity certificates multiply across a large fleet. Model-artifact signing chains, meant to remain verifiable for years, are the place to apply the conservative hash-only signature and to migrate earlier because their validity must outlast the transition. The guidance is to treat key-exchange migration as urgent and universal, signature migration as important and scheduled, mutual-authentication meshes as the size-sensitive hotspot, and durable artifact-signing roots as the one authentication case that shares key exchange's urgency.

Practitioner Toolkit

Copy-paste, strictly defensive artifacts you can use today. Nothing here attacks a real system.

pqc_pki_migration:
  key_exchange: migrate_now       # harvest-now-decrypt-later
  signatures: scheduled_before_quantum
  trust_roots: migrate_early      # long-lived, must outlast transition
certificate_strategy:
  general: ml_dsa
  durable_anchor: slh_dsa
  transition: composite_optional
  intermediates: suppress_if_cached
mutual_auth:
  size_budget: doubled

Glossary

Certificate chain

The sequence of certificates from a leaf up toward a trust anchor; the transmitted intermediate and leaf each carry a public key and a signature.

CertificateVerify

The handshake signature by which a server proves possession of its leaf private key over the transcript.

Trust anchor exemption

Because root public keys are pre-distributed, their certificates need not be transmitted, so only the chain below the root contributes to handshake size.

Composite certificate

A certificate carrying both a classical and a post-quantum key and signature, giving assumption diversity and backward-compatible verification at extra size.

Intermediate suppression

Avoiding retransmission of intermediate certificates the client already caches, shortening the certificate flight.

KEM-based authentication

Proving key possession via decapsulation instead of a signature over the transcript, removing one large handshake signature.

References

1. NIST IR 8547, Transition to Post-Quantum Cryptography Standards (2024)
2. IETF draft-ietf-tls-hybrid-design, Hybrid Key Exchange in TLS 1.3
3. NIST FIPS 204, Module-Lattice-Based Digital Signature Standard (2024)
4. NIST FIPS 205, Stateless Hash-Based Digital Signature Standard (2024)
5. RFC 9180, Hybrid Public Key Encryption (HPKE)