NIST’s pleasant post-quantum surprise

A Curveball in the Post-Quantum Standardization

NIST has announced the first algorithms it will standardize for post-quantum cryptography, marking a critical milestone in the long effort to protect the Internet from future quantum computers. The selection includes an unexpected choice that alters earlier assumptions about the path forward.

The stakes are high. While quantum computers still cannot break public-key cryptography, the threat is real: an attacker can capture encrypted traffic today and decrypt it later once a capable machine exists. That makes the replacement of key agreement protocols urgent. Digital signatures face a different, but not easier, timeline—most certificates are short-lived, but swapping them out remains complex.

Why the Threat Is Real

In 1994, mathematician Peter Shor found an algorithm that efficiently factors numbers and computes discrete logarithms—the foundations of RSA and elliptic curve cryptography. It requires a quantum computer, and for decades those machines existed only on paper. Later, physicists built real, but noisy and small, quantum computers. Today, it appears only a matter of time until one is powerful enough to break deployed public-key systems.

To see what is at risk, it helps to separate the three cryptographic primitives protecting an ordinary browser connection:

• Symmetric encryption uses one key for both encryption and decryption. It is the fast, well-understood workhorse of cryptography, and as far as anyone knows it is safe against quantum attacks. AES and ChaCha20 are examples.
• Key agreement (key exchange) lets two parties not sharing a secret derive one without revealing it to a snooping observer. Diffie–Hellman over curves like X25519 is the standard today.
• Digital signatures verify that you are actually talking to the intended website through a certificate chain up to a certificate authority. RSA is a common example.

Shor’s algorithm breaks every widely deployed key agreement and signature scheme. The urgency differs between the two. An attacker can capture and store today’s traffic and decrypt it later by breaking the key agreement with a quantum computer—personal information, credit card numbers, and private messages are all at risk. Signatures, while not storable for later breaking, still need to be replaced in time.

The NIST Selection Process

Cryptographers began addressing Shor’s work early, developing algorithms resistant to quantum attacks. In 2016 NIST—already known for standardizing AES and SHA—issued a public competition for post-quantum algorithms. Researchers submitted 82 candidates, which were publicly scrutinized and winnowed across three rounds. The final round held eight candidates. From those, NIST selected one key agreement scheme and three signature schemes, announced on Tuesday.

Kyber and Key Agreement

For key agreement, NIST selected only Kyber, a Key Encapsulation Mechanism (KEM). Unlike Diffie-Hellman key agreement, where both parties generate keypairs and combine their own private key with the other party's public key to derive a shared secret, a KEM works differently. The initiator generates a fresh keypair and sends the public key to the receiver. The receiver generates a shared secret, encrypts (encapsulates) it for that public key, and returns the ciphertext. The initiator then decrypts (decapsulates) it with their private key.

In the simple key agreement used in TLS, the round-trip counts are identical for KEM and Diffie-Hellman. In fact, Diffie-Hellman is essentially being used as a KEM in that context. But this equivalence doesn't hold for all protocols. The 3XDH handshake used by Signal, for instance, cannot be done with plain KEMs and requires the full flexibility of Diffie-Hellman.

Kyber is a balanced post-quantum KEM: it is much faster than X25519, which is already known for its speed. Its main drawback, common to many post-quantum KEMs, is relatively large ciphertext and key sizes — compared to X25519 it adds 1,504 bytes.

We have indirect data on whether that size increase matters. In 2019, together with Google, we tested two post-quantum KEMs in Chrome: NTRU-HRSS and SIKE. SIKE has very small keys but is computationally expensive; NTRU-HRSS has similar performance characteristics to Kyber but is slightly bigger and slower. Both were combined with X25519 in a hybrid configuration, meaning NTRU-HRSS couldn't benefit from its speed advantage over X25519. Even with that disadvantage, the performance difference was very small.

We expect that switching to a hybrid of Kyber and X25519 will similarly have little performance impact. However, some TLS implementations are brittle and crash on the larger KeyShare message that contains the bigger post-quantum keys. Mitigating these issues will require work, as was done to deploy TLS 1.3.

The KEM finalists that didn't win

NIST intends to standardize some of the losing KEM finalists in a fourth round. This serves several purposes: increasing diversity in security assumptions in case of a breakthrough in attacks on the structured lattices underlying Kyber, and preserving schemes with specialized but useful applications. Some may also be standardized outside of NIST.

SABER, NTRU and NTRU Prime are structured lattice schemes very similar to Kyber in performance. Any of them would have been a fine pick — OpenSSH 9.0 chose to implement NTRU Prime. BIKE and HQC are also balanced KEMs but based on different underlying hard problems; they're noticeably less efficient in both key sizes and computation, which makes them useful backups if structured lattice cryptanalysis advances. Both are advancing to a fourth round. FrodoKEM, based on unstructured lattices, was not advanced by NIST, though Germany's BSI prefers it.

The two remaining specialists are both advancing to the fourth round. Classic McEliece has unbalanced performance characteristics: a large public key (261kB) and small ciphertexts (128 bytes). That makes it unsuitable for ephemeral key exchange in TLS, where the public key must be transmitted, but ideal when the public key is distributed out-of-band anyway, as with pinned certificates in applications. Using McEliece this way requires a TLS variation known as KEMTLS, where the client encrypts a challenge to the server's KEM public key and the server proves possession by decrypting it. This implicit authentication also works with Kyber when the public key isn't known beforehand.

SIKE, based on supersingular isogenies, has very small key and ciphertext sizes but is computationally more expensive than the other contenders.

Post-Quantum Signatures

The situation for key agreement is manageable: Kyber is larger than X25519 but offers computational efficiency in return. For post-quantum signatures, the tradeoffs are worse — none of the schemes fit the bill on their own.

Falcon's floating-point problem

Among these, Falcon has the best sizes, but it has a weakness the table doesn't show: it requires fast constant-time double-precision floating-point arithmetic for acceptable signing performance. Constant time means the operation's duration doesn't depend on the data processed; if signature creation time depends on the private key, that key can often be recovered by measuring timing. Writing constant-time code is hard, but cryptographers have figured it out for integer arithmetic.

Falcon is the first major cryptographic algorithm to use double-precision floating-point arithmetic. It has been implemented in constant time for several CPUs using clever workarounds for certain instructions. But that constant-timeness is built on shaky ground: the next generation of Intel CPUs might add an optimization that breaks it, many CPUs lack fast constant-time double-precision operations, and obscure bugs may have been overlooked. It might be figured out eventually, but it's too early to deploy Falcon where signature minting timing can be measured. For offline signatures such as those in certificates, however, it's a great choice.

Dilithium's size problem

Dilithium is easy to implement safely and has better signing performance. Its signatures and public keys are much larger than Falcon's, though. To each browser visiting this page, we send six signatures and two public keys. Replacing them all with Dilithium2 would add 17KB of additional data. Our experiments last year showed the impact of such added data on TLS handshake times, with caveats: we used a large 30-segment initial congestion window, and the bump in handshake time moves from 40KB to 10KB with a normal window. The height of the bump is the round-trip time, which is very low on our broadly distributed network — switching to Dilithium alone might well double TLS handshake times for others.

More disturbingly, some connections stopped working entirely when we added too much data, likely due to misbehaving middleboxes.

We concluded that early adoption of post-quantum signatures would be more successful if those six signatures and two public keys fit in 9KB. That can be achieved by using Dilithium for the handshake signature and Falcon for the other, offline signatures.

A pleasant surprise

NIST had stated on several occasions that it would choose only two signature schemes — and not both Falcon and Dilithium, since both are based on structured lattices and thus don't add security diversity.

Given the difficulty of implementing Falcon correctly, we expected NIST to standardize Dilithium with SPHINCS+ as backup, which would have required difficult and rigorous protocol changes to keep the Internet fast. Instead, to everyone's surprise, NIST picked all three: Dilithium, Falcon, and SPHINCS+. This makes post-quantum authentication much simpler to adopt.

SPHINCS+ and other also-rans

In the excitement over Dilithium and Falcon, it's easy to overlook SPHINCS+, a stateless hash-based signature scheme. Its security rests on the second-preimage resistance of its underlying hash function, which is well understood — it's arguably the most conservative choice for a signature scheme, post-quantum or otherwise. But its performance isn't great. There's considerable flexibility in its parameter choices, trading off signature size, signing time, verification time, and the maximum number of signatures (currently set at 2⁶⁴). NIST has hinted at reducing that limit, which would improve performance; custom parameters for specific applications would help even more, but would still trail Dilithium.

Three other finalists — GeMSS, Picnic, and Rainbow — are not progressing to a fourth round. Picnic is a conservative choice similar to SPHINCS+, based on the secure multiparty computation of a block cipher. To be efficient it requires a non-standard block cipher, making its assumptions less conservative than SPHINCS+'. GeMSS and Rainbow are specialists: large public keys (hundreds of kilobytes) but very small signatures (33-66 bytes), ideal for out-of-band public key distribution such as Signed Certificate Timestamps in Certificate Transparency. Unfortunately, both turned out to be broken.

On the horizon

NIST is opening a new competition for post-quantum signature schemes. A few proposals have already caught our eye: UOV, with performance tradeoffs similar to GeMSS and Rainbow; SQISign, with small signatures but computationally expensive; and MAYO, which looks like a potential general-purpose scheme.

Finally, NIST has already standardized the stateful hash-based schemes LMS and XMSS. They share the conservative security of SPHINCS+ with much better performance. The catch: each keypair has a finite number of signature slots, and each slot can be used only once — using it twice is insecure. The signer must maintain perfect state across all used slots, and any mistake is fatal.

NIST’s Surprising Signature Selection

With Kyber locked in for key agreement, NIST turned to signatures and delivered an unexpected outcome: it selected both Dilithium and Falcon. That contradicts earlier signals from the institute and is welcome news for the Internet. Falcon’s compact signatures and Dilithium’s speed make the two a complementary pair, giving protocol designers room to optimize for their own constraints.

The practical guidelines for choosing one are straightforward:

• If large signatures and slow operations are acceptable, SPHINCS+ is the stateless choice.
• For better performance, Dilithium works when signing is done on-the-fly and can be timed; choose Falcon when signatures are generated offline.
• If you can guarantee state discipline, hash-based schemes like XMSS or LMS remain an option.

The Open Quantum Safe project is a good testbed. Our own CIRCL Go library already ships an independent Dilithium implementation; Falcon and SPHINCS+ support will follow.

Hybrids and Security Levels

A hybrid simply combines a classical scheme with a post-quantum one — for example, pairing Kyber512 with X25519 to form Kyber512X. The benefit is resilience against both a complete break of the new algorithm and implementation-level side-channel leaks. The cost is extra CPU time and larger handshakes. We currently favor hybrids, and will revisit that preference once the standardized algorithms have more field history.

All the selected schemes ship in multiple parameter sets, targeting different security levels defined against classical and quantum attacks on AES and SHA:

Level 1 might sound weak when you consider Grover’s algorithm, which finds an AES-128 key in roughly 2⁶⁴ quantum operations. But naively comparing that to classical brute force ignores important context. Grover’s quadratic speedup does not parallelize well: a billion quantum computers would each still need ~2⁴⁹ iterations to finish the job. Accounting for the estimated number of gates per iteration and realistic clock speeds, even that hypothetical fleet would need hundreds of years to crack a single key. And that analysis assumes noiseless gates — real quantum machines need costly error correction, pushing the practical timeline even further out.

None of that means level 1 is a guarantee forever, but it is a firmly comfortable margin for the foreseeable future. A more compelling reason to select a higher level is hedging against improved classical cryptanalysis. That is not foolproof either:

• Cryptanalytic breakthroughs can break multiple parameter sets at once rather than degrading gradually.
• Higher security levels do nothing to mitigate implementation flaws, such as new timing side channels.

Arguably more important than picking a high number is crypto agility — designing with an easy migration path to a replacement algorithm. Given that we are already forced to switch once, making the next switch cheap is the smart bet.

CIRCL Goes Post-Quantum

CIRCL is our optimized cryptography library for Go. It already tracks the NIST round-three submissions, including Kyber, SIKE, Dilithium and Frodo, with code that passes official test vectors. You can use CIRCL directly or as a drop-in through our Go fork.

The library exists to make post-quantum experimentation in TLS realistic. We used it to build a KEMTLS implementation in Go and run a measurement study of the protocol’s feasibility.

The small example below signs a message with eddilithium2, a hybrid of Ed25519 and Dilithium mode 2:

package main

import (
  "crypto"
  "crypto/rand"
  "fmt"

  "github.com/cloudflare/circl/sign/eddilithium2"
)

func main() {
  // Generating random keypair.
  pk, sk, err := eddilithium2.GenerateKey(rand.Reader)

  // Signing a message.
  msg := []byte("Signed with CIRCL using " + eddilithium2.Scheme().Name())
  signature, err := sk.Sign(rand.Reader, msg, crypto.Hash(0))

  // Verifying signature.
  valid := eddilithium2.Verify(pk, msg, signature[:])

  fmt.Printf("Message: %v\n", string(msg))
  fmt.Printf("Signature (%v bytes): %x...\n", len(signature), signature[:4])
  fmt.Printf("Signature Valid: %v\n", valid)
  fmt.Printf("Errors: %v\n", err)
}

Message: Signed with CIRCL using Ed25519-Dilithium2
Signature (2484 bytes): 84d6882a...
Signature Valid: true
Errors: <nil>

The API matches Go’s standard crypto.Signer interface, so integrating it into existing applications is simple. Feedback is welcome on the issue tracker.

Where Things Stand

NIST has settled key agreement on Kyber, giving us a path to protect today’s data from tomorrow’s quantum adversaries without a meaningful performance penalty. Choosing both Falcon and Dilithium for authentication is a pragmatic surprise that should make post-quantum TLS handshakes considerably faster than we predicted. The community now has the hard, well-defined work of moving these algorithms into TLS, libraries and deployments — and making sure the next migration is an easier one.