Lecture 4. 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: Definition of a lattice, fundamental parallelepiped, bases of a lattice, volume of a lattice, successive minima, LLL lattice basis reduction algorithm, shortest vector problem (SVP), shortest independent vectors problem (SIVP) 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:36 Slide 37: Lattice definition 01:56 Slide 38: Full-rank lattices 02:53 Slide 39: Example 1 03:40 Slide 40: Fundamental parallelepiped 04:31 Slide 41: Example 2 05:36 Slide 42: Example 3 06:26 Slide 43: One base is "nicer" than the other 06:53 Slide 44: Example 4 07:37 Slide 45: A lattice has infinitely many bases 08:55 Slide 46: Proof of the characterization of lattice bases 10:24 Slide 47: Volume of a lattice 11:02 Slide 48: Some bases are nicer than others 12:17 Slide 49: Successive minima 14:42 Slide 50: LLL lattice basis reduction algorithm 15:56 Slide 51: Cryptanalytic applications of LLL 17:16 Slide 52: SVP: a fundamental lattice problem 19:37 Slide 53: SIVP: another fundamental lattice problem