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 largeropt_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 iffft
isTrue
)When ζ = 1 this function essentially estimates the dual attack.
- When ζ > 1 and
solver
isexhaustive_search
this function estimates the hybrid attack as given in [INDOCRYPT:EspJouKha20]
- When ζ > 1 and
- When ζ > 1 and
solver
ismitm
this function estimates the dual MITM hybrid attack roughly following [IEEE:CHHS19]
- When ζ > 1 and
EXAMPLES:
>>> from estimator import * >>> from estimator.lwe_dual import dual_hybrid >>> params = LWE.Parameters(n=1024, q = 2**32, Xs=ND.Binary, 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(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^91.6, mem: ≈2^77.2, m: 711, β: 168, d: 1456, ↻: ≈2^11.2, ζ: 279, h1: 8, tag: dual_hybrid >>> dual_hybrid(params, mitm_optimization=True) rop: ≈2^98.7, mem: ≈2^78.6, m: 737, k: 288, ↻: ≈2^19.6, β: 184, d: 1284, ζ: 477, h1: 17, tag: dual_mitm_... >>> 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^136.2, mem: ≈2^127.8, m: 434, β: 356, d: 902, ↻: 35, ζ: 40, h1: 19, 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