V4: Master the LLL Algorithm: A Comprehensive Guide to 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: Gram-Schmidt orthogonalization, LLL-reduced basis, size reduction, swaps, LLL algorithm, lattice basis reduction, lattices, short vectors

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 54: Introduction
01:31 Slide 55: Gram-Schmidt orthogonalization
03:28 Slide 56: LLL algorithm: main ideas
06:03 Slide 57: LLL-reduced basis
08:18 Slide 58: Shortness of the first vector in an LLL-reduced basis
09:50 Slide 59: LLL lattice basis reduction
10:03 Slide 60: Size reduction
11:15 Slide 61: Size reduction doesn't change the GS basis
12:55 Slide 62: Size reduction works (1)
14:33 Slide 63: Size reduction works (2)
15:32 Slide 64: Swap
16:06 Slide 65: The LLL algorithm
17:02 Slide 66: LLL algorithm: Example (1)
18:17 Slide 67: LLL algorithm: Example (3)
18:55 Slide 68: Termination: potential function
21:04 Slide 69: Termination (1)
23:47 Slide 70: Termination (2)
25:06 Slide 71: Running time
25:38 Slide 72: Example: LLL algorithm
26:15 Slide 73: Example: randomized basis
27:11 Slide 74: Example: LLL-reduced basis
27:43 Slide 75: Example: swaps
28:24 Slide 76: Example: lengths of basis vectors
29:06 Slide 77: Example: Gram-Schmidt coefficients