PDF LaTeX source Comments

Chapter 27Deploying Post-Quantum Cryptography

27.1Why this chapter matters#

The previous parts built and analysed the algorithms. This chapter is about the harder half of the problem: getting them into web protocols, digital certificates, and infrastructure correctly and in time. The forcing function is harvest now, decrypt later (Chapter 1): an adversary can record encrypted traffic today and decrypt it once a quantum computer exists, so any long-lived secret is already exposed. Migration must therefore begin before the threat arrives, not after, and migration is an engineering project at least as much as a mathematical one.

27.2Learning goals#

After reading this chapter, you should be able to:

• explain why real deployments use hybrid classical-plus-postquantum cryptography, what crypto-agility means, and when hybrid is the wrong choice;

• describe how TLS 1.3 carries a hybrid key exchange and post-quantum certificates, and what the size costs are;

• evaluate how those sizes interact with packet loss, QUIC amplification limits, deployment tooling, and PKI structure;

• say what has already shipped, and why key exchange migrated years ahead of signatures;

• weigh the size and performance trade-offs that drive scheme choice in practice.

27.3Hybrid cryptography and crypto-agility#

The safest way to deploy a young algorithm is not to trust it alone. A hybrid scheme combines a well-understood classical algorithm with a post-quantum one through an analysed protocol construction.

Hybrid deployment hedges two opposite risks at once: a future quantum computer breaking the classical part, and an as-yet-undiscovered classical weakness in the still-young post-quantum part. It is the mainstream migration strategy precisely because it removes the need to bet everything on one new assumption.

27.3.1The combiner, concretely#

The definition above says “an analysed protocol construction” and warns that arbitrary hashing is not one. It is worth seeing what a construction that is analysed looks like, because the reason for each of its inputs is the whole content of the warning.

First, X25519 is not a KEM.#

Diffie–Hellman is key agreement, so it has to be wrapped before it will compose with one. The standard wrapping makes the ephemeral public key play the role of the ciphertext:

Then the combiner.#

With both components in KEM form, the hybrid is componentwise, and everything interesting happens on one line.

Why the ciphertexts are in the hash.#

This is the step that turns the construction into a theorem, and the reason \(\mathrm{KDF}(ss_1 \| ss_2)\) alone is not one. Suppose the ciphertexts were omitted. An IND-CCA attacker holds a challenge \((ct_1^{*}, ct_2^{*})\) and wants the key behind it. If it can find any \(ct_1' \neq ct_1^{*}\) that decapsulates to the same \(ss_1^{*}\), then \((ct_1', ct_2^{*})\) is a different ciphertext with an identical shared secret. It is not the challenge, so the decapsulation oracle will answer it — and the answer is the challenge key. The game is lost without either component having been broken.

Binding \(ct_1 \| ct_2\) closes this: change any byte of the ciphertext and the derived key changes with it. Giacon, Heuer, and Poettering [2] showed that the naive concatenation combiner is not generically CCA-preserving and gave combiners that are; Bindel, Brendel, Fischlin, Goncalves, and Stebila [3] carried the analysis into the hybrid KEM and authenticated-key-exchange setting. NIST’s KEM recommendations SP 800-227 [4] now give the corresponding standards-side guidance on hybrid constructions and approved key combiners, and NIST IR 8547 adds that a hybrid can be FIPS 140 validated as long as one input comes from an approved scheme, even if the other is disallowed, with the two shared secrets concatenated in either order [5]. The label is domain separation, so that a key derived here cannot collide with one derived by another protocol from the same primitives.

X-Wing: a real instantiation, and a caution.#

X-Wing [6] is a standalone hybrid KEM of ML-KEM-768 with X25519, designed for use where no protocol supplies a transcript. Its combiner is \[ss \;=\; \mathrm{SHA3\text{-}256}\big(ss_{\mathrm{M}} \,\|\, ss_{\mathrm{X}} \,\|\, ct_{\mathrm{X}} \,\|\, pk_{\mathrm{X}} \,\|\, \textit{XWingLabel}\big),\] with a six-byte label and a \(1216\)-byte encapsulation key against a \(1120\)-byte ciphertext. Note what is missing: the ML-KEM ciphertext \(ct_{\mathrm{M}}\) is not hashed in. That is not an oversight and not a general licence — the specification is explicit that it holds for the concrete choice of ML-KEM-768, justified by that scheme’s own proven properties. The transferable lesson is the one the definition above states abstractly: a combiner may be shortened only with a proof about the particular schemes, never by inspection.

Hybrid deployment also presupposes crypto-agility. The lifecycle requirements beyond algorithm negotiation are developed in Section 27.3.3.

27.3.2Where hybrid does not fit#

Hybrid is the appropriate default for the protocols above. The reasons are properties of those protocols rather than facts about cryptography, and one important class of system has none of them.

In TLS, a hybrid transition is nearly free. The extra classical key exchange costs a few hundred bytes on a connection that is discarded seconds later, both endpoints negotiate the algorithm without asking anyone’s permission, and no user is aware the change happened. The cost is paid once, by software vendors, and it is invisible.

On a blockchain, every one of those properties fails. The extra signature is not transient: it is written permanently into a block, relayed to every node, and stored by every archive, so a hybrid transaction costs its wire size forever and to everyone. There is no negotiation, because consensus rules are the same for all participants. And the change is emphatically not invisible — users must act, first to move to the hybrid scheme and then again to move off it, which means the ecosystem pays the coordination cost of a migration twice. Chapter 28 shows what that coordination cost actually looks like; it is the dominant term.

The generalizable rule is that hybrid is cheap where the redundant work is ephemeral, negotiated, and invisible, and expensive where it is persistent, consensus-fixed, and user-visible. Before adopting hybrid by reflex, check which of those two descriptions the system fits.

27.3.3Crypto-agility as lifecycle engineering#

Crypto-agility is more than negotiating an identifier. Standards evolve, new cryptanalysis changes confidence, implementations require patches, and long-lived devices or roots may outlast an algorithm choice. Industry guidance therefore describes agility as the ability to discover cryptographic assets and replace or upgrade algorithms in a controlled way without breaking the business system [7].

Four capabilities make that definition operational:

1. inventory: locate algorithms, keys, certificates, HSM policies, libraries, protocol endpoints, and data whose confidentiality lifetime is relevant;

2. abstraction: prevent applications from depending on one concrete key or object format where policy should make the choice;

3. policy: control allowed algorithms, parameter sets, hybrid rules, expiry, and exceptions centrally enough to audit them;

4. automation: rotate, test, deploy, observe, and roll back at the scale of the infrastructure.

Agility is constrained by wire and consensus protocols. An API cannot negotiate an identifier the peer does not understand, shrink a fixed certificate field, or change a blockchain transaction format. Consequently, the migration unit is the algorithm, implementation, protocol, and infrastructure together.

27.4Post-quantum TLS 1.3#

TLS 1.3 secures most web traffic, and it is the first place post-quantum cryptography has reached production. Two independent parts of the handshake must be upgraded: the key exchange (confidentiality) and the authentication (signatures on certificates).

27.4.1Hybrid key exchange#

The framework is settled: RFC 9954 [9] specifies how TLS 1.3 carries a hybrid key exchange, and RFC 10024 [8] instantiates it with three ECDHE–ML-KEM groups and permanent code points: X25519MLKEM768 (\(4588\), 0x11EC), SecP256r1MLKEM768 (\(4587\)), and SecP384r1MLKEM1024 (\(4589\)). RFC 10024 is a Standards Track document, not an active Internet-Draft. Of the three groups, X25519MLKEM768 is marked Recommended in the IANA registry; the two SecP groups serve more specialized regulatory and high-security requirements.

TLS takes the simpler route flagged in Section 27.3.1: the two shared secrets are concatenated and inserted in place of the ordinary (EC)DHE input to the existing TLS 1.3 key schedule. RFC 9954 requires every component to have a fixed-length shared secret, which makes the concatenation unambiguous; under that condition its analysis identifies the construction with a dual-PRF combiner [9]. HKDF-Extract [17] forms the handshake secret from the concatenated input. Subsequent Derive-Secret operations bind the handshake transcript, including the negotiated key shares; HKDF-Extract itself does not hash that transcript.

27.4.2Post-quantum authentication and its size cost#

Post-quantum certificate authentication is still a separate standardization and deployment track. The base encoding layer has advanced: RFC 9881 specifies ML-DSA in X.509 certificates and CRLs, and RFC 9909 does the same for SLH-DSA [10, 11]. Those RFCs do not by themselves complete the public WebPKI. Use of ML-DSA in TLS, composite certificate profiles, browser and trust-store support, and Certificate Transparency integration remain separate work items; the TLS ML-DSA and Merkle Tree Certificate specifications were still active Internet-Drafts at this snapshot [18, 19].

ML-DSA-65 is used here as a Level 3 illustration; a deployment choice depends on the target security category and peer support. SLH-DSA offers a more conservative assumption at larger sizes. The practical obstacle is size: post-quantum public keys and signatures are far larger than the elliptic-curve ones they replace, and a TLS handshake may carry several certificates. The extra kilobytes increase packet counts and can add round trips when they cross transport, buffering, or fragmentation thresholds.

27.4.3What has actually shipped#

It is easy to read a chapter like this one as describing a future. For key exchange, it does not. Hybrid post-quantum key agreement is on by default in mainstream browsers and in OpenSSH [20], and Cloudflare reported in April 2026 that more than \(65\%\) of human traffic reaching its network used post-quantum encryption [21]. Major cloud and edge providers now expose concrete products rather than undated experiments.

Table 27.3 records product surfaces, because a provider-wide “PQC ready” label would hide material differences between a default rollout, an opt-in feature, a private-PKI capability, and a future target.

The proposed service-level model below makes those differences auditable by recording the highest migration stage reached by a specific service and protocol surface, not by a provider as a whole. The stages form an operational progression, but they are not a security ranking: a well-tested opt-in deployment may be preferable to a default that cannot be observed or rolled back.

A cloud migration must cover four distinct traffic surfaces: customer ingress, internal service-to-service paths, administrator and developer access, and data-movement pipelines. Evidence on one surface does not establish coverage of the others. The foundation lane is similarly architectural: Cloud KMS assigns KEM keys a distinct KEY_ENCAPSULATION purpose and decapsulation operation, rather than treating ML-KEM as another encryption mode [32].

AWS reports a related systems lesson: with connection reuse, enabling hybrid ML-KEM changed the measured GenerateDataKey throughput from \(216.1\) to \(216.0\) transactions per second, about \(0.05\%\); the same report found a larger effect without reuse [24]. Extra handshake bytes and primitive work therefore do not translate directly into the same percentage loss at the application layer.

Authentication is the less mature story, and the contrast is the useful part. Certificate encodings now have Standards Track RFCs, and private-PKI products have begun to ship, but public WebPKI migration and broad relying-party support remain incomplete. The chains of trust behind code signing, firmware, and secure boot also turn over on a timescale of years. The asymmetry has a simple cause.

• Key exchange is ephemeral and two-party. Both endpoints negotiate afresh on every connection, so an upgrade propagates as fast as software updates do, and nothing needs to be re-issued.

• Signatures are long-lived and multi-party. A root certificate, a signed firmware image, or an on-chain public key commits a verifier who may not be upgraded — or may not even exist — yet.

That distinction recurs for the rest of this book. It is why “harvest now, decrypt later” is the urgent framing for confidentiality but the wrong framing for signatures, and it is why the hardest case in the next chapter is a signature case. Signatures are not exempt from urgency, only from that framing: NIST calls their migration urgent because it takes longer and needs more parties to coordinate [5].

Implementation and deployment status changes rapidly. Before making a production decision, consult the current RFC or Internet-Draft and the release notes of the selected browser, TLS library, or service for its supported groups, defaults, and authentication behaviour.

27.5Network and infrastructure effects#

27.5.1TLS performance and network amplification#

End-to-end TLS measurements show why “PQC is slower” is too crude. On a clean, high-bandwidth path, several KEMs have competitive computation. Performance can degrade when larger objects cross records, packets, initial congestion windows, or loss-recovery boundaries [33, 34].

If an exchange occupies \(N\) independently lost packets with loss probability \(p\), the probability that at least one is lost is

\[1-(1-p)^N.\]

For the illustrative \(N=16\), \(p=0.05\) case used in early PQTLS evaluation, the result is about \(56\%\). This is not a constant of PQTLS; it shows how extra bytes can move a connection into a qualitatively different loss regime.

Certificate authentication adds a second multiplier because signatures appear in certificate chains and in CertificateVerify. KEMTLS removes the server’s online handshake signature by authenticating with a KEM while retaining the CA’s offline certificate signature [35]. It demonstrates that protocol restructuring can outperform repeated attempts to optimize one signature object; it is an alternative design, not the deployed default of TLS 1.3.

A reproducible PQTLS experiment should pin library and draft versions, compiler and build flags, CPU or accelerator configuration, and certificate-chain contents. It should control RTT, bandwidth, loss, and MTU; retain packet captures and TLS message sizes; and record the negotiated group and signature algorithm for every run. Otherwise a benchmark may silently measure a classical fallback or an unrepresentative clean path.

27.5.2QUIC: when bytes alter a transport state machine#

QUIC integrates TLS 1.3 with packetization, encryption levels, loss recovery, and address validation. Before validating a client’s address, a server is limited to roughly three times the bytes it has received. Larger client Initial packets can increase the server’s budget, but larger certificates and signatures can consume it quickly. The resulting behaviour depends on the number and timing of QUIC packets, not merely on the sum of TLS bytes [36].

Measurements across QUIC implementations show that post-quantum objects change packet counts and handshake behaviour and can expose assumptions in buffering and recovery paths [37]. Cloud-network experiments provide further evidence that large post-quantum signatures increase the number of handshake packets [38]. This must be distinguished from IP fragmentation: a larger handshake creates more QUIC packets without necessarily fragmenting an IP packet.

A useful QUIC evaluation records ClientHello and server-flight bytes at every encryption level; Initial, Handshake, and 1-RTT packet counts; anti-amplification blocking; retransmissions and PTOs; completion time and CPU cost; and results under several RTT, bandwidth, MTU, and loss regimes.

27.5.3Industrial delivery chains and PKI#

A standard becomes deployable only after libraries, protocol negotiation, build configuration, conformance tests, products, and both endpoints line up. Library support for ML-KEM or ML-DSA does not prove that a production connection negotiated it. OpenSSL, BoringSSL/Chrome, Cloudflare, and wolfSSL illustrate different links in this chain [39–42].

Section 27.4.3 explains why key establishment moved first. The remaining signature migration must coordinate keys, certificates, CAs, HSMs, relying-party software, revocation, and audit policy; library support for one primitive does not close that delivery-chain gap.

Migration is also an opportunity to remove inherited redundancy. RPKI inherited a large part of the X.509 object model; adding larger post-quantum signatures without redesign can compound certificate and encoding overhead. iRPKI proposes removing unnecessary end-entity certificate structure, retaining the authorization and CA signature actually required, and using a more compact encoding [43]. The broader rule is to eliminate architectural redundancy before paying to protect it with larger objects.

27.6Implementation optimization across platforms#

Primitive timings alone do not determine whether an implementation is deployable. On a constrained device, code size, peak stack and heap use, radio bytes, and energy per operation matter together; on a slow link, transmitting a larger certificate can cost more energy than the cryptographic arithmetic itself [44]. Embedded TLS measurements likewise show that post-quantum key establishment can be practical while certificate authentication remains the harder step [45]. A deployment should therefore test KEM, certificate, and online-signing capability separately instead of assigning one undifferentiated “PQC-ready” label.

Typical constrained-device techniques include in-place polynomial transforms, buffer reuse between phases, and regenerating public matrices from seeds. Hardware accelerators instead trade look-up tables, memory ports, DSP blocks, power, and pipeline depth; server and GPU designs add batching, queueing, data-transfer, and tail-latency constraints. An optimization is meaningful only when its benefit survives serialization, transmission, and the workload in which the primitive is actually used. Section 18.9 gives a concrete FN-DSA example.

Operations that handle secret keys, ephemeral secrets, or secret-dependent sampling – especially key generation, signing, and decapsulation – require side-channel review against the applicable threat model (Chapter 26). Public-input verification has different confidentiality requirements, though it still needs robustness and denial-of-service review.

27.7Pitfalls#

Pitfall 1: deploying post-quantum only, too early.#

Dropping the classical algorithm and trusting the post-quantum one alone forfeits the hedge that hybrid provides. Until the post-quantum schemes have had many more years of scrutiny, hybrid is the conservative default — in the protocols where hybrid is cheap. Section 27.3.2 gives the test for when it is not, and the mirror-image mistake, adopting hybrid where it doubles a permanent cost and forces users to migrate twice, is just as real.

Pitfall 2: ignoring handshake and message sizes.#

Post-quantum keys and signatures are kilobytes, not tens of bytes. Buffers, packet-size assumptions, and certificate-chain limits that were fine for elliptic curves can silently break; sizes must be designed for, not discovered in production.

Pitfall 3: assuming a reference implementation is deployable.#

Reference code optimizes for clarity, not for constant-time behaviour. Shipping it unmodified can reintroduce exactly the side channels of Chapter 26.

Pitfall 4: hardcoding one algorithm.#

The standards will keep changing. A system that cannot negotiate or swap algorithms will have to be re-engineered at the worst possible time.

27.8Summary#

The mathematics of the previous parts defeats Shor’s algorithm, but that is where the abstract scheme ends and the engineering begins:

• hybrid classical-plus-postquantum deployment, with crypto-agility, is the mainstream migration strategy — where the redundant work is ephemeral, negotiated, and invisible, and not where it is permanent, consensus-fixed, and user-visible;

• TLS 1.3 hybrid ECDHE–ML-KEM key exchange is standardized in RFC 10024 and deployed at scale, while protocol and implementation support must still be checked at the time of use;

• post-quantum authentication has standardized algorithm encodings and early private-PKI deployments, but public WebPKI migration remains less mature — because key exchange is ephemeral and two-party, whereas signatures are long-lived and multi-party;

• end-to-end performance depends on packetization, loss recovery, transport state, certificate structure, and the complete delivery chain, not primitive timings alone;

• scheme choice is a trade-off among size, speed, and assumption strength, with side-channel controls scoped to the secrets and threat model of each operation.

Post-quantum cryptography is no longer a paper exercise: the standards exist, and the migration is under way. Real security will arrive only when these schemes are deployed correctly, agilely, and side-channel-safely across the protocols and systems that the world already depends on. The next chapter turns to one of the hardest cases of all – the blockchains, where the funds themselves are secured by exactly the signatures now at risk.

References