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: 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