Mathematical Prerequisites for Kyber and Dilithium Course

Video lectures for Alfred Menezes's introductory course on Kyber-KEM (ML-KEM) and the Dilithium signature scheme (ML-DSA). These lattice-based cryptographic schemes were standardized by NIST on August 13, 2024. Topics covered: Modular arithmetic, polynomial rings, modules of polynomials, lattice problems, MLWE, D-MLWE Lecture playlist: https://www.youtube.com/playlist?list=PLA1qgQLL41SSUOHlq8ADraKKzv47v2yrF Course web page: https://cryptography101.ca/kyber-dilithium The slides are available on the course web page. "Post-quantum cryptography" chapter from "Textbook of Applied Cryptography": https://drive.google.com/file/d/1D55HDa7imlBQXXW_CjbQftMuHZVoqNDa/view Other cryptography courses: https://cryptography101.ca Slides 00:00 Introduction 00:03 Slide 22: Lecture outline 00:31 Slide 23: Modular arithmetic 02:11 Slide 24: Polynomial rings 03:16 Slide 25: The polynomial ring Rq = Zq[x]/(x^n+1) 04:21 Slide 26: Example: the polynomial ring Rq = Z41[x]/(x^4+1) 05:49 Slide 27: Representing polynomials as vectors 06:50 Slide 28: The module Rq^k 07:38 Slide 29: Example: Rq^k 08:38 Slide 30: Size 09:03 Slide 31: Symmetric mod: q odd 11:01 Slide 32: Symmetric mod: q even 12:38 Slide 33: Size of polynomials 14:24 Slide 34: "Small" polynomials 15:44 Slide 35: Product of small polynomials 16:55 Slide 36: Product of small polynomials (2) 19:57 Slide 37: Lattice problems: MLWE, D-MLWE and MSIS 20:57 Slide 38: Lattice problem: MLWE 22:48 Slide 39: Example: MLWE 24:09 Slide 40: Lattice problem: D-MLWE 25:28 Slide 41: Why lattices? Corrections: 08:11 Slide 29: a*b^T should be a^T*b 19:44 Slide 36: a*b^T should be a^T*b