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 *
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_matrix`(n, sigmasq) `log_gh`(d[, logvol])

Attributes