estimator.ntru_primal.NTRUPrimalHybrid#
- class estimator.ntru_primal.NTRUPrimalHybrid[source]#
- __call__(params: ~estimator.ntru_parameters.NTRUParameters, babai: bool = True, zeta: int | None = 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 – NTRU 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 * >>> params = schemes.NTRUHPS2048509Enc.updated(Xs=ND.SparseTernary(16)) >>> NTRU.primal_hybrid(params, mitm=False, babai=False) rop: ≈2^87.8, red: ≈2^87.0, svp: ≈2^86.6, β: 116, η: 21, ζ: 302, |S|: ≈2^39.2, d: 372, prob: ≈2^-22.3, ↻... >>> NTRU.primal_hybrid(params, mitm=False, babai=True) rop: ≈2^88.0, red: ≈2^87.4, svp: ≈2^86.4, β: 98, η: 2, ζ: 318, |S|: ≈2^39.6, d: 328, prob: ≈2^-27.9, ↻: ... >>> NTRU.primal_hybrid(params, mitm=True, babai=False) rop: ≈2^80.1, red: ≈2^79.7, svp: ≈2^78.3, β: 170, η: 22, ζ: 254, |S|: ≈2^103.7, d: 495, prob: 0.708, ↻: ... >>> NTRU.primal_hybrid(params, mitm=True, babai=True) rop: ≈2^85.1, red: ≈2^84.1, svp: ≈2^84.0, β: 105, η: 2, ζ: 363, |S|: ≈2^85.0, d: 294, prob: ≈2^-22.9, ↻:...
TESTS:
We test a trivial instance:
>>> params = NTRU.Parameters(2**10, 2**100, ND.DiscreteGaussian(3.19), ND.DiscreteGaussian(3.19)) >>> NTRU.primal_bdd(params) rop: ≈2^43.6, red: ≈2^43.6, svp: ≈2^35.0, β: 40, η: 46, d: 1461, 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