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

cost