Making protocols post-quantum

Post-Quantum Protocols: Fitting New Cryptography into Old Shapes

Public-key cryptography rests on a small set of mathematical trapdoors: discrete logarithms and integer factorization. For decades, that has been enough. Protocols like TLS, DNSSEC, and SSH bolt authentication and key exchange onto their message flows, and the cost is negligible — keys and signatures are a few dozen bytes, operations take microseconds.

Quantum computers break that assumption. They do not break encryption or signatures in general; they break the specific algebraic structures underneath RSA, Diffie-Hellman, and elliptic-curve schemes. The replacements under consideration in the NIST post-quantum standardization effort do not behave like their predecessors. Some are fast but large; others are compact but slow. Some lack properties protocols have quietly come to depend on. Swapping "PQ-" in front of algorithm names is not enough.

TLS is a good case study, since it is the most widely deployed cryptographic protocol on the Internet. The question is not whether TLS can be made post-quantum — it can, in principle — but what it costs and whether the standard shapes of the protocol still make sense.

The Easy Part: Exchanging Keys

TLS 1.3 uses ephemeral Elliptic Curve Diffie-Hellman for key exchange, authenticated by a signature over the handshake. The signature is verified against a public key in the server's certificate, which is itself validated by a chain of certificates signed by certificate authorities the client trusts.

Replacing the ECDH key exchange is conceptually trivial: swap in a post-quantum Key Encapsulation Mechanism (KEM). The protocol flow does not change. But the choice of KEM matters because TLS exchanges keys for every connection, every time. The bytes of public key and ciphertext go over the wire on each handshake, and the key generation, encapsulation, and decapsulation speeds determine server load.

The round-three NIST candidates span a wide range. At a security level comparable to AES-128, the finalists — Kyber, SABER, and NTRU — and the alternates — SIKE, BIKE, FrodoKEM, HQC, and NTRU Prime — differ by orders of magnitude in both size and speed.

In practice, the trade-off resolves quickly for TLS. SIKE's tiny keys cannot compensate for its slow operations; the lattice-based finalists add roughly 1,400–2,000 bytes per handshake over current ECDH, which is an acceptable price. Pick Kyber, SABER, or NTRU, and move on — with the caveat that those measurements come from AVX2-optimized code on a modern laptop. Embedded devices, smart cards, and other constrained platforms have different constraints: code size, side channels, power consumption, and execution time all need separate evaluation.

Signatures: Where the Real Pain Starts

Signatures are harder. Unlike KEMs, which are ephemeral per connection, certificates are long-lived. Key generation happens offline, once per certificate, so it matters less. What matters is what gets transmitted: public keys and signatures appear in the server's handshake signature, in every certificate in the chain, in OCSP Stapling, and in Certificate Transparency logs. A typical TLS handshake carries several signatures and several public keys.

Among the NIST round-three signature finalists — Dilithium, Falcon, and Rainbow — the size differences are stark. Using Dilithium everywhere in the handshake means around 17 KB of signatures and public keys. Falcon gets that down to around 6 KB, but Falcon relies on 64-bit floating-point arithmetic in constant time, which is problematic on embedded devices. Rainbow, GeMSS, and SPHINCS+ each carry their own deployment burdens.

No single scheme fits everywhere. A more realistic approach is to mix them by role. Rainbow signatures are only 66 bytes — barely larger than 64-byte ed25519 signatures and much smaller than RSA-2048's 256 bytes — which makes Rainbow attractive for root certificates, OCSP staples, and CT logs, where only the signature is transmitted and key sizes do not matter as much. Falcon is a reasonable choice for intermediate certificates, where both public key and signature travel. The client only verifies these, so Falcon's signing speed is not a concern.

Rethinking Authentication with KEMs

The split between fast-but-large and small-but-slow algorithms is uncomfortable. It may justify a deeper change: using key exchange itself for authentication, not just confidentiality.

A signature proves possession of a secret key matching a public key. But so does successfully deriving a shared secret with someone who holds that public key — the two parties prove they share a key by computing a Message Authentication Code with it. This is not a new idea; Signal and other modern protocols already do this, partly for deniability, since the authentication is not a publicly verifiable signature.

In a post-quantum context, the motivation is different. KEMs and signatures have diverged in cost. Using a KEM for authentication lets a protocol trade bytes for round trips, or pick up properties like deniability for free along the way. The price is architectural: authentication requires both parties to exchange messages before it can happen. The server must send its public key first; the client cannot encapsulate a secret to a key it has not seen.

   Client                                  Server
 ClientHello         -------->
                     <--------         ServerHello
                                             <...>
                     <--------       <Certificate>  ^
 <KEMEncapsulation>                                 | Auth
 {Finished}          -------->                      |
 [Application Data]  -------->                      |
                     <--------          {Finished}  v
 [Application Data]  <------->  [Application Data]

<msg>: encrypted w/ keys derived from ephemeral KEX (HS)
{msg}: encrypted w/ keys derived from HS+KEM (AHS)
[msg]: encrypted w/ traffic keys derived from AHS (MS)

Authentication via KEM in TLS from the AuthKEM proposal

This idea is not hypothetical. The KEMTLS proposal, published at ACM CCS in 2020, and the draft-celi-wiggers-tls-authkem draft RFC describe integrating authentication via KEM into TLS 1.3. The proposal shows the shape of what that handshake would look like.

The necessary certificate chain signatures, OCSP stapling, and Certificate Transparency signatures remain, since those are verified offline. Those still need a workable signature scheme. But the per-connection handshake signature — the one that is hardest to fit into existing post-quantum constraints — can be eliminated.

A Window for Protocol Redesign

The transition to post-quantum cryptography is not only a matter of swapping primitives. It is an opportunity to re-examine the budgets protocols were designed around: the balance between round trips and bytes on the wire, the roles of signatures versus key exchange, and which properties are actually required.

For some protocols, this is straightforward. TLS can absorb larger keys and signatures, at least with the lattice-based schemes. For others, like DNSSEC with its very tight message-size limits, it is not obvious where to start. Waiting for NIST to finish standardization before thinking about how these algorithms fit into production protocols would be a mistake. The questions of which scheme fits which role, and whether existing protocol shapes still make sense, need to be answered in parallel with the standardization work.