Lecture 3. Learning With Errors (LWE) Problem (The Mathematics of Lattice-Based 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