Understanding the Learning With Errors (LWE) Problem in Lattice Cryptography 🧩

Video lectures for Alfred Menezes's introductory course on the mathematics of lattice-based cryptography. Kyber (ML-KEM) and Dilithium (ML-DSA) are lattice-based cryptosystems that are resistant to attacks by quantum computers. Hardness of the Module-SIS and Module-LWE problems is the basis for the security of Kyber and Dilithium . These lectures describe the connection between lattices and the Module-SIS and Module-LWE problems, thus explaining why Kyber and Dilithium are considered to be lattice-based cryptosystems.

Topics covered: Learning With Errors problem, LWE, Decisional LWE, short-secret LWE, Lindner -Peikert public-key encryption scheme

Lecture playlist:
https://www.youtube.com/playlist?list=PLA1qgQLL41STNFDvPJRqrHtuz0PIEJ4a8

Course web page: https://cryptography101.ca/lattice-based-cryptography/
The slides are available on the course web page.

Other cryptography courses: https://cryptography101.ca

Slides
00:00 Introduction
00:35 Slide 19: LWE definition
02:52 Slide 20: LWE example
04:06 Slide 21: LWE parameter B
05:45 Slide 22: LWE parameters m and n
07:29 Slide 23: Decisional LWE (DLWE)
08:33 Slide 24: DLWE and LWE are equivalent (1)
09:57 Slide 25: DLWE and LWE are equivalent (2)
12:06 Slide 26: Short-secret LWE (ss-LWE)
12:48 Slide 27: ss-LWE and LWE are equivalen (1)
13:55 Slide 28: ss-LWE and LWE are equivalen (2)
16:07 Slide 29: PKE: key generation
17:30 Slide 30: PKE: encryption and decryption
19:40 Slide 31: Toy example: PKE (1)
20:20 Slide 32: Toy example: PKE (2)
21:25 Slide 33: PKE: decryption works
22:58 Slide 34: PKE: security