Signatures are the harder half of the post-quantum migration

Two migrations with different shapes

The post-quantum transition contains two engineering problems that are usually discussed together and behave differently.

Key establishment migration is a change between two consenting endpoints. Both upgrade, both negotiate, and the older option can be retired when telemetry says it is safe. For externally facing TLS this is now largely a configuration change with broad client support.

Signature migration is a change to an artefact that many parties verify, often without a channel back to them. A signed firmware image is verified by devices in the field. A code signature is verified by customer systems. A certificate is verified by every client. A signed document is verified years later by someone you have never met. In each case the signer can adopt a new scheme only when the verifiers can accept it—and some verifiers cannot be updated at all.

That asymmetry, rather than any property of the algorithms, is why signing is the harder half.

The size numbers that drive decisions

The standardised post-quantum signature schemes are considerably larger than the classical schemes they replace, and the sizes are what force format and protocol decisions.

Approximate comparison, for orders of magnitude rather than exact figures:

Scheme	Public key	Signature
Elliptic-curve (Ed25519 / ECDSA P-256)	~32–64 bytes	~64 bytes
RSA-3072	~400 bytes	~384 bytes
Lattice-based (FIPS 204), common parameter set	~1.3 kB	~2.4 kB
Stateless hash-based (FIPS 205), small-signature variants	~32–64 bytes	~7–30 kB
Stateful hash-based (LMS)	~60 bytes	~1–5 kB

Two observations follow immediately. The lattice-based standard is the general-purpose choice but is roughly forty times the signature size of an elliptic-curve signature. The hash-based schemes have small public keys—attractive where the key is stored in constrained immutable memory—but large signatures, and the stateless variant’s signatures are large enough to dominate small artefacts.

Computation is rarely the constraint. Verification for the lattice scheme is fast, and for hash-based schemes it is cheap by design. It is the bytes that break things.

Certificates are where size compounds

A TLS handshake does not carry one signature. It carries a certificate chain, each certificate containing a public key and a signature, plus a handshake signature, plus revocation or transparency material.

Replacing every classical signature and key in that chain with a lattice-based equivalent multiplies the handshake size several times over. A chain that was two kilobytes becomes ten or more, which crosses packet boundaries, adds round trips on lossy paths, and matters at scale.

This is why certificate migration is being approached with more care than the key exchange change was. The practical mitigations under discussion all reduce what has to travel: shorter chains, omitting intermediates the client already holds, compressing certificates, and separating the authentication of long-lived roots from the per-connection material. None of these is a pure configuration change, which is why NIST’s transition guidance allows a longer runway for signatures than the urgency of key establishment would suggest.

For internal PKI the constraint is softer, because you control both ends. It is worth measuring anyway: an internal service mesh with high connection churn may find handshake bandwidth becomes a visible cost.

Firmware headers were sized for classical keys

The sharpest instance of the size problem is in devices. A firmware image header is a fixed structure, often defined years ago, with a field sized for a specific signature. A bootloader in mask ROM or write-protected flash parses that structure and verifies that signature using a public key or key hash in immutable storage.

If the field is 64 bytes and the new signature is 2.4 kilobytes, the format cannot express it. If the immutable key storage holds a 32-byte hash and the verification routine only implements one algorithm, the device cannot verify the new scheme. Neither can be changed for units already manufactured.

The consequence is that every device currently in design is making a permanent decision. NIST SP 800-193 already argues for protection, detection and recovery in firmware; the post-quantum addition is to provision for algorithm change: a scheme identifier in the header, a generously sized signature field, space for a larger key or key hash, and a verification routine capable of dispatching on the identifier.

Hash-based signing is a particularly good fit here. Firmware signing produces few signatures, verification is cheap and simple to implement, the public key is small, and the state management burden for the stateful variants falls on the signing side where a hardware module can handle it properly.

Verifiers you cannot reach

Beyond devices, the recurring blocker is a verifier outside your control. The pattern is consistent across sectors:

• a customer’s build system verifying your code signature with a pinned key;
• a partner validating a signed message with a library version they choose;
• an operating system or app store that decides which signing algorithms it accepts;
• a regulator’s system that validates a submitted signature;
• a licensing client shipped to customers, with a public key compiled in.

For each of these the migration sequence is: the verifier must accept the new scheme before you can stop producing the old one, and typically must accept both for a period. That requires a communication channel, a version negotiation, or a dual-signature arrangement where the artefact carries both a classical and a post-quantum signature and each verifier uses what it understands.

Dual signing is the pragmatic answer in most of these cases, and it should be designed in now. It costs size and it makes the transition possible without a synchronised upgrade across parties you do not control.

Choosing among the standardised schemes

There is no single correct choice, and treating scheme selection as one organisational decision produces poor outcomes. Match the scheme to the use:

• General-purpose signing, size acceptable: the lattice-based standard. Fast, well analysed, the default for certificates and tokens.
• Firmware and boot verification: a stateful hash-based scheme. Small public key, conservative security assumptions, few signatures needed, state manageable in an HSM.
• Cases needing minimal assumptions with no state management: the stateless hash-based standard, accepting large signatures.
• Constrained links and small artefacts: measure first. The answer may be that no current scheme fits and the format or transport has to change.

The state requirement in stateful hash-based schemes deserves respect rather than avoidance. Reusing a one-time key breaks the scheme, so the signing side must track state reliably—which is a solved problem inside a hardware module with proper accounting, and a hazard in a distributed signing service. Firmware signing is well suited because it is centralised and low-volume.

Archives need validation, not migration

A signature applied to a document in 2018 cannot be migrated. The artefact exists, it is signed with what was available, and the question is whether someone in 2040 can still establish that it was validly signed when it was signed.

This is a long-term validation problem rather than an algorithm problem, and the established answer is archival: timestamp the signature with a trusted authority, and periodically re-attest the archive—adding a fresh timestamp or an enveloping signature with current algorithms before the existing ones are considered weak. The chain of timestamps carries the original validity forward.

Organisations with decades-long retention obligations for signed material should treat this as a distinct workstream with its own owner. It is not solved by adopting a new signing algorithm for new documents, and discovering the gap when an old signature is challenged is the expensive path.