V3: Gram-Schmidt Orthogonalization (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: Orthogonal basis, projections, Gram-Schmidt orthogonalization, lattices 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 39: Orthogonal bases 01:36 Slide 40: Linear algebra background 02:57 Slide 41: Projections 03:47 Slide 42: Exercises 04:38 Slide 43: Application of orthogonal bases 06:19 Slide 44: Orthogonal bases exist (1) 07:16 Slide 45: Orthogonal bases exist (2) 10:00 Slide 46: Orthogonal bases exist (3) 11:29 Slide 47: Gram-Schmidt orthogonalization 13:18 Slide 48: Gram-Schmidt and lattices 14:39 Slide 49: A lower bound for the first successive minimum 17:23 Slide 50: Volume of a lattice (1) 18:36 Slide 51: Volume of a lattice (2)