Welcome to the resource topic for
**2023/200**

**Title:**

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

**Authors:**
Johanna Loyer, André Chailloux

**Abstract:**

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 .