Post-Quantum Authentication: Lessons from Prague

Four obstacles came up again and again. First, the new keys and signatures break old size limits. Second, verifiers and their roots have the longest deployment timeline but must move first, and migration isn't complete until verifiers stop accepting classical roots. Third, several proposed approaches do more than swap a classical signature algorithm for a post-quantum one, and each of them comes with costs. Fourth, diverging regulatory requirements and technical constraints are driving different approaches to post-quantum authentication, creating a risk of fragmentation.

In August we asked for evidence about what delays the deployment of post-quantum authentication in production systems. The Internet Architecture Board (IAB) workshop that followed met in Prague on 11 and 12 October. Day 1, at the Czech Technical University, brought together about forty people under the Chatham House Rule. Day 2, at Cisco, was on the record, and the twenty-two position papers and the slides are public. In this blog post, we describe what we heard from participants about these four obstacles and about AI coding agents, and what happens next.

One thing was clear: people are comfortable with post-quantum signatures from a security perspective. Nobody reported a security failure in ML-DSA or SLH-DSA. "I implemented PQC and my biggest problem was escaped ampersands," one participant said.

Ericsson's paper calls ML-DSA and SLH-DSA the only mature options for systems that must migrate by 2030 or 2031. Two hardware vendors have shipped firmware signing that combines a classical signature with LMS (RFC 8554). But in many systems, the new signatures cannot simply replace the old ones, often because they are too large for the limits those systems were built with, such as packet budgets, URL lengths, and device memory.

Bigger keys and signatures

Post-quantum keys and signatures are a different size class from the ones they replace. An ML-DSA-65 signature is 3,309 bytes, whereas an Ed25519 signature is 64 bytes. Participants reported where the difference causes trouble: in handshakes, in signed requests and tokens, on constrained devices, and in archives. In signature validation, one participant said the main factor is the size of the key, not the math. If we were sizing a deployment, we would measure what our systems send, handshakes and requests alike, against every limit on the path. The transport layer may need to change before the credential formats.

Handshakes

In a handshake, larger certificates and signatures mean more packets. Going past the initial congestion window costs a round trip, and the more data a flight carries, the more likely it is to lose a packet. The network is out to get you, one participant said: even if the client and server are fine, that does not mean the middleboxes are.

In a simulation in Cisco's SD-WAN slides, 16.3% of ML-DSA-87 handshakes at 3% packet loss took more than five seconds over Datagram Transport Layer Security (DTLS) 1.2, and 0.2% over DTLS 1.3. The presenters attributed the difference to DTLS 1.2 retransmitting a whole flight of handshake messages when one datagram disappears, and proposed moving to DTLS 1.3 before changing credentials. Sean Turner said in the session, "Please don't do DTLS 1.2 and PQ [post-quantum cryptography]."

Requests and tokens

Identity systems put signatures inside tokens and requests, and those pass through components with fixed size limits. The UK Government Digital Service measured the data its systems send during a typical journey to prove and verify someone's identity. It grew from 6.7 KB to 44.5 KB with ML-DSA-65 signatures and ML-KEM-768 key exchange. A signed OAuth request passed in a URL grows with its signature, and each component on the path has its own URL limit, from 8 kibibytes (KiB) at Amazon's CloudFront to 16 KiB for a load balancer's request line.

Devices and archives

Ericsson's paper says ML-DSA and ML-KEM are unsuitable for constrained IoT radio systems, particularly those with payloads of only a few tens of bytes. PQShield's example of ML-DSA-87 on a constrained device used about 26.5 of 30 KiB before allowing for handshake, cryptographic primitive, or application RAM. Aleutian AI's paper calculated that an archive of a million records would carry 3.31 GB of ML-DSA-65 signatures, against about 64 MB for raw P-256 signatures. Aleutian AI has signed every record with ML-DSA-65 in production since August.

Roots and verifiers

Verifiers and the roots they trust have to move first, and they take the longest to update. They also decide when the migration is done: a verifier is not protected until it stops accepting classical roots, whatever certificates have been deployed. Our first step in a migration plan is to list the verifiers we cannot update, because they determine how long the old algorithm stays trusted. The plan also has to say when to stop accepting it.

Verifiers

Authentication has more participants and dependencies than key establishment because a verifier must know in advance what it will accept. A signer cannot switch until the verifiers that check its signatures can. Verifiers, whether a browser, a card reader, or the boot code in a device, are usually the slowest part to update, so they have to move first. Only in a negotiated protocol such as Transport Layer Security (TLS) can a server hold both kinds of certificates and give each client the one it understands.

Even verifiers that are ordinary software take a long time to update. npm's paper says the registry would probably wait at least 12 months for people to adopt a CLI that can verify post-quantum signatures before it starts offering them. The previous algorithm transition is still incomplete: on Day 2, Aaron Gable said Let's Encrypt still issues certificates for RSA keys from a separate RSA hierarchy, because some clients cannot validate ECDSA. Issuing them from its ECDSA hierarchy, he said, would "break more than 1% of our customers," and he called that "the unfortunate reality of how poorly the transition to ECDSA has gone."

Root rollover

When the old classical root vouches for a new post-quantum root, trust still rests on the algorithm being retired. Each verifier trusts a root key it was given at manufacture or installation, and a new root can be introduced by having the old root sign it, so that clients that already trust the old root accept the new one. As Mike Ounsworth put it, "The thing that you're rooting is the thing that's about to die." Clients update their trust anchors at different times, so there is no flag day on which everyone can switch.

Long-lived devices

Devices that stay in service for decades are the hard case. One participant said that secure bootstrap is the root of trust and needs much more long-term safety. Participants described roots that devices must still use to verify firmware 20 to 30 years after installation. They pointed out that anyone who can break the classical signature that vouches for a new root can forge their own root. One forged root unlocks a fleet. Netflix's paper calls these forge-later attacks, "where attackers use quantum computing to forge authentication in systems that rely on long-term trust."

Definition of done

David Benjamin's paper for Google states the goal: an active attacker with a quantum computer must not be able to intercept connections between updated clients and updated services. If that is not achieved, the paper says, "PQ certs just waste bytes." Adding post-quantum certificates does not achieve it on its own. An attacker chooses which certificate to present, so a client that would still accept a forged classical certificate is vulnerable, whatever the real server has deployed. The client is protected only when it stops accepting classical roots, and the paper says it cannot do that until almost all of the services it talks to have moved. On Day 2, Benjamin called deleting classical trust on the client the durable end state.

That moves the definition of done: a migration is not finished until verifiers stop accepting classical roots. The Cisco SD-WAN presenters said the classical certificates built into their routers at the factory may stay in use alongside post-quantum ones until about 2035, because replacing all the hardware by 2030 is not possible. They agreed that, as long as those certificates stay in use, an attacker who can forge a classical certificate could impersonate a network controller and take over the network.

Trade-offs

In August we said that each approach moves cost from one constraint to another, and in Prague we heard more about these costs. We also said that simpler levers, such as avoiding signatures where no third party needs to check them later, might buy more than new cryptography in some systems, and that we did not have enough published measurements to know where. Before choosing a signature algorithm, decide what actually needs signing.

Merkle Tree Certificates

Merkle Tree Certificates shrink what goes on the wire by moving repeated signature cost into shared log infrastructure, inclusion proofs, and an update channel. A tree lets one signature cover many objects, with an inclusion proof tying each object to what was signed, and how much this saves on the wire depends on what the verifier can reuse.

Deploying them depends on software, hardware, and protocols that are not all available yet. Gable said that Internet scale is not the hard part: the design needs many hashes but few signatures. The details are the hard part, and no library yet builds the new certificate's signature block. The panel listed more gaps: the certificate log must have a single writer and never fork, few hardware security modules (HSMs) can sign with ML-DSA today, and no enrollment protocol can deliver a second certificate for the same request at a later time.

A language model pointed at the draft and the specifications behind it, Gable said, will produce a compliant implementation in a few hours, if you accept whatever comes out. Let's Encrypt's four-person team had spent about five months on a high-assurance version built into its existing certificate authority, and was almost done.

Fewer signatures

Netflix's paper says the move to post-quantum authentication in its protocols "is not a substitution problem", and describes its work to reduce the number of signatures it needs. Where no one needs to prove to a third party who sent a message, and the threat model permits it, Netflix prefers keys derived from a shared secret, using a hash-based message authentication code (HMAC) or authenticated encryption, over signatures. Asked on Day 2 what that gave up, the Netflix presenter said the price was complexity: the backend used to treat every type of device the same way, and it no longer can.

Composites

Composites make the opposite move, buying two signatures as insurance against one component failing. A composite signature combines ML-DSA with a traditional signature algorithm, and both components have to validate. On Day 1 we heard them described as the fix for "I don't trust the cryptography".

Ounsworth said that composites "turn a zero-day into a 20-day". Benjamin said a public PKI is likelier to fail by trusting the wrong party, and signing twice doesn't fix that unless two certificate authorities attest to the same thing. Later, on document signing with smart cards, Ounsworth put the window in practical terms: employees can get new ID badges in a month, not in three hours.

Diverging standards

Some deployments will need pure post-quantum algorithms, others will require composites, while applications constrained by signature sizes may need to adopt fundamentally different constructions, such as Merkle trees. Policy on composites and other hybrids is splitting by jurisdiction. On Day 2, one participant said divergent standards are the cost: the NSA says no hybrid while somebody else requires it. Another said industry wants fewer options, because a vendor serving many countries pays for each conflicting policy. This diversity may be unavoidable, but we heard that the aim should be convergence, even if governments diverge.

AI coding agents

AI coding agents came up as an unexpected cause of divergence between implementations. One participant described a deployment where coding agents had no single authoritative source for which post-quantum algorithm and implementation to use, so different agents implemented different formats. We also heard that AI does not use libraries correctly, and that agentic coding works against crypto agility, the ability to change algorithms later, because an agent writes its own cryptography instead of calling a library. Suggestions in the room included scanning pull requests for hand-written cryptography and writing guides that coding agents can read.

What happens next

We closed the workshop with a list of follow-up topics, and on 27 October we asked the attendees which of five they would work on: deployment guidance, long-lived devices and roots of trust, authentication based on key encapsulation mechanisms (KEMs), Merkle-tree designs, and PKCS #11 and other interfaces to HSMs.

We will try to publish the workshop report as quickly as possible. It will appear on the workshop page. It will record what we heard rather than issue guidance, and the takeaways in this post are our own.

In August we wrote that the threat to authentication may be further away than the threat to key establishment, but that the migration is also longer. In Prague we heard how long its slowest parts take, and where it ends. npm's registry would probably wait at least 12 months for clients before it offers post-quantum signatures. The classical certificates built into one vendor's routers may stay in use until about 2035, and some devices must verify firmware against the same root for 20 to 30 years. With different deployments moving towards different cryptographic approaches, maintaining interoperability throughout this transition will be an additional challenge. The parts of a system that take longest to change are also the parts that have to change first, and the migration is not done until verifiers stop accepting classical roots. That is why work on authentication cannot wait until the key-establishment migration is finished.

Thanks

Thank you to CESNET and the Czech Technical University for the room on Day 1, to Cisco for Day 2, to the program committee, to everyone who wrote a paper and then argued about someone else's, and to everyone who joined remotely.