[Resource Topic] 2023/200: Classical and quantum 3 and 4-sieves to solve SVP with low memory

Welcome to the resource topic for 2023/200

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

Authors: 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 scalar products.

In this work, we present a framework for k-sieve algorithms: we filter the input list of lattice vectors using a code structure modified from [BDGL16] to get lists centred around k codewords summing to the null-vector. Then, we solve a simpler instance of the configuration problem in the k filtered lists.
Based on this framework, we describe classical sieves for k=3 and 4 that introduce new time-memory trade-offs.
We also use the k-Lists algorithm [KMPM19] inside our framework, and this improves the time for k=3 and gives new trade-offs for k=4.

ePrint: https://eprint.iacr.org/2023/200

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .