NIST's Post-Quantum Cryptography Standards, Explained for Developers

In August 2024, NIST published the first three finalized post-quantum cryptography standards as FIPS 203, 204, and 205. These standards end an eight-year competition that began with 69 submitted algorithms in 2016 and narrowed through multiple rounds of cryptanalysis to three winners. The standards define new key encapsulation and signature algorithms designed to resist attacks from quantum computers.

The threat is specific and well-understood. Shor's algorithm, published by Peter Shor in 1994, can factor integers and compute discrete logarithms in polynomial time on a quantum computer. RSA and elliptic curve cryptography (ECC) both rely on the hardness of these exact problems. A sufficiently large quantum computer running Shor's algorithm would break RSA-2048, ECDSA, and Diffie-Hellman in hours or days instead of billions of years.

No such quantum computer exists today. The largest quantum factoring demonstration is 15 = 3 x 5, achieved with nuclear magnetic resonance in 2001. But the transition to post-quantum algorithms must happen before quantum computers arrive, because encrypted data captured today can be decrypted later once the hardware exists. This is the "harvest now, decrypt later" threat model.

This post covers the three NIST standards, the lattice mathematics behind them, their key sizes and performance characteristics, and what developers should do today. The algorithms being replaced can be tested using the RSA Encrypt/Decrypt tool, the ECDSA Signature tool, and the Diffie-Hellman Key Exchange tool.

NIST announced the Post-Quantum Cryptography Standardization Process in 2016, published in Federal Register Notice 82 FR 31421. The goal was to develop new public-key cryptographic standards that resist both classical and quantum attacks. The NIST PQC project page documents the full timeline.

The competition received 69 complete submissions by the November 2017 deadline. NIST evaluated them over four rounds spanning six years. Round 1 (2017-2019) narrowed the field based on initial cryptanalysis. Round 2 (2019-2020) focused on the most promising candidates. Round 3 (2020-2022) selected the first set of algorithms for standardization: CRYSTALS-Kyber for key encapsulation and CRYSTALS-Dilithium, Falcon, and SPHINCS+ for signatures. Round 4 (2022-2024) continued analysis of backup candidates and finalized the standards.

NIST published the final standards in August 2024. The naming convention changed from the competition names to formal FIPS designations: ML-KEM (Module-Lattice-Based Key Encapsulation Mechanism), ML-DSA (Module-Lattice-Based Digital Signature Algorithm), and SLH-DSA (Stateless Hash-Based Digital Signature Algorithm). The original competition names (Kyber, Dilithium, SPHINCS+) remain in common use among developers and library documentation.

FIPS 203 standardizes ML-KEM, formerly known as CRYSTALS-Kyber. ML-KEM is a key encapsulation mechanism, not a direct encryption algorithm. The difference matters. In traditional RSA encryption, you encrypt data directly with the recipient's public key. In a KEM, you use the public key to encapsulate a symmetric key, then use that symmetric key with an AEAD cipher (like AES-GCM) to encrypt the actual data. This is called hybrid encryption and is how TLS already works with Diffie-Hellman.

ML-KEM is built on the Module Learning With Errors (MLWE) problem, a lattice-based hardness assumption. The security of MLWE does not depend on factoring or discrete logarithms, so Shor's algorithm does not apply. The mathematical structure involves polynomial rings over finite fields, where the hardness comes from adding small random noise to a system of linear equations. Removing the noise to recover the secret is computationally infeasible for both classical and quantum computers.

ML-KEM defines three parameter sets. ML-KEM-512 provides security roughly equivalent to AES-128. ML-KEM-768 matches AES-192. ML-KEM-1024 matches AES-256. Public key sizes range from 800 bytes (ML-KEM-512) to 1,568 bytes (ML-KEM-1024). Ciphertext sizes are similar. Compare this to RSA-2048, where a public key is 256 bytes. The trade-off is larger keys for quantum resistance.

Performance is where ML-KEM wins. Key generation, encapsulation, and decapsulation each take tens of microseconds on modern hardware. RSA-2048 key generation takes milliseconds, and RSA-2048 decryption takes around a millisecond. ML-KEM is faster than RSA across all operations despite the larger key sizes. The RSA Encrypt/Decrypt tool lets you compare RSA performance characteristics directly.

FIPS 204 standardizes ML-DSA, formerly CRYSTALS-Dilithium. ML-DSA is a digital signature algorithm based on the Module Learning With Errors problem, the same lattice family as ML-KEM but used for a different cryptographic purpose. Signatures prove authenticity and integrity: the signer holds a private key, and anyone with the public key can verify that a message was signed by the key holder and was not modified.

ML-DSA replaces ECDSA and RSA-PSS in the post-quantum transition. ECDSA, standardized in FIPS 186-5, relies on the elliptic curve discrete logarithm problem, which Shor's algorithm solves efficiently. RSA-PSS relies on integer factorization, the other problem Shor's algorithm breaks.

ML-DSA defines three security levels. ML-DSA-44 provides AES-128-equivalent security with a 1,312-byte public key and a 2,420-byte signature. ML-DSA-65 provides AES-192-equivalent security with a 1,952-byte public key and a 3,309-byte signature. ML-DSA-87 provides AES-256-equivalent security with a 2,592-byte public key and a 4,595-byte signature.

The signature sizes are the main drawback. ECDSA with the P-256 curve produces 64-byte signatures. RSA-2048 produces 256-byte signatures. ML-DSA-44 produces signatures nearly ten times larger than ECDSA. For protocols where signatures are transmitted frequently (TLS certificate chains, DNSSEC, JWT tokens), this bandwidth increase is a real engineering concern. The ECDSA Signature tool shows current ECDSA signature sizes for comparison.

NIST also selected Falcon (to be standardized as FN-DSA in a future FIPS publication) as an alternative signature scheme with smaller signatures but more complex implementation requirements. Falcon uses NTRU lattices and requires floating-point arithmetic for signing, which makes constant-time implementation harder.

FIPS 205 standardizes SLH-DSA, formerly SPHINCS+. Unlike ML-KEM and ML-DSA, SLH-DSA is not lattice-based. It is a stateless hash-based signature scheme built on the Merkle tree construction. Its security depends only on the properties of the underlying hash function (SHA-2 or SHA-3), not on any number-theoretic assumption.

This conservative design choice is deliberate. Lattice-based cryptography is relatively new, and while no practical attacks on MLWE have been found, the cryptographic community has less confidence in lattice assumptions than in hash function security. NIST selected SLH-DSA as a hedge: if a breakthrough breaks lattice-based schemes, SLH-DSA remains secure because it relies only on hash functions.

The trade-off is performance. SLH-DSA signatures are 7,856 to 49,856 bytes depending on the parameter set. Signing takes milliseconds, not microseconds. Verification is faster but still slower than ML-DSA. SLH-DSA is not suitable for high-frequency signing operations or bandwidth-constrained protocols. Its primary use case is code signing, firmware signing, and long-term document signing where signature size and signing speed matter less than maximum confidence in the security assumption.

SLH-DSA parameter sets include SLH-DSA-SHA2-128s, SLH-DSA-SHA2-128f, SLH-DSA-SHA2-192s, SLH-DSA-SHA2-192f, SLH-DSA-SHA2-256s, and SLH-DSA-SHA2-256f, plus equivalent SHA-3 variants. The "s" variants optimize for signature size (smaller signatures, slower signing). The "f" variants optimize for signing speed (faster signing, larger signatures).

Shor's algorithm works by reducing factoring and discrete logarithms to the period-finding problem, which a quantum computer solves using the quantum Fourier transform. The algorithm finds the period of a function over a cyclic group, and that period reveals the factors of an integer or the discrete logarithm of a group element.

Lattice problems do not have this structure. The Learning With Errors (LWE) problem, introduced by Oded Regev in 2005, asks: given a matrix A and a vector b = As + e (where s is a secret vector and e is a small random error vector), recover s. The error vector e is what makes the problem hard. Without the error, this is a system of linear equations solvable by Gaussian elimination. With the error, the problem is provably as hard as the worst-case lattice problems, which are believed to resist both classical and quantum attacks.

The quantum Fourier transform does not help here because there is no periodic structure to exploit. The best known quantum attacks on LWE are Grover's algorithm variants, which provide a quadratic speedup over classical attacks. A quadratic speedup means AES-128-equivalent security drops to AES-64-equivalent under quantum attack, which is why the parameter sets are sized to account for this. ML-KEM-512 with Grover's speedup still provides roughly 64 bits of quantum security, matching the NIST security category 1 requirement.

Module-LWE extends this to polynomial rings, which gives better performance and smaller keys while maintaining the same security guarantees. The "module" in ML-KEM and ML-DSA refers to this polynomial ring structure.

The post-quantum transition is not a future problem. Several actions are actionable today.

Inventory your cryptographic dependencies. Identify where RSA, ECDSA, ECDH, and Diffie-Hellman are used in your systems. This includes TLS certificates, SSH keys, VPN configurations, code signing pipelines, database encryption, and API authentication. The Diffie-Hellman Key Exchange tool demonstrates the key exchange that TLS uses today.

Adopt hybrid key exchange where available. Google, Cloudflare, and Amazon have already deployed hybrid post-quantum TLS in production. Hybrid mode combines a classical algorithm (like X25519) with a post-quantum algorithm (like ML-KEM-768) so that the connection remains secure even if one of the two algorithms is broken. This is the approach recommended by the IETF in draft-ietf-tls-hybrid-design. OpenSSL 3.2 and later support ML-KEM through provider plugins.

Plan for crypto-agility. Hard-coding algorithm choices makes migration painful. Abstracting cryptographic operations behind interfaces lets you swap algorithms without rewriting application code. This is not a theoretical concern: the deprecation of SHA-1, MD5, and RC4 each required years of remediation across the industry because too many systems had algorithm choices baked into their architecture.

Monitor standards updates. NIST has indicated that additional FIPS publications for Falcon (FN-DSA) and a future digital signature standard from Round 4 candidates are forthcoming. Library support is evolving rapidly, with OpenSSL, BoringSSL, and liboqs adding ML-KEM and ML-DSA support throughout 2024 and 2025.

The TLS cipher suites explained post covers how cipher suite negotiation works and why it matters for the post-quantum transition. The encoding vs encryption vs hashing post clarifies the distinction between encoding (which provides no security) and encryption (which does), a distinction that becomes more important when discussing post-quantum migration with non-technical stakeholders.