Ctrl+K

estimator.lwe_guess.MITM

estimator.lwe_guess.MITM#

class estimator.lwe_guess.MITM[source]#
__call__(params: LWEParameters, success_probability=0.99, optimization='analytical')[source]#

Estimate cost of solving LWE via Meet-In-The-Middle attack.

Parameters:

  • params – LWE parameters

  • success_probability – the targeted success probability

  • model – Either “analytical” (faster, default) or “numerical” (more accurate)

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.

  • k: Splitting dimension.

  • ↻: Repetitions required to achieve targeted success probability

EXAMPLE:

>>> from estimator import *
>>> from estimator.lwe_guess import mitm
>>> params = LWE.Parameters(n=64, q=2**40, Xs=ND.UniformMod(2), Xe=ND.DiscreteGaussian(3.2))
>>> mitm(params)
rop: ≈2^37.0, mem: ≈2^37.2, m: 37, k: 32, ↻: 1
>>> mitm(params, optimization="numerical")
rop: ≈2^39.2, m: 36, k: 32, mem: ≈2^39.1, ↻: 1
>>> params = LWE.Parameters(n=1024, q=2**40, Xs=ND.SparseTernary(n=1024, p=32), Xe=ND.DiscreteGaussian(3.2))
>>> mitm(params)
rop: ≈2^215.4, mem: ≈2^210.2, m: ≈2^13.1, k: 512, ↻: 43
>>> mitm(params, optimization="numerical")
rop: ≈2^216.0, m: ≈2^13.1, k: 512, mem: ≈2^211.4, ↻: 43

Methods

X_range(nd)

__init__()

cost(params, k[, success_probability])

local_range(center)

mitm_analytical(params[, success_probability])

Attributes

locality

Contents