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 (Jul 31). Introduction to cryptography, SKE definition, CPA security.
(Reference: [KL] Section 1.4, Chapter 3)
Lecture 2-4 (Aug 4,5,7). 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 (Aug 11). 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 (Aug 12). 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 (Aug 14). 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 (Aug 18). Lattice trapdoors continued, Digital signature
(References: same as before)
Lecture 9 (Aug 19). Digital signature construction, Identity Based Encryption: definition, construction overview
(References: [GPV08] paper section 6, [Pei16] section 5.5)
Lecture 10 (Aug 21). 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 (Aug 25). Efficient construction of IBE, Generalizing IBE to inner product encryption
(References: [ABB10] paper, Slides by Shweta Agrawal)
Lecture 12 (Aug 28). Inner product encryption
(References: [AFV11] paper, Slides by Shweta Agrawal, [Pei16] section 6)
Lecture 13-15 (Sep 1,2,8). Attribute Based Encryption
(References: [Pei16] section 6, [BGGHNSVV14] paper)
Lecture 16 (Sep 9). Homomorphic Encryption - Definition, GSW scheme
(References: this lecture note)
Lecture 17 (Sep 11). Wrapping up GSW, Bootstrapping. Learning with Rounding (LWR) assumption
(References: same as above, [BPR11] for LWR)
Lecture 18-22 (Sep 22,23,25,29,30). Midsem discussion, LWR assumption (recall after midsem), PRF from LWR in random oracle model and standard model, key homomorphic PRF (KHPRF), Application of KHPRF - distributed PRF
(References: [BPR11] Section 3 for LWR; [BLMR13] Sections 1,4,5,7 for PRF constructions, key homomorphism and applications)
Lecture 23 (Oct 3). Commitment scheme - definition, construction from SIS; Vector Commitment - definition
(References: [WW22] for Vector commitment definition)
Lecture 24-26 (Oct 6,7,9). Constructions of vector Commitment (with and without private opening) from SIS; Basis Augmented SIS (BASIS) assumptions-BASIS_rand and BASIS_struct; reduction from SIS to BASIS_rand
(References: [PPS21] for construction without private opening; [WW22] Section 3 for construction with private opening and BASIS assumptions)
Lecture 27,28 (Oct 13,14). Functional commitment (FC) definition and construction from BASIS_struct assumption; alternate form of BASIS_struct; ell-succinct SIS assumption and construction of FC from ell-succinct SIS
(References:[WW22] Section 4, for FC from BASIS_struct, [WW23] Section 3, for ell-succinct assumption and Appendix B, for FC construction)
No class (due to no attendance) on Oct 16; Semester break (Oct 18-25)
Lecture 29 (Oct 27). Recap of FC construction from BASIS_struct and ell-succinct SIS assumptions; BASIS_struct implies ell-succinct SIS
(References: same as above; [Wee24] Section 6.1 for relation between BASIS_struct aand ell-succinct SIS)