January 2025
Hardness of the Module-SIS and Module-LWE problems is the basis for the security of Kyber (ML-KEM) and Dilithium (ML-DSA). These lectures by Alfred Menezes describe the connection between lattices and the Module-SIS and Module-LWE problems, thus explaining why Kyber and Dilithium are considered to be lattice-based cryptosystems.
Learning outcomes
On successful completion of this course, students will:
- Understand what a lattice is, and some of their basic properties.
- Learn the fundamental lattices problems including the Shortest Vector Problem (SVP), the Shortest Independent Vector Problem (SIVP), and their approximations.
- Understand the connection between lattices and the SIS, LWE, Module-SIS and Module-LWE problems.
Note to instructors
If you are teaching a course in applied cryptography and would like to use my video lectures as a secondary source or a primary source, please send me an email message. I will be happy to arrange a meeting with you, to tell you about my experience teaching applied cryptography over the past 30 years, and we can have a discussion about the curriculum, exercises, projects, and tests for your course. If you use any of the resources (videos or slides) on this web page in your classes, please do provide your students a link to my page (cryptography101.ca).
YouTube Lectures
1. Introduction
2. Short Integer Solutions (SIS)
4. Lattices
Additional Material
Errata (last updated: January 9, 2025)
Here is a list of errors in the video lectures. These errors have already been corrected in the lecture slides (available below).
- Slide 10 (V2): Ar=0 should be Az=0
- Slide 11 (V2): Second solution should be (1,0,-2,-1,3)
- Slide 13 (V2): “b in Zqm” should be “b in Zqn”
- Slide 15 (V2): [1,n+1] should be [1,m+1]
- Slide 42 (V4): In Note 2, the coefficient “-3” should be “+3”
- Slide 56 (V5): Az=b should be Az=0 (in the diagram on the top right)
- Slide 67 (V5): The circle should be centred at b (not y)
- Slide 68 (V5): Matrix D’ is over the real numbers (not the integers)
- Slide 88 (V6): -4x^4 should be -4x^3
- Slide 118 (V7): e is selected from S_{\eta_1}^k (not from S_{\eta_2}^k)
- Slide 119 (V7): z is selected from S_{\eta_2}^k (not from S_{\eta_1}^k)