IACR News item: 20 February 2023
Johanna Loyer, André Chailloux
ePrint Report
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$.
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$.
Additional news items may be found on the IACR news page.