Events
Spring 2020
Fine-Grained Complexity of Lattice Problems
Tuesday, February 4th, 2020, 10:00 am–12:00 pm
Parent Program:
Speaker:
Huck Bennett, University of Michigan
Location:
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.