Replacing TLS Certificates with Post-Quantum Alternatives

TLS certificates are the most widely deployed public-key infrastructure on the planet. Every HTTPS connection, every API call, every email server handshake, every VPN tunnel relies on TLS certificates to authenticate servers and establish encrypted sessions. There are approximately 800 million active TLS certificates in use today, and every one of them is built on RSA or elliptic curve cryptography that a quantum computer will break.

Replacing this infrastructure is not optional. It is a mathematical certainty that RSA and ECC will be broken by Shor's algorithm running on a sufficiently powerful quantum computer. The only questions are when the quantum computer arrives and whether your TLS infrastructure will be ready.

How TLS Uses Public-Key Cryptography

To understand what needs to change, you need to understand how TLS uses public-key cryptography today. A TLS handshake involves two distinct cryptographic operations: key exchange and authentication.

Key exchange establishes a shared secret between the client and server. In modern TLS 1.3, this is done using ephemeral Diffie-Hellman key exchange, typically with ECDHE (Elliptic Curve Diffie-Hellman Ephemeral) using the P-256 or X25519 curves. The shared secret is used to derive the symmetric keys that encrypt the actual application data. Breaking the key exchange means an adversary can derive the session keys and decrypt all application data.

Authentication proves the server's identity to the client. The server presents a certificate containing its public key, signed by a certificate authority (CA). The client verifies the CA's signature to establish trust. The server then proves it possesses the corresponding private key. In TLS 1.3, authentication uses either RSA-PSS or ECDSA signatures. Breaking the authentication means an adversary can impersonate legitimate servers.

These two operations have different threat timelines. Key exchange is vulnerable to harvest-now-decrypt-later: an adversary who records an ECDHE key exchange today can break it with a quantum computer later and decrypt the session. Authentication is vulnerable to real-time attack: once a quantum computer is available, an adversary can forge certificates in real time, enabling man-in-the-middle attacks.

The Post-Quantum Replacements

ML-KEM for Key Exchange (FIPS 203)

ML-KEM (Module Lattice-based Key Encapsulation Mechanism), standardized as FIPS 203, replaces ECDHE for key exchange. ML-KEM is based on the Module Learning With Errors (MLWE) problem, which is believed to be hard for both classical and quantum computers.

ML-KEM uses a different paradigm than Diffie-Hellman. Instead of both parties contributing to the shared secret, ML-KEM uses key encapsulation: the server generates a keypair, the client uses the server's public key to encapsulate a shared secret, and the server decapsulates it using its private key. The result is the same -- both parties share a secret -- but the mathematical foundation is quantum-resistant.

ML-KEM comes in three parameter sets. ML-KEM-512 provides NIST Level 1 security with 800-byte public keys and 768-byte ciphertexts. ML-KEM-768 provides Level 3 security with 1,184-byte public keys and 1,088-byte ciphertexts. ML-KEM-1024 provides Level 5 security with 1,568-byte public keys and 1,568-byte ciphertexts.

The key size increase is significant compared to ECDHE (32 bytes for X25519), but it is manageable. A TLS handshake that currently exchanges approximately 500 bytes of key material will exchange approximately 2,500 bytes with ML-KEM-768. This adds roughly 2 KB to the handshake, which at modern network speeds adds less than a millisecond of latency.

ML-DSA for Signatures (FIPS 204)

ML-DSA, standardized as FIPS 204, replaces RSA and ECDSA for digital signatures. ML-DSA-44 provides NIST Level 2 security with 1,312-byte public keys and 2,420-byte signatures. ML-DSA-65 provides Level 3 with 1,952-byte public keys and 3,293-byte signatures. ML-DSA-87 provides Level 5 with 2,592-byte public keys and 4,595-byte signatures.

For comparison, an RSA-2048 signature is 256 bytes, and an ECDSA P-256 signature is 64 bytes. ML-DSA signatures are an order of magnitude larger. In a TLS handshake, the server typically sends two signatures: its own and the CA's. With ML-DSA-65, this adds approximately 6 KB.

SLH-DSA for Defense in Depth (FIPS 205)

SLH-DSA, standardized as FIPS 205, provides hash-based signatures independent of lattice assumptions. Its security depends only on the collision resistance of the underlying hash function (SHA-256 or SHAKE-256), making it a valuable hedge against future lattice cryptanalysis advances.

SLH-DSA-SHA2-128f produces 17,088-byte signatures. This makes it less suitable for every TLS handshake, but valuable for certificate chain signatures where bandwidth cost is paid once during certificate issuance rather than on every connection.

The Hybrid Approach

NIST, the IETF, and every major browser vendor recommend a hybrid approach for the transition. Hybrid TLS combines classical and post-quantum algorithms in a single handshake, ensuring security as long as either algorithm family is unbroken.

For key exchange, hybrid mode concatenates an ECDHE key share with an ML-KEM key share. The final session key derives from both shared secrets. If ML-KEM has a flaw, ECDHE still provides classical security. If a quantum computer breaks ECDHE, ML-KEM still provides quantum security.

Chrome already supports hybrid key exchange (X25519Kyber768) in production. Firefox and Safari are deploying support. On the server side, OpenSSL 3.x, BoringSSL, and AWS-LC all support hybrid ML-KEM. The ecosystem is ready for hybrid deployment today.

Migration Path: Phase by Phase

Phase 1: Enable Hybrid Key Exchange (Weeks 1-4)

The highest priority is enabling hybrid key exchange. This protects against harvest-now-decrypt-later for all new TLS sessions. For most web servers, this is a configuration change -- updating the TLS library and adding the hybrid cipher suite.

For cloud-hosted applications, the change may be simpler still. AWS ALB, Cloudflare, and Google Cloud Load Balancing all support hybrid TLS. Enabling it is a configuration flag.

Phase 2: Prepare Certificate Infrastructure (Months 1-3)

Post-quantum certificates require coordination with certificate authorities. Select a CA that issues PQ certificates, generate PQ keypairs, and configure servers to present them. For organizations operating their own internal CA, update the CA software to support ML-DSA key generation and certificate signing.

Audit certificate management processes: ACME/certbot needs PQ key type support, certificate pinning policies need updating, and certificate transparency logs need to accept PQ entries.

Phase 3: Deploy Post-Quantum Certificates (Months 3-6)

Deploy PQ certificates alongside classical certificates. Servers present both chains during handshake. PQ-capable clients use the PQ certificate; others fall back to classical. Start with internal services, then expand to external-facing services.

Phase 4: Add Post-Quantum Attestation Layer (Parallel)

In parallel with TLS migration, add a post-quantum attestation layer for application data. While PQ TLS protects the transport, PQ attestation protects the data itself. Every API response can receive an H33-74 attestation providing three-family post-quantum proof of integrity.

Phase 5: Deprecate Classical-Only TLS (Months 6-12)

Once PQ TLS is deployed across all services, begin deprecating classical-only cipher suites following the same pattern used for TLS 1.0, TLS 1.1, and SHA-1 certificates.

Certificate Size and Handshake Impact

The most practical concern with PQ TLS is certificate and handshake size increase.

Classical (ECDSA P-256): Two certificates totaling approximately 2,200 bytes with 64-byte signatures.

Post-Quantum (ML-DSA-65): Two certificates totaling approximately 12,600 bytes with 3,293-byte signatures.

Hybrid (ECDSA + ML-DSA-65): Approximately 14,700 bytes total -- roughly seven times the classical chain.

On a 100 Mbps connection, this adds 0.1 milliseconds. On a 10 Mbps mobile connection, 1 millisecond. On a 1 Mbps connection, 12 milliseconds. For most applications, this is acceptable. Optimization techniques include certificate compression (TLS 1.3), cached certificate chains, and session resumption.

What Cannot Wait

The most important message: hybrid key exchange cannot wait. Every TLS session using classical-only key exchange contributes to the harvest-now-decrypt-later stockpile. Hybrid key exchange eliminates this risk for all new sessions and can be enabled with a configuration change.

Certificate migration can proceed on a longer timeline because authentication forging requires a real-time quantum computer. Key exchange is the urgent priority because it is vulnerable to offline, retroactive attack.

Enable hybrid key exchange today. Plan the certificate migration. Deploy the attestation overlay in parallel. The first step takes days, not years.