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