V6: Mastering Lattice Basis Reduction: The Power of the 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: LLL algorithm, lattice basis reduction, floating point, enumeration, sieving, BKZ, SVP challenges

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:35 Slide 97: LLL recap
03:06 Slide 98: The LLL algorithm
04:03 Slide 99: LLL refinement: the parameter \delta
05:50 Slide 100: LLL refinement: Gram-Schmidt computations
06:43 Slide 101: LLL refinement: deep insertion
08:10 Slide 102: LLL refinement: floating point
10:10 Slide 103: BKZ
10:43 Slide 104: Solving SVP exactly: enumeration and sieving
11:50 Slide 105: SVP challenges
13:07 Slide 106: LLL swap operation
15:38 Slide 107: BKZ block operation
19:20 Slide 108: BKZ algorithm
21:13 Slide 109: BKZ analysis
24:18 Slide 110: BKZ in practice
25:23 Slide 111: Lattice challenges
26:16 Slide 112: Readings