Quantum Implications for PKI

Quantum computing keeps surfacing in board conversations, vendor pitches, and now federal deadlines, and it’s putting Public Key Infrastructure (PKI) teams in the same spot: is our PKI quantum ready? That question is aimed at the wrong clock. Nobody can say when a quantum computer capable of breaking RSA (Rivest-Shamir-Adleman) and Elliptic Curve Cryptography (ECC) will exist. What you can measure today is how long your own migration will take, and for most enterprises that number is longer than expected. Quantum risk isn’t a 2035 problem you can defer. It’s a 2026 problem, because that’s when the clock has to start for federal deadlines, certificate lifetime changes, and Hardware Security Module (HSM) upgrade cycles.

The risk doesn’t land the same way everywhere. The deadlines reach further into the private sector than most PKI teams expect, and the exposure differs across internal certificate authorities (CAs), public Transport Layer Security (TLS) certificates, and the HSMs underneath both. Separating what’s urgent from what’s overstated makes the case for the first move in quantum readiness: a cryptographic bill of materials.

Two threat clocks matter for PKI, and they run on different timelines. Harvest now, decrypt later is already live: traffic recorded today can be decrypted once a capable quantum computer exists. Forged authentication needs that machine first, but carries the longest remediation chain, since every signing key and root of trust must be replaced. Mosca’s inequality holds both: if how long your data must stay confidential (X) plus how long your migration takes (Y) exceeds the time until such a machine exists (Z), you’re already behind. Our quantum readiness overview covers the X + Y > Z framing and the general primer, including why RSA and ECC fall to Shor’s algorithm.

The National Institute of Standards and Technology (NIST) determines when algorithms get retired, and NIST Internal Report (IR) 8547 is its post-quantum roadmap, still an initial public draft. It proposes disallowing RSA, elliptic-curve algorithms, and Diffie-Hellman key exchange after 2035, with 112-bit-strength instances such as RSA-2048 deprecated after 2030. Executive Order 14412, signed June 22, 2026, turned that guidance into binding federal deadlines: post-quantum key establishment on high-value and high-impact systems by December 31, 2030, and post-quantum digital signatures, the certificate side, by December 31, 2031. That second date is the one that falls on PKI.

Under a proposed Federal Acquisition Regulation (FAR) rule due in December 2026, covered federal contractors would have to comply by 2030 with the Federal Information Processing Standards (FIPS) that incorporate post-quantum cryptography (PQC), a year ahead of the agencies’ signature deadline. National Security Systems follow a separate National Security Agency track, the Commercial National Security Algorithm Suite 2.0 (CNSA 2.0), with deadlines between 2030 and 2033.

For most organizations, that pressure lands first on infrastructure nobody outside the security team sees: the CAs running internal systems, with no public root program watching. Sequencing is the core problem. A leaf can’t move to the Module-Lattice-Based Digital Signature Algorithm (ML-DSA) before its issuing CA does, and migrating the CA while the offline root still signs with RSA leaves the chain rooted in classical math anyway. The order runs root, then issuing CA, then leaf.

Internal roots complicate this by lasting 10 to 20 years. Rekeying one means the old root stays valid until everything issued under it expires, so one migration can span the old root’s remaining life. Nothing forces the issue the way it does for public TLS, so internal estates drift.

The advantage is a finite, known relying-party population you can inventory and test without coordinating with the whole internet. The estate is usually bigger than assumed: container and service mesh certificates, build-pipeline signing, and device certificates. Machine identities now outnumber human ones by roughly 109:1, according to Palo Alto Networks’ 2026 Identity Security Landscape survey, and in almost every assessment we run, the unmanaged certificate population is larger than the managed one.

Microsoft made ML-DSA generally available in Active Directory Certificate Services (AD CS) on Windows Server 2025 in May 2026. Plan 18 to 24 months from procurement to a steady-state internal CA, and longer across multiple forests: a 24-month multi-forest project that starts in 2029 finishes right at the 2031 deadline. AD CS supports pure ML-DSA only. Composite certificates are planned but not available, existing CAs can’t be converted in place, and Network Device Enrollment Service (NDES) enrollment isn’t supported, so AD CS estates need a parallel ML-DSA hierarchy and relying-party testing before committing production trust. Where a platform does support composite certificates, still an Internet Engineering Task Force (IETF) draft, pairing ML-DSA-65 with a classical signature protects without breaking services that don’t recognize it yet. Our PKI services and PKI Assessments cover hierarchy design and pilots.

Public TLS faces two problems at once. Certificate lifetimes are collapsing under CA/Browser Forum Ballot SC-081v3, approved April 11, 2025, shown below.

By the final phase, validation evidence expires faster than the certificate itself. Manual renewal isn’t viable anymore, which makes certificate lifecycle automation a prerequisite.

Post-quantum certificates are also physically larger. Our PQC Migration Guide puts a full ML-DSA-65 chain at roughly 14 to 15 KB added to the handshake, enough to approach or exceed a typical initial congestion window and add round trips, just as shorter lifetimes mean more handshakes. Benchmark against your own traffic first, for example in our Innovation Lab.

Key exchange already has a working answer: pair a classical algorithm with a post-quantum one. Cloudflare reported in August 2026 that over two-thirds of browser traffic to its network is protected this way. Authentication hasn’t caught up: it needs coordinated upgrades across clients, servers, CAs, and root stores, and publicly trusted post-quantum certificates aren’t issuable at scale yet.

Merkle Tree Certificates: The Emerging Path for Post-Quantum TLS

Google announced Merkle Tree Certificates in February 2026: instead of every certificate carrying its own signature, the CA signs one commitment covering millions of certificates, and each carries a compact proof as small as 736 bytes. As of October 2026, Chrome has named this its preferred path and is building a separate Quantum-resistant Root Store around it, and Let’s Encrypt targets staging in late 2026 and production in 2027.

This is emerging, not finalized. It’s still an active IETF draft, with no production issuance, and it only covers public Web PKI, not internal CAs, code signing, or device certificates. Don’t chase the spec. Get the estate into a state where a change this size is a configuration update, not a fire drill.

The HSM sets the pace for everything above it: a root CA can’t sign with ML-DSA until the HSM holding its key can do so inside a validated boundary. That validation runs in two NIST-run stages people routinely conflate. The Cryptographic Algorithm Validation Program (CAVP) confirms the algorithm math is correct; the Cryptographic Module Validation Program (CMVP) confirms the whole module meets FIPS 140-3, the actual bar for compliance. A vendor can truthfully say its HSM “supports ML-DSA” on CAVP alone while the module still sits in CMVP’s queue.

Several HSM vendors hold CAVP certification for ML-DSA, the Module-Lattice-Based Key-Encapsulation Mechanism (ML-KEM), and the Stateless Hash-Based Digital Signature Algorithm (SLH-DSA). Module-level validation is only starting to follow. Validations that put post-quantum algorithms inside the boundary began appearing in mid-2026, but as of October 2026 most mainstream platforms are still in the CMVP queue for FIPS 140-3 validation of their post-quantum firmware. Many of those modules already hold FIPS 140-3 validation on classical firmware, which is why the distinction matters: check module-level status for your exact model and firmware build on NIST’s Modules In Process list, not in the vendor’s announcement.

Firmware and code signing add one more constraint. Stateful hash-based signatures, Leighton-Micali Signature (LMS) and eXtended Merkle Signature Scheme (XMSS), are what CNSA 2.0 mandates for firmware signing, but each one-time key can sign exactly once. Signing state must therefore be enforced inside the HSM, because restoring a backup that rewinds that state breaks the scheme. If you can’t guarantee that, use SLH-DSA instead.

Bigger keys and signatures need re-tested storage and throughput assumptions, and firmware should land on a CMVP-validated build at least six months before any policy CA is expected to sign with ML-DSA. Offline root ceremonies happen once or twice a year, which is why root migration realistically slips to 2027 or 2028. There’s a second clock too: FIPS 140-2 certificates moved to NIST’s Historical list in September 2026. Existing deployments can keep running, but new purchases should specify FIPS 140-3, so roots on older HSMs need a replacement plan. Our HSM services cover firmware assessment and key ceremonies.

The estimates keep moving in one direction. Resource estimates for breaking RSA-2048 fell from 20 million qubits in 2019 to under a million by May 2025, then to roughly 11,000 to 14,000 in a March 2026 paper from Oratomic, Caltech, and UC Berkeley, a drop of nearly two orders of magnitude in under a year, on paper, with far longer runtimes. The same paper puts breaking ECC with a 256-bit key at a few days on about 26,000 qubits, which makes elliptic-curve hierarchies the earlier target for PKI. And supporting an algorithm isn’t the same as being protected by it: a system that negotiates ML-KEM but still accepts a classical-only handshake has “transitioned” in name only.

You cannot migrate cryptography you cannot see. A Cryptographic Bill of Materials (CBOM) is a structured, machine-readable inventory of cryptographic assets and how they relate, what a software bill of materials is to software components, not a spreadsheet of certificate expiry dates. A credible CBOM reaches five places, covered in our quantum readiness overview: network and protocol, certificates, code and dependencies, keys and hardware, and prioritization metadata. Certificates and keys and hardware are the PKI-relevant pair, so go deep there.

CBOM support is now built into OWASP CycloneDX 1.6, and Executive Order 14412 Section 5(d) directs the Cybersecurity and Infrastructure Security Agency (CISA) and NIST to publish minimum CBOM elements within 270 days of signing, roughly March 2027.

For certificates, discovery has to reconcile several sources at once: CA records, endpoint scans, configuration data, and application-owner input, including the unmanaged, self-signed certificates nobody remembers issuing. A scan of TLS endpoints is one slice of an inventory, not the inventory. For keys and hardware, catalog HSM partitions, key ceremonies, every root and issuing hierarchy, and every place private keys live. Prioritize by exposure and impact, public-facing systems first.

Cloudflare itself cautions against treating an exhaustive CBOM as a prerequisite, since it can consume a whole procurement cycle and go stale before it’s finished. Its alternative is a quantum impact inventory: what breaks if this is compromised, how likely, what can be done, in what order. Start with the most exposed systems and let the full CBOM fill in behind you. The same baseline makes the 47-day certificate schedule survivable.

Crypto agility doesn’t mean supporting every algorithm at once. It means that when the community converges on something better, the upgrade is a configuration change, not a re-architecture. The 47-day certificate schedule already demands it, and past algorithm deprecations forced the same scramble, each taking years because systems hardcoded their choices.

This isn’t one migration either. ML-KEM and ML-DSA are the current answer, not the final one, and SLH-DSA exists partly as a hedge in case lattice-based schemes are later weakened. Executive Order 14412 mandates specific algorithms and says nothing about building systems that can swap them again. Compliance and agility aren’t the same goal, and only one keeps paying.

The sequence matters: discover and assess the estate, protect internet-facing traffic with hybrid key exchange (right for the next few years, secure as long as either component holds, though not fully post-quantum), put PQC into procurement language, upgrade HSM firmware, migrate internal CAs (composite certificates where the platform supports them, a parallel ML-DSA hierarchy where it doesn’t), then code signing, secure email, and finally public TLS leaves once the CA/Browser Forum permits it. Internal CAs come first because you control both ends; public roots come last because you don’t control that timeline.

Realistically: discovery and procurement in 2026, HSM and internal CA migration 2026 to 2028, code signing and secure email 2027 to 2029, public TLS leaves closing it out 2029 to 2031.

In the five phases of our PQC Migration Guide, discovery and assessment are phases one and two, procurement, automation, and HSM firmware are phase three, hybrid and pilot hierarchies are phase four, and production CA, code-signing, and public TLS migration land in phase five.

Four things move this forward: start discovery on your most exposed systems, not everywhere at once. Automate certificate lifecycle management before you need it. Use tooling that already exists: OpenSSL 3.5 has supported ML-KEM and ML-DSA natively since April 2025. And identify your long-lived keys today (roots, code-signing keys, firmware keys), since they’re the slowest to change.

For organizations ready to start that sequence, a Quantum Readiness Assessment is the place to begin.