Spring 2020

Fine-Grained Complexity of Lattice Problems

Tuesday, Feb. 4, 2020 10:00 am12:00 pm PST

Add to Calendar


Huck Bennett, University of Michigan


Calvin Lab Auditorium, Room 116

The area of fine-grained complexity works to establish strong computational lower bounds by giving highly efficient reductions between computational problems. Understanding the fine-grained complexity of lattice problems is especially well-motivated by the need to understand the precise security of real-world lattice-based cryptosystems, where the difference in solving a lattice problem in 2^n versus 2^(n/20) versus 2^sqrt(n) time may mean the difference between a cryptosystem being secure, insecure with current parameters, and effectively broken in practice.

In this talk, I will survey recent work on the fine-grained complexity of lattice problems, with a focus on the Closest Vector Problem (CVP). I will also describe connections between the geometry of lattices and proving computational lower bounds, and will present a number of open questions.
Based on joint work with Divesh Aggarwal, Alexander Golovnev, and Noah Stephens-Davidowitz.