estimator.lwe_guess.ExhaustiveSearch#

class estimator.lwe_guess.ExhaustiveSearch[source]#
__call__(params: estimator.lwe_parameters.LWEParameters, success_probability=0.99, quantum: bool = False)[source]#

Estimate cost of solving LWE via exhaustive search.

Parameters

  • params – LWE parameters

  • success_probability – the targeted success probability

  • quantum – use estimate for quantum computer (we simply take the square root of the search space)

Returns

A cost dictionary

The returned cost dictionary has the following entries:

  • rop: Total number of word operations (≈ CPU cycles).

  • mem: memory requirement in integers mod q.

  • m: Required number of samples to distinguish the correct solution with high probability.

EXAMPLE:

>>> from estimator import *
>>> from estimator.lwe_guess import exhaustive_search
>>> params = LWE.Parameters(n=64, q=2**40, Xs=ND.UniformMod(2), Xe=ND.DiscreteGaussian(3.2))
>>> exhaustive_search(params)
rop: ≈2^73.6, mem: ≈2^72.6, m: 397.198
>>> params = LWE.Parameters(n=1024, q=2**40, Xs=ND.SparseTernary(n=1024, p=32), Xe=ND.DiscreteGaussian(3.2))
>>> exhaustive_search(params)
rop: ≈2^417.3, mem: ≈2^416.3, m: ≈2^11.2

Methods

__init__()