With the rapid advancement of quantum computing, many classical cryptographic systems become vulnerable to quantum attacks, motivating the study of post-quantum cryptography. Among the leading post-quantum candidates, lattice-based cryptography stands out due to its strong security guarantees and versatility. This course aims to provide a theoretical foundation of lattice-based cryptography, along with its applications in constructing various foundational as well as advanced cryptographic primitives from lattice-based assumptions. The course will involve rigorous analysis of formal proofs of correctness and security of these constructions.
Foundations of Cryptography and motivation for Post-Quantum Cryptography: A quick refresher on basic cryptographic primitives (one-way functions (OWF), pseudorandom generators (PRG), pseudorandom function (PRF), secret key and public key encryption schemes, digital signatures), and formal security definitions; classical hard problems and known results for their quantum solutions; overview of post quantum cryptography domains (lattices, isogenies, code-based cryptography).
Introduction to Lattices: Lattices and lattice basis; hard problems in lattices and relations between them; LLL algorithm for lattice basis reduction and its application.
LWE and SIS problem and applications: LWE (search and decision) and SIS problem; worst case to average case hardness; trapdoor generation; variants and relationships; constructions of basic cryptographic primitives from these assumptions, including OWF, secret key and public key encryption schemes, digital signatures.
Learning with Rounding (LWR): Definition, and reduction from LWE; applications.
Advanced cryptographic constructions from Lattices: Homomorphic encryptions and other selected advanced cryptographic primitives from lattice-based assumptions - definitions, formal constructions, various associated security notions and extensions.
Evaluation will consist of assignments, mid-semester and end-semester exams, and a paper reading project with class presentation and/or viva.
There are no formal prerequisites, however, the course assumes mathematical maturity and involves rigorous analysis, including proofs and reductions. Familiarity and comfort with basic linear algebra and probability is required. Overall, interest and aptitude for theoretical computer science are expected. A background in cryptography would be helpful but not necessary.
For foundational concepts in cryptography, the following are good reference books:
- Introduction to Modern Cryptography by Jonathan Katz and Yehuda Lindell
- Foundations of Cryptography by Oded Goldreich Volume 1 and 2.
We will use resources from other related course pages. Some of them are: Vinod Vaikuntanathan’s course on Lattices, LWE and PQC, Oded Regev’s course on Lattices in Computer Science, Shweta Agrawal’s course on PQC, and other similar course pages
Related research papers.