Paper 2023/200

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

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 \mathrm{\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 $$-sieve algorithms: we filter the input list of lattice vectors using a code structure modified from [BDGL16] to get lists centred around $$ codewords summing to the null-vector. Then, we solve a simpler instance of the configuration problem in the $$ filtered lists. Based on this framework, we describe classical sieves for $$ and $$ that introduce new time-memory trade-offs. We also use the $$-Lists algorithm [KMPM19] inside our framework, and this improves the time for $$ and gives new trade-offs for $$.