Sieving for shortest lattice vectors using near neighbor techniques

Talk by Dr. Thijs Laarhoven

Date: 26.04.17  Time: 15.00 - 16.00  Room: Y27H28

One of the fundamental hard problems in lattice-based cryptography is the Shortest Vector Problem (SVP): given a basis of a lattice, find a shortest non-zero vector in this lattice. Several methods are known for solving this problem, and currently lattice sieving has the best known (heuristic) time complexity for solving SVP in high dimensions. Recent progress in lattice sieving has been focused on using optimized near neighbor techniques, similar to those used by May and Ozerov for decoding binary linear codes.
This talk will introduce the basics of lattices and lattice-based cryptography, discuss different approaches for solving SVP, and describe the ideas behind combining lattice sieving with nearest neighbor searching.