PKI & Certificate Impact

Post-quantum keys and signatures are far larger than their classical counterparts, and that single fact ripples through every layer of a public-key infrastructure — certificate sizes, chain lengths, protocol buffers, and the slow business of distributing new trust anchors.

Why PKI is the hardest part

Certificates bind identities to public keys using signatures, and they chain up to root CAs whose public keys are baked into trust stores everywhere — browsers, operating systems, devices, and embedded firmware. Migrating PKI means re-issuing certificates with PQC or composite keys and getting new roots into all those trust stores. Trust-store distribution takes years, which is why root and intermediate CA migration is the longest pole in most migration plans.

The size blowup

PQC public keys, signatures, and KEM ciphertexts are much larger than RSA/ECC equivalents — often by an order of magnitude or more. A certificate carries a public key and a signature; a chain carries several certificates. The cumulative effect:

• Bigger certificates. Each cert grows with both its embedded key and the issuer's signature.
• Bigger chains. A classical certificate chain is typically a few KB; a PQC or composite certificate chain can grow to tens of KB.
• Buffer and MTU limits. Handshake messages may exceed fixed buffers or fragment across packets, breaking assumptions in firmware, embedded TLS stacks, and middleboxes.

The practical responses: keep chains short, prune unnecessary intermediates, and test that every consumer (load balancers, embedded clients, middleboxes) tolerates the larger handshakes.

Composite and hybrid certificates

During the transition, CAs can issue certificates that carry both a classical and a PQC key/signature. A composite certificate binds the two so verification succeeds only if both verify — the same dual-assurance idea as hybrid key exchange (see Hybrid Cryptography). A composite certificate binds classical and PQC material into a single certificate structure, but it generally requires verifiers to support the new algorithm identifiers and encoding formats; for legacy systems that do not support PQC or composite formats at all, dual certificates or parallel certificate chains may still be needed. The cost is, again, size: a composite cert carries two of everything.

CA hierarchy migration

• Roots and intermediates must become PQC-capable. A leaf certificate's post-quantum authentication strength depends on the security of every signature and key in the chain above it; if an upper-level CA still relies entirely on RSA/ECDSA, the whole chain retains a quantum-vulnerable link.
• Trust stores propagate slowly. New roots must reach every browser, OS, and device — a multi-year process gated by update cadences you do not control.
• Plan parallel hierarchies. Run classical and PQC/composite hierarchies side by side, migrating leaves and revoking legacy on a schedule.

Alternatives under exploration

• Shorter chains to limit cumulative size.
• Merkle-tree certificates that amortize signature cost across many certs.
• KEMTLS — a handshake design that authenticates using long-term KEM keys instead of signatures, reducing the signature bytes on the wire.

For certificate format and field details, see X.509.

Standards & references

• RFC 9794 — PQ/T hybrid terminology underpinning composite certificates.
• NIST PQC project — the standardized signature and KEM algorithms used in certs.
• NCCoE SP 1800-38 — migration practice guide covering PKI and trust stores.
• Resources — full standards register