CSS 420.1: Cryptography from Lattices

Lecture Timings: Tuesday and Thursday at 2 - 3.30 PM.

Prerequisites: Basics of discrete probability and linear algebra.

Assignments and Lecture Notes: Piazza

References:

Lattices in Computer Science by Oded Regev.
Lattices, Learning with Errors and Post-Quantum Cryptography by Vinod Vaikuntanathan.
Lattices in Cryptography by Chris Peikert.
Lattice-based Cryptosystems by Dakshita Khurana.
A Decade of Lattice Cryptography by Chris Peikert.

Course Summary:

Date	Topics Covered	References
09/08/22	Introduction to Lattices	Regev: Lecture-1
16/08/22	Minkowski's Theorem LLL Reduced Basis	Regev: Lecture-1 Regev: Lecture-2
18/08/22	LLL Algorithm Babai's Nearest Plane Algorithm	Regev: Lecture-2 Regev: Lecture-3
23/08/22	Attacks on Low Exponent RSA with Deterministic Padding	Regev: Lecture-4
25/08/22	SIS assumption Collision-Resistance from SIS	Peikert: Chapter-4.1 Micciancio-Regev: Worst-case to Average-case Reductions
30/08/22	LWE assumption Secret-Key Encryption from LWE	Peikert: Chapter-4.2 Regev: Learning with Errors Survey
06/09/22	Completing proof of SKE Public-Key Encryption from LWE	Vaikuntanathan: Lecture-1 Leftover Hash Lemma
08/09/22	Dual-Regev Encryption GSW Fully Homomorphic Encryption	Vaikuntanathan: Lecture-1 Khurana: Lecture-11 Khurana: Lecture-12
13/09/22	Bootstrapping Applications of FHE: PIR and Secure Computation	Khurana: Lecture-11 Gentry: Computing Arbitrary Functions of Encrypted Data
20/09/22	Trapdoor Functions Introduction to Lattice Trapdoors	Jain: Chapter-6 Vaikuntanathan: Lecture-6
22/09/22	Type-1 and Type-2 Lattice Trapdoors	Vaikuntanathan: Lecture-6
27/09/22	Trapdoors for SIS Introduction to Digital Signatures	Vaikuntanathan: Lecture-6
29/09/22	Pre-Image Sampler and Digital Signatures	Halevi-Malkin: SIS-based Signatures Gentry-Peikert-Vaikuntanathan
04/10/22	Sampling from Discrete Gaussians	Gentry-Peikert-Vaikuntanathan Micciancio-Regev
06/10/22	Identity-based Encryption	Gentry-Peikert-Vaikuntanathan
11/10/22	CCA-2 Security from IBE	Boneh-Canetti-Halevi-Katz
13/10/22	Selective Secure IBE without Random Oracles	Cash-Hofheinz-Kiltz-Peikert
18/10/22	Attribute-based Encryption	Boneh et al.
20/10/22	Attribute-based Encryption Contd.	Boneh et al.
25/10/22	Zero-Knowledge Proofs	Pass-shelat: Chapter-4 Rosen: Introduction to ZK
27/10/22	Zero-Knowledge Proofs contd.	Pass-shelat: Chapter-4
1/11/22	NIZKs in the Random Oracle Model
3/11/22	NIZKs from circular-secure LWE	Canetti-Lombardi-Wichs
10/11/22	NIZKs from LWE	Peikert-Shiehian
15/11/22	Review Lecture