estimator.lwe_guess.MITM

class estimator.lwe_guess.MITM

__call__(params: LWEParameters, success_probability=0.99, optimization='analytical')

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.Binary, 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(32), Xe=ND.DiscreteGaussian(3.2))
>>> mitm(params)
rop: ≈2^217.8, mem: ≈2^210.2, m: ≈2^15.5, k: 512, ↻: 226
>>> mitm(params, optimization="numerical")
rop: ≈2^215.6, m: ≈2^15.5, k: 512, mem: ≈2^208.6, ↻: 226

Methods

X_range(nd)
__init__()
cost(params, k[, success_probability])
local_range(center)
mitm_analytical(params[, success_probability])

Attributes

locality