Rotate the root, slowly

When CISOs first scope a PQC PKI migration, the question they ask is "which algorithm goes at the root?". When they're three quarters in, the question becomes "how many certs did the old root sign?" and the answer is rarely complete. PKI migration is mostly the second question, in slow motion.

Why this takes quarters, not sprints

A PKI is a tree of trust. The root signs intermediates, the intermediates sign leaves, the leaves are presented by end-entities to relying parties who chain back to the root. Migrating the root algorithm doesn't break anything immediately — old leaves still work, old intermediates still work — but it doesn't fix anything either until the relying parties learn to trust the new root and every certificate has been re-signed under the new chain.

The work, ordered:

1. Stand up the new root with the PQC algorithm. SLH-DSA-256 for highest assurance; ML-DSA for shorter-lived roots.
2. Distribute the new root to every relying party (users, servers, devices, vendor systems) so it joins the trust store alongside the old one.
3. Cross-sign for continuity: issue a cross-certificate so relying parties that only know the old root can still chain leaves signed by the new chain through a path that ends at the old root.
4. Migrate intermediates under the new chain.
5. Re-issue end-entity certificates from the new intermediates as they expire (or sooner where forced).
6. Deprecate the old root once every leaf it signed has either expired or been re-issued under the new chain.

Step 2 is where every PKI migration discovers that its certificate inventory is incomplete. Step 5 is where it discovers that "every leaf the old root signed" includes the certificate baked into the vendor appliance nobody documented.

Algorithm per tier

Use different PQC algorithms at different tiers, matching lifetime to security assumption:

• Root: SLH-DSA-256. Validity measured in decades. Hash-only assumptions (see the SLH-DSA piece) justify the larger signature because the root is verified rarely and signed once.
• Issuing intermediates: SLH-DSA-128 or ML-DSA-65 depending on lifetime. 5–10 year intermediates can sit on ML-DSA-65 for the smaller signature; 10–20 year intermediates should consider SLH-DSA-128.
• TLS leaves: ML-DSA-44 or FN-DSA-512. Re-issued frequently, presented on every handshake, so signature size matters.
• mTLS client / device / token certs: ML-DSA-44.
• Code-signing leaves: SLH-DSA-128s where the signed artefact lives a decade; ML-DSA-65 otherwise.

The cross-sign question

The trust-distribution step is the longest-running operational task. Until every relying party trusts the new root, you cannot decommission the old one. Cross-signing is the bridge — you issue a cross-certificate that makes the new root's intermediates also chainable through the old root. Relying parties on the old trust store keep working; relying parties on the new one work too.

The cross-signing window is usually 18–36 months for an enterprise. Plan it explicitly:

• Year 1: new root deployed, old root still primary. New leaves issued from a new intermediate cross-signed by the old root.
• Year 2: trust stores converted progressively. New leaves chained directly through the new root where relying party supports it; through the old root via cross-sign where it doesn't.
• Year 3+: old root revoked. Cross-signed intermediates retired. Anything still chained through the old root fails — by design, after sufficient notice.

The hidden re-issuance work

Three categories that surprise every migration:

• Long-validity leaves. Certificates with 5–10 year validity, often issued for embedded systems or long-lived service accounts. They won't expire on their own in time. Plan forced re-issuance.
• Code-signed artefacts. A code-signing leaf cert that's been used to sign a hundred releases needs to be replaced — and the signatures on the old releases either re-signed under the new chain (best) or accepted as legacy-trusted via a timestamping authority (workable).
• Vendor appliances. Network gear, backup systems, monitoring servers — each shipped with a baked-in cert that chains to your old root. Each vendor's re-issuance process is bespoke. Discover them now, not at cutover.

What to do this quarter

If the PQC PKI migration hasn't started:

1. Inventory the leaves. Real number, not the estimate. Pull from the CA database; reconcile against certificate transparency logs for any public-facing certs; interview each application team.
2. Specify the new hierarchy. Algorithm per tier, key sizes, validity periods, naming conventions, cross-sign plan.
3. Run a small live re-issuance. Pick one application's leaves and re-issue them through the new chain. Surface the integration problems before they're a cross-organisation issue.

Start now even if migration to PQC at scale is two years out. The discovery and hierarchy decisions don't depend on timing; they take quarters to get right; and the cost of getting them wrong only shows up at cutover.