Ctrl+K

estimator.ntru_primal.PrimalDSD

estimator.ntru_primal.PrimalDSD#

class estimator.ntru_primal.PrimalDSD[source]#

Estimate cost of solving (overstretched) NTRU via dense sublattice discovery

__call__(params: ~estimator.ntru_parameters.NTRUParameters, red_cost_model=<estimator.reduction.MATZOV object>, red_shape_model='gsa', log_level=1, **kwds)[source]#

Estimate cost of solving (overstretched) NTRU using the Dense sublattice. Code is adapted from Léo Ducas and Wessel van Woerden. See WvanWoerden/NTRUFatigue for original source

Parameters:

  • params – NTRU parameters.

  • red_cost_model – How to cost lattice reduction.

  • red_shape_model – How to model the shape of a reduced basis.

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.

  • d: Lattice dimension.

EXAMPLE:

>>> from estimator import *
>>> NTRU.primal_dsd(schemes.NTRUHRSS701Enc)
rop: ≈2^190.2, red: ≈2^190.2, δ: 1.003095, β: 571, d: 1400, tag: dsd

>>> params = NTRU.Parameters(n=113, q=512, Xs=ND.UniformMod(3), Xe=ND.UniformMod(3))
>>> NTRU.primal_dsd(params, red_shape_model="zgsa")
rop: ≈2^41.3, red: ≈2^41.3, δ: 1.012468, β: 42, d: 226, tag: dsd

>>> NTRU.primal_dsd(params, red_shape_model="cn11")
rop: ≈2^41.2, red: ≈2^41.2, δ: 1.012468, β: 41, d: 226, tag: dsd

>>> NTRU.primal_dsd(params, red_shape_model=Simulator.CN11)
rop: ≈2^41.2, red: ≈2^41.2, δ: 1.012468, β: 41, d: 226, tag: dsd

The success condition was formulated in [EC:KirFou17] and further refined in [AC:DucWoe21]

Note

Non-overstretched parameters (where the probability of Dense sublattice discovery is 0) will return β = d.

Methods

DSLI_vols(dsl_logvol, FL_shape)

DSL_logvol_circulant(n, sigmasq)

DSL_logvol_circulant_fixed(n, R)

DSL_logvol_matrix(n, sigmasq)

__init__()

log_gh(d[, logvol])

Attributes

DSL_logvol

ball_log_vol

prob_dsd

proj_logloss

Contents