NIST finalizes post-quantum encryption standards

On August 13, the US National Institute of Standards and Technology (NIST) published the final form of its new post-quantum cryptographic standards. One key-exchange mechanism and two digital-signature schemes are now officially sanctioned by the institute. Adopting the new standards should be fairly painless for most developers, but the overhead added by the schemes could pose challenges for some applications.

Why post-quantum cryptography

In 1994, Peter Shor developed Shor's algorithm, which can use a quantum computer to efficiently find the prime factors of a number. Scott Aaronson, a noted researcher of computational complexity, has an accurate explanation of the algorithm aimed at laypeople. For our purposes, it suffices to note that — while quantum computers are not yet anywhere near large enough to handle existing key sizes — they are getting larger over time, and may one day be able to completely undermine cryptography that relies on the difficulty of factoring large numbers. NIST's article on the new standards suggests that the threat could be realized within a decade.

Of course, modern cryptography is generally trending away from RSA, the original asymmetric encryption scheme based on the difficulty of factoring large numbers, for a number of reasons; other schemes offer smaller signatures, faster operation, and harder problems for classical computers. Unfortunately, most of the alternative algorithms depend, in one form or another, on the discrete logarithm problem instead of the factorization problem for their security. Due to the underlying similarities of the problems, Shor's algorithm applies equally well to solving discrete logarithms. Cryptographers hate being rushed into signing off on new systems, so work to find a suitable replacement that is not vulnerable to Shor's algorithm or related quantum methods has been underway for decades.

In 2016, NIST recognized the necessity of replacing existing public-key cryptography by announcing a competition to find a replacement for two types of cryptography: key exchange and digital signatures. The competition proceeded in four rounds, narrowing down the candidate systems as attacks were found. The competition ended in July 2022 with the selection of CRYSTALS-Kyber as the winning key-exchange mechanism, with three different signature schemes also making it to the end of the contest. Since then, the institute has been working on producing a final standard suitable for implementation and inclusion into the Federal Information-Processing Standards (FIPS).

The mechanisms

NIST's competition set out to find replacements for two kinds of cryptographic operation: key exchange and signing. Symmetric cryptography — that is, cryptography that assumes both participants have a pre-shared key — is not generally vulnerable to quantum computers. The exception is Grover's algorithm, which applies to reversing any function, but which does not provide enough of a speedup compared to classical computers to cause meaningful problems for cryptography. The problem with symmetric cryptography is sharing the key without letting it leak. If symmetric cryptography were the only tool available, every client and every server would need a shared secret, which is obviously infeasible. Generally, this dilemma is solved by a key-exchange algorithm, which uses asymmetric (public-key) cryptography to let two computers communicate securely just long enough to agree on a symmetric key.

Although NIST chose CRYSTALS-Kyber as a key-exchange mechanism, the institute released its own slightly tweaked version under the name ML-KEM. The algorithm makes key exchange possible by encoding messages as equations in a finite field (in a way specified by a public key), and then deliberately adding errors to the encoding. Removing these errors is computationally difficult — unless one has the private key, which makes it easy to remove them. The problem of taking the equation and correcting the errors is called learning with errors in the cryptography literature, and is believed to be difficult even with help of a quantum computer.

The same technique can be used to construct a digital signature by demonstrating that whoever has a private key can produce a value that, when combined with parts of the public key, is close to the hash of the value being signed. This is believed to be hard to do without the private key, because if it were possible, the solution could be adapted to solve learning-with-errors problems — and no such method has been disclosed. The exact details of how to construct a signature scheme have been standardized by NIST as ML-DSA.

One downside of these techniques are that the keys (and signatures) are somewhat larger than those used in current asymmetric cryptography. For applications where large public keys would be prohibitively expensive, NIST also defined a second post-quantum cryptographic-signature method that uses a completely different approach. SLH-DSA is a digital-signature scheme that combines multiple hashes in such a way as to make a signature hard to fake without completely breaking the underlying hash function.

While it is difficult to compare cryptographic algorithms directly, since they are not exactly equivalent in terms of security, it is possible to compare them by determining how large keys need to be to withstand the current best attacks against each. This is not a perfect approach, since it is always possible that a new attack against a method could radically change its effective security. Still, here is a rough comparison (targeting the same level of security as 128-bit AES) between the previous FIPS-standard digital-signature algorithms, which are widely used, and the new post-quantum recommendations:

Algorithm	Public key size	Signature size
Ed25519	256 bits	512 bits
ECDSA	256 bits	1,024 bits
RSA	2,820 bits	3,072 bits
ML-DSA-44	10,496 bits	19,360 bits
SLH-DSA-SHA2-128s	256 bits	62,848 bits

Unfortunately, unlike ECDSA and RSA, it's not trivial to simply "scale-up" ML-DSA keys to a given size to meet security requirements. NIST defines three sizes of ML-DSA key that work: ML-DSA-44 (10,496-bit public keys), ML-DSA-65 (15,616-bit public keys), and ML-DSA-87 (20,736-bit public keys). The largest of these is claimed to meet the criteria for NIST's highest level of security. The tradeoff between key and signature size versus security is one that will need to be made by individual applications — but even the smallest ML-DSA signatures will require multiple network packets on most networks, which may well have implications for quickly establishing encrypted connections.

Adoption

Now that NIST has standardized some post-quantum cryptography, it would be nice if that cryptography actually worked. Unfortunately, while it seems likely, both the learning-with-errors and hash-based approaches have received far less scrutiny to date than traditional RSA or elliptic-curve cryptography. Therefore, NIST is currently advising that people should deploy these new techniques in conjunction with existing techniques.

The Open Quantum Safe project, which is part of the Linux Foundation's Post-Quantum Cryptography Alliance, has produced an implementation of ML-KEM and ML-DSA. There is a standalone library, liboqs, as well as an OpenSSL provider that makes the algorithms available to users of OpenSSL. Other TLS libraries, such as wolfSSL and BoringSSL, have also integrated liboqs. Generally, developers wishing to stay on top of potential security problems will only need to upgrade their cryptography library. Anyone who explicitly manages their list of TLS ciphers should consider enabling the new ciphers when possible. Unlike many security updates, this is not terribly urgent — NIST has published these standards well in advance of any reasonable threat from quantum computers — but adopting these mechanisms promptly can decrease the risk of store-now-decrypt-later attacks in the future.

Of course, TLS is not the only protocol that will eventually need post-quantum protections. OpenSSH 9.0 included NTRU Prime, one of the submissions that NIST did not end up selecting, as a key-exchange mechanism. It seems likely that the project will eventually add the option to use ML-KEM. For now, the default key-exchange mechanism for OpenSSH is a combination of NTRU Prime and x25519, a conventional elliptic-curve key-exchange mechanism. The project does not yet support post-quantum SSH keys.

Whether these new encryption schemes will hold up in the long term remains to be seen — but they have held up to six years of scrutiny. The fact that they are now FIPS requirements is enough to ensure that the implementers of secure software will need to deal with them for many years.