This course introduces the foundations of lattice-based cryptography, a leading approach towards achieving post-quantum security. It aims to develop an understanding of the mathematical foundations, security principles, and design techniques underlying lattice-based constructions, with an emphasis on their use in building advanced cryptographic systems. The course is theoretical in nature and involves rigorous analysis of constructions along with formal proofs of correctness and security.
Prerequisites: No formal prerequisite. Mathematical maturity and interest in theoretical CS is expected.
Time and Venue: Tue, Fri 12:00-13:00, Wed 14:00-15:00 in KD103.
Evaluation:
Assignments(30%), Midsem(20%), Endsem(20%), Project(25%), Class participation(5%)
The following book provides a useful cryptographic background covered in the course:
[KL] Jonathan Katz and Yehuda Lindell, Introduction to Modern Cryptography (3rd Ed.).
References to online lecture notes, research papers, and survey articles will be provided throughout the semester.
[Pei16] Chris Peikert, A Decade of Lattice Cryptography.
[VV] Vinod Vaikuntanathan's course page
Lecture 1. Introduction to cryptography, SKE definition, CPA security.
(Reference: [KL] Section 1.4, Chapter 3)
Lecture 2,3,4. OWF, PRG, PRF, negligible function, OTP, SKE from PRG and PRF, security proofs by hybrids, Introduction to lattices - basis, successive minima, hard problems and their relations - exact and approximate SVP, CVP, approximate SIVP, good and bad basis, PKE.
(References: [KL] Chapters 2,3,7; )
Lecture 5. SIS and LWE - definition, total and planted regime, connection to lattice problems, BDD, PKE from short secret LWE.
(References: [VV-Lec1], [Pei16] sections 4, 5.)
Lecture 6. Regev and dual Regev's PKE, normal forms of SIS and LWE, worst case to average case reduction in LWE, equivalence of ssLWE and LWE
(References: [Pei16])
Lecture 7. Search to decisional LWE reduction, Lattice trapdoors
(References: [VV-Lec4] for search to decsional reduction; for lattice trapdoors: Slides by Shweta Agrawal, [Pei16] section 5.4)
Lecture 8. Lattice trapdoors continued, Digital signature
(References: same as before)
Lecture 9. Digital signature construction, Identity Based Encryption: definition, construction overview
(References: [GPV08] paper section 6, [Pei16] section 5.5)
Lecture 10. Identity Based Encryption constructions in random oracle and standard model
(References: [GPV08] paper section 7, Slides by Shweta Agrawal, [Pei16] section 5.5)
Lecture 11. Efficient construction of IBE, Generalizing IBE to inner product encryption
(References: [ABB10] paper, Slides by Shweta Agrawal)
Lecture 12. Inner product encryption
(References: [AFV11] paper, Slides by Shweta Agrawal, [Pei16] section 6)
Lecture 13-15. Attribute Based Encryption
(References: [Pei16] section 6, [BGGHNSVV14] paper)
Lecture 16. Homomorphic Encryption - Definition, GSW scheme
(References: this lecture note)
Lecture 17. Wrapping up GSW, Bootstrapping. Learning with Rounding (LWR) assumption
(References: same as above, [BPR11] for LWR)