- BDGL16.short_vectors(beta, d, N=None, B=None, preprocess=True, sieve_dim=None)#
Cost of outputting many somewhat short vectors.
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, here: β or
This implementation uses that a sieve outputs many somehwat short vectors [Kyber17].
beta – Cost parameter (≈ SVP dimension).
d – Lattice dimension.
N – Number of vectors requested.
B – Bit-size of entries.
preprocess – Include the cost of preprocessing the basis with BKZ-β. If
Falsewe assume the basis is already BKZ-β reduced.
sieve_dim – Explicit sieving dimension.
(ρ, c, N)
>>> from estimator.reduction import RC >>> RC.ADPS16.short_vectors(100, 500, 1) (1.0, 6.16702733460158e8, 1, 100) >>> RC.ADPS16.short_vectors(100, 500) (1.1547..., 6.16702733460158e8, 1763487, 100) >>> RC.ADPS16.short_vectors(100, 500, 1000) (1.1547..., 6.16702733460158e8, 1763487, 100)