Post-Quantum Migration

The largest cryptographic migration in the history of the Internet, currently underway. PKI engineers will spend the next decade refactoring around it. This chapter is the survival guide.

3.1 Why this chapter exists

Two facts collide in 2025–2026 to make post-quantum cryptography (PQC) urgent rather than optional. First, in 2024 the NIST PQC standardisation effort closed its first round with three published standards — FIPS 203 (ML-KEM), FIPS 204 (ML-DSA), and FIPS 205 (SLH-DSA). Second, the regulatory environment has begun to assume their availability: eIDAS 2 (Regulation 2024/1183) explicitly contemplates PQC algorithms for qualified trust services, and the EU AI Act’s high-risk audit-trail obligations imply retention windows that survive the deprecation of any classical algorithm.

The migration cost is not symbolic. ML-DSA signatures are roughly 13× larger than RSA-PSS-2048 signatures. ML-KEM ciphertexts are about 4× larger than RSA-2048 ciphertexts. Storage, bandwidth, and HSM key-handling all change. We cover the engineering implications in §3.5; first, we explain why this is happening at all.

3.2 The threat model — harvest now, decrypt later

Quantum computers do not yet exist at the scale required to break RSA-2048 or ECDSA-P256. They may exist later — cryptographically relevant quantum computers (CRQCs) — at some point in the 2030–2040 window, with substantial uncertainty either side. The threat model that makes PQC urgent today is harvest now, decrypt later (HNDL):

An adversary records encrypted traffic and signed artefacts today, stores them indefinitely, and waits. When CRQC capability arrives, the adversary decrypts the harvest and forges signatures over its private key.

The HNDL adversary has implications across both secrecy (KEM / encryption) and authenticity (signature) primitives, but the implications are different.

For secrecy, HNDL is acute: a 30-year medical record encrypted under RSA-OAEP today is at risk if a CRQC arrives in 2042. Migration to PQC KEMs needs to start now for any data that must remain confidential for decades.

For signatures, HNDL is more nuanced. A signature made today is legally bound to the algorithm in use at sign time; an attacker breaking the algorithm in 2042 cannot retroactively forge a 2026 signature without also rewriting the timestamp record. RFC 3161 TSA evidence pinned to today’s signing date acts as a partial defence. But — and this is the regulatory implication — audit relies on the signature still validating in 2042, and a deprecated algorithm complicates verification even when the underlying signed data hasn’t been forged.

Hence the practical PQC migration target for trust services like EATF: hybrid mode, where every signed artefact carries both a classical and a PQC signature. Verifier policy can require either, both, or any specified subset.

3.3 The three NIST PQC standards

3.3.1 ML-KEM (FIPS 203) — Module-Lattice Key-Encapsulation

ML-KEM (formerly Kyber) is a key-encapsulation mechanism. The KEM abstraction is operationally simpler than the older “encrypt the session key with RSA” pattern: a sender calls encapsulate to produce a ciphertext and a shared secret; the recipient calls decapsulate on the ciphertext to recover the same shared secret.

Security rests on the Module-Learning-With-Errors (M-LWE) problem, a structured-lattice variant of the standard LWE problem. Informally, the M-LWE assumption says that distinguishing

$$(\mathbf{A},\, \mathbf{A}\mathbf{s} + \mathbf{e} \bmod q) \quad \text{from} \quad (\mathbf{A},\, \mathbf{u})$$

is hard, where $\mathbf{A} \in R_q^{k \times l}$ is a public matrix in a polynomial ring $R_q = \mathbb{Z}_q[x] / (x^n + 1)$, $\mathbf{s}, \mathbf{e}$ are short ring elements drawn from a small-coefficient distribution, and $\mathbf{u}$ is uniform.

ML-KEM comes in three parameter sets matched to NIST security levels: ML-KEM-512 (level 1, ~128-bit classical security), ML-KEM-768 (level 3, ~192-bit), ML-KEM-1024 (level 5, ~256-bit). Most deployments will use ML-KEM-768.

3.3.2 ML-DSA (FIPS 204) — Module-Lattice Digital Signature

ML-DSA (formerly Dilithium) is a signature scheme built on the same M-LWE / Module-Short-Integer-Solution (M-SIS) hardness. The signature equation, in its rejection-sampling form, satisfies:

$$\mathbf{z} = \mathbf{y} + c \cdot \mathbf{s_1}, \qquad \mathbf{w} = \mathbf{A} \mathbf{y} - c \cdot \mathbf{s_2} \cdot \mathbf{1},$$

where $c$ is a hash-derived challenge polynomial of small Hamming weight, $\mathbf{y}$ is a fresh masking value drawn from a wide distribution, and the signer rejects the candidate signature if $\mathbf{z}$ leaks information about $\mathbf{s_1}$ (Fiat-Shamir with abort).

Three parameter sets, again matched to NIST security levels: ML-DSA-44 (level 2), ML-DSA-65 (level 3, the EATF default), ML-DSA-87 (level 5).

ML-DSA-65 signatures are roughly 3309 bytes (vs 256 bytes for RSA-2048-PSS, ~71 bytes for ECDSA-P256, ~64 bytes for Ed25519). The public key is 1952 bytes (vs 270, 91, 32 respectively). This size delta is the practical cost of M-LWE security, and it dominates the migration’s storage discussion in §3.5.

3.3.3 SLH-DSA (FIPS 205) — Stateless Hash-Based DSA

SLH-DSA (formerly SPHINCS+) is a stateless hash-based signature. Unlike ML-DSA, its security rests only on the security of the underlying hash function — there is no number-theoretic or lattice assumption. This is the conservative choice when paranoia about future cryptanalytic surprises in lattice schemes is the deciding factor.

The signature is a Merkle-tree-of-Merkle-trees structure with HORST / FORS one-time signatures at the leaves. Signature size is the dominant operational concern: roughly 7856 bytes (SLH-DSA-128s) to 49 856 bytes (SLH-DSA-256s, ~50 KB). Verification is fast; signing is comparatively slow because of the deep hash tree.

For most general-purpose deployments — including EATF — ML-DSA-65 is the right balance of size, speed, and security margin. SLH-DSA is reserved for archival signatures where decades-long signature validity outweighs size concerns.

3.3.4 Quick comparison

Property	RSA-PSS-2048	ECDSA-P256	Ed25519	ML-DSA-65	SLH-DSA-128s
Signature size	256 B	~71 B	64 B	3 309 B	7 856 B
Public key size	270 B	91 B	32 B	1 952 B	32 B
Sign cost (relative)	medium	fast	fastest	medium	slow
Verify cost (relative)	fast	fast	fastest	fast	very fast
Security assumption	RSA factoring	ECDLP	EdDLP	M-LWE / M-SIS	hash strength
Quantum-broken?	Yes (Shor)	Yes (Shor)	Yes (Shor)	No known attack	No known attack
Estonia QTSP support (2026)	yes	yes	partial	piloting	no

3.4 Hybrid signing — the practical bridge

Pure-PQC deployments are operationally premature in 2026: ML-DSA has been a standard for less than two years; auditors, HSM vendors, and regulators are still calibrating. Hybrid signing — producing both a classical and a PQC signature over the same canonical payload — gives deployers transition coverage without betting the audit trail on a single algorithm.

The EATF hybrid envelope appears in the paper preprint §5.7 as two entries in the signatures array of an .aep package:

flowchart LR
    P[Canonical CBOR payload]
    P --> H[SHA-256 of canonical bytes]
    H --> S1[RSA-PSS-2048 signature]
    H --> S2[ML-DSA-65 signature]
    S1 --> E[.aep Evidence Package]
    S2 --> E
    E --> V{Verifier policy}
    V -->|either| OK1[Accept on first valid match]
    V -->|both| OK2[Require all signatures valid]
    V -->|threshold| OK3[Require k of n valid]

The probability that a hybrid signature remains unforgeable is governed by the verifier-policy combiner. If $P_c$ denotes the probability that the classical primitive is broken (Shor by 2042, say) and $P_q$ the probability that the PQC primitive is broken (unknown but currently believed small), then under the “both” policy the joint break probability is approximately

$$P_{\text{hybrid}} \approx P_c \cdot P_q,$$

assuming independence of the two breaks. This is much smaller than either $P_c$ or $P_q$ alone — the combiner gives us the security of the strongest assumption, not the weakest.

Under the “either” policy, the joint break is bounded by

$$P_{\text{either}} \le \min(P_c, P_q),$$

which is operationally easier (a verifier accepts whichever signature it can validate) but security-weaker. EATF defaults to “either” for routine verification and “both” for high-stakes audit; deployer policy decides.

3.5 Operational pitfalls

3.5.1 Certificate and signature inflation

The size figures in §3.3.4 cascade: a hybrid certificate carrying both an RSA public key and an ML-DSA-65 public key is ~2.2 KB larger than a classical-only certificate. A typical TLS handshake ships the leaf, two intermediates, and a root — five certificates under hybrid is ~11 KB additional payload. Most deployments will absorb this without issue; constrained environments (smart cards, embedded devices, IoT) may not.

For AI evidence packages, the size delta is acute because packages are emitted at high volume:

• A classical-only .aep package is ~600 bytes (CBOR envelope + RSA-PSS signature + minimum metadata).
• A hybrid .aep package is ~4 600 bytes.

Over a year of operation at 100 packages/hour, this is the difference between roughly 500 MB and 4 GB of audit-ledger growth.

3.5.2 HSM key handling

Most contemporary HSMs (Utimaco, Thales, nCipher) support classical RSA / ECDSA natively; ML-DSA support is rolling out through firmware updates in 2025–2026. Operators planning hybrid mode need to confirm:

• Can the HSM generate ML-DSA-65 keys natively, or must the keys be wrapped in software and stored as opaque blobs?
• Does the HSM’s policy engine treat ML-DSA keys as first-class for audit and access control?
• For QTSP-grade operations, has the HSM vendor obtained a Common Criteria evaluation covering ML-DSA?

The Utimaco virtual-HSM clone limitation noted in the 2026-04-07 EJBCA OCSP responder incident — where a virtual HSM cannot auto-replicate keys to its standby — applies equally to ML-DSA keys. Plan accordingly.

3.5.3 Migration timelines

A realistic industry curve, informed by the 2024 NIST publications and the regulatory positions of NIST, BSI, ANSSI, and the EU Commission:

timeline
    title PQC migration realistic curve
    2024 : FIPS 203/204/205 published
         : eIDAS 2 amendments enter force
    2025 : Hybrid mode pilots (TLS, signing)
         : First QTSP ML-DSA pilots in EU
    2026 : Hybrid mode mainstream
         : EATF / Aletheia hybrid default
    2027 : Most CAs offer hybrid certificates
         : Smart-card / Mobiil-ID PQC pilots
    2028 : EU AI Act high-risk full enforcement
         : Hybrid required for new long-term audit
    2030 : Pure-PQC deployments common
         : Classical algorithms deprecated for new issuance
    2035 : Classical signatures unverifiable in core stacks
         : Archival migration completes

The slope is steepest between 2025 and 2028. Deployers planning EU AI Act high-risk systems with retention obligations beyond five years should be running hybrid by 2027 at the latest.

3.6 Decision tree — which algorithm where

flowchart TB
    Q1{What are you protecting?}
    Q1 -->|secrecy / encryption| K[Use ML-KEM-768]
    Q1 -->|signature / authenticity| Q2{Retention horizon?}

    Q2 -->|< 1 year| RT[Classical only is OK]
    Q2 -->|1-10 years| H1[Hybrid: RSA-PSS + ML-DSA-65]
    Q2 -->|10+ years, archival| Q3{Lattice-paranoid?}

    Q3 -->|moderate| H2[Hybrid: RSA-PSS + ML-DSA-65]
    Q3 -->|extreme| H3[Hybrid: RSA-PSS + SLH-DSA-128s]

    H1 --> EATF
    H2 --> EATF
    H3 --> EATF
    K --> TLS[TLS 1.3 hybrid key exchange]

EATF defaults: hybrid RSA-PSS-2048 + ML-DSA-65 for signing artefacts; ML-KEM-768 for any KEM-using transport (none in the current .aep flow, but planned for partner-integration secure channels).

3.7 Operational checklist

A short, dryly opinionated checklist for any team starting a PQC migration in 2026:

1. Audit your retention horizons. Anything signed today and audited in 2030+ is a hybrid candidate now.
2. Establish a hybrid-default signing pipeline before you migrate downstream verifiers. Verifiers can defer to “either” policy while signers always emit “both”.
3. Confirm HSM ML-DSA support in firmware before committing to a hardware refresh.
4. Budget for size inflation. Audit-ledger storage 4–7×; bandwidth ~+11 KB per TLS handshake under hybrid.
5. Pin the EATF version emitting the artefact. When ML-DSA is eventually superseded, downstream verifiers will need to know which envelope format applied.
6. Watch the regulatory dates. The EU AI Act high-risk enforcement timeline (full applicability in 2027, with high-risk audit obligations crystalising through 2028) is the operational deadline.
7. Don’t over-engineer. SLH-DSA’s 50 KB signatures are not the default for a reason. Use ML-DSA-65 unless you have a specific archival or paranoia requirement.

3.8 Outgoing links

• → Chapter 6 · operational playbooks include the hybrid-PQC rollout playbook.
• → Chapter 8 · long-term PQC standardisation, 30-year retention under algorithm deprecation, and the open problems they imply.
• → Preprint §5.2 / §5.7 · EATF hybrid-signature handling, formal version.
• → liboqs and oqs-provider for open-source PQC tooling (local repos at ~/projects/liboqs/ and ~/projects/oqs-provider/).
• → PKI Consortium PQC working group.