Ctrl+K

estimator.sis_lattice.SISLattice

estimator.sis_lattice.SISLattice#

class estimator.sis_lattice.SISLattice[source]#

Estimate cost of solving SIS via lattice reduction.

__call__(params: ~estimator.sis_parameters.SISParameters, zeta: int | None = None, red_shape_model='gsa', red_cost_model=<estimator.reduction.MATZOV object>, log_level=1, **kwds)[source]#

Estimate the cost of attacking SIS using lattice reduction

Parameters:

  • params – SIS parameters.

  • zeta – Number of coefficients to set to 0 (ignore)

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 Sieving call to generate short vectors.

  • ζ: Number of ignored coordinates.

  • |S|: Guessing search space.

  • prob: Probability of success in guessing.

  • repeat: How often to repeat the attack.

  • d: Lattice dimension.

EXAMPLES:

>>> from estimator import *
>>> SIS.lattice(schemes.Dilithium2_MSIS_WkUnf)
rop: ≈2^152.2, red: ≈2^151.3, sieve: ≈2^151.1, β: 427, η: 433, ζ: 0, d: 2304, prob: 1, ↻: 1, tag: infinity

>>> SIS.lattice(schemes.Dilithium2_MSIS_WkUnf, red_shape_model="lgsa")
rop: ≈2^151.3, red: ≈2^150.2, sieve: ≈2^150.5, β: 423, η: 431, ζ: 0, d: 2304, prob: 1, ↻: 1, tag: infinity

>>> params = SIS.Parameters(n=113, q=2048, length_bound=512, norm=2)
>>> SIS.lattice(params)
rop: ≈2^47.0, red: ≈2^47.0, δ: 1.011391, β: 61, d: 276, tag: euclidean

>>> SIS.lattice(params.updated(norm=oo, length_bound=16), red_shape_model="lgsa")
rop: ≈2^61.0, red: ≈2^59.9, sieve: ≈2^60.1, β: 95, η: 126, ζ: 0, d: 2486, prob: 1, ↻: 1, tag: infinity

>>> SIS.lattice(params.updated(norm=oo, length_bound=16), red_shape_model="cn11")
rop: ≈2^65.9, red: ≈2^64.9, sieve: ≈2^64.9, β: 113, η: 142, ζ: 0, d: 2486, prob: 1, ↻: 1, tag: infinity

>>> SIS.lattice(params.updated(norm=oo, length_bound=1), red_shape_model="cn11")
rop: ≈2^246.2, red: ≈2^245.2, sieve: ≈2^245.2, β: 764, η: 751, ζ: 0, d: 2486, prob: 1, ↻: 1, tag: infinity

The success condition for euclidean norm bound is derived by determining the root hermite factor required for BKZ to produce the required output. For infinity norm bounds, the success conditions are derived using a probabilistic analysis. Vectors are assumed to be short as in [MATZOV22] P.18, or [Dilithium21] P.35.

Note

When using euclidean norm bounds and the length bound is too small, this function returns β = d, and rop: inf

Methods

__init__()

cost_zeta(zeta, params[, ignore_qary, ...])

This function optimizes costs for a fixed number of coordinates to 'ignore', denoted ζ.

Attributes

cost_euclidean

cost_infinity

Contents