Post-Quantum Cryptography: How Do We Protect the Internet?

The previous post ended on an uncomfortable fact: a large enough quantum computer would break RSA and elliptic-curve cryptography, the trust layer under HTTPS, VPNs, PKI and digital signatures. Recorded traffic is already at risk ("harvest now, decrypt later"), and migrations take years.

This post is the good news. The replacement already exists. In August 2024, after an eight-year public competition, the US National Institute of Standards and Technology (NIST) published the first three post-quantum cryptography standards: ML-KEM, ML-DSA and SLH-DSA. NIST is encouraging organisations to begin migrating now. And if you're reading this in a current browser, there's a good chance the connection to this page is already protected by one of them.

While writing this post, I ran a simple check from an ordinary Windows laptop with OpenSSL 3.5 against two of the largest sites on the Internet:

echo | openssl s_client -connect www.google.com:443 -brief

Protocol version: TLSv1.3
Ciphersuite: TLS_AES_256_GCM_SHA384
Peer certificate: CN=www.google.com
Signature type: ecdsa_secp256r1_sha256
Verification: OK
Negotiated TLS1.3 group: X25519MLKEM768

That last line is post-quantum cryptography, live, by default. The line two above it (an elliptic-curve signature) is the part that hasn't moved yet. Between them, those two lines tell you exactly where the world is in this migration, and this post explains both.

The Migration at a Glance

Remember from the previous post that public-key cryptography does two jobs: agreeing keys (so data can be encrypted) and signing (so identities and software can be trusted). The three standards split along exactly those lines:

Symmetric encryption (AES) and hashes (SHA-2, SHA-3) stay. They only need larger sizes, as explained in the previous post.

What Makes an Algorithm "Post-Quantum"?

Shor's algorithm works because factoring and discrete logarithms have a hidden repeating structure (a period) that quantum interference can find. Post-quantum algorithms are built on problems with no such structure, where decades of research have found no efficient attack, classical or quantum.

An intuition for lattices

The two main standards use lattices, so it's worth having a picture of them.

Imagine solving a set of simple equations, but every answer has had a small random error added to it. With exact answers, ordinary school algebra solves the system instantly. With small errors sprinkled in, and with hundreds of unknowns, the problem becomes extraordinarily hard: you can't tell which combination of small errors produced what you see. That's the learning with errors (LWE) problem, and ML-KEM and ML-DSA are built on a structured version of it.

Geometrically, it's like being given a point near a regular grid of points in hundreds of dimensions and asked which grid point is closest. In two dimensions you'd just look. In 768 dimensions, with a deliberately skewed grid, no known algorithm, classical or quantum, does much better than an exponential search.

ML-KEM (FIPS 203): The New Key Exchange

What a KEM does

Today, TLS uses Diffie-Hellman: both sides contribute a public value and compute the same secret. ML-KEM is a key encapsulation mechanism (KEM), which works slightly differently:

You can do all three steps yourself with OpenSSL 3.5 or later:

# 1. Key generation (the client)
openssl genpkey -algorithm ML-KEM-768 -out kem.pem
openssl pkey -in kem.pem -pubout -out kem_pub.pem
 
# 2. Encapsulation (the server, using only the public key)
openssl pkeyutl -encap -pubin -inkey kem_pub.pem -out ciphertext.bin -secret server_secret.bin
 
# 3. Decapsulation (the client, using the private key)
openssl pkeyutl -decap -inkey kem.pem -in ciphertext.bin -secret client_secret.bin
 
cmp server_secret.bin client_secret.bin && echo "shared secrets match"

On the test machine, the ciphertext was 1,088 bytes, both secrets were 32 bytes, and they matched.

Parameter sets

ML-KEM-768 is the general-purpose default, and it's the one used in today's hybrid TLS. Security-focused government profiles, such as the NSA's CNSA 2.0, specify ML-KEM-1024.

Is it fast?

Yes, and that surprises people. On the same laptop, OpenSSL's built-in benchmark gave:

ML-KEM's cost isn't speed; it's size. An X25519 public share is 32 bytes; an ML-KEM-768 public key is 1,184. That's still small enough for almost every protocol, but it adds about a kilobyte in each direction to a handshake, which matters more than you'd think (see the hybrid section below).

ML-DSA (FIPS 204): The New General-Purpose Signature

ML-DSA is the default replacement for RSA and ECDSA signatures: in certificates, in TLS handshakes, in code signing, in documents and in tokens. It's also lattice-based, and its signing process involves a clever trick: it generates a candidate signature, checks whether that signature would leak anything about the private key, and if so throws it away and tries again ("rejection sampling"). That's why signing is a little slower and less predictable than verifying.

Compare that with an ECDSA P-256 public key of 64 bytes and a signature of about 72. ML-DSA signatures are roughly 30 to 60 times bigger. You can see it with real certificates:

openssl genpkey -algorithm ML-DSA-65 -out mldsa.pem
openssl req -x509 -new -key mldsa.pem -subj "/CN=pq-test.contoso.local" -days 365 -outform DER -out mldsa.der

On the test machine, an otherwise identical self-signed certificate came out at 408 bytes with ECDSA P-256, 805 bytes with RSA-2048, and 5,534 bytes with ML-DSA-65. The benchmark showed about 1,270 ML-DSA-65 signatures and 6,550 verifications per second, against 3,371 signatures per second for RSA-2048: fast enough for almost any use, with optimised implementations faster still.

SLH-DSA (FIPS 205): The Conservative Backup

SLH-DSA is a different kind of insurance. It's built entirely from hash functions, the most studied and trusted building blocks in cryptography. If you believe SHA-256 is secure, you can believe SLH-DSA is secure; it doesn't depend on lattices at all. That matters because lattice cryptography is younger, and nobody wants every signature in the world to rest on a single mathematical assumption.

The price is size and speed:

Three and a half signatures per second would be useless for a web server, but it's perfectly fine for things that are signed rarely and trusted for a long time: root CA certificates, firmware images, boot loaders and long-term archives. Verification is fast (about 3,400 per second), which is what devices do most often.

Why Three Standards, and More Coming?

NIST deliberately didn't pick just one. Cryptographic history is full of algorithms that looked strong until someone found a clever attack, and the post-quantum competition itself had two dramatic examples. In 2022, SIKE, an isogeny-based finalist candidate, was broken by a classical attack that ran on a single laptop in about an hour. The same year, Rainbow, a multivariate signature finalist, was also broken. Neither involved a quantum computer.

That's why the plan relies on diversity:

• ML-KEM and ML-DSA (lattices) for everyday use.
• SLH-DSA (hashes) as a signature backup based on completely different maths.
• FN-DSA (from Falcon), another lattice signature with smaller signatures but trickier implementation, is being standardised as FIPS 206.
• HQC, a code-based KEM, was selected in March 2025 as a backup to ML-KEM, in case lattices ever turn out to be weaker than expected.

It's also why most deployments today use hybrid cryptography.

Bigger Keys, Real Consequences

Key exchange grows by about 2 KB per handshake, which almost every network handles easily. Signatures are the hard part, because a TLS handshake doesn't carry just one. A typical server sends a leaf certificate and an intermediate certificate (each containing a public key and a signature), then signs the handshake itself:

Fourteen kilobytes doesn't sound like much, but many servers can only send about 14 KB before waiting for the client to acknowledge (TCP's initial congestion window). Real certificates also carry extensions and Certificate Transparency proofs. So moving the whole Web PKI to ML-DSA could add a network round trip to many connections, which is why signature migration on the public Web is moving more slowly and why researchers and the IETF are working on ideas such as certificate compression, smarter trust anchor negotiation and new certificate designs.

Inside an enterprise the trade-off is different: a Wi-Fi authentication or VPN handshake happens far less often than a web page load, and you control both ends.

Hybrid Cryptography: Belt and Braces

Post-quantum algorithms are new, and their implementations are newer. So instead of switching from classical to post-quantum in one step, most deployments today combine both:

The logic is simple: if a future quantum computer breaks X25519, ML-KEM still protects the session. If someone finds a flaw in ML-KEM (or its implementation), X25519 still protects it. The connection is safe as long as either one holds.

Hybrid key exchange is already everywhere

• Browsers: Chrome, Edge and Firefox negotiate X25519MLKEM768 by default, and Apple has added hybrid post-quantum TLS to its platforms.
• Large websites and CDNs: Google, Cloudflare and other major providers support it, so a large share of all HTTPS traffic is already protected against harvest now, decrypt later.
• Libraries and tools: OpenSSL 3.5 (April 2025) includes ML-KEM, ML-DSA and SLH-DSA, and offers the hybrid group by default, as the test above showed. OpenSSH uses a hybrid post-quantum key exchange by default.
• Messaging: Signal (PQXDH) and Apple iMessage (PQ3) added post-quantum key agreement in 2023 and 2024.
• Operating systems: Microsoft has added ML-KEM and ML-DSA to Windows' cryptography libraries, so applications can start using them.

There's one practical lesson from the rollout: when browsers first enabled hybrid key exchange, the larger first message (the TLS ClientHello) broke some old firewalls, proxies and load balancers that assumed it would fit in a single packet. If you run TLS-inspecting middleboxes, test them with post-quantum handshakes now.

You can check any server yourself:

echo | openssl s_client -connect your-server.example.com:443 -groups X25519MLKEM768 -brief

If the output says Negotiated TLS1.3 group: X25519MLKEM768, that endpoint supports hybrid key exchange. If the connection fails, it doesn't, and it's a candidate for your migration list.

Hybrid signatures are less settled

For signatures, "hybrid" means attaching both a classical and a post-quantum signature, or using composite certificates whose key and signature combine both algorithms. The IETF is standardising composite ML-DSA for X.509, but the approach is still being debated, partly because it makes already-large certificates even larger. Expect a mix of composite, dual-chain and pure post-quantum designs while this settles.

What This Means for PKI

This is where the post-quantum migration meets this site's PKI series, and the companion post Quantum-Safe PKI: What Happens to Certificates in the Quantum Era? goes much deeper, with a working post-quantum CA lab. The key insight is that the migration has two very different speeds:

• Key exchange migration mostly doesn't touch your PKI. Hybrid ML-KEM in TLS works with today's RSA and ECDSA certificates. It's a software upgrade to clients, servers and middleboxes, and it's the part that fixes harvest now, decrypt later.
• Signature migration is a PKI project. New algorithms in certificates mean new CA keys, new hierarchies, new templates, and every relying party that checks a certificate (browsers, RADIUS servers, VPN gateways, applications, devices) must understand them.

For an enterprise PKI like the one built in the PKI implementation lab, the practical consequences are:

Where PQC Lands in the Stack

The pattern is clear: much of the migration arrives through vendors. Your job is to know where cryptography is used, make sure updates can actually be deployed, and push vendors for roadmaps.

The Timelines

The details differ, but the message is the same everywhere: plan now, protect the highest-risk systems by about 2030, finish by about 2035. For a large organisation, nine years is not a long time.

A Practical Migration Plan

Common mistakes

Quick Recap

• Post-quantum cryptography is new mathematics that runs on ordinary computers; it's not quantum hardware.
• NIST published three standards in 2024: ML-KEM (FIPS 203) for key exchange, ML-DSA (FIPS 204) for signatures, and SLH-DSA (FIPS 205) for conservative hash-based signatures.
• ML-KEM is as fast as today's key exchange, just bigger: about 2 KB per handshake.
• Post-quantum signatures are much bigger: an ML-DSA-65 certificate measured 5,534 bytes against 408 for ECDSA, which is why signature migration is slower.
• Hybrid key exchange (X25519MLKEM768) is already deployed in browsers and major websites, and protects against harvest now, decrypt later.
• For PKI, plan a parallel post-quantum hierarchy, check every relying party, and watch hardware key storage and product support.
• Timelines converge on about 2030 for high-risk systems and 2035 for everything.
• Start now: inventory, prioritise, build crypto-agility, turn on hybrid key exchange, then migrate signatures.

What's Next on the Learning Path

Stage 10, Quantum Networking, turns from defending against quantum computers to using quantum physics itself: quantum key distribution, teleportation, entanglement distribution and the idea of a quantum internet, and how they compare with the post-quantum cryptography in this post. The full 11-stage path is listed at the end of the beginner's guide.