Parameters and the Security Estimate: Core-SVP, BKZ Block Size, and NIST Levels

Abstract

A hardness assumption does not by itself tell an engineer which numbers to use. This piece bridges the gap between asymptotic lattice hardness and the concrete parameters of the deployed standards. It describes the attack that sets the bar — lattice-basis reduction with a sieving subroutine, applied to LWE embedded as a lattice problem — and the block size that controls its cost. It then presents the conservative Core-SVP cost model, which prices an attack as a single call to a sieving oracle in the reduction's block dimension, giving the familiar exponents that separate classical from quantum effort. It connects the required block size to the root-Hermite factor and the geometry of a reduced basis, maps the results onto NIST's security categories, and explains why estimates are a moving target that standards absorb with margin. The theme: parameter choice is an explicit cost accounting against the best known attack, deliberately conservative, and revised as attacks improve.

Knowing that a problem is believed hard is not the same as knowing which numbers make it hard enough. The gap between the asymptotic statements of the previous articles and a deployable scheme is filled by a concrete security estimate: a quantitative accounting of how much work the best known attack costs at a given choice of dimension, modulus and error, tuned so that the cost exceeds a target such as the effort to search a 128-bit key. This article develops that accounting — the attack that sets the bar, the cost model used to price it, the basis geometry that fixes the model's key parameter, and the way the results map onto the security levels the standards claim.

The attack that sets the bar

Concrete security is measured against the best known attack, and for lattice schemes that attack is basis reduction combined with sieving. An LWE instance is first turned into a purely geometric problem: the samples and the noisy values are embedded into a lattice constructed so that the secret-and-error vector appears as an unusually short vector in it. Recovering the secret becomes finding that short vector — a unique shortest vector or bounded-distance decoding problem on the embedded lattice. This is the primal attack; a closely related dual attack instead looks for short vectors in the orthogonal lattice to distinguish samples from uniform.

The workhorse for finding short vectors is the Block-Korkine-Zolotarev algorithm, BKZ. It improves a lattice basis by repeatedly solving the exact shortest-vector problem within projected blocks of a chosen size, the block size beta, and stitching the results together. Larger blocks produce shorter vectors and thus a stronger attack, but the cost of each block's exact solve grows steeply with beta. The entire difficulty of the attack, and therefore the entire security estimate, concentrates in one question: how large a block size beta is needed to find a vector short enough to recover the secret?

The exact-solve inside each block is itself performed by a sieving algorithm, which is where the dominant cost lives. So the estimate reduces to two linked quantities: the block size beta required for the attack to succeed, and the cost of the sieving oracle at that block size. The next two sections handle them in turn.

The instance is embedded as a lattice, reduced by BKZ at some block size, whose per-block sieving cost sets the security estimate.

Core-SVP: a conservative cost model

The Core-SVP model, standard in the concrete-hardness literature, prices an attack in the most conservative reasonable way. BKZ makes many calls to its block-size sieving oracle — a number polynomial in the dimension — but Core-SVP charges for only a single call, ignoring the polynomial multiplier entirely. Because it undercounts the real work, it yields a lower bound on attack cost, and choosing parameters against a lower bound errs on the side of security: the true attack is at least this expensive and probably more.

The cost of one sieving call in block dimension beta is exponential in beta, with a leading exponent established by the best known sieve algorithms. Classically the exponent is approximately 0.292, so the cost is two raised to roughly 0.292 times beta. The best known quantum sieve improves the exponent modestly, to approximately 0.265, reflecting a Grover-style square-root-flavored speedup on part of the search rather than an exponential collapse. The quantum improvement is real but small — nothing like the catastrophe Shor's algorithm inflicts on factoring — which is exactly why lattice problems anchor post-quantum security.

The smallness of the quantum gain deserves emphasis. Moving the exponent from 0.292 to 0.265 shaves roughly a tenth off the exponent; a problem needing block size a few hundred to reach 128-bit classical security still needs a large block size against a quantum attacker. There is no known quantum algorithm that changes the exponential character of lattice sieving, and that is the structural reason the standards can claim quantum resistance with only moderately larger parameters than a purely classical analysis would demand.

The best known quantum sieve lowers the Core-SVP exponent only modestly, from about 0.292 to 0.265 — a small gain, not an exponential collapse.

\[\text{Core-SVP cost} \approx 2^{0.292\,\beta}\ (\text{classical}), \qquad 2^{0.265\,\beta}\ (\text{quantum})\]

\[\text{single sieve call charged; the polynomial number of BKZ calls is ignored (a lower bound)}\]

Finding the block size

The block size beta that an attack requires is fixed by the geometry of a BKZ-reduced basis. Under the geometric series assumption, a widely used and empirically supported heuristic, BKZ at block size beta produces a basis whose successive vector lengths decay in a geometric progression governed by a single quantity, the root-Hermite factor, written as delta. A larger block size yields a delta closer to one and thus a slower decay and shorter vectors overall; delta is the compact summary of how much a given block size accomplishes.

The attack succeeds when the reduction is strong enough that the embedded short vector — the secret-and-error vector the primal attack is hunting — stands out from the geometric progression predicted by the assumption. Writing that success condition in terms of delta, the dimension of the embedded lattice, and the size of the error yields an inequality that can be solved for the smallest beta that works. That beta, fed into the Core-SVP exponent, produces the estimated bit-security of the parameter set. The chain is fully explicit: parameters determine the embedding geometry, the geometry determines the required beta, and beta determines the cost.

Because doing this by hand is error-prone, the community relies on the lattice estimator of Albrecht and collaborators, an open tool that enumerates the known attacks — primal, dual and their variants — computes the required block size for each under the standard heuristics, applies the cost models, and reports the minimum over attacks as the estimated security. Every serious lattice parameter set is checked against it.

\[\delta(\beta) \approx \left(\tfrac{\beta}{2\pi e}\right)^{1/(2\beta)} \quad(\text{root-Hermite factor; } \delta \to 1 \text{ as } \beta \text{ grows})\]

\[\text{GSA: } \|\mathbf{b}_i^{*}\| \approx \delta^{\,d-2i}\, \mathrm{Vol}(\mathcal{L})^{1/d}; \quad \text{success when the planted vector beats this profile}\]

Mapping onto NIST security levels

The estimated bit-security is finally compared against the security categories that the standardization process defined. Rather than fixing an abstract bit count, the categories are anchored to the cost of attacking well-understood symmetric primitives: category one requires an attack at least as costly as exhaustively searching a 128-bit block-cipher key, category three ties to a 192-bit key, and category five to a 256-bit key. Phrasing the target in terms of key search rather than a bare exponent keeps the goalposts tied to primitives whose security is broadly agreed upon.

The table below lines up the three deployed key-encapsulation parameter sets against these categories. Each set is chosen so that its estimated attack cost, computed through the chain just described, clears the corresponding key-search bar with margin. The larger module ranks of the previous article are precisely how the higher categories are reached: more rank raises the embedded dimension, which raises the required block size, which raises the Core-SVP cost into the higher category.

The order-of-magnitude gate counts in the table are approximate and model-dependent; different cost models shift them, which is the point of the next section. What is stable is the alignment: each parameter set is designed to sit at or above its category's symmetric-key reference under the conservative Core-SVP accounting.

NIST security categories anchored to symmetric key search, with the ML-KEM parameter set targeting each. Gate counts are approximate and model-dependent.
NIST category	Classical bar (approx.)	Reference primitive	ML-KEM set
Category 1	~2^143 gates	AES-128 key search	ML-KEM-512
Category 3	~2^207 gates	AES-192 key search	ML-KEM-768
Category 5	~2^272 gates	AES-256 key search	ML-KEM-1024

A moving target, absorbed by margin

A concrete security estimate is a snapshot of the best known attack, not a permanent truth, and it moves as the attacks improve. Sieving has been optimized repeatedly, memory-versus-time trade-offs are actively studied, and there is a running debate about whether Core-SVP is too conservative — it ignores the polynomial number of BKZ calls and the real cost of the enormous memory sieving needs — or, conversely, whether a pure gate-count that includes memory access is the fairer measure. Reasonable analyses of the same parameter set can differ by tens of bits depending on which accounting is used.

Standards absorb this uncertainty with margin rather than precision. The deployed parameters are set comfortably above the category bars under the conservative model, so that plausible future improvements in sieving erode the margin without breaching the target. This is why a parameter set advertised for a given category typically shows an estimated security noticeably higher than the bar: the excess is a deliberate buffer against the attack getting better, which historically it does, gradually, rather than suddenly.

For anyone deploying these schemes — including the operators of large autonomous agent fleets that will rely on post-quantum key exchange at scale — the practical discipline follows from this. Track the parameter sets the standards specify rather than inventing your own; re-check against the current lattice estimator when planning long-lived systems; and prefer the higher category for secrets that must remain confidential for decades, since the margin, not a single point estimate, is what carries the security forward through years of incremental cryptanalysis.

📌

Estimates move; margins carry. A bit-security number is a snapshot of today's best attack. Standards sit above the category bar on purpose so that gradual sieving improvements erode margin without breaching the target — track the standard sets rather than hand-tuning.

Key takeaways

Concrete security is measured against the best known attack: embed the LWE instance as a lattice so the secret-and-error vector is unusually short, then find it with BKZ basis reduction plus sieving.
The whole estimate turns on the BKZ block size beta needed to succeed and the cost of the sieving oracle at that block size, which dominates the work.
The conservative Core-SVP model charges a single sieve call — a lower bound — at cost roughly 2^(0.292 beta) classically and 2^(0.265 beta) quantumly; the small quantum gain is why lattices resist quantum attack.
The required beta follows from the root-Hermite factor and the geometric series assumption: parameters fix the embedding geometry, geometry fixes beta, and beta fixes the Core-SVP cost.
NIST categories anchor targets to symmetric key search (128/192/256-bit), and ML-KEM-512/768/1024 are chosen to clear categories 1/3/5 with margin via increasing module rank.
Estimates are a moving target as sieving and cost models improve; standards absorb the uncertainty with deliberate margin, so track the standardized sets and re-check long-lived deployments against the current estimator.

Practitioner Toolkit

Copy-paste, strictly defensive artifacts you can use today. Nothing here attacks a real system.

✅Auditing a lattice parameter claimchecklist

Check that a security estimate is stated precisely enough to trust.

Which attacks were considered (primal, dual, and their variants)?
What cost model is used (Core-SVP vs a gate-count including memory)?
What block size beta does the attack require, and what estimated bit-security results?
Which NIST category is targeted, and how much margin above the bar is there?
Was the estimate produced by a current lattice estimator, and when?

🚀Re-check a deployment's parametersquickstart

Refresh a long-lived system's security estimate before relying on it.

Record the exact standardized parameter set in use (do not hand-tune).
Run the current lattice estimator against it for classical and quantum models.
Compare the reported security to the target category bar and note the margin.
For decades-long secrets, prefer the higher category to bank extra margin.

🔒Parameter-margin recordpolicy

A documentation stub capturing the estimate and its margin.

lattice_parameters:
  scheme_set: ML-KEM-768
  target_category: 3          # AES-192 key-search bar
  cost_model: core_svp        # conservative lower bound
  estimated_security_bits: recorded_from_estimator
  margin_above_bar_bits: recorded
  attacks_considered: [primal, dual]
review:
  estimator_version: recorded
  recheck_due: for_long_lived_systems

Illustrative documentation template, not a product config.

Glossary

Primal / dual attack: Embedding an LWE instance as a lattice so the secret-and-error vector is short (primal), or working in the orthogonal lattice to distinguish samples from uniform (dual).
BKZ / block size (beta): Block-Korkine-Zolotarev basis reduction, which solves exact shortest-vector problems in projected blocks of size beta; larger beta gives shorter vectors at steeply higher cost.
Sieving: The exponential-time algorithm used to solve the exact shortest-vector problem inside each BKZ block; it dominates the attack cost.
Core-SVP model: A conservative cost accounting that charges one sieve call in dimension beta, giving cost about 2^(0.292 beta) classical and 2^(0.265 beta) quantum.
Root-Hermite factor (delta): A single quantity summarizing how short the vectors a given block size produces; delta approaches one as beta grows, under the geometric series assumption.
NIST security category: A target anchored to symmetric key search: categories 1, 3, 5 require attacks at least as costly as searching 128-, 192-, 256-bit keys.