Ctrl+K

estimator.lwe_dual.DualHybrid

estimator.lwe_dual.DualHybrid#

class estimator.lwe_dual.DualHybrid[source]#

Estimate cost of solving LWE using dual attacks.

__call__(solver, params: ~estimator.lwe_parameters.LWEParameters, success_probability: float = 0.99, red_cost_model=<estimator.reduction.MATZOV object>, opt_step=8, log_level=1, fft=False)[source]#

Optimizes the cost of the dual hybrid attack (using the given solver) over all attack parameters: block size β, splitting dimension ζ, and splitting weight h1 (in case the secret distribution is sparse). Since the cost function for the dual hybrid might only be convex in an approximate sense, the parameter opt_step allows to make the optimization procedure more robust against local irregularities (higher value) at the cost of a longer running time. In a nutshell, if the cost of the dual hybrid seems suspiciously high, try a larger opt_step (e.g. 4 or 8).

Parameters:

  • solver – Algorithm for solving the reduced instance

  • params – LWE parameters

  • success_probability – The success probability to target

  • red_cost_model – How to cost lattice reduction

  • opt_step – control robustness of optimizer

  • fft – use the FFT distinguisher from [AC:GuoJoh21]. (ignored for sparse secrets)

The returned cost dictionary has the following entries:

  • rop: Total number of word operations (≈ CPU cycles).

  • mem: Total amount of memory used by solver (in elements mod q).

  • red: Number of word operations in lattice reduction.

  • β: BKZ block size.

  • ζ: Number of guessed coordinates.

  • h1: Number of non-zero components among guessed coordinates (if secret distribution is sparse)

  • prob: Probability of success in guessing.

  • repetitions: How often we are required to repeat the attack.

  • d: Lattice dimension.

  • t: Number of secrets to guess mod 2 (only if fft is True)

  • When ζ = 1 this function essentially estimates the dual attack.

  • When ζ > 1 and solver is exhaustive_search this function estimates

    the hybrid attack as given in [INDOCRYPT:EspJouKha20]

  • When ζ > 1 and solver is mitm this function estimates the dual MITM

    hybrid attack roughly following [EPRINT:CHHS19]

EXAMPLES:

>>> from estimator import *
>>> from estimator.lwe_dual import dual_hybrid
>>> params = LWE.Parameters(n=1024, q = 2**32, Xs=ND.Uniform(0,1), Xe=ND.DiscreteGaussian(3.0))
>>> LWE.dual(params)
rop: ≈2^107.0, mem: ≈2^66.4, m: 970, β: 264, d: 1994, ↻: 1, tag: dual
>>> dual_hybrid(params)
rop: ≈2^103.2, mem: ≈2^97.4, m: 937, β: 250, d: 1919, ↻: 1, ζ: 42, tag: dual_hybrid
>>> dual_hybrid(params, mitm_optimization=True)
rop: ≈2^130.1, mem: ≈2^127.0, m: 1144, k: 120, ↻: 1, β: 347, d: 2024, ζ: 144, tag: dual_mitm_hybrid
>>> dual_hybrid(params, mitm_optimization="numerical")
rop: ≈2^129.0, m: 1145, k: 1, mem: ≈2^131.0, ↻: 1, β: 346, d: 2044, ζ: 125, tag: dual_mitm_hybrid

>>> params = params.updated(Xs=ND.SparseTernary(params.n, 32))
>>> LWE.dual(params)
rop: ≈2^103.4, mem: ≈2^63.9, m: 904, β: 251, d: 1928, ↻: 1, tag: dual
>>> dual_hybrid(params)
rop: ≈2^92.1, mem: ≈2^78.2, m: 716, β: 170, d: 1464, ↻: 1989, ζ: 276, h1: 8, tag: dual_hybrid
>>> dual_hybrid(params, mitm_optimization=True)
rop: ≈2^98.2, mem: ≈2^78.6, m: 728, k: 292, ↻: ≈2^18.7, β: 180, d: 1267, ζ: 485, h1: 17, tag: ...

>>> params = params.updated(Xs=ND.CenteredBinomial(8))
>>> LWE.dual(params)
rop: ≈2^114.5, mem: ≈2^71.8, m: 1103, β: 291, d: 2127, ↻: 1, tag: dual
>>> dual_hybrid(params)
rop: ≈2^113.6, mem: ≈2^103.5, m: 1096, β: 288, d: 2110, ↻: 1, ζ: 10, tag: dual_hybrid
>>> dual_hybrid(params, mitm_optimization=True)
rop: ≈2^155.5, mem: ≈2^146.2, m: 1414, k: 34, ↻: 1, β: 438, d: 2404, ζ: 34, tag: dual_mitm_hybrid

>>> params = params.updated(Xs=ND.DiscreteGaussian(3.0))
>>> LWE.dual(params)
rop: ≈2^116.5, mem: ≈2^73.2, m: 1140, β: 298, d: 2164, ↻: 1, tag: dual
>>> dual_hybrid(params)
rop: ≈2^116.2, mem: ≈2^100.4, m: 1137, β: 297, d: 2155, ↻: 1, ζ: 6, tag: dual_hybrid
>>> dual_hybrid(params, mitm_optimization=True)
rop: ≈2^160.7, mem: ≈2^156.8, m: 1473, k: 25, ↻: 1, β: 456, d: 2472, ζ: 25, tag: dual_mitm_hybrid

>>> dual_hybrid(schemes.NTRUHPS2048509Enc)
rop: ≈2^131.7, mem: ≈2^128.5, m: 436, β: 358, d: 906, ↻: 1, ζ: 38, tag: dual_hybrid

>>> LWE.dual(schemes.CHHS_4096_67)
rop: ≈2^206.9, mem: ≈2^137.5, m: ≈2^11.8, β: 616, d: 7779, ↻: 1, tag: dual

>>> dual_hybrid(schemes.Kyber512, red_cost_model=RC.GJ21, fft=True)
rop: ≈2^149.8, mem: ≈2^92.1, m: 510, t: 76, β: 399, d: 1000, ↻: 1, ζ: 22, tag: dual_hybrid

Methods

__init__()

fft_solver(params, success_probability[, t])

Estimate cost of solving LWE via the FFT distinguisher from [AC:GuoJoh21].

optimize_blocksize(solver, params[, zeta, ...])

Optimizes the cost of the dual hybrid attack over the block size β.

Attributes

cost

dual_reduce

Contents