estimator.estimate_lwe

estimator.estimate_lwe(n, alpha=None, q=None, secret_distribution=True, m=<Mock name='mock()' id='139938827128976'>, reduction_cost_model=<function CheNgu12>, skip=('mitm', 'arora-gb', 'bkw'))[source]

Highlevel-function for estimating security of LWE parameter sets

Parameters:
  • n – LWE dimension n > 0
  • alpha – noise rate 0 ≤ α < 1, noise will have standard deviation αq/sqrt{2π}
  • q – modulus 0 < q
  • m – number of LWE samples m > 0
  • secret_distribution – distribution of secret, see module level documentation for details
  • reduction_cost_model – use this cost model for lattice reduction
  • skip – skip these algorithms

EXAMPLE:

sage: from estimator import estimate_lwe, Param, BKZ
sage: d = estimate_lwe(*Param.Regev(128))
usvp: rop:  ≈2^57.7,  red:  ≈2^57.7,  δ_0: 1.009214,  β:  102,  d:  357,  m:      228
 dec: rop:  ≈2^61.5,  m:      229,  red:  ≈2^61.5,  δ_0: 1.009595,  β:   93,  d:  357,  babai:  ≈2^46.8,  ...
dual: rop:  ≈2^81.4,  m:      376,  red:  ≈2^81.4,  δ_0: 1.008810,  β:  111,  d:  376,  |v|:  736.521,  ...

sage: d = estimate_lwe(**Param.LindnerPeikert(256, dict=True))
usvp: rop: ≈2^137.8,  red: ≈2^137.8,  δ_0: 1.005788,  β:  229,  d:  594,  m:      337
 dec: rop: ≈2^142.9,  m:      334,  red: ≈2^142.9,  δ_0: 1.006061,  β:  212,  d:  590,  babai: ≈2^128.5,  ...
dual: rop: ≈2^166.0,  m:      368,  red: ≈2^166.0,  δ_0: 1.005479,  β:  249,  repeat: ≈2^131.0,  d:  624,  ...

sage: d = estimate_lwe(*Param.LindnerPeikert(256), secret_distribution=(-1,1))
usvp: rop: ≈2^103.2,  red: ≈2^103.2,  δ_0: 1.006744,  β:  179,  d:  506,  m:      249
 dec: rop: ≈2^142.9,  m:      334,  red: ≈2^142.9,  δ_0: 1.006061,  β:  212,  d:  590,  babai: ≈2^128.5,  ...
dual: rop: ≈2^112.3,  m:      268,  red: ≈2^112.3,  δ_0: 1.006445,  β:  192,  repeat:  ≈2^76.5,  d:  508,  ...

sage: d = estimate_lwe(*Param.LindnerPeikert(256), secret_distribution=(-1,1), reduction_cost_model=BKZ.sieve)
usvp: rop:  ≈2^80.7,  red:  ≈2^80.7,  δ_0: 1.006744,  β:  179,  d:  506,  m:      249
 dec: rop: ≈2^111.8,  m:      369,  red: ≈2^111.8,  δ_0: 1.005423,  β:  253,  d:  625,  babai:  ≈2^97.0,  ...
dual: rop:  ≈2^90.6,  m:      284,  red:  ≈2^90.6,  δ_0: 1.006065,  β:  212,  repeat:  ≈2^53.5,  d:  524,  ...

sage: d = estimate_lwe(n=100, alpha=8/2^20, q=2^20, skip="arora-gb")
mitm: rop: ≈2^329.2,  m:       23,  mem: ≈2^321.5
usvp: rop:  ≈2^32.0,  red:  ≈2^32.0,  δ_0: 1.013310,  β:   40,  d:  141,  m:       40
 dec: rop:  ≈2^33.7,  m:      156,  red:  ≈2^33.7,  δ_0: 1.021398,  β:   40,  d:  256,  babai:        1, ...
dual: rop:  ≈2^35.3,  m:      311,  red:  ≈2^35.3,  δ_0: 1.014423,  β:   40,  d:  311,  |v|:  ≈2^12.9,  ...
 bkw: rop:  ≈2^56.8,  m:  ≈2^43.5,  mem:  ≈2^44.5,  b:   2,  t1:   5,  t2:  18,  l:   1,  ncod:  84,  ...