Rajsekar Manokaran: Average-case Complexity of Lattice Problems
Rajsekar Manokaran, Theory Group, KTH CSC
Tid: Må 2013-09-09 kl 12.10 - 13.00
Plats: Room 1537, Osquars backe 2, 5th floor, KTH CSC
The average-case complexity of a problem is the complexity of solving instances of it picked from a specific distribution. In a seminal work, Ajtai [STOC '96] showed a relation between the average-case complexity and the worst-case complexity of lattice problems. This result is central to cryptography implemented using lattices. Subsequently, Micciancio and Regev [FOCS '04] improved the parameters involved in the proof while also simplifying the presentation.
In this talk, I will describe the result along the lines of the work of Micciancio and Regev. Time permitting, I will describe the recent improvements achieved by Micciancio and Peikert [CRYPTO '13].