# 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

 `cost`(params, k[, success_probability]) `local_range`(center) `mitm_analytical`(params[, success_probability])

Attributes