Why Post-Quantum TLS Can’t Just Swap in New Algorithms

The TLS protocol that protects most Internet traffic has relied on the same basic architecture since SSL 1.0 appeared in 1994: a key exchange authenticated by digital signatures. Over the years, RSA gave way to Diffie-Hellman and Elliptic-curve Diffie-Hellman for key exchange, and signatures moved from RSA toward ECDSA and Ed25519. These shifts to elliptic curve cryptography brought meaningful speed and bandwidth benefits.

Quantum computers threaten this architecture. Cloudflare and Google have already run a large-scale experiment integrating post-quantum key exchanges into TLS stacks and Chrome Canary clients, measuring feasibility and performance. But replacing both the key exchange and the signature with post-quantum primitives is not straightforward. The mathematical objects used by post-quantum algorithms are larger than those used by elliptic curves or RSA, so public keys, signatures, and key exchange material all grow substantially.

The problem is particularly acute for signatures. Post-quantum signature schemes are not only larger than their classical counterparts; they are also significantly more expensive than post-quantum key encapsulation mechanisms (KEMs). This article examines a proposal called KEMTLS, which replaces handshake signatures with KEM-based key exchanges to reduce the size and computational cost of a fully post-quantum TLS 1.3 handshake.

The Cost of a Straightforward Post-Quantum Handshake

TLS 1.3, standardized in August 2018, brought the handshake down to one round trip and introduced several security improvements. Its handshake proceeds in three phases: parameter negotiation, key exchange, and authentication. The key exchange phase establishes shared keying material; everything after that phase is encrypted. The authentication phase proves possession of the server’s (and optionally the client’s) private key.

Past experiments introduced post-quantum algorithms into the handshake by advertising them in the supported_groups and key_share extensions, using KEMs to generate shared secrets. Those approaches provide what is often called “transitional security”: they protect confidentiality against quantum adversaries but do not address quantum-resistant authentication. Using post-quantum signatures for authentication is possible, but the size penalty is severe.

Consider a typical TLS 1.3 handshake using X25519 and RSA-2048. The public keys, certificate, handshake signature, and certificate chain total roughly 1,376 bytes. Replacing X25519 with the post-quantum KEM Kyber512 and RSA with the post-quantum signature Dilithium II—two of the more efficient submissions to the NIST post-quantum standardization process—raises that to 10,036 bytes based on the round-2 parameter sets. Most of that increase comes from the signature algorithm, not the key exchange.

KEMTLS: Authenticating Through Key Exchange

Signatures are not the only way to prove possession of a private key. Protocols such as Signal, the Noise framework, and WireGuard authenticate through key exchanges, but they require long-term key material to be known in advance. The OPTLS proposal by Krawczyk and Wee showed how to authenticate the TLS handshake without signatures using a non-interactive key exchange (NIKE), but the only reasonably efficient post-quantum NIKE construction is CSIDH, whose security remains debated.

KEMTLS, designed by Peter Schwabe, Douglas Stebila, and Thom Wiggers and presented at ACM CCS 2020, takes a different approach. It replaces the handshake signature with an additional post-quantum KEM key exchange. The server’s certificate contains a long-term KEM public key. By carefully ordering the key derivation steps, the server can decrypt the client’s messages only if it holds the corresponding private key, providing implicit authentication without a handshake signature.

KEMTLS still requires certificate authorities to sign the long-term KEM keys with their own signatures, so it does not eliminate signatures from the trust model entirely. During the handshake itself, application data is implicitly rather than explicitly authenticated, and downgrade resilience and forward secrecy are slightly weaker until the handshake completes. Once the full handshake finishes, those properties are restored.

The size savings are substantial. Using Kyber512 and Dilithium II in the same example handshake, KEMTLS transmits 8,344 bytes instead of 10,036—a reduction that holds even for algorithm pairs like NTRU and Falcon, where the size gap is less pronounced. Because KEM operations are also computationally lighter than signing operations, the efficiency gain is amplified in practice.

Implementing KEMTLS in Go

Cloudflare implemented the full KEMTLS handshake in Go’s TLS 1.3 stack as part of an effort to demonstrate that TLS can be fully post-quantum safe. The work proceeded in several stages:

  • Cloning and maintaining a fork of Go to integrate post-quantum algorithms.
  • Implementing the post-quantum algorithms in Cloudflare’s cryptographic library, CIRCL.
  • Using delegated credentials rather than requiring certificate authorities to issue certificates with long-term post-quantum KEM keys. A delegated credential is a short-lived key that the certificate’s owner has authorized for use in TLS.
  • Adding mutual authentication (client and server) via delegated credentials for the authentication process.

The implementation required changes to how Go handles the TLS 1.3 handshake and its key schedule, though the process was straightforward. The server’s handshake flow was interrupted after sending its certificate (sendServerCertificate()) to insert the KEMTLS-specific messages, and the client side was extended accordingly. Only one new configuration constant was added: serverConfig.ClientAuth = RequestClientKEMCert, which lets a server request a client KEMTLS certificate.

The implementation is designed to be transparent. If a delegated credential or certificate holds a public key for a supported post-quantum KEM, the handshake proceeds with KEMTLS automatically. If the server requests client authentication via KEMTLS, the handshake uses that path as well. The next step is running this code on Cloudflare’s infrastructure to measure real-world performance.