Core-SVP and Lattice Security Estimation
Core-SVP is the model that answers a question every buyer of post-quantum cryptography eventually asks: how do we know ML-KEM is “128-bit secure” when nobody has a quantum computer to test it against? The security of a lattice scheme cannot be measured by running the attack, because the attack is infeasible by design, so it is estimated by modeling the cost of the best known attack and confirming that cost clears a target. Core-SVP is the standard, deliberately conservative way to do that modeling, and the Lattice Estimator is the software that runs the calculation for real parameters. Understanding it is understanding why a lattice bit-security number is a careful floor with a cushion rather than a hard measured fact, and why those numbers get revised over time.
The short version:
- Lattice security is estimated on paper rather than measured by experiment. The attack (running BKZ with a large block size) is too expensive to actually run, so the cost is modeled analytically and checked against a target strength.
- Core-SVP is the standard conservative model. It charges the attacker only for the single most expensive step inside the attack, one call to a shortest-vector solver in the block dimension, which lower-bounds the true cost and builds in a safety margin.
- The Lattice Estimator is the tool. An open, community-maintained software module computes the block size an attack needs and the resulting cost for any given parameter set, so choices can be re-checked as knowledge improves.
- NIST security categories tie the number to something concrete. Instead of a raw bit count, a scheme is placed in a category defined by the difficulty of breaking AES or SHA, which is how security levels 1 through 5 are assigned.
- The estimates are conservative and get revised. They deliberately understate the attacker’s cost, and as sieving and reduction research sharpens, the numbers are updated, which is a feature of a healthy, watched field.
Picture estimating how long it would take a thief to tunnel into a vault you can never actually let them try. You cannot time the real break-in, so you model it: you take the fastest digging method anyone has published, you charge the thief only for the single hardest meter of rock, and you check that even that optimistic figure runs to centuries. If it does, you call the vault safe, knowing your estimate was generous to the thief on purpose so the real dig can only be slower. Core-SVP is that estimate for a lattice, and the safety margin comes from charging the attacker for the cheapest version of the hardest step.
Why does lattice security have to be estimated?
Lattice security has to be estimated because the attack that would break a scheme is, by construction, far too expensive to run, so its cost can only be reasoned about on paper. Breaking ML-KEM means recovering a Learning With Errors secret, and the best way to do that is to rephrase it as a lattice problem and attack it with BKZ at a large enough block size. The whole point of the parameter choice is that the required block size costs astronomically more than any computer could deliver, which means nobody can ever demonstrate the break to confirm the number. The security claim is therefore a claim about the modeled cost of an attack that will never be run at full size.
Source: NIST FIPS 203, Module-Lattice-Based Key-Encapsulation Mechanism Standard, August 13, 2024, csrc.nist.gov.
This is a real difference from symmetric cryptography, where “128-bit security” for AES means a brute-force key search over a space whose size is a plain, uncontested count. A lattice estimate has moving parts: how good the best reduction algorithm is, how its cost scales with block size, how many times it must run, and how much memory it needs. Each of those is an active research question, so the bit-security figure is the output of a model built from the current best answers, and it shifts as those answers improve. That is not a weakness unique to lattices. It is the honest cost of building security on a problem whose best attack is still being studied.
What is the core-SVP model?
The core-SVP model is a way of pricing a full lattice-reduction attack by charging only for its single most expensive ingredient: one call to a shortest-vector-problem solver in the block dimension. A real BKZ run calls such a solver many times, on many blocks, across many rounds, and drags along memory and bookkeeping costs. Core-SVP throws all of that away and counts one solve. Because the real attack does strictly more work than that, the core-SVP figure is a lower bound on the attacker’s cost, which is exactly the conservative direction you want a security estimate to lean: it credits the attacker with the cheapest imaginable version of the attack, so the true attack can only be harder.
Source: E. Alkim, L. Ducas, T. Pöppelmann, P. Schwabe, “Post-quantum key exchange - a new hope,” USENIX Security 2016, IACR ePrint 2015/1092.
The single number that solve costs comes from the best known lattice sieve. Classically, the Becker-Ducas-Gama-Laarhoven sieve of 2016 runs in time about 2^(0.292 times the block size). A quantum-accelerated variant is estimated at roughly 2^(0.265 times the block size), which is where a lattice scheme’s separate “quantum” security figure comes from. So the core-SVP recipe is: find the smallest block size at which the attack recovers the secret, then read off 2^(0.292 times that block size) for the classical strength and 2^(0.265 times that block size) for the quantum strength. Everything else about the attack is deliberately left uncounted, as a cushion.
Source: A. Becker, L. Ducas, N. Gama, T. Laarhoven, “New directions in nearest neighbor searching with applications to lattice sieving,” SODA 2016, IACR ePrint 2015/1128.
What is the Lattice Estimator and what does it do?
The Lattice Estimator is the open, community-maintained software that carries out this calculation for a concrete parameter set, so a designer does not have to work the block-size arithmetic by hand. Written as a module for the Sage mathematics system and maintained by Martin Albrecht along with a group of contributors, it takes the parameters of an LWE, SIS, or NTRU instance and estimates the cost of the known attacks against it, including the primal and dual lattice-reduction attacks. It is the direct successor to the earlier “LWE Estimator” from Albrecht, Player, and Scott’s 2015 study of the concrete hardness of Learning With Errors.
Source: M. Albrecht et al., “Lattice Estimator,” github.com/malb/lattice-estimator; M. R. Albrecht, R. Player, S. Scott, “On the concrete hardness of Learning with Errors,” Journal of Mathematical Cryptology, 2015, IACR ePrint 2015/046.
The value of a shared, open tool is that it makes security claims reproducible and comparable. When a scheme’s designers publish a parameter set and a security estimate, anyone can run the same estimator against those parameters and check the number, and when a cryptanalyst finds a better attack, they can add it to the estimator so its effect on every scheme is visible at once. This is the mechanism behind the “automated, repeatable verification” posture that serious cryptography demands: the estimate is not an assertion in a paper, it is a computation anyone can re-run as the state of the art moves. That re-runnability is also why bit-security figures for the same scheme can differ slightly between sources, since they depend on which version of the estimator and which cost assumptions were used.
How do NIST security categories fit in?
NIST security categories are the layer that turns a raw estimated cost into a policy-usable label, by pegging each level to the difficulty of a well-understood symmetric problem rather than to an abstract bit count. Instead of certifying a scheme as “so many bits,” NIST defined five categories, and a scheme qualifies for a category if breaking it is at least as hard as a named reference task, the reference tasks being key searches and collision searches against AES and SHA-3. That framing sidesteps arguments about the exact bit figure and anchors the claim to primitives the whole field trusts.
| NIST category | At least as hard as | Example ML-KEM parameter set |
|---|---|---|
| 1 | Key search on AES-128 | ML-KEM-512 |
| 3 | Key search on AES-192 | ML-KEM-768 |
| 5 | Key search on AES-256 | ML-KEM-1024 |
Source: NIST, “Submission Requirements and Evaluation Criteria for the Post-Quantum Cryptography Standardization Process,” 2016, csrc.nist.gov; NIST FIPS 203, August 13, 2024, csrc.nist.gov.
The practical translation is direct. When you see ML-KEM-768 described as category 3, the chain behind that label is: the core-SVP model, run through the Lattice Estimator on ML-KEM-768’s parameters, produces a cost that meets or exceeds the difficulty of an AES-192 key search, so NIST places it in category 3. Choosing a parameter set is choosing a category, and choosing a category is choosing which symmetric strength you want the lattice scheme to match. See Security Level (NIST) for the full category-to-parameter map across all the standards.
Why are these estimates conservative, and why do they change?
The estimates are conservative on purpose, because a security floor should credit the attacker generously so the real world can only be safer, and they change because the science underneath them is genuinely alive. The core-SVP model already leans conservative by charging for a single sieve call and ignoring the memory, the many repeated calls, and the bookkeeping a real attack pays for. On top of that, the standardized parameters are chosen with extra room above the target category, so a modest improvement in cryptanalysis does not immediately push a scheme below its label. The design goal is that the published number is a floor with a cushion, and the true attack cost sits comfortably above it.
The revisions happen because lattice reduction and sieving are active research areas where the cost figures keep sharpening in both directions. A faster sieve lowers the estimated cost of a given block size and pushes bit-security estimates down; a discovery that a real attack needs far more memory than assumed pushes them back up. Neither kind of update is a crisis. It is the intended behavior of a field that keeps its attacks in the open and its estimator re-runnable, so the numbers track the best current understanding rather than freezing at a first guess. The honest caveat this leaves is that lattice security rests on a belief that these algorithms will keep improving only slowly, which is why the standards also fund code-based and hash-based backups on unrelated math.
The MATZOV 2022 report, a worked example of the estimate moving
The clearest concrete example of a downward revision is the April 2022 report from MATZOV, the Center of Encryption and Information Security of the Israeli Defense Forces, titled Report on the Security of LWE: Improved Dual Lattice Attack. It refined the dual attack on Learning With Errors with two ingredients, enumerating over more coordinates of the secret and swapping in an FFT-based distinguisher, and the combined effect measurably lowered the estimated security of Kyber, Saber, and Dilithium, in the report’s own framing bringing them below the thresholds NIST had defined for their categories. This is the abstract point about incremental cryptanalysis made concrete: the same class of scheme, the same parameters, a lower published cost, arrived at by sharpening the model rather than building any hardware.
Source: MATZOV, Report on the Security of LWE: Improved Dual Lattice Attack, April 2022, zenodo.org/records/6412487.
The follow-through is the part worth keeping in view. The MATZOV numbers are not universally accepted, because the sharpest versions of the dual attack rest on an independence assumption that later work argued contradicts well-tested heuristics in certain regimes, so the size of the drop is itself contested and has been partly walked back by subsequent analysis. That is the conservative margin doing its job: the parameters carried enough cushion above their category that an incremental attack of this strength moved the estimated floor without breaking the scheme, and the community response was a public back-and-forth in the open literature rather than a scramble. The lesson for a planner is that a headline claiming a PQC scheme was “weakened” usually describes exactly this kind of margin-eating refinement, not a practical break, and the way to read it is to ask whether the parameters still clear their NIST category after the dust settles.
Common misconceptions
- “128-bit security means the same thing for ML-KEM as for AES.” For AES it is a plain count of keys to search. For ML-KEM it is the output of a model, the conservative core-SVP estimate, that depends on the best known lattice attack, so it is a careful floor with a cushion rather than an uncontested measured number.
- “If the security estimate went down, the scheme is broken.” A downward revision usually means a sharper cost model or a slightly faster sieve, not a practical break. The parameters carry margin above the target, so a modest revision moves the floor, not the roof, and the schemes stay well inside their categories.
- “Core-SVP is the exact cost of the attack.” It is deliberately a lower bound. It charges the attacker for one call to a shortest-vector solver and ignores the memory and the many repeated calls a real BKZ run needs, so the genuine attack is more expensive than the estimate.
- “The NIST category is a raw bit number.” A category is defined by comparison to a symmetric reference task, like breaking AES-192, rather than by a specific bit count. That anchors the claim to well-understood primitives and avoids fights over the precise lattice bit figure.
- “You can just measure lattice security by running the attack.” The attack is infeasible by construction, which is the entire point of the parameters. Security can only be estimated, which is why the model and the estimator exist and why the number is reproducible rather than measured.
Questions people ask
How is the security of ML-KEM actually estimated? By modeling the best known attack. The LWE secret is rephrased as a lattice problem, the BKZ block size needed to solve it is computed, and the core-SVP model prices that block size using the best lattice sieve. The Lattice Estimator runs the calculation, and the result is checked against a NIST category.
What does core-SVP mean? It is a conservative costing model that charges an attacker only for the single most expensive step of a lattice-reduction attack, one call to a shortest-vector solver in the block dimension. Because a real attack does far more work, core-SVP gives a lower bound on cost, which is the safe direction for a security estimate to err.
Why do different sources give slightly different bit-security numbers for the same scheme? Because the number is the output of a model with assumptions (which sieve, which cost exponents, how much memory), and those assumptions differ between sources and versions of the estimator. The figures cluster closely and all clear the scheme’s NIST category; the small spread reflects an active field rather than disagreement about safety.
Do the security estimates get weaker over time? They get revised in both directions as cryptanalysis sharpens. A faster sieve lowers an estimate; a more realistic memory cost raises it. The standardized parameters carry deliberate margin above their category so ordinary revisions do not drop a scheme below its label, and the field watches this continuously.
What is the Lattice Estimator? An open, community-maintained software module (for the Sage system, maintained by Martin Albrecht and contributors) that computes the estimated cost of the known attacks against a given lattice parameter set. It makes security claims reproducible: anyone can re-run it, and new attacks get added so their effect is visible across all schemes.
How does an estimate become a NIST security level? NIST defined categories 1 through 5 by the difficulty of breaking a reference symmetric primitive (AES-128, AES-192, AES-256, and hash-collision tasks). A scheme’s estimated cost is compared to those references, and it lands in the highest category it clears, which is how ML-KEM-512, ML-KEM-768, and ML-KEM-1024 map to categories 1, 3, and 5.
Everything here is the map, given freely. When your team needs the security levels behind its post-quantum choices explained and defended to an auditor, that’s what an alignment briefing is for.
Last verified 2026-07-14 · Maintained by Addie LaMarr, LaMarr Labs.