Marin Ivezic
NIST’s December 2016 call for post-quantum proposals set out five security strength categories instead of a list of required bit strengths. Nine years later those five numbers run through the parameter tables of FIPS 203, FIPS 204 and FIPS 205, through procurement questionnaires, and through the algorithm-selection questions on most post-quantum assessments. They are also, in our experience of marking that work, the single most confidently misread thing in the standards.
What a security category actually claims
A category isn’t a measurement of how strong an algorithm is, it’s a floor. The claim takes one shape: breaking this parameter set should cost at least as much as solving a named reference problem drawn from symmetric cryptography.
That phrasing does real work. NIST could have asked submitters to state a bit strength, and submitters would have complied, and the numbers would have been incomparable across lattices, hashes, codes and isogenies, because each family measures its own hardness differently and each set of estimates carries its own uncertainty. Anchoring instead to AES and SHA gives one yardstick that every submission has to be held against. Whatever we don’t know about lattice cryptanalysis, we know a great deal about the cost of attacking AES.
The five categories
Categories 1, 3 and 5 are anchored to key search: recovering one specific secret key by trying candidates until one works. Categories 2 and 4 are anchored to collision search: finding any two distinct inputs that produce the same hash output.
| Category | Reference problem | Approximate classical work | Comparable classical public key |
|---|---|---|---|
| 1 | Key search on a 128-bit block cipher (AES-128) | 2^128 | RSA-3072, ECC P-256 |
| 2 | Collision search on a 256-bit hash (SHA-256) | 2^128 | no clean equivalent |
| 3 | Key search on a 192-bit block cipher (AES-192) | 2^192 | RSA-7680, ECC P-384 |
| 4 | Collision search on a 384-bit hash (SHA-384) | 2^192 | no clean equivalent |
| 5 | Key search on a 256-bit block cipher (AES-256) | 2^256 | RSA-15360, ECC P-521 |
The public-key column comes from the comparable-strength tables in NIST SP 800-57 Part 1, and it’s a rough mapping rather than an equivalence. Categories 2 and 4 have no entry because collision resistance has no meaningful RSA analogue.
Why two different reference problems
The two families exist because two different attacks dominate in two different settings. Break a key encapsulation mechanism and you are usually recovering a specific secret. Break a signature scheme and you may be doing something else entirely: producing two messages that hash to the same value, then transplanting a legitimate signature onto the one the signer never saw. A scheme can resist the first attack comfortably and fail at the second.
Categories 1 and 2 both sit near 128 bits of classical work, and 3 and 4 both sit near 192. The ladder isn’t evenly spaced, and NIST’s ordering of 2 below 3 rests on an explicit assumption: that a collision on SHA-256 becomes reachable before a key search on AES-192 does. If that assumption ever inverts, the ordering inverts with it.
The quantum arithmetic behind the floors
The reference problems were chosen partly because we understand their quantum attack costs better than we understand anyone else’s.
Grover and key search
Grover’s algorithm searches an unstructured space of 2^n in about 2^(n/2) evaluations, which suggests AES-128 falls to roughly 2^64 quantum steps. Read on its own, that number is misleading. Grover’s speedup is fundamentally serial: the algorithm builds its advantage over a long sequence of iterations that cannot be split across machines cheaply. Run the search on two quantum computers instead of one and you gain a factor of the square root of two, not a factor of two. Parallelism buys much less here than intuition suggests.
Once the serial cost is folded in, the total gate count for key search on AES-128 climbs far beyond the naive 2^64, and even the friendliest assumptions leave it outside anything on a current hardware roadmap. MAXDEPTH is NIST’s ceiling on how many gate operations an attacker can run in sequence. It constrains runtime and the parallelism an attacker needs, not the total gate count.
Collision search and BHT
The Brassard-Hoyer-Tapp algorithm (BHT) finds hash collisions in about 2^(n/3) steps, against 2^(n/2) for the classical birthday attack. For SHA-256 that drops the theoretical figure from 2^128 to roughly 2^85, and that is where most summaries stop.
The step count omits the memory. BHT needs quantum-accessible random access memory on the order of the step count itself, and no one has a credible design for storing and addressing 2^85 entries coherently. Under any cost model that charges for memory, classical parallel collision search remains competitive. This is why Category 2 survives as a meaningful tier despite the headline exponent.
MAXDEPTH
MAXDEPTH is the constraint candidates most often skip, and it is worth stating what sets the ceiling: decoherence or wall-clock time ends any computation eventually, and NIST put forward plausible values from about 2^40 up to 2^96. An attack whose natural circuit depth exceeds the ceiling has to be restructured into parallel chunks, and for Grover that restructuring is expensive rather than free.
The practical consequence: submissions are evaluated on several metrics at once, including quantum gate count, circuit depth and classical operations, and a parameter set only earns a category when it clears the reference cost on all of them.
Where the standardized parameter sets land
| Parameter set | Standard | Category |
|---|---|---|
| ML-KEM-512 | FIPS 203 | 1 |
| ML-KEM-768 | FIPS 203 | 3 |
| ML-KEM-1024 | FIPS 203 | 5 |
| ML-DSA-44 | FIPS 204 | 2 |
| ML-DSA-65 | FIPS 204 | 3 |
| ML-DSA-87 | FIPS 204 | 5 |
| SLH-DSA-128s and 128f | FIPS 205 | 1 |
| SLH-DSA-192s and 192f | FIPS 205 | 3 |
| SLH-DSA-256s and 256f | FIPS 205 | 5 |
ML-KEM is the standardized key encapsulation mechanism, ML-DSA and SLH-DSA the standardized signature schemes, the first lattice-based and the second hash-based. FN-DSA, drafted as FIPS 206 and not final at the time of writing, follows the same pattern with FN-DSA-512 at Category 1 and FN-DSA-1024 at Category 5.
ML-DSA-44 is the only standardized set that uses Category 2 at all, and the choice reflects the collision-resistance argument above: for a signature scheme, the collision floor is the relevant one.
Choosing a category for a real deployment
The default rule is to match what you are replacing. A system protecting traffic at roughly 128-bit strength today, with AES-128 and RSA-3072 or P-256, has Category 1 as its minimum equivalent. A system on P-384 and AES-192 should be looking at Category 3. AES-256 points at Category 5.
Two constraints usually override the default.
The first is regulation. The NSA’s Commercial National Security Algorithm Suite 2.0 (CNSA 2.0) specifies ML-KEM-1024 and ML-DSA-87 for national security systems, which is Category 5 with no discretion. If you supply into that space, the decision is already made.
The second is size. Higher categories mean larger keys, larger ciphertexts and larger signatures, and in constrained protocols that cost is real. NIST’s own guidance during the process was that Categories 1 through 3 would very likely be sufficient for the foreseeable future, with 4 and 5 held as hedges against unexpected cryptanalytic progress. ML-KEM-768 has become the de facto commercial default for good reasons on both sides of that trade.
Three misreadings we see in assessments
Treating the category as a bit count. Category 3 is a floor, not a bit count: it says the best known attack on the parameter set costs at least as much as key search on AES-192 under the specified cost models. Two Category 3 schemes from different families may have very different margins above that floor.
Assuming even spacing. Categories 1 and 2 sit at comparable classical work, as do 3 and 4. Moving from Category 1 to Category 2 is a change of attack model, not a step up in strength.
Forgetting that the floor is a claim under assumptions. ML-KEM-512 sat at the centre of a long argument over whether its Category 1 claim held under the most pessimistic cost assumptions for lattice sieving. The claim survived and the parameter set was standardized. The lesson stands anyway: a category is an assertion about a cost model, and cost models are revised.
Where this fits in certification prep
Categories are the connective tissue between a threat model and a parameter table, which is why they appear in nearly every part of our post-quantum curriculum: in algorithm selection, in migration planning, and in the assessment questions that ask candidates to justify a choice rather than recall it.
Our post-quantum cryptography certification programs cover the categories alongside the FIPS 203, 204 and 205 parameter sets, the cost models behind them, and the selection decisions they drive in real migrations. You can review the current programs and enrollment details at quantumacademy.com/.
For migration methodology that builds on these selection decisions, see pqcframework.org. For deeper technical background on the standards themselves, PostQuantum.com carries the longer analyses.