V6: LLL Improvements (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: LLL algorithm, lattice basis reduction, floating point, enumeration, sieving, BKZ, SVP challenges

Lecture playlist:    • Lattice Basis Reduction  

Course web page: https://cryptography101.ca/lattice-ba...
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