V2: Gauss's Algorithm (Lattice Basis Reduction)

These lectures give a detailed explanation of the Lenstra-Lenstra-Lovász (LLL) lattice-basis reduction algorithm, one of the most powerful and versatile tool in cryptanalysis. All the required mathematical background in linear algebra and lattices is provided. Topics covered: Gauss's algorithm, short-vector problem (SVP), lattices Lecture playlist: https://www.youtube.com/playlist?list=PLA1qgQLL41SQ5oQDDH4V5ApkxnoKi_8jl Course web page: https://cryptography101.ca/lattice-basis-reduction/ The slides are available on the course web page. Other cryptography courses: https://cryptography101.ca Slides 00:00 Introduction 00:37 Slide 27: Problem statement 01:35 Slide 28: Projecting a vector onto another vector 03:19 Slide 29: Gauss's algorithm: main idea 05:26 Slide 30: Gauss's algorithm 06:27 Slide 31: Running time 07:18 Slide 32: Example 1 08:29 Slide 33: Example 2 08:43 Slide 34: First successive minimum 10:19 Slide 35: Second successive minimum 12:27 Slide 36: Higher-dimension lattices