Description

Lattices have turned out to be a key source of hardness assumptions for post-quantum cryptography. In this iteration of Advanced Tools from Modern Cryptography, we will look at some advanced cryptographic primitives like identity-based encryption, fully-homomorphic encryption and zero-knowledge proofs through the lens of lattices. The course will have the following structure.

• Module I: We will study lattices from a mathematical and algorithmic point of view. In particular, we will cover several fundamental worst-case lattice problems (e.g., SVP and CVP) and algorithms for these problems (e.g., LLL).
• Module II: We will study the average-case lattice assumptions that post-quantum cryptography relies on (e.g., SIS and LWE). Under these assumptions, we will then construct basic cryptographic primitives like one-way functions, collision-resistant hash functions and public-key encryption.
• Module III: Finally, we will construct advanced cryptographic primitives like fully-homomorphic encryption and identity-based encryption from lattices

Prerequisites

Knowledge of basic cryptography, as covered in CS409 or CS409m, will be assumed. This course will involve some amount of theory, and thus we will expect mathematical maturity.

Who can credit?

The course is open to all CS, EE, Math and IEOR students except for BTech1s and BTech2s. If you are a BTech2 who has taken either CS409 or CS409m, and are keen to credit this course, please reach out to me.

Grading and Attendance

• Attendance is not mandatory (but encouraged)
• There will be five ungraded assignments to help you with quizzes and exams.
• Instructions for scribing:
• Please try to submit your scribe notes within two weeks of the lecture.
• Please use this \(\LaTeX\) template for scribing (output) -- you will find the necessary instructions in the \(\TeX\) file. In case you have trouble compiling, drop by my office.
• I will maintain the scribe notes (along with all my other course material) in this CSE Gitlab repository. Please drop me an e-mail if you'd like to be added as a member there.

Below you can find the list of resources relevant to this course. The list of per-lecture resources (e.g., further reading) can be found at the end of the respective notes.

• The course will not be based on a textbook. We will rely on lecture notes from the first two related courses below and also papers from the references listed in course material. Talks from Simons Institute's Lattices: Algorithms, Complexity, and Cryptography Boot Camp will be a useful resource.

• CSE206A (Spring 2007): Lattices Algorithms and Applications by Daniele Micciancio, on which Module I will be based on.
• CS294: Lattices, Learning with Errors and Post-Quantum Cryptography by Vinod Vaikuntanathan, on which Modules II and III will be based on.
• Lattices in Cryptography by Chris Peikert
• 6.876J: Advanced Topics in Cryptography by Vinod Vaikuntanathan

• Since we will use a lot of linear algebra, please brush it up: 3Blue1Browns's course is an excellent resource for this.
• It will be useful to know basics of coding theory: reading Chapters 1 and 2 from Essential Coding Theory by Guruswami, Rudra and Sudan should suffice.
• Basic computational complexity can be found in the second recitation in MIT6875.

• Autumn'23, by Manoj Prabhakaran
• Spring'22, by Manoj Prabhakaran
• Spring'20, by Manoj Prabhakaran
• Spring'19, by Manoj Prabhakaran
• Autumn'17, by Manoj Prabhakaran