V3: Mastering Gram-Schmidt & Lattice Basis Reduction (LLL Algorithm) 📐

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: Orthogonal basis, projections, Gram-Schmidt orthogonalization, 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:33 Slide 39: Orthogonal bases
01:36 Slide 40: Linear algebra background
02:57 Slide 41: Projections
03:47 Slide 42: Exercises
04:38 Slide 43: Application of orthogonal bases
06:19 Slide 44: Orthogonal bases exist (1)
07:16 Slide 45: Orthogonal bases exist (2)
10:00 Slide 46: Orthogonal bases exist (3)
11:29 Slide 47: Gram-Schmidt orthogonalization
13:18 Slide 48: Gram-Schmidt and lattices
14:39 Slide 49: A lower bound for the first successive minimum
17:23 Slide 50: Volume of a lattice (1)
18:36 Slide 51: Volume of a lattice (2)