Lecture 5. SIS/LWE and lattices (The Mathematics of Lattice-Based Cryptography)

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"