The first post-quantum encryption standards

After many years of research and testing, in mid-August 2023, the U.S. National Institute of Standards and Technology (NIST) finally introduced fully-fledged post-quantum encryption standards — FIPS 203, FIPS 204, and FIPS 205. So let’s discuss them and see why they should be adopted as soon as possible.

Why do we need post-quantum cryptography?

First, let’s briefly outline the threat quantum computers pose to cryptography. The issue lies in the fact that quantum computing can be used to break asymmetric encryption. Why is this important? As a rule, today’s communication encryption typically uses a dual system:

• All messages are encrypted using a symmetric algorithm (like AES), which involves a single key shared by all participants. Symmetric algorithms work well and fast, but there’s a problem: the key must be somehow securely transmitted between interlocutors without being intercepted.
• That’s why asymmetric encryption is used to transmit this key (like RSA or ECDH). Here, each participant has a pair of keys — a private and a public one — which are mathematically related. Messages are encrypted with the public key, and decrypted only with the private one. Asymmetric encryption is slower, so it’s impractical to use it for all messages.

The privacy of correspondence is ensured by the fact that calculating a private key from the corresponding public key is an extremely resource-intensive task — potentially taking decades, centuries, or even millions of years to solve. That is — if we’re using traditional computers.

Quantum computers significantly speed up such calculations. Specifically, Shor’s quantum algorithm can crack private keys for asymmetrical encryption much faster than its creators expected — in minutes or hours rather than years and centuries.

Once the private key for asymmetric encryption has been calculated, the symmetric key used to encrypt the main correspondence can also be obtained. Thus, the entire conversation can be read.

In addition to communication protocols, this also puts digital signatures at risk. In the majority of cases, digital signatures rely on the same asymmetric encryption algorithms (RSA, ECDSA) that are vulnerable to attacks by quantum computers.

Today’s symmetric encryption algorithms, on the other hand, are much less at risk from quantum computers than asymmetric ones. For example, in the case of AES, finding a 256-bit key using Grover’s quantum algorithm is like finding a 128-bit key on a regular computer. The same applies to hashing algorithms.

The trio of post-quantum cryptography standards: FIPS 203, FIPS 204, and FIPS 205

The primary task for cryptographers has become the development of quantum-resistant asymmetric encryption algorithms, which could be used in key transfer and digital signature mechanisms. The result of this effort: the post-quantum encryption standards FIPS 203, FIPS 204, and FIPS 205, introduced by the U.S. National Institute of Standards and Technology (NIST).

FIPS 203

FIPS 203 describes a key encapsulation mechanism based on lattice theory — ML-KEM (Module-Lattice-Based Key-Encapsulation Mechanism). This asymmetric cryptographic system — which is resistant to quantum algorithm attacks — is designed to transfer encryption keys between interlocutors.

ML-KEM was developed as part of CRYSTALS (Cryptographic Suite for Algebraic Lattices) and is also known as CRYSTALS-Kyber, or simply Kyber.

FIPS 203 features three parameter variants for ML-KEM:

• ML-KEM-512: Security level 1 (equivalent to AES-128);
• ML-KEM-768: Security level 3 (equivalent to AES-192);
• ML-KEM-1024: Security level 5 (equivalent to AES-256).

FIPS 204

FIPS 204 defines a digital signature mechanism, also based on algebraic lattices, called ML-DSA (Module-Lattice-Based Digital Signature Algorithm). Previously known as CRYSTALS-Dilithium, this mechanism was developed within the same CRYSTALS project as Kyber.

FIPS 204 has three parameter variants for ML-DSA:

• ML-DSA-44: Security level 2 (equivalent to SHA3-256);
• ML-DSA-65: Security level 3;
• ML-DSA-87: Security level 5.

FIPS 205

The third standard, FIPS 205, describes an alternative digital signature mechanism: SLH-DSA (Stateless Hash-Based Digital Signature Algorithm). Unlike the other two cryptosystems, which are based on algebraic lattices, SLH-DSA is based on hashing. This mechanism is also known as SPHINCS+.

This standard involves the use of both the SHA2 hash function with a fixed output length, as well as the SHAKE function with an arbitrary length. For each base cryptographic-strength level, SLH-DSA offers sets of parameters optimized for a higher speed (f — fast), or a smaller signature size (s — small). Thus, FIPS 205 has more variety — with as many as 12 parameter options:

• SLH-DSA-SHA2-128s, SLH-DSA-SHAKE-128s, SLH-DSA-SHA2-128f, SLH-DSA-SHAKE-128f: Security level 1;
• SLH-DSA-SHA2-192s, SLH-DSA-SHAKE-192s, SLH-DSA-SHA2-192f, SLH-DSA-SHAKE-192f: Security level 3;
• SLH-DSA-SHA2-256s, SLH-DSA-SHAKE-256s, SLH-DSA-SHA2-256f, SLH-DSA-SHAKE-256f: Security level 5.

HNDL, and why it’s time to start using post-quantum encryption

For now, the threat of quantum algorithms breaking asymmetric encryption is mostly theoretical. Existing quantum computers lack the power to actually do it in practice.

Until last year, it was believed that sufficiently powerful quantum systems were still a decade away. However, a 2023 paper suggested ways to optimize hacking using a combination of classic and quantum computing. As a result, the timeline for achieving quantum supremacy seems to have shifted: RSA-2048 could very well be broken within a few years.

It’s also important to remember the concept of HNDL — “harvest now, decrypt later” (or SNDL — “store now, decrypt later”). Attackers with significant resources could already be collecting and storing data that can’t currently be decrypted. Once quantum computers with sufficient power become available, they’ll immediately begin retroactive decryption. Of course, when this fateful moment comes, it will already be too late, so quantum-resistant encryption standards should be implemented right now.

The ideal approach to deploying post-quantum cryptography based on established IT industry practices is hybrid encryption; that is, encrypting data in two layers: first with a classical algorithm, then with a post-quantum one. This forces attackers to contend with both cryptosystems — significantly lowering the chances of a successful breach. This approach is already being used by Signal, Apple, Google, and Zoom.