From 2016 to FIPS 203: how NIST picked post-quantum cryptography

The National Institute of Standards and Technology has run its selection and standardisation process for post-quantum cryptography since 2017. The reason is concrete: by some estimates a quantum computer could break the widely deployed RSA algorithm as early as 2030. The cryptographic community treats the NIST process as the most important joint effort to develop and evaluate algorithms that resist quantum attacks. It runs in several rounds, each with its own conference. Every round drops some algorithms and puts others under closer scrutiny.

Most symmetric cryptographic primitives adapt to quantum security fairly easily. Doubling key lengths, for instance, cancels out the speed-up Grover's algorithm provides. The effort therefore focuses on asymmetric cryptography, in particular digital signatures and key encapsulation mechanisms. The future standards appear as Federal Information Processing Standard, among them FIPS 203, FIPS 204 and FIPS 205.

A template taken from AES

The format was tried, open and transparent, modelled on the AES standardisation process of 1997-2000 that the cryptographic community still praises. Academic research into the potential impact of quantum computing goes back at least to 2001. In 2015 US federal authorities announced plans to move every government information processing system covered by confidentiality requirements onto cryptography resistant to quantum computers. At the PQCrypto conference in 2016, NIST announced it would standardise quantum-safe cryptographic primitives. In December 2016 the process opened with a call for proposals.

When submissions closed at the end of 2017, 23 digital signature systems and 59 encryption and key encapsulation methods had come in. Of that number, 69 were judged complete and eligible for the first round, and 23 candidates moved on to further work. Seven algorithms and eight alternative candidates advanced to the second round. On 22 July 2020 NIST announced seven finalists, among them three signature systems, plus eight alternative designs.

Who won, who fell

The third round produced four winners: CRYSTALS-Kyber as a key encapsulation mechanism, and CRYSTALS-Dilithium, FALCON and SPHINCS+ as digital signature systems. These are the ones NIST is standardising now. The fourth round, announced in July 2022 and examining four further algorithms, was still running in March 2024. In 2024 NIST published the final versions of its first three post-quantum cryptography standards. Two lattice-based algorithms made the first cut: ML-KEM, widely known as Kyber, and ML-DSA, known as Dilithium. Not every construction survived. The widely discussed SIDH/SIKE construction was spectacularly broken in 2022, though the attack concerned only that family of schemes and does not generalise to other isogeny-based constructions.