V2: Master Gauss's Algorithm & Lattice Basis Reduction (LLL) 🧮

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