lattice-estimator-rs

A Rust reimplementation of the lattice-estimator by Martin Albrecht et al.

Overview

lattice-estimator-rs estimates the concrete security of lattice-based cryptographic schemes. Given a parameter set for an LWE, NTRU, or SIS instance, the estimator evaluates all known attacks and reports their cost in terms of the number of ring/gate operations (rop), the BKZ block size (beta), lattice dimension (d), and other attack-specific metrics.

This is a faithful port of the Python/SageMath lattice-estimator to pure Rust, with no external C or SageMath dependencies. It is suitable for embedding in Rust toolchains, parameter-search loops, and CI pipelines where installing SageMath is impractical.

Quick Start

Command-line tool

The easiest way to use the estimator is through the CLI. Build it with the cli feature:

cargo install --path . --features cli
# or
cargo build --release --features cli

Estimate a predefined scheme:

lattice-estimator estimate --scheme kyber512

  LWEParameters(n=512, q=3329, Xs=D(σ=1.22), Xe=D(σ=1.22), m=512, tag=Some("Kyber 512"))
  Cost model: MATZOV, Shape model: gsa

  bkw                  :: rop: ≈2^280.8, ...
  usvp                 :: β: 406, d: 998, rop: ≈2^143.8
  bdd                  :: β: 389, d: 1013, rop: ≈2^140.2
  dual                 :: β: 427, d: 1024, rop: ≈2^150.5
  dual_hybrid          :: β: 385, rop: ≈2^139.7
  ...

  Security: 139.7 bits (weakest attack: dual_hybrid)

Export results as JSON:

# To a file
lattice-estimator estimate --scheme kyber512 --output results.json

# To stdout
lattice-estimator estimate --scheme kyber512 --json

Use custom parameters:

# Custom LWE instance
lattice-estimator estimate --problem lwe --n 1024 --q 2^32 \
  --secret binomial:3 --error gaussian:3.2

# Custom NTRU instance
lattice-estimator estimate --problem ntru --n 512 --q 12289 \
  --secret gaussian:4.05 --error gaussian:4.05 --ntru-type circulant

# Custom SIS instance
lattice-estimator estimate --problem sis --n 512 --q 12289 \
  --length-bound 5833.9 --sis-norm euclidean

Choose a different cost model:

lattice-estimator estimate --scheme kyber512 --cost-model adps16

List all available schemes:

lattice-estimator schemes

Noise distribution syntax:

Format	Distribution	Example
binomial:ETA or cb:ETA	Centered Binomial	binomial:3
gaussian:STDDEV or dg:STDDEV	Discrete Gaussian	gaussian:3.2
gaussian:STDDEV:MEAN	Discrete Gaussian with mean	gaussian:3.2:1.0
uniform:A:B	Uniform over [A, B]	uniform:-1:1
uniform:Q or u:Q	Balanced uniform mod Q	u:8
tuniform:BITS or tu:BITS	T-uniform over [-2^b, 2^b]	tuniform:1
ternary:P:M or st:P:M	Sparse ternary (P +1s, M -1s)	ternary:127:127
binary	Uniform {0, 1}	binary
ternary	Uniform {-1, 0, 1}	ternary

As a library

Add the dependency to your Cargo.toml:

[dependencies]
lattice-estimator = "0.1"

Estimate the security of Kyber-512:

use lattice_estimator::*;

fn main() {
    let params = schemes::kyber512();
    let model = reduction::RC::matzov();
    let results = lwe::estimate(&params, &model, "gsa");
    for (name, cost) in &results {
        println!("{:20} :: {}", name, cost);
    }
}

The output lists each attack with its estimated cost. The minimum rop across all attacks gives the concrete security level (in bits) of the parameter set.

Supported Attacks

LWE

Attack	Function
Primal uSVP	lwe::primal::primal_usvp
Primal BDD	lwe::primal::primal_bdd
Primal Hybrid (with MITM)	lwe::primal::primal_hybrid
Dual	lwe::dual::dual
Dual Hybrid (MATZOV)	lwe::dual::matzov
Coded-BKW	lwe::bkw::coded_bkw
Arora-GB	gb::arora_gb
Exhaustive Search	lwe::guess::exhaustive_search_cost
MITM	lwe::guess::mitm
Guess Composition	lwe::guess::guess_composition

NTRU

Attack	Function
Dense Sublattice Discovery (DSD)	ntru::primal::primal_dsd
uSVP	ntru::primal::primal_usvp
BDD	ntru::primal::primal_bdd
Hybrid (with MITM)	ntru::primal::primal_hybrid

SIS

Attack	Function
Lattice attack (Euclidean and infinity norm)	sis::lattice::lattice

Supported Cost Models

Cost models are accessed through the reduction::RC helper:

Model	Constructor	Reference
ADPS16	RC::adps16()	[USENIX:ADPS16]
BDGL16	RC::bdgl16()	[SODA:BDGL16]
CheNgu12	RC::chengu12()	[PhD:Chen13]
ABFKSW20	RC::abfksw20()	[C:ABFKSW20]
ABLR21	RC::ablr21()	[C:ABLR21]
Kyber	RC::kyber()	[Kyber20] / [AC:AGPS20]
GJ21	RC::gj21()	[AC:GuoJoh21]
MATZOV (default)	RC::matzov()	[MATZOV22]
LaaMosPol14	RC::laamospol14()	[DCC:LaaMosPol15]
ChaLoy21	RC::chaloy21()	[AC:ChaLoy21]

Supported BKZ Simulators

Simulators model the Gram-Schmidt profile of a BKZ-reduced lattice basis. They are selected by name when calling an estimator (e.g., "gsa", "zgsa", "lgsa").

Simulator	Description
GSA	Geometric Series Assumption [Schnorr03]
ZGSA	Z-shape GSA for NTRU fatigue [DucWoe21]
LGSA	L-shape GSA with basis rerandomization [Dilithium21]

Predefined Schemes

The schemes module provides ready-to-use parameter sets for widely deployed lattice-based schemes:

Family	Schemes
Kyber (ML-KEM)	kyber512, kyber768, kyber1024
Saber	lightsaber, saber, firesaber
NTRU-HPS/HRSS	ntruhps2048509enc, ntruhps2048677enc, ntruhps4096821enc, ntruhrss701enc
Dilithium (ML-DSA)	dilithium2_msis_wkunf, dilithium2_msis_strunf, dilithium3_msis_wkunf, dilithium5_msis_wkunf
Falcon	falcon512_unf, falcon512_skr, falcon1024_skr
FrodoKEM	frodo640, frodo976, frodo1344
TFHE	tfhe630, tfhe1024
HElib	helib80_1024

Parameter Search

The search module provides high-level tools for finding optimal parameter sets that satisfy a given security guarantee. Rather than manually guessing parameters and checking them, you specify a target security level and let the estimator find the smallest parameters that achieve it.

Estimating security of a parameter set

use lattice_estimator::*;
use lattice_estimator::search::*;

let params = schemes::kyber512();
let model = reduction::RC::matzov();
let (bits, weakest, _) = estimate_security(&params, &Attack::fast(), &model, "gsa");
println!("Security: {:.1} bits (weakest: {})", bits, weakest);
// Output: Security: 143.8 bits (weakest: usvp)

Checking against a target

let target = SecurityTarget::new(128.0);
assert!(check_security(&params, &target, &model, "gsa"));

Searching for minimal parameters

Find the smallest LWE dimension n that achieves a target security level:

let model = reduction::RC::matzov();
let config = SearchConfig::new(
    128.0,                                                        // target bits
    3329.0,                                                       // modulus q
    nd::NoiseDistribution::CenteredBinomial { eta: 3, n: None },  // secret
    nd::NoiseDistribution::CenteredBinomial { eta: 3, n: None },  // error
)
.with_n_range(256, 1024)
.with_attacks(Attack::fast());

let result = search_lwe_params(&config, &model).unwrap();
println!("Smallest n: {} ({:.1} bits)", result.params.n, result.security_bits);
// Output: Smallest n: 454 (128.4 bits)

Convenience searches

Search for Kyber-like parameters (CenteredBinomial noise, q = 3329, n a multiple of 256):

let result = search_kyber_like(128.0, 3, &model).unwrap();
// Finds n=512 as the smallest multiple of 256 with >= 128-bit security

Find the largest modulus for FHE applications (fixed n, sparse secret):

let xs = nd::NoiseDistribution::SparseTernary { p: 16, m: 16, n: None };
let (q, result) = search_max_modulus(128.0, 1024, xs, 3.2, &model).unwrap();
println!("Max q = 2^{:.0} at {:.1}-bit security", q.log2(), result.security_bits);
// Output: Max q = 2^24 at 130.9-bit security

Available functions

Function	Purpose
estimate_security	Get the security level (in bits) for a parameter set
check_security	Boolean check: does a parameter set meet a target?
search_lwe_params	Binary search over n for the smallest secure dimension
search_kyber_like	Find Kyber-structured params (n a multiple of 256, q = 3329)
search_max_modulus	Find the largest q for a fixed n that still meets a target

Attack subsets can be selected via Attack::all() (all 7 attacks) or Attack::fast() (uSVP + dual only, much faster).

Differences from the Python Implementation

This Rust port is designed to produce results equivalent to the Python/SageMath lattice-estimator for all practical purposes. There are, however, several inherent differences:

Numerical precision

Rust uses IEEE 754 f64 (64-bit double-precision floats), while SageMath uses arbitrary-precision real numbers (RealField). In practice the impact is negligible: estimates typically agree to within +/-0.01 bits, which is far smaller than the +/-5-10 bits of inherent model uncertainty.

Optimization algorithms

The local_minimum binary-search routine is reimplemented faithfully, but ceiling/floor rounding at search boundaries can cause the reported BKZ block size to differ by +/-1 from the Python result.

Missing CN11 simulator

The CN11 (Chen-Nguyen) BKZ simulator requires fpylll, a C library with Python bindings that is not available in pure Rust. The GSA, ZGSA, and LGSA simulators are fully implemented and sufficient for all standard analyses.

Special function approximations

• Digamma: Stirling series approximation.
• Regularized incomplete beta: Continued fraction expansion.
• Chi-squared CDF: Wilson-Hilferty normal approximation.

These are standard numerical approximations with error well below the model uncertainty.

A Note on Accuracy

The dominant source of uncertainty in lattice security estimation is the security models, not numerical precision. These models rest on heuristic assumptions -- the Geometric Series Assumption, the Core-SVP hardness model, the independence heuristic for hybrid attacks -- whose real-world accuracy is uncertain by roughly +/-5-10 bits. Both this Rust implementation and the Python original are subject to the same model uncertainty. For any practical parameter selection or security comparison, the two implementations produce equivalent conclusions.

License

This project is licensed under the MIT License.