estimator

Description

Cost estimates for solving LWE.

# Supported Secret Distributions #

The following distributions for the secret are supported:

  • "normal" : normal form instances, i.e. the secret follows the noise distribution (alias: True)
  • "uniform" : uniform mod q (alias: False)
  • (a,b) : uniform in the interval [a,…,b]
  • ((a,b), h) : exactly h components are [a,…,b]∖\{0\}, all other components are zero

Classes

BKZ Cost estimates for BKZ.
Cost([data]) Algorithms costs.
Logging Control level of detail being printed.
OrderedDict(*args, **kwds) Dictionary that remembers insertion order
Param Namespace for processing LWE parameter sets.
SDis Distributions of Secrets.
partial partial(func, *args, **keywords) - new function with partial application

Functions

alphaf(sigma, q[, sigma_is_stddev]) Gaussian width σ, modulus q → noise rate α
amplify(target_success_probability, ...[, ...]) Return the number of trials needed to amplify current success_probability to
amplify_sigma(target_advantage, sigma, q) Amplify distinguishing advantage for a given σ and q
arora_gb(n, alpha, q[, secret_distribution, ...]) Arora-GB as described in [AroGe11,ACFP14]_
betaf(delta) Compute block size β from root-Hermite factor δ_0.
binary_search(f, start, stop, param[, predicate]) Searches for the best value in the interval [start,stop] depending on the given predicate.
binary_search_minimum(f, start, stop, param) Return minimum of f if f is convex.
bkw_coded(n, alpha, q[, ...]) Coded-BKW as described in [C:GuoJohSta15]
delta_0f(beta) Compute root-Hermite factor δ_0 from block size β.
drop_and_solve(f, n, alpha, q[, ...]) Solve instances of dimension n-k with increasing k using f and pick parameters such that cost is minimised.
dual_scale(n, alpha, q, secret_distribution) Estimate cost of solving LWE by finding small (y,x/c) such that y ⋅ A ≡ c ⋅ x mod q as
enumeration_cost(n, alpha, q, ...[, ...]) Estimates the cost of performing enumeration.
estimate_lwe(n[, alpha, q, ...]) Highlevel-function for estimating security of LWE parameter sets
gb_cost(n, D[, omega]) Estimate the complexity of computing a Gröbner basis.
guess_and_solve(f, n, alpha, q, ...[, ...]) Guess components of the secret.
lattice_reduction_cost(cost_model, delta_0, d) Return cost dictionary for returning vector of norm` δ_0^d Vol(Λ)^{1/d}` using provided lattice reduction algorithm.
lattice_reduction_opt_m(n, q, delta) Return the (heuristically) optimal lattice dimension m
mitm(n, alpha, q[, secret_distribution, m, ...]) Meet-in-the-Middle attack as described in [AlbPlaSco15]
primal_usvp(n, alpha, q[, ...]) Estimate cost of solving LWE using primal attack (uSVP version)
reduction_default_cost(beta, d[, B]) Runtime estimation given β and assuming [CheNgu12] estimates are correct.
rinse_and_repeat(f, n, alpha, q[, ...]) Find best trade-off between success probability and running time.
sieve_or_enum(func) Take minimum of sieving or enumeration for lattice-based attacks.
sigmaf(stddev) standard deviation → Gaussian width parameter σ
stddevf(sigma) Gaussian width parameter σ → standard deviation
success_probability_drop(n, h, k[, fail, ...]) Probability that k randomly sampled components have fail non-zero components amongst them.
switch_modulus(f, n, alpha, q, ...)
param f:run f