estimator.lwe_guess.ExhaustiveSearch

estimator.lwe_guess.ExhaustiveSearch#

class estimator.lwe_guess.ExhaustiveSearch[source]#
__call__(params: 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.Binary, 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(32), Xe=ND.DiscreteGaussian(3.2))
>>> exhaustive_search(params)
rop: ≈2^413.9, mem: ≈2^412.9, m: ≈2^11.1

Methods

__init__()

Contents