A new heuristic sieving algorithm for the Shortest Vector Problem

What is it about?

The Shortest Vector Problem asks for a given discrete lattice basis what the shortest nonzero vector is from its origin. Several algorithms like enumerations, sieves or metaheuristics are used for finding it. The paper proposes a new sieving algorithm that uses a concept of Etalé spaces and coboundary maps on sheaves. These concepts are common in Algebraic Geometry, but allow to structure a set of candidate vectors into an Etalé space which allows for memory-efficient sieving.

Featured Image

Photo by Batyrkhan Shalgimbekov on Unsplash

Photo by Batyrkhan Shalgimbekov on Unsplash

Why is it important?

Cryptosystems based on lattices (e.g. "Learning with errors") will get more and more applications in secure internet communication. It is a candidate of post-quantum cryptography, since a quantum computer cannot solve the Shortest Vector Problem easily. This is a reason that current cryptosystems like RSA or ECC are transitioning to post-quantum cryptography like that based on lattices. For future cryptanalysis of lattice algorithms, a new sieving algorithm is proposed. It is more memory-efficient than other types of sieving algorithms and allows to run it on current supercomputers even for larger lattice dimensions.

Perspectives