- Kyber.short_vectors(beta, d, N=None, B=None, preprocess=True)#
Cost of outputting many somewhat short vectors using BKZ-β.
The output of this function is a tuple of four values:
ρ is a scaling factor. The output vectors are expected to be longer than the shortest vector expected from an SVP oracle by this factor.
c is the cost of outputting N vectors
N the number of vectors output, which may be larger than the value put in for N.
β’ the cost parameter associated with sampling
This is using an observation insprired by [AC:GuoJoh21] that we can run a sieve on the first block of the basis with negligible overhead.
beta – Cost parameter (≈ SVP dimension).
d – Lattice dimension.
N – Number of vectors requested.
preprocess – Include the cost of preprocessing the basis with BKZ-β. If
Falsewe assume the basis is already BKZ-β reduced.
(ρ, c, N, β')
>>> from estimator.reduction import RC >>> RC.Kyber.short_vectors(100, 500, 1) (1.0, 2.7367476128136...19, 100, 1) >>> RC.Kyber.short_vectors(100, 500) (1.1547, 2.7367476128136...19, 176584, 84) >>> RC.Kyber.short_vectors(100, 500, 1000) (1.1547, 2.7367476128136...19, 176584, 84)