In this course, we will take a deep dive into the study of point lattices. While the initial study of lattices, that goes back to at least 1800s, was only from the mathematical foundations point of view, it has played a transformative role in modern day cryptography and theoretical computer science at large. Algorithms to solve problems over lattices can be used for a variety of tasks not necessarily related to cryptography.
In this course, we will study several average-case decoding problems over lattices, most notably the Learning with Errors (LWE) problem, and how these problems give rise to almost magical utility to build powerful cryptographic tools. In addition, these problems are widely believed to be hard against quantum computers. Therefore, lattices are today at the forefront for building post-quantum cryptography. Moreover, what makes lattices really exciting is that LWE and other related problems can be shown to be as hard as worst-case problems over lattices and therefore cryptographic constructions built from lattices can be based on hardness of worst-case complexity problems.
The course will consist of two components:
i) In the first component, we will cover foundations of lattices including the study of structural properties of lattices, algorithms to solve lattice problems and reductions between lattice problems.
ii) In the second component, we will focus exclusively on advanced cryptographic applications of lattices and related problems.
Evaluation: The evaluation would be based on participation in the class. Each student would be required to scribe a lecture, present a paper towards the later half of the course, and work on a survey/original research (Topics should be discussed with the instructor).
Lecture Schedule: Our lecture schedule and the topics covered are described below. The schedule will be updated with scribe notes as and when they are available.
Scribe Notes: An incomplete set of lecture notes for this course can be found here. These lecture notes have not been proofread and may contain occasional errors.
1/19: Introduction to the course, LWE and SIS problems.
Textbook and Other Similar Courses: There is no textbook for this course. However, we will point to readings time to time which may consist of papers, book chapters or lecture notes from courses run at other universities. This course is inspired by a number of exceptionally other well-designed courses run at other universities. Each course below offers a slightly different take on lattices:
Course by Vinod Vaikunthanthan at MIT
Course by Daniele Micciancio at UCSD
Course by David Wu at UT Austin
We also point you to two classic surveys on the topic:
A Decade of Lattice Cryptography by Chris Peikert
The Learning with Errors Problem by Oded Regev