|Date||Jul 05, 2016|
|Dept.||Inria, France and CNRS/JFLI and the University of Tokyo, Japan|
In a breakthrough 1996 result, Ajtai presented the first average-case problem (SIS) provably as hard as several worst-case lattice approximation problems.
This special property initiated the development of provably secure lattice-based cryptography, and brought many results in the past twenty years.
In this talk, we survey worst-case to average-case reductions for lattice problems, (including SIS, LWE and variants), and discuss recent results, including as joint work with Gama, Izabachene and Xie (EUROCRYPT 2016), and an arxiv preprint by Eldar and Shor.