COL872: Lattices in Computer Science
Course Instructor:
Rajendra Kumar
410, Bharti Building
Email: rajendra@cse.iitd.ac.in
Course Timing:
Lecture: Tuesday and Friday 2:00pm-3:30pm
Classroom: LH614
If you are interested in this course and are not able to register, please submit a student general request for pre-requisite waiver and also write an email to me.
Course Description:
This course will focus on the foundation of Lattice-based cryptography. Lattices are mathematical objects, and their study serves as a bridge between number theory and geometry. In the last two decades, lattices have garnered more attention due to their applications in Cryptography. Lattice-based cryptography is the most promising candidate for security against quantum computers, and very soon, it will be deployed all over the internet. To get more confidence on these cryptosystems, we need to understand the hardness of these lattice problems that underlie the security of lattice-based cryptography.
In this course, we plan to cover topics such as the mathematical properties of lattices, lattice reductions, algorithms and hardness of lattice problems, and lattice-based cryptographic schemes. We will also explore the underlying hardness assumptions and security proofs of lattice-based cryptography. Throughout the course, we will discuss recent results, open problems, and potential research directions.
Prerequisites:
Data Structures and Algorithms (COL 106 or equivalent)
Discrete Mathematical Structures (COL 202 or MTL 180 or equivalent )
No background on cryptography is required.
Course Outline:
We plan to cover the following topics:
Preliminaries and basic properties of Lattices
LLL and Babai's algorithm and their applications
Cryptanalysis of RSA
Basic complexity results
Exponential time algorithms
Lattice-based crypto construction
Security of Lattice-based crypto
Fine-grained hardness of Lattice problems
Grading Policy:
Assignment: 10%
2 Quizzes: 20%
Class Participation: 10%
Minor exam: 20%
Project: 40%
Audit pass criterion: Minimum 75% attendance and at least 30 marks from minor exam and project.
For those missing minor exam due to medical reasons, a re-exam may be conducted if they get prior approval from the instructor before the date of regular minor exam.
References:
Here are some courses offered on lattices and their applications:
Oded Regev’s class “Lattices in Computer Science” at Tel Aviv University.
Daniel Dadush and Leo Ducas’s class on ”Intro to Lattice Algorithms and Cryptography” at Utrecht University.
Chris Peikert’s class on “Lattices in Cryptography” at the University of Michigan.
Daniele Miccancio’s class on “Lattice Algorithms and Applications” at UCSD.
Vinod Vaikuntanathan’s classes on “Lattices” and “Learning with Errors and Post-Quantum Cryptography” at MIT.