What are the Quantum-Resistant Cryptography Standards of NIST?

In August, the U.S. Department of Commerce’s National Institute of Standards and Technology (NIST) finalized the publication of the first encryption algorithm standards designed to withstand cyberattacks from future quantum computers. Often dubbed “post-quantum cryptography”, or PQC in short, these algorithms can be run on today’s computers but base their security on the hardness of complex mathematical problems that are deemed to be so hard to be intractable even for future quantum computers.

After an open selection process that lasted over 8 years and which has seen incredible advancements in the area of cryptanalysis, the first “batch” of NIST-approved standards have been published as FIPS-203, FIPS-204, and FIPS-205.

FIPS-203 describes ML-KEM (“Modular Lattice Key Encapsulation Mechanism”), previously known as “Kyber”. This is an algorithm for asymmetric exchange of encryption keys based on structured lattices. Among its advantages are comparatively small encryption keys that two parties can exchange easily, as well as its speed of operation.

FIPS-204 describes ML-DSA (“Modular Lattice Digital Signature Algorithm”), previously known as “Dilithium”. This is a digital signature algorithm also based on structured lattices. Compared to other similar schemes, it offers a good trade-off between speed, signature and key size, and ease of implementation on different hardware.

FIPS-205 describes SL-DSA (“Stateless Hash-Based Digital Signature Algorithm”), previously known as “Sphincs+”. This is a digital signature scheme alternative to MLDSA, based on hash functions. Compared to ML-DSA it is generally slower and with larger key sizes and signatures, but it is arguably the top in terms of theoretical security.

Why Organizations Must Prepare for Quantum-Safe Technology

The publication of the NIST PQC standards signals the official beginning of the migration to quantum-secure infrastructures for governments and organizations around the globe.

Even if NIST is, strictly speaking, a US-only institution, its guidelines have generally been adopted across the Western world, especially in cases (like the one at hand) where the standards are the result of an open, global selection process involving industrial and academic experts from all around the world.

The new standards must now be integrated by business and government agencies into their digital infrastructures. This has enormous costs and brings many technological difficulties, as previous experience in cryptography migration has taught us (e.g., the migration from 3DES to AES, now a ubiquitous and necessary encryption standard). But it must be done nevertheless, either by virtue of regulatory compliance (government organizations are issuing or have already issued official guidelines for businesses and contractors who want to be compliant in this sense) or by virtue of market pressure.

Whether quantum computers large enough to threaten modern, quantum-vulnerable encryption will ever be built or not, that’s not even relevant anymore: the path is forward.

Some large organizations have already launched their pilot programs years ago to integrate the new standards into their infrastructures. Most businesses have so far lagged behind, waiting and not willing to take any risks until the general directions would be clear. But now the time to wait is over.

Most businesses are impacted immediately, the more urgently exposed being probably hardware manufacturers, who must ensure their chips allow fast and reliable support of the new standards on products that might have a very long lifetime.

Expert Insights: Preparing for the Transition to Post-Quantum Cryptography

The migration to quantum-resistant cryptography will be unavoidable but particularly painful, even more than the AES or SHA3 migration. This is because, unlike traditional cryptographic schemes, there is no single “one-size-fits-all” quantum-secure solution.

The three new NIST standards are just the first batch, but more will follow: FIPS-206 (FN-DSA, previously known as “FALCON”) is already on its way and should be published soon, while there is already discussion about standardizing other schemes, as well as an additional round of calls for submission on new algorithms not based on structured lattices (to increase diversity and have a backup solution if one hardness assumption falls apart).

Most of these schemes have very different profiles in terms of speed, key size, etc, so each of them is best tailored to one specific application but not another. Selection of which standard to adopt must follow a careful, case-by-case assessment, which increases complexity and costs for business.

Cryptographic agility (a technology stack framework that allows substituting existing algorithms with functionally equivalent ones as drop-in replacements) is the best long-term investment in the realm of cryptographic compliance because it would allow eliminating or largely reducing, the pain of another migration in case one weakness is found on the adopted standards and an immediate backup solution is necessary.

For the short-term, so-called hybrid solutions are being explored, where a current, quantum-vulnerable but well-tested cryptographic schemed is coupled with a novel, quantum-resistant one for added security and compliance. However, the cryptographic community is currently divided on whether the extra security guarantees offered by hybrid solutions outweigh the added complexity and performance loss.

It is often said that key exchange algorithms are more urgently in need of replacement than digital signature algorithms due to the threat of store-now-decrypt-later attacks: an adversary can already intercept and store encrypted information today and decrypt it when quantum computers become available, while quantum-insecure digital signatures can simply be phased out if and when the quantum threat materializes in the future, and are hence less of an urgent matter.

However, we only partially agree with this view because of the likely scenario where quantum computing capabilities are developed as “black programs” by adversarial entities or governments. In other words, we could face a scenario where our digital signatures and certificates start being compromised, and we would have no idea why. It could be because of a regular hack and exfiltration of the secret key, or it might be because an adversary has attacked the public key quantumly, and we do not know.

In any case, it is very urgent that CISOs take this threat seriously and start acting immediately.