estimator.reduction.Kyber.short_vectors
estimator.reduction.Kyber.short_vectors#
- Kyber.short_vectors(beta, d, N=None, B=None, preprocess=True)[source]#
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.
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.
- Parameters
beta – Cost parameter (≈ SVP dimension).
d – Lattice dimension.
N – Number of vectors requested.
preprocess – Include the cost of preprocessing the basis with BKZ-β. If
False
we assume the basis is already BKZ-β reduced.
EXAMPLES:
>>> from estimator.reduction import RC >>> RC.Kyber.short_vectors(100, 500, 1) (1.0, 2.7367476128136...19, 100) >>> RC.Kyber.short_vectors(100, 500) (1.1547, 2.7367476128136...19, 176584) >>> RC.Kyber.short_vectors(100, 500, 1000) (1.1547, 2.7367476128136...19, 176584)