COL872: Lattices in Computer Science

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.

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.  

Class Schedule:

• 23rd July: Introduction to Lattices   Ref: 1st section of Regev's notes on Introduction

• 26th July: Computional Problems on Lattices.   

• 30th July:  Reduction between Lattice Problems

• 2nd August: Geometric bounds on Lattices

• 6th August: LLL algorithm   Ref: Regev's note on LLL algorithm

• 9th August: Continued LLL algorithm and Babai's Nearest Plane Algorithm 

• 20th August: Hardness of Lattice Problems

• 23rd August: Fine-grained hardness of CVP

• 27th August: Barrier for Hardness

• 30th August: QUIZ 1

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.