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