Why Post-Quantum Signatures Matter Now
Quantum computers threaten the two pillars of TLS cryptography. Shor’s algorithm, run on a sufficiently large stable quantum machine, breaks both the digital signatures (like RSA) that authenticate servers and the key exchanges (like Diffie–Hellman) that establish encryption keys. Post-quantum (PQ) cryptography aims to close that gap, and NIST’s standardization effort is expected to produce its first results in early 2022.
At Cloudflare, we’ve already tested PQ key exchanges in a joint 2019 experiment with Google, finding minimal performance impact — and many NIST finalists perform even better. But replacing the signatures in TLS is more urgent and more complex than swapping out key exchanges. An attacker can already record encrypted traffic today, store it, and decrypt it years later with a quantum computer. Replacing key exchanges mitigates that risk, but signature migration carries longer lead times: it requires coordinated changes to browsers, servers, certificate authorities (CAs), and certificate management infrastructure.
There’s another complication: TLS leans heavily on small, fast signatures. A single page load can involve six signatures — two in the certificate chain, one handshake signature, an OCSP staple, and two SCTs for certificate transparency. PQ signature schemes have widely varying performance trade-offs, and all six signatures have different requirements. While we could theoretically reduce the number of signatures — for example via KEMTLS or by suppressing intermediate CA certificates — such fundamental changes take years to adopt. So we also need to understand how drop-in PQ signatures perform in plain TLS today.
Surveying the Candidates
The three finalists in NIST’s competition are Dilithium, Falcon, and Rainbow. The table below compares them with the classical algorithms RSA and ECDSA, alongside other PQ schemes like GeMMS, SPHINCS+, and SQISign that may see future standardization:
The table comes with important caveats. It compares security level 1 instances, and signing and verification times vary considerably by platform and implementation. Falcon512’s signing time, in particular, is discussed further below. Note that XMSS is stateful, can only sign a million messages, requires significant storage for fast signing, and is not yet standardized — far from a drop-in option.
No single PQ signature is an obvious replacement for RSA or ECDSA. All produce larger signatures except Rainbow, GeMMS, and SQISign — but Rainbow and GeMMS have enormous public keys, and SQISign is prohibitively slow.
Matching Algorithms to Roles
Within TLS, not all signatures are created equal:
- Online signatures — only the handshake signature is generated fresh for each incoming TLS connection, so signing speed is critical. Dilithium fits this role well.
- Offline signatures — the rest are created months or years in advance, making signing time less relevant. These split into two groups:
- With a public key — the certificate chain’s signatures include their public keys; here Falcon seems most suited for its compact size.
- Without a public key — SCTs and OCSP staples are bare signatures. Rainbow appears optimal here, since its massive public keys are not transmitted.
Using Dilithium, Falcon, and Rainbow together would let us optimize simultaneously for speed and size. Combining schemes, however, carries costs: a security flaw in any one of them compromises the whole system, and clients must implement three distinct algorithms — a burden on small devices, especially if they require separate hardware support.
The Case for a Single Scheme
Could we instead settle on just one algorithm? Falcon512 is tempting on paper — it adds roughly 5KB of extra space over a classical handshake, comparable to the hybrid Dilithium–Falcon–Rainbow approach. But Falcon has a serious caveat: efficient signing depends on constant-time 64-bit floating-point arithmetic. Without it, signing runs about 20x slower. Constant-time execution is not merely a performance nicety — a variable-time implementation could leak the secret key incrementally through timing measurements.
Most PCs have sufficiently constant-time floating-point units, but many smaller devices do not. For general-purpose online signing, Falcon looks like a poor fit.
That leaves Dilithium2, which requires roughly 17KB of additional data. The next question is whether that space cost actually matters in practice — we’ll examine that trade-off next.
Measuring the Real Cost of Bigger TLS Handshakes
Earlier studies of post-quantum signatures in TLS have been useful starting points, but they leave significant gaps. In particular, they haven't accounted for the full set of signatures involved in a handshake — SCTs and OCSP staples make up half of them, so ignoring them materially changes the results. And the network conditions tested, typically between two datacenters or in simulations with unrealistic packet loss, don't reflect real-world last-mile connections.
To take a first step toward filling those gaps, we ran a large-scale experiment designed around the single most conspicuous variable: size. The question was straightforward: how do larger certificates affect the TLS handshake, in terms of both speed and reliability?
Emulating larger signatures without modifying clients
We needed a way to make handshakes bigger without changing client software. Padding a valid certificate with a dummy extension would require a custom certificate for every size we wanted to test — too cumbersome. Responding with a dummy ServerHello extension is not permitted by TLS 1.2 without a corresponding ClientHello extension. That left a third option: appending dummy certificates to the certificate chain.
Dummy certificates are 1kB self-signed invalid certificates unrelated to the actual chain. Clients have learned to ignore such unrelated certificates because their presence is a common misconfiguration; TLS 1.3 even states these SHOULD be ignored. Across hundreds of browsers we tested, none objected. However, standards and reality don't always align — on live traffic we saw a small but not insignificant number of clients choke on the extra certificates. To avoid harming anyone's connection, we ran the experiment on separate, dedicated connections.
Probing via challenge pages
On a small fraction of our CAPTCHA challenge pages, we selected a number n and a random key, then sent that key in two separate background requests:
0.tls-size-experiment-c.cloudflareresearch.com— the control, a normal webpage that records the TLS handshake time under the key._[n]_.tls-size-experiment-1.cloudflareresearch.com— the live endpoint, which adds n dummy certificates to its chain and likewise stores the handshake time.
The control matters as much as the experimental side: it lets us tell whether live connections are actually missing or just slow. We built both endpoints with Cloudflare Workers and KV.
Before launching, we probed how far we could push the dummy data. TLS 1.3 theoretically allows a 16MB certificate chain, but clients in practice reject much smaller ones. OpenSSL, for example, rejects a 102kB chain; the most restrictive client we found, Go's TLS client, rejects any handshake over 64kB. We therefore tested with between 1 and 59 dummy certificates.
Why the congestion window matters
To read the results, a quick primer on TCP's congestion window. Internet data travels in packets of roughly 1.4kB, and routers occasionally drop packets when overloaded — that is congestion. To avoid causing it, TCP starts conservatively with typically ten packets (~14kB). As acknowledgements come back, the sender rapidly increases the number of packets in flight — the congestion window (cwnd). If congestion occurs and packets are dropped, the sender halves the window. TCP treats every dropped packet as a congestion signal; Wi-Fi's separate retransmission layer hides losses from TCP.
Larger signatures should therefore produce two predictable effects:
- A gentle slope: each packet takes longer to transmit over a constrained link, especially slow or spotty ones.
- A cwnd wall: once the congestion window is full, the sender stalls for a full round trip before continuing. This hurts more when the roundtrip time is high.
Post-quantum research has focused most attention on the second effect — larger signatures simply don't fit inside typical initial congestion windows. A frequently proposed fix is to enlarge the initial cwnd globally, but that is far from a simple change, and it's worth testing whether it solves the problem in the first place.
What the experiment showed
Over 24 days we collected 964,499 live connections from 454,218 distinct /24 IPv4 (or /48 IPv6) prefixes across 11,239 autonomous systems. First, did bigger handshakes actually fail?
Some missing control connections are expected — 2.4% of live connections had no matching control, easily explained by users navigating away. But we found significantly more controls without a corresponding live connection: 3.6%. Breaking down live connections by the number of added dummy certificates (the graph below, left) shows the noise of random size selection. Storing the certificate count in the control request yields a cleaner picture (right), with visible bumps at 10kB and 30kB — evidence that some clients or middleboxes cannot handle handshakes of those sizes.
How much slower are fat handshakes?
Looking at weighted median and 75th-percentile handshake times — weighted so each truncated IP contributes equally — reveals the expected slope and wall. The slowdown relative to the control connection is shown on the right below.
We see a not-so-gentle slope up to about 40kB, where a little wall appears — matching Cloudflare's default initial congestion window of 30 packets. Crucially, adding 35kB still fits within our initial cwnd, yet the median handshake with that extra data is 40% slower, and the slowest 10% of connections take 60% longer. Even without hitting the congestion window, the added bytes are far from free.
Mapping this back to concrete post-quantum schemes: using Dilithium2 as a drop-in replacement requires around 17kB of extra data. That also fits within our initial congestion window, with a median slowdown of 20% — worse for users in the tail. With the more common initial congestion window of ten packets, we'd expect much worse, around 60–80%.
Several caveats limit direct extrapolation:
- We used an initial congestion window of 30 packets; with the more common default of ten, the wall would move from 40kB down to around 10kB.
- Cloudflare's global presence keeps our RTTs artificially low, understating the cwnd wall's effect for typical users.
- Challenge pages attract bots, which tend to run on well-connected providers closer to us than average users.
- The endpoint server lacked HTTP/3 support, and IPv6 was only added ten days in, accounting for 10.9% of measurements.
- Real TLS handshakes vary more in size due to certificate extensions, SCTs, and other factors than our controlled setup.
Practical takeaways
The TLS handshake is only one step — roughly 5–20% — of everything needed to render a webpage. A handshake 60% slower might not be noticeable in casual browsing, but such differences accumulate, and performance-sensitive developers treat even single-percent regressions as unacceptable.
Given the number of stakeholders and technical constraints, waiting too long to adopt post-quantum signatures in TLS is risky. Yet asking content servers, browser vendors, and clients to accept double-digit slowdowns is a hard sell. Our evidence suggests adoption will be easiest if six signatures and two public keys can fit within roughly 9kB.
Bas Westerbaan is co-submitter of the SPHINCS+ signature scheme.
References
SKD20: Sikeridis, Kampanakis, Devetsikiotis. Assessing the overhead of post-quantum cryptography in TLS 1.3 and SSH. CoNEXT'20.
PST20: Paquin, Stebila, Tamvada. Benchmarking Post-Quantum Cryptography in TLS. PQCrypto 2020.
SKD21: Sikeridis, Kampanakis, Devetsikiotis. Post-Quantum Authentication in TLS 1.3: A Performance Study. NDSS2020.
PKNLN22: Paul, Kuzovkova, Lahr, Niederhagen. Mixed Certificate Chains for the Transition to Post-Quantum Authentication in TLS 1.3. To appear in AsiaCCS 2022.
