V4: The LLL Algorithm (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. Lecture notes: "A gentle introduction to lattice-based cryptography" https://drive.google.com/file/d/1-G9qYuQhuHr0W4-YglVGub1PxdLyFHC6/view?usp=drive_link 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 Corrections 09:32 Slide 58: Third last line: Delete "\leq min_i {2^{i-1} ||b_i^*||^2} \leq 2^{n-1} \lambda_1(L)^"