Ctrl+K

estimator.reduction.MATZOV

estimator.reduction.MATZOV#

class estimator.reduction.MATZOV(nn='classical')[source]#

Improved enumeration routine in list decoding from [MATZOV22].

Parameters:

nn – Nearest neighbor cost model. We default to “ListDecoding” (i.e. BDGL16) and to the “depth × width” metric. Kyber uses “AllPairs”.

__call__(beta, d, B=None, C=5.46)#

Runtime estimation from [Kyber20] and [AC:AGPS20].

Parameters:

  • beta – Block size ≥ 2.

  • d – Lattice dimension.

  • B – Bit-size of entries.

  • C – Progressive overhead lim_{β → ∞} ∑_{i ≤ β} 2^{0.292 i + o(i)}/2^{0.292 β + o(β)}.

EXAMPLE:

>>> from math import log
>>> from estimator.reduction import RC, Kyber
>>> log(RC.Kyber(500, 1024), 2.0)
176.61534319964488
>>> log(Kyber(nn="list_decoding-ge19")(500, 1024), 2.0)
172.68208507350872

Methods

LLL(d[, B])

Runtime estimation for LLL algorithm based on [AC:CheNgu11].

__init__([nn])

param nn:

Nearest neighbor cost model. We default to "ListDecoding" (i.e. BDGL16) and to

beta()

Estimate required block size β for a given root-hermite factor δ based on [PhD:Chen13].

d4f(beta)

Dimensions "for free" following [EC:Ducas18].

delta(beta)

Compute root-Hermite factor δ from block size β.

short_vectors(beta, d[, N, preprocess, B, ...])

Cost of outputting many somewhat short vectors according to [AC:GuoJoh21].

short_vectors_simple(beta, d[, N, B, preprocess])

Cost of outputting many somewhat short vectors.

svp_repeat(beta, d)

Return number of SVP calls in BKZ-β.

Attributes

NN_AGPS

Contents