Desiderata.

Certificate chain size in PQ TLS

A post-quantum certificate chain costs roughly five times what a classical one costs, on every connection. Compression recovers a fraction. Nothing that closes the gap is deployed.

Why it is not solved

Certificate compression (RFC 8879) is shipped and does help, but it works by squeezing redundancy out of the chain, and an ML-DSA signature is close to incompressible — the bytes are high-entropy by construction. The chain is large because the signatures are large, and compression cannot argue with that. For the sizes involved, see compatibility.

Why Merkle trees are not enough

An inclusion proof only shrinks the chain for certificates the tree covers. That requires a participating CA, a relying party that tracks recent tree heads, and a certificate young enough to appear in one. Everything outside that set — private PKI, offline verification, long-lived certificates, anything issued between publications — still needs a full chain. So the fallback path has to be kept, and it remains exactly the size it always was. Merkle Tree Certificates narrow the common case; they do not remove the requirement, and a design that must carry both paths is not obviously cheaper than one that carries one.

What would close it

Three lines of work, none of them deployed, and they are not moving at the same speed. Merkle Tree Certificates, which replace the per-connection chain with an inclusion proof, have been adopted by the IETF PLANTS working group. Trust anchor negotiation, which lets a client say which roots it holds so the server can send the shortest chain that will verify, is an active TLS working-group draft. Abridged certificates, which ship a shared dictionary of known intermediates so they need not be transmitted at all, stalled: the draft expired at revision 02 and has no successor.

The motion is real even though the deploy axis is not. Cloudflare and Chrome have run a Merkle Tree Certificate feasibility experiment against live traffic; Chrome has named the design its preferred path for post-quantum certificates on the public web; and Let's Encrypt committed to it on 3 June 2026, targeting a staging environment that issues Merkle Tree Certificates before the end of that year and production in 2027. None of that is something you can put in front of a browser today, which is why deploy reads none — but this is a gap being worked, not merely described.

watch draft-ietf-plants-merkle-tree-certs · draft-ietf-tls-trust-anchor-ids · draft-ietf-tls-cert-abridge (expired) verified 2026-08-09

ClientHello past the first packet

A hybrid key share pushes the ClientHello beyond a single segment. The protocol has always permitted that; a long tail of deployed middleboxes disagrees.

Why it is not solved

X25519MLKEM768 carries a 1,184-byte ML-KEM encapsulation key beside a 32-byte X25519 share, which takes the ClientHello past the payload of one TCP segment. Nothing in TLS 1.3 forbids this. But firewalls, WAFs, and load balancers written against an assumption that the ClientHello arrives whole in the first segment — an assumption that held for twenty years and is now false — drop or stall the connection. The failure mode is the unhelpful kind: a hang or a reset at setup, on a path the client cannot see and the server never hears about.

What would close it

Nothing in the protocol. The fix is replacing or reconfiguring the offending appliance, so this one closes on a hardware refresh cycle rather than a standards cycle. Most of the tail was driven out by large deployments enabling hybrid by default and absorbing the breakage reports; what remains is disproportionately enterprise inspection appliances and older embedded stacks.

It is listed here despite being nearly closed, because it is the clearest worked example of a gap that closed by attrition rather than by agreement — which is also how certificate requests will have to close.

watch RFC 8446 · middlebox behaviour verified 2026-08-08

Certificate requests with PQ keys

PKCS#10 encodes post-quantum keys without modification. The trouble is that a request which used to be 500 bytes is now roughly seven thousand, and the pipe it travels through was sized for 500.

Why it is not solved

Proof of possession requires the request to be self-signed by the key being certified, so both the public key and a full signature land in the same object. For ML-DSA-87 that is a 2,592-byte key plus a 4,627-byte signature: 7,219 bytes of payload before DER framing, a subject name, or a single attribute, against roughly 500 bytes for a whole P-256 request.

Transports sized for the old number break in unglamorous ways. SCEP's GET path carries the request base64-encoded inside a URL — RFC 8894 requires POST wherever the CA supports it, but the GET path is what a long tail of deployed clients and front ends actually speaks, and a 7 KB request base64-encoded into a URI meets HTTP 414 rather than a certificate. EST and several CA front ends impose request size caps. Embedded enrolment clients allocate fixed buffers. None of this is a cryptographic problem.

What would close it

Nothing exotic: raised limits, resized buffers, and CA front ends that accept an unrecognised algorithm in the subject public key info instead of rejecting the request outright. This entry is worth separating from the others precisely because it is not waiting on a standard. No draft will fix it, so it will resolve slowly, one deployed implementation at a time, and it will be the last thing to clear.

watch RFC 9881 · OID assignments verified 2026-08-09

Revocation at post-quantum scale

Every revocation answer carries a signature, and post-quantum signatures are kilobytes. Revocation was already the least loved part of PKI; the constants just got considerably worse.

Why it is not solved

An OCSP response is mostly signature. Replace an ECDSA signature with ML-DSA-65 and the signature alone goes from about 70 bytes to 3,309, before the responder certificate is attached. Stapling then adds that to a handshake already carrying a post-quantum chain and a post-quantum key share. A CRL absorbs its signature once and so is barely affected — but CRL distribution at scale was never comfortable, and nothing about that improved.

What would close it

Short-lived certificates, which sidestep revocation rather than solving it, and which public TLS is converging on regardless as maximum lifetimes fall. Browser-side compressed revocation sets work well but are browser-proprietary and unavailable to private PKI — which is exactly where certificate lifetimes are longest and revocation matters most.

watch CA/Browser Forum Baseline Requirements · automated issuance verified 2026-08-08

Operating stateful hash-based signatures

LMS and XMSS are finished standards with good implementations and a failure mode that destroys the key. Signing twice from the same one-time leaf is not a degradation; it is a break.

Why it is not solved

A stateful scheme signs with a one-time key drawn from a finite tree, and the private state has to advance with every signature. Sign twice from one leaf and forgery becomes possible. That turns ordinary operational practice into a hazard: a restored backup, a warm standby that was never told it was standby, a VM snapshot, a signer that crashed before flushing state. Every one of those is a routine recovery action, and every one of them can reuse a leaf.

This is not an implementation defect to be fixed. It is inherent to the construction, which is why NIST SP 800-208 requires the state be held in hardware, and why CNSA 2.0 confines LMS and XMSS to firmware and software signing instead of general PKI.

What would close it

Nothing at the algorithm level — the constraint does not go away. What is missing is operational: state that survives failover inside the hardware boundary, and tooling that makes reuse structurally impossible rather than merely discouraged in a runbook. Until that is ordinary, stateful signatures stay confined to low-rate, high-value, tightly controlled signing, which is exactly where they are found.

watch RFC 8554 · RFC 8391 · SP 800-208 · algorithm guidance verified 2026-08-08

Hardware key protection for PQ algorithms

The algorithms are standardized, but the box you are meant to keep the key inside may not implement them, and the interface used to reach it is still catching up.

Why it is not solved

PKCS#11 is how most software reaches a hardware module, and post-quantum mechanisms arrived in it late. So even where a module supports ML-DSA in firmware, the application path to that support may be vendor-proprietary, which quietly undoes the portability that made PKCS#11 worth using. Larger keys and signatures also press on assumptions baked into older modules.

The sharper problem is validation. A module that gains post-quantum support in a firmware update does not thereby gain a validated certificate covering it. The same device can satisfy a validated-module requirement for its classical algorithms and fail it for the post-quantum ones — a distinction easy to miss when procurement sees one certificate number and one product name.

What would close it

Three things moving together: firmware across the installed base rather than the current model line, PKCS#11 post-quantum mechanisms implemented consistently enough to be portable, and validation certificates that name the post-quantum algorithms explicitly. The installed base is the slowest of the three, and it is the one that decides when this is actually finished.

watch NIST CMVP · HSM support verified 2026-08-08

Algorithm agility and composite signatures

A certificate commits to one algorithm for its whole life. Migration therefore means reissuing everything, and the encoding that would carry two algorithms in one credential is approved but unimplemented.

Why it is not solved

A composite signature binds a classical and a post-quantum algorithm into one credential, so a break in either leaves the other standing. The encoding has cleared IETF review and sits in the RFC Editor queue, which settles the format but ships nothing: mainstream tooling still does not implement it. OpenSSL 4.0 (14 April 2026) adds no composite algorithm, and neither did the 3.x line before it, so the algorithm strings that look plausible in configuration examples are simply invented. See composite signatures for what that means in practice.

The transition has already done its own interop damage. Pre-standard names and parameter sets are not interchangeable with the FIPS ones despite resembling them closely, so keys generated under the older names do not verify under the new — a failure that presents as a configuration problem and is not one.

What would close it

The composite encoding published and implemented, and then the harder half: certificate profiles and relying-party software that can be taught to accept a new algorithm without reissuing the trust anchor. Agility is usually discussed as a property of algorithms. In deployment it is a property of the verifier, which is the component nobody issuing certificates controls.

watch draft-ietf-lamps-pq-composite-sigs · algorithm naming verified 2026-08-09

Long-term signature validity

A signature made today may need to be checked in 2050. Post-quantum algorithms fix the mathematics and leave the harder half — proving when the signature was made — much as it was.

Why it is not solved

Long-term validation rests on trusted timestamps and on evidence records that periodically re-protect an archive before its algorithms weaken. Both mechanisms are specified, and both are, in the deployed world, signed classically — so an archive intended to outlive RSA is held together by RSA. Re-timestamping under a post-quantum algorithm works in principle, but the timestamp authorities, the archive formats, and the validation software all have to move together, and they are owned by different people with different incentives.

What would close it

Timestamp authorities that sign with post-quantum algorithms, evidence-record and advanced-signature profiles that name them, and validation software that accepts them without special configuration. Document signing feels this first, because it is the one setting where the verification event is routinely expected decades after the signing event, and where nobody gets to reissue.

watch RFC 3161 · RFC 4998 · signature guidance verified 2026-08-08