The Dilithium Number-Theoretic Transform Explained

In this video, V4a: The Dilithium Number-Theoretic Transform (NTT), Alfred Menezes explores the critical role of the number-theoretic transform (NTT) in the Dilithium Signature Scheme, a lattice-based, quantum-resistant cryptographic solution standardized by NIST on August 13, 2024. This video is part of the "Kyber and Dilithium" series, which provides state-of-the-art instruction in post-quantum cryptography and lattice-based cryptographic schemes. Targeted for computer science students, software engineers, mathematicians, security engineers, and applied cryptographers, this video introduces the number-theoretic transform (NTT), a mathematical tool used for fast polynomial multiplication—a core operation in the Dilithium signature scheme. You’ll gain insights into how NTT enhances the efficiency of the Dilithium algorithm, enabling faster, more secure digital signatures that can withstand quantum attacks. Join us as we dive into the specifics of NTT within the context of lattice-based cryptography, and discover why it’s fundamental to quantum-resistant cryptographic systems. Whether you’re new to cryptography or advancing your expertise, this video is essential for understanding the computational optimizations behind Dilithium. #DilithiumNTT #QuantumResistant #PostQuantumCryptography #LatticeCryptography #NumberTheoreticTransform 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 01:15 Slide 142: Multiplication in Rq 03:07 Slide 143: NTT outline 04:21 Slide 144: NTT definition 07:12 Slide 145: NTT preliminaries 08:15 Slide 146: NTT preliminaries (2) 10:47 Slide 147: NTT computation 12:33 Slide 148: Computing a0(x) and a1(x) 14:21 Slide 149: NTT running time 15:32 Slide 150: Computing NTT^{-1} 17:32 Slide 151: NTT example (1) 18:36 Slide 152: NTT example (2) 19:28 Slide 153: Dilithium NTT 21:36 Slide 154: In-place computation of the Dilithium NTT 23:24 Slide 155: Using NTT in Dilithium key generation 25:13 Slide 156: Using NTT in Dilithium signature generation