Lattice Parameter Selection — Security Levels and Trade-offs

Choosing the parameters of an LWE-based cryptosystem is not guesswork. There is a rigorous methodology — the Core-SVP model — that takes LWE parameters $(n, q, \sigma)$ and computes the bit-security of the resulting scheme by estimating the cost of the best known attack. This section explains the methodology, the tools, and the tradeoffs that drive parameter selection for real-world PQC deployments.

Beginner's Intuition 💡

Choosing the right parameters for lattice cryptography is like choosing the dimensions of a bank vault.

If the walls are too thin (low parameters), robbers (hackers) will break in. But if the walls are fifty feet thick solid steel (extremely high parameters), the vault is completely impenetrable, but it's so heavy and expensive that the bank can't even afford to open the doors to do business (the cryptography is perfectly secure, but extremely slow and uses too much memory).

Parameter Selection is the rigorous, heavily tested mathematical process of finding the exact "Goldilocks zone"—parameters that are mathematically guaranteed to be unbreakable by both current and future quantum computers, while still being small and fast enough to use every day on your smartphone.

The Core-SVP Security Model

The idea is direct: security is measured by the cost of the best known lattice attack. The best attacks on LWE all reduce to solving SVP in a related lattice via BKZ reduction. The minimum block size $\beta$ needed for the attack to succeed determines the security — because the cost of BKZ- $\beta$ is exponential in $\beta$ .

Definition 34 — Core-SVP Security

The Core-SVP security of an LWE instance is:

$\lambda_{\mathrm{core}} = \min_{\text{attack}} \log_2(T_{\mathrm{SVP}}(\beta^*))$

where the minimum is over all known attacks (primal, dual, combinatorial), and for each attack, $\beta^*$ is the optimal block size that minimizes the total attack cost, and $T_{\mathrm{SVP}}(\beta^*)$ is the cost of running BKZ- $\beta^*$ .

SVP cost models: classical $T_{\mathrm{SVP}}(\beta) = 2^{0.292\beta}$ (using sieving); quantum $T_{\mathrm{SVP}}(\beta) = 2^{0.265\beta}$ (quantum sieving with QRAM).

The Three Main LWE Attacks

Attack 1: The Primal (Usvp) Attack

The primal attack embeds the LWE secret and error as a short vector in a higher-dimensional lattice, then uses BKZ to find it. Given $$m$$ LWE samples $(A \in \mathbb{Z}_q^{m \times n}, b = As + e)$ , construct the $$(m+n+1)$$ -dimensional lattice containing the short vector $$(s, e, 1)$$ . BKZ must find this vector, whose length is $\approx \sqrt{n+m} \cdot \sigma$ .

Primal Attack Cost

The primal attack succeeds when the embedded vector becomes the unique shortest vector — i.e., when BKZ- $\beta$ output root Hermite factor satisfies:

$\delta_\beta^{2m} \cdot q^{2(m-n)/m} \leq \sigma^2 \cdot (m+n)$

Solving for the optimal number of samples $$m^*$$ and minimum block size $\beta^*$ gives the primal attack cost $2^{0.292\beta^*}$ . The Lattice Estimator automates this optimization numerically.

Attack 2: The Dual Attack

The dual attack finds a short vector $$w$$ in the dual lattice $\Lambda_q(A)^\vee$ . Such a vector distinguishes LWE samples from random: the inner product $\langle w, b \rangle \approx \langle w, As \rangle + \langle w, e \rangle$ has small second term (since $$w$$ is short and $$e$$ is small), making it distinguishable from uniform.

Dual Attack Cost

Find a short dual vector $w \in \Lambda_q(A)^\vee$ with $\|w\| = \delta^m \cdot q^{1-m/n}$ (BKZ output norm in the dual lattice). This distinguishes LWE from random when the advantage satisfies:

$\epsilon \approx e^{-\pi \|w\|^2 \sigma^2}$

To amplify advantage to a constant, repeat distinguishing with $T = 1/\epsilon^2$ trials. Total cost: $T_{\mathrm{BKZ}}(\beta) \cdot T$ . For most LWE parameters, the primal attack is slightly cheaper than the dual attack after the 2020 improvements to dual attacks (Ducas-Pulles 2023).

Attack 3: Combinatorial Attacks (for binary/ternary secrets)

When the LWE secret distribution is very sparse (binary: $s \in \{0,1\}^n$ , or ternary: $s \in \{-1,0,1\}^n$ ), combinatorial attacks become competitive. The most important is the BKW algorithm (Blum-Kalai-Wasserman) and its variants, including meet-in-the-middle and sparse secret lattice attacks.

Dilithium and Kyber use secret distributions bounded by a small constant ( $\eta = 2$ or 3), making the secret ternary. This is why combinatorial attacks must be included in the security analysis — the Lattice Estimator accounts for them automatically.

The Lattice Estimator

The Lattice Estimator (Albrecht, Player, Scott — and contributors) is the standard open-source tool for computing LWE security estimates. All NIST PQC submissions were required to provide Lattice Estimator security estimates. It implements:

Algorithms implemented

Primal uSVP attack (via BKZ- $\beta$ with BKZ simulator)
Primal hybrid attack (lattice reduction + MITM)
Dual attack (and Ducas-Pulles improvement)
Dual hybrid attack
BKW and its variants
Arora-Ge algebraic attack
Exhaustive search (for small secret spaces)

Cost models

Three classical SVP cost models: sieving $2^{0.292\beta}$ , enumeration $2^{0.18\beta}$ , or user-specified.

Two quantum models: quantum sieving $2^{0.265\beta}$ , or Grover-amplified enumeration.

BKZ simulation (Chen-Nguyen) for accurate Gram-Schmidt profile prediction.

Usage

Written in Python (SageMath and pure Python versions). Install: pip install lattice-estimator.

Input: LWE parameters as an LWE.Parameters object. Output: dictionary mapping attack names to estimated bit costs. Open source: github.com/malb/lattice-estimator ↗

Concrete Security Estimates

To illustrate the methodology, here are the security estimates for the three ML-KEM parameter sets computed via the Lattice Estimator with the BKZ-sieving cost model:

ML-KEM Security Estimates (Core-SVP, BKZ+Sieve)

ML-KEM-512 ( $n=256, k=2, q=3329, \eta_1=3, \eta_2=2$ ):
Classical: ~118 bits. Quantum: ~107 bits. NIST Level 1.

ML-KEM-768 ( $n=256, k=3, q=3329, \eta_1=2, \eta_2=2$ ):
Classical: ~182 bits. Quantum: ~165 bits. NIST Level 3.

ML-KEM-1024 ( $n=256, k=4, q=3329, \eta_1=2, \eta_2=2$ ):
Classical: ~246 bits. Quantum: ~223 bits. NIST Level 5.

Note: quantum estimates already account for quantum sieving speedup. All are above the 128/192/256-bit targets, with comfortable safety margins against unforeseen improvements.

The Parameter Space Tradeoffs

Four parameters control the fundamental security-efficiency tradeoff for Module-LWE schemes:

Dimension n (ring size)

Larger $$n$$ : more security per module element, better NTT efficiency (fewer small NTTs). Constraint: $$n$$ must be a power of 2 for NTT, and $q \equiv 1 \pmod{2n}$ . Kyber fixes $$n = 256$$ ; all tuning is done via $$k$$ .

Module rank k

Larger $$k$$ : more security (linearly more module equations). Key sizes scale as $$O(k^2)$$ (public key) and $$O(k)$$ (ciphertext). Going from k=2 to k=4 roughly doubles key size for a large security gain. The "correct" $$k$$ balances size vs security target.

Modulus q

Larger $$q$$ : more room for errors (better correctness at given noise rate) but less security (larger lattice determinant). Kyber uses a small prime $$q = 3329$$ — the smallest prime that works for NTT at $$n=256$$ . This keeps key sizes compact.

Error distribution σ

Larger $\sigma$ : more security (harder to find the short vector in the primal attack) but worse correctness (more decryption failures). Kyber uses centered binomial with $\eta \in \{2, 3\}$ , giving $\sigma \approx 1$ . Decryption failure probability: $< 2^{-139}$ for ML-KEM-512.

The Decryption Failure Analysis

Parameters must also ensure that decryption succeeds with overwhelming probability. A decryption failure in a KEM reveals information about the secret key — if an attacker can trigger failures (e.g., via a CCA attack on a non-FO-transformed scheme), they can extract the secret. The Fujisaki-Okamoto transform prevents this, but failures must still be rare enough for correctness.

Failure Probability Computation

Decryption fails when the total noise $e_{total} = e_1 + e_2 + \langle s, e_3 \rangle$ exceeds $$q/4$$ in any coefficient. The total noise is a sum of bounded distributions — analyzed via the Rényi divergence or moment-generating functions.

For Kyber: noise terms are products/sums of centered binomial variables. The failure probability is computed as the probability that any of the $k \cdot n = 768$ coefficients exceeds the threshold. Using the union bound and tail bounds:

$\Pr[\text{failure}] \leq k \cdot n \cdot \Pr[e_{coeff} > q/4]$

Kyber is parameterized to ensure $\Pr[\text{failure}] < 2^{-139}$ for ML-KEM-512, well below any practical concern.

Summary: Security Estimation Workflow

Step-by-Step Security Analysis

1. Define scheme: Choose $(n, k, q, \eta, \gamma_1, \gamma_2, \dots)$ based on your security target and size budget.

2. Run Lattice Estimator: Input parameters; get estimated bit cost of each attack type.

3. Find minimum cost attack: The minimum over all attack types is your classical security level.

4. Adjust for quantum: Apply the quantum SVP cost model; re-run estimator. Take the minimum as quantum security.

5. Check decryption failure: Compute $\Pr[\text{failure}]$ analytically. Must be $< 2^{-100}$ at minimum.

6. Iterate: If security is too low, increase $$n$$ or $$k$$ . If performance is too slow or keys too large, tune downward within security constraints.

The Lattice Estimator — What It Is and How to Use It

The Lattice Estimator (Albrecht, Player, Scott, and many contributors) is the standard open-source tool for computing security estimates of LWE-based cryptosystems. All NIST PQC submissions were required to provide Lattice Estimator estimates. It is the de facto reference for the field.

The estimator implements every known attack on LWE — primal uSVP, primal hybrid (lattice reduction + meet-in-the-middle), dual, dual hybrid, BKW variants, Arora-Ge, and exhaustive search — and reports the estimated bit cost of each under multiple cost models (classical sieving at $2^{0.292eta}$ , quantum sieving at $2^{0.265eta}$ , enumeration, or user-specified). The minimum across all attacks is the security estimate.

Installation:

# Option 1: pip (pure Python version, no SageMath required)
pip install lattice-estimator

# Option 2: SageMath version (more features, some attacks require it)
sage -pip install lattice-estimator

# Or clone the repository for the latest version:
git clone https://github.com/malb/lattice-estimator
cd lattice-estimator

Basic usage:

from estimator import LWE, ND, RC

# Define LWE parameters: n=256, q=3329, secret distribution, error distribution
params = LWE.Parameters(
    n = 256,                          # LWE dimension
    q = 3329,                         # modulus
    Xs = ND.CenteredBinomial(eta=3),  # secret distribution (eta=3 for Kyber-512)
    Xe = ND.CenteredBinomial(eta=2),  # error distribution
    m = 256,                          # number of LWE samples (can be varied)
    tag = "Kyber-512 (one module)",
)

# Run all attacks and print results
result = LWE.estimate(params)
# Output: dictionary mapping attack name -> estimated bit cost
# e.g. {'primal_usvp': 118.2, 'dual': 121.5, 'bkw': 176.3, ...}

# Minimum is the security level:
security = min(v.rop for v in result.values())
print(f"Security estimate: {security:.1f} bits")

The estimator returns a Cost object per attack with fields: rop(total ring operations, i.e., bit cost), beta (BKZ block size), m (number of LWE samples used), and attack-specific fields. The key output is rop.

For Module-LWE (Kyber, Dilithium): the estimator works on a single LWE instance with dimension $n c d o t k$ . For ML-KEM-768 ( $k = 3, n = 256$ ), set n = 768 (the total LWE dimension after "unrolling" the module structure). The module structure does not affect the security estimate beyond this dimension scaling.

Concrete Example — Security of Kyber-512 via BKZ Cost

Let us walk through the primal attack cost estimate for Kyber-512 step by step, to show concretely how the security estimate is computed.

Kyber-512 parameters: $n = 256, k = 2, q = 3329$ , secret distribution $B_{3}$ (centered binomial, $e t a = 3$ ), error distribution $B_{2}$ ( $e t a = 2$ ). The total LWE dimension for the module unrolling is $N = k n = 512$ .

Step 1 — Set up the primal lattice. Given $m$ LWE samples $(A inma t hbb Z_{q}^{mim es N}, b = A s + e)$ , construct the $(N + m + 1)$ -dimensional q-ary lattice:

L amb d a = l e f t x inma t hbb Z^{N + m + 1} : x e q u i v (s, e, 1) p m o d L amb d a_{q} (A) i g h t

The embedded short vector is $v = (s, e, 1)$ with norm approximately:

∣ v ∣ a pp r o x s q r t N c d o t s i g m a_{s}^{2} + m c d o t s i g m a_{e}^{2} + 1

For Kyber-512: $s i g m a_{s}^{2} = 3/2$ (variance of $B_{3}$ ), $s i g m a_{e}^{2} = 1$ (variance of $B_{2}$ ). With $m = N = 512$ :

∣ v ∣ a pp r o x s q r t 512 c d o t 1.5 + 512 c d o t 1 a pp r o x s q r t 1280 a pp r o x 35.8

Step 2 — Determine required BKZ block size. BKZ- $eta$ finds a vector whose norm satisfies the Hermite factor bound:

lambda_1(Lambda) leq delta_eta^{N+m} cdot mathrm{Vol}(Lambda)^{1/(N+m)}

where the root Hermite factor is $delta_eta approx left( rac{eta}{2pi e} cdot (pieta)^{1/eta} ight)^{1/(2eta-2)}$ . The primal attack succeeds when BKZ output quality is good enough to isolate $v$ as the unique shortest vector. Numerically optimizing over $m$ and $eta$ (which the Lattice Estimator does automatically): the optimal block size for Kyber-512 is approximately $eta^* approx 382$ .

Step 3 — Apply the BKZ cost formula. Using the BKZ+sieving cost model:

T_ ext{BKZ}(eta^*) approx rac{N+m}{eta} cdot T_ ext{SVP}(eta^*) = rac{1024}{382} cdot 2^{0.292 imes 382} approx 2^{118}

The factor $(N+m)/eta$ accounts for the number of BKZ tours (the polynomial overhead from running the sieve multiple times). The dominant term is the SVP cost $2^{0.292eta^*}$ .

Result: approximately 118 bits of classical security for Kyber-512 under the primal attack with the BKZ+sieving cost model. The Lattice Estimator returns the same value to within rounding. For quantum security, substitute $0.265eta$ for the SVP cost, giving approximately 107 bits — well above the 100-bit quantum security target for NIST Level 1.

The Core-SVP Hardness Model

The Core-SVP model gives a formula to go directly from a BKZ block size $eta$ to a bit security level $l amb d a$ . It is the standard model used by NIST and in essentially all PQC standardization discussions.

Classical Core-SVP:

lambda_ ext{classical}(eta) = 0.292 cdot eta

This comes from the best known classical SVP algorithm (lattice sieving, specifically the BDGL sieve of Becker, Ducas, Gama, Laarhoven 2016), which solves SVP in dimension $eta$ in time $2^{0.292eta + o(eta)}$ . The $0.292$ constant is the exponent of the sieve's space complexity (the time complexity is slightly higher with a constant factor, but the exponent dominates for security estimation).

Quantum Core-SVP:

lambda_ ext{quantum}(eta) = 0.265 cdot eta

This comes from the quantum speedup of sieving algorithms. A quantum computer can run a variant of the BDGL sieve using Grover's algorithm to accelerate the nearest-neighbor search step, reducing the exponent from 0.292 to approximately 0.265. This assumes access to a quantum random access memory (QRAM) — a device that does not yet exist but is assumed in the model for a conservative (adversary-favorable) estimate.

The formula in practice: given an LWE parameter set, the security estimation workflow is:

For each attack (primal, dual, hybrid, ...), find the optimal BKZ block size $eta^*$ that minimizes total attack cost.
Compute $lambda = lfloor 0.292 cdot eta^* floor$ (classical) or $lfloor 0.265 cdot eta^* floor$ (quantum).
The security level is $mi n_{e x t a tt a c k s} l amb d a$ .

Important caveats. The Core-SVP model ignores polynomial factors — it counts only the dominant exponential term. In practice, the BKZ algorithm has polynomial overhead from running multiple tours and the sieve has a significant memory requirement (approximately $2^{0.208eta}$ bits of RAM). Some security analyses add a "BKZ overhead" term to account for this:

lambda_ ext{BKZ}(eta, n) = 0.292eta - log_2!left( rac{n}{eta} ight)

The log term is usually small (5–15 bits for realistic parameters) but can matter at the margins. The Lattice Estimator uses a more precise BKZ simulator (Chen-Nguyen) that accounts for the full Gram-Schmidt profile rather than assuming the geometric series assumption (GSA), giving slightly more accurate results than the raw Core-SVP formula.

Common Mistakes in Parameter Selection

Parameter selection errors in lattice cryptography tend to be subtle and dangerous — a scheme with a 50-bit security level looks identical to a 128-bit scheme to someone not running the estimator. Here are the mistakes that appear most frequently.

Mistake 1 — Using too small a modulus q

A common misconception is that a larger modulus $q$ always means more security. In fact, the opposite is true. Security of LWE depends on the ratio $q / s i g ma$ : a larger $q$ relative to the error $s i g ma$ makes LWE easier (the error is relatively smaller, making the LWE distinguishing problem easier). However, too small a $q$ causes decryption failures (the error exceeds the decryption threshold). The correct approach is to choose $q$ as small as correctness allows (minimizing key sizes) and then tune $n$ and $k$ for security. Kyber uses the minimal possible prime $q = 3329$ for NTT at $n = 256$ . Schemes that inflate $q$ without justification are paying a security cost they do not need to.

Mistake 2 — Ignoring hybrid attacks

The primal hybrid attack combines lattice reduction with a meet-in-the-middle (MITM) search over part of the secret. For secrets with small support (ternary, sparse binary), this can be significantly cheaper than the pure lattice attack. Many parameter selection analyses only run the primal uSVP and dual attacks, forgetting the hybrid variants. The Lattice Estimator includes primal_hybrid and dual_hybrid — always run all attacks, not just the obvious ones. For Kyber and Dilithium with their bounded secret distributions, the hybrid attack is typically 10–20 bits cheaper than the pure primal attack at the same parameters. Parameters sized only against the pure primal attack may be 10–20 bits weaker than intended.

Mistake 3 — Forgetting to account for quantum speedup

Designing a system with 128-bit classical security is not sufficient for post-quantum security. The quantum Core-SVP model gives a speedup of factor $0.265/0.292 a pp r o x 0.908$ in the exponent — meaning a system with 128 bits of classical security has approximately $128 im es 0.908 a pp r o x 116$ bits of quantum security. This gap is non-trivial. NIST Level 1 requires 128 bits ofquantum security (defined as at least as hard as AES-128 against a quantum adversary). If you design for 128-bit classical security and apply quantum correction, you may fall below the threshold. Always run the estimator with the quantum cost model explicitly and verify the quantum security level meets your target.

Mistake 4 — Not accounting for decryption failure probability

Security and correctness are competing forces: increasing error size $s i g ma$ improves security but increases decryption failure probability. A decryption failure in a KEM can be catastrophic: under a chosen-ciphertext attack model, an attacker who can observe whether decryption succeeds can run a "failure boosting" attack to recover the secret key with surprisingly few oracle queries — far fewer than the security level would suggest. Even with the Fujisaki-Okamoto transform (which prevents the attacker from learning whether decryption failed), the failure probability must be below $2^{- l amb d a}$ to avoid leaking information to a passive attacker over many sessions. The requirement is typically $P_{e} x t f ai l < 2^{- 100}$ at minimum, and Kyber targets $2^{- 139}$ . Always compute the failure probability analytically (using tail bounds on the noise distribution) and verify it is negligible before finalizing parameters.

Mistake 5 — Using a custom or modified parameter set without re-running the full analysis

The NIST-standardized parameter sets (ML-KEM-512/768/1024, ML-DSA-44/65/87) have been analyzed exhaustively by dozens of research groups worldwide. If you modify any parameter — even a seemingly minor one like changing $e t a$ from 2 to 3, or adjusting the compression parameters — you must re-run the complete security analysis from scratch. The security of an LWE scheme is highly sensitive to parameter interactions. There is no safe shortcut: use the standardized parameter sets as published in FIPS 203 and FIPS 204 unless you have a specific technical reason to deviate and the expertise to re-validate the security.

References

Tools and papers for parameter selection

Lattice Estimator (Albrecht et al.) — the standard security estimation tool: github.com/malb/lattice-estimator ↗

Micciancio & Regev, "Lattice-based Cryptography" — mathematical foundations of the security model: PDF ↗

Regev, "On Lattices, Learning with Errors..." — the worst-case reduction that justifies the Core-SVP model: ACM ↗

Systematic Review of Lattice-Based Cryptography (2025): iacis.org ↗