estimator.lwe_primal.PrimalHybrid
estimator.lwe_primal.PrimalHybrid#
- class estimator.lwe_primal.PrimalHybrid[source]#
- __call__(params: estimator.lwe_parameters.LWEParameters, babai: bool = True, zeta: typing.Optional[int] = None, mitm: bool = True, red_shape_model='gsa', red_cost_model=<estimator.reduction.MATZOV object>, log_level=1, **kwds)[source]#
Estimate the cost of the hybrid attack and its variants.
- Parameters
params – LWE parameters.
zeta – Guessing dimension ζ ≥ 0.
babai – Insist on Babai’s algorithm for finding close vectors.
mitm – Simulate MITM approach (√ of search space).
- Returns
A cost dictionary
The returned cost dictionary has the following entries:
rop
: Total number of word operations (≈ CPU cycles).red
: Number of word operations in lattice reduction.δ
: Root-Hermite factor targeted by lattice reduction.β
: BKZ block size.η
: Dimension of the final BDD call.ζ
: Number of guessed coordinates.|S|
: Guessing search space.prob
: Probability of success in guessing.repeat
: How often to repeat the attack.d
: Lattice dimension.When ζ = 0 this function essentially estimates the BDD strategy as given in [RSA:LiuNgu13].
When ζ ≠ 0 and
babai=True
this function estimates the hybrid attack as given in [C:HowgraveGraham07]When ζ ≠ 0 and
babai=False
this function estimates the hybrid attack as given in [SAC:AlbCurWun19]
EXAMPLES:
>>> from estimator import * >>> LWE.primal_hybrid(schemes.Kyber512.updated(Xs=ND.SparseTernary(512, 16)), mitm = False, babai = False) rop: ≈2^91.5, red: ≈2^90.7, svp: ≈2^90.2, β: 178, η: 21, ζ: 256, |S|: ≈2^56.6, d: 531, ... >>> LWE.primal_hybrid(schemes.Kyber512.updated(Xs=ND.SparseTernary(512, 16)), mitm = False, babai = True) rop: ≈2^88.7, red: ≈2^88.0, svp: ≈2^87.2, β: 98, η: 2, ζ: 323, |S|: ≈2^39.7, d: 346, ... >>> LWE.primal_hybrid(schemes.Kyber512.updated(Xs=ND.SparseTernary(512, 16)), mitm = True, babai = False) rop: ≈2^74.1, red: ≈2^73.7, svp: ≈2^71.9, β: 104, η: 16, ζ: 320, |S|: ≈2^77.1, d: 359, ... >>> LWE.primal_hybrid(schemes.Kyber512.updated(Xs=ND.SparseTernary(512, 16)), mitm = True, babai = True) rop: ≈2^85.8, red: ≈2^84.8, svp: ≈2^84.8, β: 105, η: 2, ζ: 366, |S|: ≈2^85.1, d: 315, ...
TESTS:
We test a trivial instance:
>>> params = LWE.Parameters(2**10, 2**100, ND.DiscreteGaussian(3.19), ND.DiscreteGaussian(3.19)) >>> LWE.primal_bdd(params) rop: ≈2^43.7, red: ≈2^43.7, svp: ≈2^22.1, β: 40, η: 2, d: 1516, tag: bdd
Methods
__init__
()babai_cost
(d)cost_zeta
(zeta, params[, red_shape_model, ...])This function optimizes costs for a fixed guessing dimension ζ.
svp_dimension
(r, D)Return η for a given lattice shape and distance.
Attributes