3.4 Lattice Estimator & Parameter Selection

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.

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$.

In practice the model is a formula that goes directly from a BKZ block size $\beta$ to a bit security level $\lambda$. It is the standard model used by NIST and in essentially all PQC standardization discussions.

Classical Core-SVP:

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 $\beta$ in time $2^{0.292\beta + o(\beta)}$. The $0.292$ constant is the exponent of the sieve’s time complexity (its memory is about $2^{0.2075\beta}$ vectors); the $o(\beta)$ term and polynomial factors are dropped for security estimation.

Quantum Core-SVP:

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:

1. For each attack (primal, dual, hybrid, ...), find the optimal BKZ block size $\beta^*$ that minimizes total attack cost.
2. Compute $\lambda = \lfloor 0.292 \cdot \beta^* \rfloor$ (classical) or $\lfloor 0.265 \cdot \beta^* \rfloor$ (quantum).
3. The security level is $\min_{\text{attacks}} \lambda$.

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.2075\beta}$ stored vectors). Some security analyses add a “BKZ overhead” term for the number of SVP calls — for example about 8 tours of roughly $d$ calls each in dimension $d$:

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.

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$.

Attack 2: The Dual Attack

The dual attack finds a short vector $w$ in the dual lattice $\Lambda_q(A)^*$. 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.

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 coefficients bounded by a small constant $\eta$: values in $\{-\eta, \dots, \eta\}$ with $\eta = 2$ or 3 for Kyber ($\eta = 3$ for the ML-KEM-512 secret) and 2 or 4 for Dilithium. These secrets are not ternary, but they are small, which is why combinatorial and hybrid attacks must be included in the security analysis — the Lattice Estimator accounts for them automatically.

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. NIST did not require it, but most lattice-based PQC submissions used it (or its predecessor) for their 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.292\beta}$, quantum sieving at $2^{0.265\beta}$, 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=512, q=3329, secret distribution, error distribution
params = LWE.Parameters(
    n = 512,                          # LWE dimension k*n = 2*256 for Kyber-512
    q = 3329,                         # modulus
    Xs = ND.CenteredBinomial(eta=3),  # secret distribution (eta=3 for Kyber-512)
    Xe = ND.CenteredBinomial(eta=2),  # error distribution
    m = 512,                          # number of LWE samples (can be varied)
    tag = "Kyber-512 (unrolled)",
)

# Run all attacks and print results
result = LWE.estimate(params)
# Output: dictionary mapping attack name -> Cost object
# (rop = estimated number of operations, so take log2 for bits)

# Minimum is the security level:
from math import log2
security = min(log2(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 (estimated number of operations; its base-2 log is the 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 \cdot 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 Security Estimates

To illustrate the methodology, here are the Core-SVP security estimates for the three ML-KEM parameter sets, as reported with the BKZ-sieving cost model in the Kyber round-3 specification:

The Parameter Space Tradeoffs

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

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.

Summary: Security Estimation Workflow

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, $\eta=3$), error distribution $B_2$ ($\eta=2$). The total LWE dimension for the module unrolling is $N = kn = 512$.

Step 1 — Set up the primal lattice. Given $m$ LWE samples $(A \in \mathbb{Z}_q^{m \times N}, b = As + e)$, construct the $(N + m + 1)$-dimensional q-ary lattice:

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

For Kyber-512: $\sigma_s^2 = 3/2$ (variance of $B_3$), $\sigma_e^2 = 1$ (variance of $B_2$). With $m = N = 512$:

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

where the root Hermite factor is $\delta_0 \approx \left(\frac{\beta}{2\pi e} \cdot (\pi\beta)^{1/\beta}\right)^{1/(2\beta-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 $\beta$ (which the Lattice Estimator does automatically): the optimal block size for Kyber-512 is approximately $\beta^* \approx 406$.

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

Core-SVP counts a single SVP call in dimension $\beta^*$. A full BKZ run makes many such calls (fuller models charge roughly $8d$ of them for lattice dimension $d$), which adds a polynomial factor that Core-SVP deliberately leaves out. The dominant term is the SVP cost $2^{0.292\beta^*}$.

Result: approximately 118 bits of classical security for Kyber-512 under the primal attack with the Core-SVP sieving cost model, matching the Kyber round-3 specification. For quantum security, substitute $0.265\beta$ for the SVP cost, giving approximately 107 bits. Neither number is compared to 128 directly: NIST Level 1 is defined by the cost of AES-128 key search, and fuller gate-count estimates place ML-KEM-512 at that level.

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.

References