Post-Quantum Cryptography: The Algorithms Replacing RSA Before the Quantum Computer Arrives

The internet’s security infrastructure runs on two mathematical problems: integer factoring and the elliptic curve discrete logarithm. RSA encrypts by multiplying large primes; ECDH exchanges keys using elliptic curve arithmetic; ECDSA signs certificates using the same. Every TLS handshake that makes a browser show a padlock, every SSH session, every signed software update — all of these depend on the assumption that no efficient algorithm exists for these problems.

Shor’s algorithm is an efficient algorithm for both. A fault-tolerant quantum computer running Shor’s algorithm would break RSA-2048 in hours. It would break 256-bit ECC in similar time. Not weaken — break completely, at any key size, unconditionally.

The world has known this since 1994. In 2016, NIST launched a competition to standardise replacements. In August 2024, after eight years of evaluation across three rounds and sixty-nine submissions, NIST published four Federal Information Processing Standards: ML-KEM (FIPS 203), ML-DSA (FIPS 204), SLH-DSA (FIPS 205), and FN-DSA (FIPS 206). These are the algorithms replacing RSA and ECC. Understanding them requires understanding both the threat they address and the mathematics they rely on — which is, in each case, deliberately different from anything Shor’s algorithm can touch.

The Threat Landscape: What Breaks, What Bends, What Holds

The threat is asymmetric in both the technical and practical sense. RSA and ECC are completely broken — no engineering solution involving larger keys can save them, because Shor’s algorithm runs in polynomial time in the key size. Symmetric cryptography (AES, SHA, HMAC) is only weakened, and the fix is already standardised: use 256-bit keys and 384-bit hash outputs. The migration problem is therefore almost entirely about asymmetric cryptography: key exchange, digital signatures, and public-key encryption.

The Mathematical Foundation: Four Families of Hard Problems

Post-quantum cryptography does not use one hard problem — it uses four distinct families, each resting on mathematical structures that quantum computers are not known to attack efficiently. The deliberate diversity is a hedge: if one family turns out to be broken, the others remain.

Lattice problems (LWE, SIS, NTRU). A lattice is a regular grid of points in high-dimensional space. The hardest problem on a lattice — finding the shortest non-zero vector — resists all known quantum attacks. The algorithms deployed in practice use related problems (LWE and SIS) that can be reduced to lattice problems in the worst case. ML-KEM, ML-DSA, and FN-DSA all belong to this family.

Hash-based cryptography. If cryptographic hash functions are secure against Grover’s algorithm (which they are, with 256-bit outputs), then signature schemes built entirely from hash functions are quantum-safe by construction. SLH-DSA uses Merkle trees of one-time signatures, each built from hash function evaluations. The security assumption is minimal: SHA-256 or SHAKE-256 must resist preimage attacks.

Code-based cryptography. Based on the hardness of decoding random linear error-correcting codes — a problem studied since the 1970s with no known quantum speedup. Classic McEliece, the oldest PQC system still unbroken, belongs here. Downside: key sizes in the hundreds of kilobytes to megabytes.

Isogeny-based cryptography. Based on the hardness of finding maps between elliptic curves (isogenies). SIKE was the prominent representative — until it was broken in 2022 by a classical attack running in under an hour on a laptop. The collapse of SIKE is the field’s most important cautionary tale.

Learning With Errors: The Dominant Hard Problem

The most widely deployed post-quantum algorithms rest on a single hard problem introduced by Oded Regev in 2005: Learning With Errors (LWE). Given a public random matrix $A$ and the noisy product

$$\mathbf{b} = A\mathbf{s} + \mathbf{e} \pmod q,$$

the task is to recover the secret vector $\mathbf{s}$. Without the small error term $\mathbf{e}$, Gaussian elimination solves this instantly; with it, no efficient classical or quantum algorithm is known.

The LWE problem has a property that no other cryptographic hardness assumption currently possesses: a worst-case to average-case reduction. Breaking RSA requires only that factoring specific numbers is hard; breaking LWE in a random instance is provably as hard as solving the hardest possible lattice problem in the worst case. This means that even if an attacker is extremely lucky in their choice of problem instance, the hardness guarantee still holds — a much stronger security foundation than RSA.

Practical implementations use Ring-LWE or Module-LWE, which add algebraic structure (working in polynomial rings rather than integer vectors) to improve efficiency while retaining provable worst-case hardness. ML-KEM and ML-DSA are Module-LWE schemes; their “module” structure lets them use smaller parameters than plain LWE while keeping security proofs intact.

The NIST Standards: What Was Standardised and Why

ML-KEM (FIPS 203) — formerly CRYSTALS-Kyber

ML-KEM is a Key Encapsulation Mechanism — the replacement for ECDH and DH. It allows two parties to establish a shared secret without a prior shared key:

1. The recipient generates a public/private key pair and publishes the public key.
2. The sender generates a random key, encapsulates it using the recipient’s public key, and sends the ciphertext.
3. The recipient decapsulates with their private key to recover the shared secret.

The security rests on Module-LWE: without the private key, recovering the encapsulated key from the ciphertext requires solving LWE. ML-KEM comes in three security levels: ML-KEM-512 (comparable to AES-128), ML-KEM-768 (AES-192), and ML-KEM-1024 (AES-256). For most applications, ML-KEM-768 is recommended.

ML-DSA (FIPS 204) — formerly CRYSTALS-Dilithium

ML-DSA is a digital signature scheme — the replacement for ECDSA and RSA-PSS for signing certificates, software, and messages. It is based on the Module-LWE and Module-SIS (Short Integer Solution) problems, using a “Fiat-Shamir with aborts” construction to achieve security against adaptive chosen-message attacks.

ML-DSA signatures are significantly larger than ECDSA signatures (2–4 KB vs 71 bytes), which has implications for TLS certificate chains, firmware update packages, and any protocol where signature bandwidth matters.

SLH-DSA (FIPS 205) — formerly SPHINCS+

SLH-DSA is a stateless hash-based signature scheme — the most conservative option in the NIST portfolio. Its security assumption is minimal: if SHA-256 or SHAKE-256 resists preimage and second-preimage attacks (which they do, with 2¹²⁸ quantum resistance under Grover), then SLH-DSA is secure against all known attacks, classical or quantum.

The construction uses a hypertree of WOTS+ (Winternitz One-Time Signature) instances, where each node’s public key is a Merkle root of the keys below it. The simplicity of the security assumption comes at a cost: SLH-DSA signatures range from 8 KB to 50 KB depending on parameter choice, and signing is slow. It is recommended for applications where signature size is tolerable and security minimalism is paramount — signing firmware images, for example, where a smaller signature is not worth the risk of relying on lattice assumptions.

FN-DSA (FIPS 206, draft) — formerly FALCON

FN-DSA is a compact lattice signature scheme based on NTRU lattices, producing signatures of ~666–1280 bytes — significantly smaller than ML-DSA. The signing algorithm uses fast Fourier sampling over Gaussian distributions on NTRU lattices, which achieves high efficiency but requires careful implementation to avoid floating-point side-channel attacks. FIPS 206 was published in draft form and is expected to be finalised in 2025.

The Cautionary Tale: SIKE’s 2022 Collapse

Among the NIST round 3 finalists was SIKE (Supersingular Isogeny Key Encapsulation) — an algorithm based on the presumed hardness of finding isogenies between supersingular elliptic curves. SIKE had spent four years in NIST evaluation, survived three rounds of scrutiny, and was considered a promising candidate due to its very small key sizes.

On 30 July 2022, Wouter Castryck and Thomas Decru posted a preprint showing a classical polynomial-time attack on SIKE. Running the attack on a single core of a laptop computer took 62 minutes to break SIKE’s highest security level. One week later, NIST eliminated SIKE from the competition.

The attack exploited the specific mathematical structure of supersingular isogeny graphs — a “glue-and-split” theorem from classical algebraic geometry that nobody had applied to the problem before. SIKE’s security had rested on the assumption that no such technique existed. The assumption was wrong.

The collapse of SIKE carries three lessons. First, novel mathematical assumptions in cryptography carry genuine risk; the more recent the problem’s study, the greater the chance of an undiscovered attack. Second, the NIST evaluation process, despite its rigor, cannot guarantee that a finalist has no classical vulnerability. Third, the diversity of the NIST portfolio — lattice, hash-based, and code-based algorithms, not all isogeny-based — means that a single breakthrough does not compromise the entire migration effort.

Key and Signature Sizes: The Cost of Quantum Resistance

The size increase is the most immediate engineering challenge in the PQC migration. A TLS 1.3 handshake today carries two ECDSA signatures (~71 bytes each) in the certificate chain. With ML-DSA, the same handshake carries signatures of ~3,293 bytes each — adding approximately 6 KB to every new TLS connection. For constrained environments (IoT devices with limited RAM, satellite links with low bandwidth, real-time control systems) this overhead is not trivial.

Hybrid schemes mitigate this by combining classical and post-quantum algorithms: the handshake carries both an ECDH key share and an ML-KEM encapsulation. The session key is derived from both; security holds if either component is secure. This is the approach deployed by Cloudflare, Google Chrome, and major browsers since 2023 for key exchange — ECDH × 25519 + ML-KEM-768 in a hybrid construction. Hybrid signatures (ECDSA + ML-DSA) are more complex and less deployed, but work is underway in IETF standards.

Harvest Now, Decrypt Later: Why This Is Already Urgent

The urgency of post-quantum migration is not driven by the quantum computer existing — it doesn’t. It is driven by the fact that encrypted data collected today can be stored and decrypted in the future. This is the harvest now, decrypt later (HNDL) threat.

Consider a diplomatic cable encrypted with RSA-2048 in 2025, intended to remain classified for 30 years. If a state actor intercepts and stores that ciphertext today, and a CRQC becomes available in 2035, the cable is decrypted a decade before its classification period ends. The same applies to medical records, financial transaction histories, proprietary intellectual property, and any other long-lived sensitive data.

This drives migration timelines that have nothing to do with the current state of quantum hardware:

• US NSA (CNSA Suite 2.0): required transition of national security systems to PQC algorithms by 2030.
• CISA / NIST: recommends beginning PQC migration now, especially for systems with long data lifetimes.
• EU / ENISA: similar guidance, with particular urgency for critical infrastructure.
• GCHQ / NCSC (UK): recommends hybrid schemes for key exchange immediately while signature migration plans are developed.

The Migration Path: TLS, PKI, and What Changes

The most immediate impact is on TLS, which secures essentially all web traffic. TLS 1.3 uses ECDH for key exchange and ECDSA or RSA for authentication (certificate signatures). Both components must be replaced:

Key exchange: ML-KEM replaces ECDH. Hybrid ML-KEM-768 + X25519 is already deployed by Cloudflare, Google, and Apple in production TLS. The IETF standardised this hybrid in RFC 9180 and related drafts. The key exchange change is backward-compatible and already in wide deployment.

Certificate signatures: ML-DSA and FN-DSA replace ECDSA and RSA in X.509 certificates. This is more complex: the entire PKI (Public Key Infrastructure) must transition, meaning certificate authorities, web servers, intermediate CAs, and client trust stores must all support PQC signature verification. Certificate chains with ML-DSA signatures are 4–10× larger than current chains, requiring TLS implementation changes and potentially increasing handshake latency.

Code signing and firmware: software update systems, secure boot chains, and firmware verification must transition to ML-DSA or SLH-DSA. The conservative choice — SLH-DSA — is appropriate here since signatures are verified infrequently and the security assumption is minimal.

SSH and VPN: OpenSSH has supported ML-KEM key exchange since version 9.0 (released 2022). WireGuard, IPsec, and OpenVPN implementations are in various stages of PQC integration.

Post-Quantum Is Not Quantum Cryptography

One important clarification: post-quantum cryptography is entirely classical software running on classical computers. It does not use quantum mechanics. Its security is computational — based on the hardness of mathematical problems — not information-theoretic.

Quantum Key Distribution (QKD), such as the BB84 protocol covered separately in this series, takes a different approach: it uses quantum mechanics to distribute cryptographic keys with information-theoretic security guarantees. QKD is unconditionally secure under its physical assumptions (quantum mechanics is correct, the channel is authenticated) but requires specialised hardware, has severe distance limitations, and does not currently integrate with existing internet infrastructure.

PQC and QKD address the same threat — quantum computers breaking key exchange — through fundamentally different means. PQC is the near-term practical solution; QKD is a long-term research direction with different security properties and infrastructure requirements. The NIST PQC standards are what will be deployed in browsers, servers, and cryptographic libraries over the next decade. QKD, despite its theoretical elegance, is not a practical substitute at internet scale.

The Honest Assessment

The NIST PQC standards represent the most significant change to deployed cryptography since the adoption of AES in 2001. Unlike that transition — which required changing a symmetric cipher and was relatively straightforward — this transition requires replacing the mathematical foundations of public-key cryptography that have been in use for nearly fifty years.

The standards are not the end of the work. Lattice cryptography has existed for roughly twenty years; its security assumptions, while well-studied, have not been subjected to the four decades of scrutiny that RSA has endured. New classical attacks on LWE remain possible, though the worst-case hardness reduction provides stronger theoretical assurance than RSA ever did. The SIKE collapse demonstrates that even carefully evaluated candidates can fall to novel attacks.

The appropriate response is what the NIST process itself embodies: multiple independent mathematical assumptions, conservative parameter sizes, hybrid schemes during the transition, and ongoing cryptanalytic research. The migration to post-quantum cryptography is not a one-time event — it is the beginning of a period in which cryptographic agility (the ability to swap algorithms without breaking systems) becomes a design requirement rather than an afterthought.

The quantum computer has not arrived. The damage it will do to current cryptography is already determined. The window to migrate closes not when the quantum computer arrives, but when adversaries with HNDL collections gain access to one.

Sources & Further Reading

1. NIST. FIPS 203: Module-Lattice-Based Key-Encapsulation Mechanism Standard. Federal Information Processing Standards Publication 203 (2024)
2. NIST. FIPS 204: Module-Lattice-Based Digital Signature Standard. Federal Information Processing Standards Publication 204 (2024)
3. NIST. FIPS 205: Stateless Hash-Based Digital Signature Standard. Federal Information Processing Standards Publication 205 (2024)
4. Oded Regev. On Lattices, Learning with Errors, Random Linear Codes, and Cryptography. Proc. 37th ACM Symposium on Theory of Computing (STOC); Journal of the ACM 56(6) (2005)
5. Wouter Castryck, Thomas Decru. An Efficient Key Recovery Attack on SIDH. EUROCRYPT 2023; IACR ePrint 2022/975 (2023)

Discussion

← All articles