Cryptanalysis: Lattice Basis Reduction Techniques

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 reducion, side-channel attacks, ECDSA signature generation, ECDSA attacks 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:39 Slide 80: Cryptanalytic applications of LLL 01:49 Slide 81: General methodology 02:49 Slide 82: Side-channel attacks on ECDSA 03:58 Slide 83: ECDSA: domain parameters and key generation 05:18 Slide 84: ECDSA: signature generation 06:28 Slide 85: Leakage: two signatures (1) 08:48 Slide 86: Leakage: two signatures (2) 10:08 Slide 87: Leakage: two signatures (3) 12:13 Slide 88: Leakage: many signatures (1) 14:22 Slide 89: Leakage: many signatures (2) 15:36 Slide 90: Leakage: many signatures (3) 17:19 Slide 91: Leakage: many signatures (4) 18:39 Slide 92: Example: ECDSA attacks (1) 20:00 Slide 93: Example: ECDSA attacks (2) 20:43 Slide 94: Other LLL applications