Ctrl+K

estimator.ntru_primal.NTRUPrimalHybrid

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 *
>>> NTRU.primal_hybrid(schemes.NTRUHPS2048509Enc.updated(Xs=ND.SparseTernary(508,16)),
... 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(schemes.NTRUHPS2048509Enc.updated(Xs=ND.SparseTernary(508,16)),
... 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(schemes.NTRUHPS2048509Enc.updated(Xs=ND.SparseTernary(508,16)),
... 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(schemes.NTRUHPS2048509Enc.updated(Xs=ND.SparseTernary(508,16)),
... 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

cost

Contents