estimator.lwe_primal.PrimalHybrid

estimator.lwe_primal.PrimalHybrid#

class estimator.lwe_primal.PrimalHybrid[source]#
__call__(params: ~estimator.lwe_parameters.LWEParameters, 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 – 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 *
>>> params = schemes.Kyber512.updated(Xs=ND.SparseTernary(16))
>>> LWE.primal_hybrid(params, mitm=False, babai=False)
rop: ≈2^89.3, red: ≈2^88.8, svp: ≈2^87.7, β: 106, η: 18, ζ: 321, |S|: ≈2^39.7, d: 360, prob: ≈2^-26.9, ↻...

>>> LWE.primal_hybrid(params, mitm=False, babai=True)
rop: ≈2^88.4, red: ≈2^87.8, svp: ≈2^86.9, β: 98, η: 2, ζ: 321, |S|: ≈2^39.7, d: 347, prob: ≈2^-28.1, ↻...

>>> LWE.primal_hybrid(params, mitm=True, babai=False)
rop: ≈2^73.4, red: ≈2^72.5, svp: ≈2^72.3, β: 109, η: 15, ζ: 320, |S|: ≈2^82.8, d: 366, prob: 0.001, ↻...

>>> LWE.primal_hybrid(params, mitm=True, babai=True)
rop: ≈2^85.5, red: ≈2^84.5, svp: ≈2^84.5, β: 105, η: 2, ζ: 364, |S|: ≈2^85.0, d: 316, prob: ≈2^-23.2, ↻...

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.6, red: ≈2^43.6, svp: ≈2^21.9, β: 40, η: 2, d: 1514, tag: bdd

We also test a LWE instance with a large error (coming from issue #106):

>>> LWE.primal_bdd(LWE.Parameters(n=256, q=12289, Xs=ND.UniformMod(2), Xe=ND.UniformMod(1024)))
rop: ≈2^115.4, red: ≈2^41.3, svp: ≈2^115.4, β: 40, η: 336, d: 336, tag: bdd

>>> LWE.primal_bdd(LWE.Parameters(n=700, q=2**64, Xs=ND.UniformMod(2), Xe=ND.UniformMod(2**59)))
rop: ≈2^259.8, red: ≈2^42.8, svp: ≈2^259.8, β: 40, η: 854, d: 854, tag: bdd

# small n example (Issue #182)
>>> LWE.primal_bdd(LWE.Parameters(n=8, q = 2**128, Xs=ND.UniformMod(2**128), Xe=ND.UniformMod(2**(126))))
rop: ≈2^185.5, red: ≈2^184.4, svp: ≈2^184.7, β: 585, η: 585, d: 585, 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[, is_homogeneous])

Return required svp dimension for a given lattice shape and distance.

svp_dimension_gsa(d, log_total_vol, log_delta, D)

Return required svp dimension for a given lattice shape and distance.

Attributes

cost

Contents