Migrating to Post-Quantum Cryptography: What Changes in Practice

By Nika, NodeTimes newsroom.

A post-quantum migration starts with crypto agility, not with choosing an algorithm: until a primitive can be replaced by configuration instead of a release, the scheme you pick expires together with the system. The bottleneck is not the mathematics but the trust infrastructure around it, because certificates, signing roots and device firmware move on their own clocks. The practical question is therefore not which algorithm to adopt, but in what order the components can change.

What has to change, and in what order

Four classes of primitive move on different clocks, and only one of them is a pure software change: key establishment, which a hybrid handshake switches on by configuration, while signatures, certificates and the hardware that stores keys each drag a new root, a new client or a new device behind them.

Post-quantum cryptography (PQC): a family of algorithms built to stay secure against an attacker who holds a cryptographically relevant quantum computer, standardised by NIST as FIPS 203, FIPS 204 and FIPS 205. Key establishment (also called key exchange): the part of a handshake that agrees a shared secret. Digital signatures: the mechanism that proves authorship and integrity. Crypto agility is the ability to swap one primitive for another through configuration rather than a code change; the post-quantum glossary carries the rest of the vocabulary this subject runs on.

The order is not a preference: inventory, then agility, then a hybrid phase, then retirement.

The urgency comes from key establishment rather than signatures. A signature is verified when it is used, so a forged signature has to be produced at that moment, and both what breaks in that scheme and what has to replace it are set out in the explainer on how quantum computers break ECDSA; a key exchange that is recorded now can be decrypted later, which is the harvest now, decrypt later problem and the reason traffic with a long confidentiality lifetime moves first.

Crypto agility first

Agility comes before the algorithm, because a stack that cannot swap a primitive commits to whichever algorithm it adopts first and can only change its mind through a release.

In practice agility is a small set of engineering decisions rather than a product. The algorithm identifier must be negotiated at runtime instead of hard-coded, key material must be stored as opaque bytes rather than fixed-width columns, and the system must be able to hold two schemes at once without a data migration. The test is simple: can you turn the new primitive on for one percent of traffic, and turn it off again, without touching application code?

• Hard-coded curve names, key lengths or hash identifiers in configuration that ships with the binary.
• Database columns sized for a 32-byte public key that silently truncate a larger one.
• Libraries pinned to a single version, where the upgrade is itself the project.
• A certificate or key format that encodes the algorithm inside the identifier, so both ends must move on the same day.

The same property decides how fast the later steps go. Post-quantum signatures are larger than the elliptic-curve ones they replace, so anywhere the size leaked into a protocol field, a column width or a rate limit, the size becomes a migration task of its own.

Hybrid mode: classical and post-quantum together

Hybrid mode runs a classical and a post-quantum primitive in the same handshake, which keeps the connection safe as long as neither part is broken; it does not add the two strengths together.

The construction is deliberately conservative: if the post-quantum half turns out to be broken by classical cryptanalysis, the classical half still protects the session, and if the quantum threat arrives earlier than expected, the post-quantum half holds. Hybrid key exchange is what deployments reach for first, because it needs no new trust anchor: the certificates in a hybrid handshake can still be classical, while the key agreement is already quantum-resistant.

For signatures the calculation is different, because a hybrid signature is verified by whoever consumes it, and that consumer has to understand both schemes. Hybrid signatures are a transition device for systems you control on both ends; for anything facing the open internet they are a compatibility tax paid twice.

• Mandatory where the traffic is recorded today and read later: long-lived sessions, VPN, backups in transit.
• Worth it where both ends are yours and you can retire the hybrid form on a schedule.
• Avoidable where the peer still runs a stack that cannot be updated, and the only honest option is to isolate that peer.

The cost is measured in bytes. A classical X25519 key share is 32 bytes; an ML-KEM-768 encapsulation key is 1184 bytes and its ciphertext 1088 bytes, so a hybrid share is roughly thirty-eight times the classical one. The arithmetic does not improve much if you move between parameter sets: the post-quantum share is large in every one of them, so its size becomes an engineering task, a field width or a fragmentation budget, long before it becomes a cryptographic one. The algebra behind that key exchange is set out in the explainer on lattice-based cryptography.

What breaks in the handshake

The handshake breaks first on size, not on security: a larger key share and a larger signature can push the client's first flight past the packet budget and add a round trip.

A TLS 1.3 ClientHello carries the key shares, and when that message exceeds the initial congestion window of a TCP connection it has to be fragmented across several packets. Fragmentation itself is survivable; the price is a second round trip before the server can answer, and a second round trip is exactly what a high-latency connection notices most.

Signature sizes matter in a different place. In a TLS handshake the server's signature sits in the CertificateVerify message, and an ML-DSA-65 signature is 3309 bytes against 64 bytes for an Ed25519 signature, with a 1952-byte public key against 32. The flight still fits, but every middlebox that parses inside the record layer now has a longer structure to handle, and old parsing code is where the surprises are.

Certificates and trust chains are the real lag

The deadline of a migration is set by the certificate chain, not by the algorithm, because a new key is useless until the client on the other side can verify it.

A certificate is not one file. It is a leaf, one or more intermediates, and a root that lives in a trust store you do not control: a browser, an operating system, a Java keystore, a firmware image. Reissuing your own leaf with a post-quantum signature is a day of work; waiting for every client to accept that signature is the actual schedule. Certificate validity periods cut both ways: a short cycle forces a reissue, which is what a migration wants, while the root and the intermediate that anchor the leaf live in trust stores you do not control and outlast your own schedule.

• Network appliances that terminate TLS and cannot be patched, only replaced.
• Industrial and medical devices with a firmware update path that requires a service visit.
• Smart cards and secure elements where the algorithm is fixed in silicon.
• Long-lived code-signing roots whose replacement invalidates every artefact signed under them.

Long-term confidentiality is where the chain hurts most. A session recorded now cannot wait for the client to be upgraded later, so the transport layer moves before the certificate layer is ready, and hybrid mode is what bridges the two.

A staged migration plan

Five steps cover the path from an inventory to a post-quantum default, and each has a completion test that can be run rather than argued about.

1. Inventory: a list of every primitive, key, certificate and device, with the owner and the update path for each. Done when no public-key operation is left without a named owner.
2. Agility: the algorithm becomes a configuration value. Done when you can switch one primitive for another in production and roll it back.
3. Hybrid: the post-quantum primitive runs alongside the classical one. Done when both are visible in the handshake and the failure of either is tested.
4. Retirement: the classical primitive is switched off. Done when a full client population completes the handshake without it.
5. Verification: a scheduled check that the inventory still matches reality. Done when a new service cannot reach production with an unlisted primitive.

The standards bodies give the horizon that makes this urgent rather than theoretical: NIST IR 8547 plans quantum-vulnerable algorithms at the 112-bit security level as deprecated after 2030 and disallowed after 2035, and the stronger parameter sets as disallowed in that same year, with no deprecation phase before it.

The order is easy to get backwards: the signature algorithm is the visible part of the work, while the inventory is the step with the longest chain of dependencies behind it. Shipping the inventory is the only step that makes the rest of the plan estimable.

Frequently asked questions

Do we have to replace all cryptography at once?

No. The migration runs component by component, and the first component to change is the one that can accept a new scheme without an architectural change.

That is usually key establishment in transport, because hybrid key exchange needs no new certificate and no new trust anchor.

What is crypto agility and why start there?

Crypto agility is the ability to replace a cryptographic primitive through configuration rather than a release, and without it any algorithm you choose goes out of date with the system around it.

It is also the property that turns a multi-year project into a sequence of deployable steps.

Is hybrid mode twice as strong?

No. Hybrid mode keeps a connection secure as long as neither of its two halves is broken, and it does not combine their strengths into a larger one.

The point of the second half is that it survives a failure of the first, not that it adds to it.

Why do certificates set the deadline?

Because the schedule follows the trust chain rather than the algorithm: as long as a client cannot accept a new signature, replacing the key changes nothing on its own.

Leaf certificates are the fast part; intermediates, roots and firmware are the slow part.

What can be done now, before the standards settle?

Start with the inventory: the list of primitives, devices and certificates whose update schedule you do not control.

An inventory is also the only deliverable that stays useful if a parameter set or a timeline is revised, because it describes your systems rather than a standard.