Description
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.
All scheduled dates:
Upcoming
No Upcoming activities yet