Classical and quantum 3 and 4-sieves to solve SVP with low memory

ePrint Report: Classical and quantum 3 and 4-sieves to solve SVP with low memory

Johanna Loyer, André Chailloux

The Shortest Vector Problem (SVP) is at the foundation of lattice-based cryptography.
The fastest known method to solve SVP in dimension $d$ is by lattice sieving, which runs in time $2^{td+o(d)}$ with $2^{md+o(d)}$ memory for constants $t,m \in \Theta(1)$.
Searching reduced vectors in the sieve is a problem reduced to the configuration problem, \ie searching $k$ vectors satisfying given constraints over their …

cryptography eprint report foundation johanna low memory problem quantum report