Marin Ivezic
An ECDSA P-256 signature is 64 bytes. The ML-DSA-65 signature that will replace it is 3,293 bytes, and the public key grows from 64 bytes to 1,952. Push that through a WebPKI certificate chain, where a browser checks a leaf certificate against one or two intermediates and a root, and a handshake carrying 3 to 5 KB of certificate data today carries several times that once every key and every signature in the chain is post-quantum.
Google and Cloudflare have both run that arithmetic and reached the same conclusion. Their answer, Merkle Tree Certificates, is a draft working its way through the IETF that replaces the chain of signatures with a compact inclusion proof against a published tree. Two of the largest operators of TLS on the internet decided the certificate format has to be rebuilt rather than resized.
The encryption half of the same migration looks nothing like that. Adding ML-KEM, the module-lattice key encapsulation mechanism standardized as FIPS 203, to a TLS handshake in hybrid mode costs about a kilobyte and a configuration change on servers you already run. Chrome and the major content delivery networks have been doing it in production since 2024.
We teach migration sequencing at Quantum Academy, and this is the point where architects most often rewrite their plan. The default order protects confidentiality first and defers signatures. The dependency structure of the work argues for the reverse.
Two migrations under one label
A post-quantum program usually appears on the roadmap as a single workstream. Underneath it sit two jobs with almost nothing in common operationally.
The first is key establishment, the negotiation that leaves two endpoints holding a shared secret they can encrypt a session with. Post-quantum, that job goes to ML-KEM, normally deployed next to a classical exchange so that neither algorithm has to be trusted on its own.
The second is digital signatures, the mechanism that lets a receiver confirm that a message, a certificate, a firmware image or a login token came from the party it claims to and hasn’t been altered since. Post-quantum, that job goes to ML-DSA for general use, standardized as FIPS 204, and to the hash-based schemes LMS, XMSS and SLH-DSA where the thing being signed is firmware or code.
Key establishment is ephemeral. It is negotiated fresh for every session, between two parties who are both present in the transaction at the time, and when it fails the connection falls back or drops and someone notices within seconds. Signatures are the opposite in every one of those respects. They are verified later, by parties you may never deal with directly, against public keys sitting in trust stores you don’t administer, over artifacts that can outlive the hardware they shipped on.
That distinction is the one we spend the most time on early in our post-quantum courses, because plans that blur it tend to schedule the hard half last.
The usual case for encryption first is Harvest Now, Decrypt Later, or HNDL: an adversary records encrypted traffic today and stores it until a machine capable of breaking the key exchange exists. The threat is real, and the response is a change you can make this quarter on infrastructure you control. The signature side needs years of dependency work before the equivalent change is even possible.
Sequence by who has to agree
Severity arguments are hard to act on, because everything in a security program is severe. The axis we use instead is dependency. For each place a signature is produced or verified, count the parties outside your organization who have to agree before the algorithm can change. That count predicts lead time better than anything else in the plan, and it sorts the work into four groups.
Firmware and software signing, where you own both ends
Zero external parties. You hold the signing key and you write the verification code that ships in your own products, so nothing stands between you and a new algorithm except your own release engineering.
This is also the group with the oldest standardized answer. NIST SP 800-208 approved the stateful hash-based signature schemes LMS and XMSS in 2020. Their security rests on hash functions rather than on the factoring and discrete logarithm problems that Shor’s algorithm attacks, which makes them a conservative choice for anything with a long verification horizon. The NSA’s Commercial National Security Algorithm Suite 2.0 (CNSA 2.0) names them for software and firmware signing.
Statefulness, in plain terms
LMS and XMSS build a signing key from a large but finite set of one-time keys arranged in a tree. Each signature consumes one of them, and the signer has to record which ones are spent. Sign twice with the same one-time key and the security guarantee is gone.
In practice that turns a cryptographic property into an operations problem. The index counter has to live inside the hardware security module alongside the key. Backups have to be handled so that restoring an old snapshot can never rewind the counter. Any high-availability design that puts the same key in two places needs a partition of the index space rather than a shared count. None of this is exotic for a team already running HSM-backed code signing, but it’s design work, and it is why we tell learners to pilot the state handling before committing to a date.
SLH-DSA, standardized as FIPS 205, avoids the state problem entirely and pays for it in size. Its smallest parameter set produces signatures of about 7.9 KB. For a firmware image measured in megabytes that trade is usually easy. For a bootloader with a signature slot fixed in the device design, it may not be available at all.
Private PKI, where you own the trust store
Also zero external parties, and often missed, because internal certificate authorities rarely appear in the same inventory as public ones. If you operate your own CA and you control the clients that trust it, you can issue ML-DSA certificates now. OpenSSL 3.5, used with the Open Quantum Safe (OQS) provider, supports ML-DSA, and several commercial CA products have added issuance.
We would treat the internal CA as the rehearsal space for everything the public migration will eventually demand. The failures show up quickly, and most of them are about size rather than cryptography. Certificate-based network access over EAP-TLS is the usual first casualty. A chain that fits comfortably in the fragment budget with ECDSA certificates stops fitting with ML-DSA, and the symptom that reaches the help desk is that laptops can’t join the wireless network. Embedded clients with fixed certificate buffers fail in a similar way. We would rather architects meet that on a pilot than in a change window.
Public WebPKI, where the parties are outside your control
Several external parties, in a sequence you cannot reorder. Before a publicly trusted ML-DSA certificate can be issued, the CA/Browser Forum has to amend its Baseline Requirements, certificate authorities have to build issuance, and browsers and operating systems have to ship verification. The encoding groundwork is done, since the IETF has published the X.509 algorithm identifiers for ML-DSA. The policy and deployment work has not started in earnest.
There is a precedent for how long this takes, and our reading of it is not encouraging. NIST began the deprecation of SHA-1 for digital signature generation in 2011. Browsers and the CA/Browser Forum spent the following years setting and then defending a sunset date, publicly trusted SHA-1 certificates were finally cut off at the start of 2017, and the SHAttered collision was published weeks after that. Six years to retire one hash function, for a replacement of identical size that required no protocol changes and no new certificate structure. ML-DSA is a larger key, a larger signature, and on the evidence of Merkle Tree Certificates quite possibly a different authentication design. Planning on a shorter timeline than SHA-1 got would be optimistic.
For public-facing TLS, then, the instruction is to track the standards work, keep the inventory current, and spend the engineering effort on the three groups you can actually move.
Identity federation, where the dependency is invisible
One or two parties, usually inside the building. Every SAML assertion, OIDC identity token and internally issued JWT carries a signature, most often RSA or ECDSA, produced by a key the identity provider holds and publishes for relying parties to fetch. Nothing about that key shows up in a TLS scan, which is why it is the layer we most often find missing from an inventory built by scanning.
The dependency sits with the relying parties. You can’t rotate the identity provider to a post-quantum algorithm until every application that validates its tokens can verify the new one, and in most enterprises that means a long list of libraries and vendor products. The work is not cryptographic; it is a survey, a set of vendor commitments and a coordinated cut-over. It also runs on calendar time and cannot be compressed by spending more.
The consequence side
Everything above is an argument from difficulty. There is a second argument, from consequence, and it points the same way.
When harvested traffic is eventually decrypted, an adversary learns what was said. The damage is bounded by what they captured, each session costs them separately, and forward secrecy limits how far any single recovered key reaches. It is retrospective, and it is expensive per unit.
A derived signing key works forward instead. Whoever holds it can produce artifacts that every downstream verifier accepts, at a time and a scale of their choosing. A code-signing key turns every update channel that trusts it into a distribution path. A certificate authority key allows certificates for any domain. A firmware signing key reaches devices that will keep accepting updates long after the vendor stops shipping them. An identity provider key mints tokens for any user, and no access control or audit trail downstream is in a position to object, because checking the signature was the control.
The resource estimates point the same direction. Roetteler, Naehrig, Svore and Lauter estimated in 2017 that breaking 256-bit elliptic curve discrete logarithms, the problem underneath ECDSA, needs roughly 2,330 logical qubits, against roughly 4,100 for factoring RSA-2048 in a comparable model. Both figures have come down since. Gidney’s 2025 analysis put RSA-2048 at 1,399 logical qubits, under a million noisy physical qubits and under a week of runtime. The ordering has held throughout. The elliptic curve signature algorithms the industry adopted for their small keys and fast verification are the cheaper target.
The industry already has a reference point for what the outcome looks like. The 2020 SolarWinds compromise reached roughly 18,000 organizations through a legitimately signed update, and the automated systems that installed it behaved correctly at every step. Getting there took months of stealthy access to a build pipeline, with the risk of detection that came with it. A signing key recovered by computation removes both.
What CNSA 2.0 already sequenced
The NSA’s CNSA 2.0 sets post-quantum requirements for US national security systems, and it doesn’t put every use case on one deadline. Software and firmware signing comes first, with LMS and XMSS available for immediate use. Web services, networking equipment and operating systems follow behind it.
The ordering is legible two ways. As a threat assessment, it names what the NSA expects to fail hardest. As an engineering judgment, it names what takes longest to fix. Both readings support the same plan.
For vendors selling into those environments, this is a contract requirement rather than advice. For everyone else, we would treat it as the most credible published opinion on sequencing available to us, from an organization with unusual visibility into both halves of the problem.
Putting it into the plan
Nothing here argues for pausing the encryption workstream. Hybrid ML-KEM is cheap, ready and worth deploying now. The argument is about where the scarce resources go, and the scarce resources are architecture time, vendor management and executive attention.
Four things we would put into the next planning cycle.
Extend the inventory to signing keys. A cryptographic bill of materials assembled from network scanning finds TLS endpoints. It doesn’t find the code-signing key in a build system, the firmware signing key held in an HSM at a contract manufacturer, the identity provider’s token signing key, or the container image signing keys in a registry. Those have to be collected by asking.
Start hash-based signing for firmware and code this quarter. No external party has to agree, the standard has been final since 2020, and the state-management design is the only real engineering.
Stand up an ML-DSA issuing CA internally, non-production first. The purpose is to find the size failures in clients, network access and embedded devices while finding them is free.
Put the signature question into procurement. For every vendor shipping signed firmware into your environment, ask when their updates will carry a NIST-standardized post-quantum signature, and record the devices whose verification logic cannot be updated at all. Those have a service life bounded by cryptanalysis rather than by hardware, which makes them a capital planning item now rather than a security item later.
The methodology for running both workstreams in parallel is documented at pqcframework.org, and the deeper technical treatment of the signature threat model is at PostQuantum.com.
Where to build the skill
Sequencing decisions like this are the substance of post-quantum architecture work, and they are hard to make well from reading alone. The trade-offs only become concrete once you have sized a certificate chain against a real handshake budget, designed the state handling for a hash-based signing key, and written the vendor question yourself. That is what our post-quantum cryptography certification path is built around: inventory scope, algorithm selection, migration sequencing, and the program governance that holds a multi-year effort together between planning cycles. Current programs and formats are listed at quantumacademy.com/. If you are mapping the role before the training, QuantumCareers.com covers where post-quantum architecture sits against the adjacent security disciplines.