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 .