V4b: The Kyber Number-Theoretic Transform (NTT) (Kyber and Dilithium short 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: Kyber Number-Theoretic Transform (NTT) 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:14 Slide 158: NTT outline 02:12 Slide 159: Mathematical preliminaries 03:10 Slide 160: NTT definition 05:51 Slide 161: NTT preliminaries 08:09 Slide 162: NTT computation 09:29 Slide 163: NTT running time 10:06 Slide 164: Addition and multiplication in Qi 11:00 Slide 165: NTT example (1) 11:40 Slide 166: NTT example (2) 13:13 Slide 167: NTT example (3) 14:31 Slide 168: Kyber NTT 16:32 Slide 169: Computing the Kyber NTT 16:47 Slide 170: Using NTT in Kyber key generation 18:21 Ending Correction: 16:35 Slide 169: *whose entries are integers modulo 3329