Understanding Lattice-Based Cryptography: SIS, LWE, and Practical Applications 🔐

Video lectures for Alfred Menezes's introductory course on the mathematics of lattice-based cryptography. Kyber (ML-KEM) and Dilithium (ML-DSA) are lattice-based cryptosystems that are resistant to attacks by quantum computers. Hardness of the Module-SIS and Module-LWE problems is the basis for the security of Kyber and Dilithium . These lectures 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.

Topics covered: SIS lattice, solving SIS, LWE lattice, solving LWE, Bounded Distance Decoding problem, BDD, worst-case to average-case reductions, Gaussian distributions

Lecture playlist:
https://www.youtube.com/playlist?list=PLA1qgQLL41STNFDvPJRqrHtuz0PIEJ4a8

Course web page: https://cryptography101.ca/lattice-based-cryptography/
The slides are available on the course web page.

Other cryptography courses: https://cryptography101.ca

Slides
00:00 Introduction
00:26 Slide 56: Definition of the SIS lattice
02:37 Slide 57: Rank of the SIS lattice
04:29 Slide 58: Volume of the SIS lattice
06:43 Slide 59: A basis of the SIS lattice
09:23 Slide 60: Solving SIS
10:31 Slide 61: Solving SIS_2
12:27 Slide 62: Average-case hardness of SIS
14:48 Slide 63: The worst-case to average-case reduction is asymptotic
16:01 Slide 64: SIS summary
17:14 Slide 65: Definition of the LWE lattice
18:19 Slide 66: A basis of the LWE lattice
20:42 Slide 67: Solving LWE
21:59 Slide 68: Reducing BDD to SVP (1)
25:19 Slide 69: Reducing BDD to SVP (2)
25:43 Slide 70: Average-case hardness of LWE
27:48 Slide 71: Gaussian distributions
28:29 Slide 72: LWE summary

Corrections:
00:26 Slide 56: In the figure, "Az=b" should be "Az=0"