NIST's Post-Quantum Signature Standards
In 1994, Peter Shor published Shor’s algorithm which showed how a hypothetical quantum computer could break most modern cryptographic algorithms.
At that time, no one had built a quantum computer capable of actually running Shor’s algorithm, but since then there’s been intense speculation about when we’ll be able to actually build a “Cryptographically Relevant Quantum Computer” (CRQC). Michele Mosca, co-founder of the Institute for Quantum Computing at Waterloo, estimated a 50% chance of a CRQC by 2031. The Global Risk Institute’s 2024 expert survey concluded the threat “may be closer than previously thought.” NIST itself stated in August 2024 that “a device with the capability to break current encryption methods could appear within a decade.” Germany’s BSI estimated 10-15 years from 2025, noting that “the question of ‘if’ or ‘when’ is no longer paramount.” And in March 2026, Google announced a 2029 target for completing its own post-quantum cryptography migration, signaling that the company believes Q-Day — the day a quantum computer can break current encryption — may arrive far sooner than the 2030—2035 window most forecasters had assumed.
Cryptographers prefer the terminology CRQC to just “Quantum Computer” because many of the quantum computers that have been built have a completely different architecture that makes them unable to run Shor’s algorithm. For example, D-Wave’s machines are quantum annealers designed for optimization problems — they lack the universal gate set needed for Shor’s algorithm entirely. Google’s Willow chip (announced December 2024) demonstrated a landmark result in quantum error correction, but with only 105 qubits it is roughly 40,000x short of the estimated 4 million physical qubits needed to factor RSA-2048.
In order to prepare for the arrival of such a machine, in 2016 NIST began a long-term project to identify and standardize new cryptographic algorithms that would remain secure in the presence of a CRQC.
NIST has been responsible for standardizing a lot of the cryptography we use every day including SHA-2 (FIPS 180-4), SHA-3 (FIPS 202), AES (FIPS 197), and ECDSA (FIPS 186-5).
To come up with SHA-3, NIST used a public competition, where anyone was allowed to submit a candidate hash function, and the candidates were then publicly analyzed, and after three rounds and five years, NIST chose Keccak to become the SHA-3 standard (64 submissions in 2008, narrowed to 51, then 14, then 5 finalists, with Keccak selected in October 2012 and FIPS 202 published in August 2015).
The SHA-3 standardization process was widely seen as a success, and NIST used the same process to come up with signature schemes that could plausibly resist a CRQC.
- December 2016 — NIST issues call for proposals for post-quantum algorithms
- November 2017 — Submission deadline closes (69 accepted from 82 submitted)
- January 2019 — Round 2 announced: 26 algorithms advance
- July 2020 — Round 3 announced: 7 finalists + 8 alternates
- May 2022 — The White House issues NSM-10, directing federal agencies to inventory vulnerable cryptographic systems and begin migrating to post-quantum standards, with a target of 2035
- July 2022 — Four algorithms selected for standardization (3 signatures + 1 KEM)
- December 2022 — Congress passes the Quantum Computing Cybersecurity Preparedness Act, codifying the PQ migration mandate into law and requiring agency migration plans within one year of NIST publishing standards
- August 2024 — FIPS 203, 204, and 205 published as final standards
In July 2022, NIST announced three signature schemes for standardization. Two of them — ML-DSA and SLH-DSA — were published as final standards in August 2024. The third, FALCON (now FN-DSA), was selected at the same time but its standard (FIPS 206) remains in development due to implementation complexity: FALCON requires careful floating-point arithmetic in its FFT-based signing, making it harder to specify securely against side-channel attacks.
| Original Name | Standard Name | FIPS | Approach | Status |
|---|---|---|---|---|
| CRYSTALS-Dilithium | ML-DSA | FIPS 204 | Lattice-based (module-LWE) | Final, Aug 2024 |
| SPHINCS+ | SLH-DSA | FIPS 205 | Hash-based (stateless) | Final, Aug 2024 |
| FALCON | FN-DSA | FIPS 206 | Lattice-based (NTRU + FFT) | In development |
All three of these schemes are “classical” schemes (meaning that they run on standard computers, not quantum computers), but they are believed to offer security in the presence of an attacker with a CRQC.
With these schemes in place, it is now time for people to begin migrating their software to use these new post-quantum signature schemes. This migration is not optional for the US government: NSM-10 (May 2022) directed federal agencies to inventory vulnerable systems and complete their transition by 2035, and the Quantum Computing Cybersecurity Preparedness Act (December 2022) codified the mandate into law, requiring agencies to have migration plans in place within one year of NIST publishing its standards — a deadline that has now passed.
This migration is also challenging because digital signatures are used everywhere, and the PQ signature schemes standardized by NIST all have signatures that are at least 10x larger than most prior signature schemes (e.g. ECDSA). Thus these schemes cannot easily be used as a drop-in replacement for ECDSA in situations where signature size is a bottleneck.