Mathematics of Lattices
summary
Straightforward introduction to lattice math with no new results: precise definitions (determinant, successive minima, covering radius), basic theorems (Minkowski bounds, product transference: lambda_i(L)·lambda_{n−i+1}(L) = Θ(1..n)), and algorithmic connections. Shows Gram‑Schmidt orthogonalization and size reduction as algorithmic tools, defines the smoothing parameter (Gaussian width ~ √n·λ_n up to logs), and explains how Q-ary lattices* encode SIS/LWE and why BDD reduces to SIVP via the dual lattice (unique-decoding radius ≈ λ1/(2n)). Good for establishing foundations before later cryptography talks.
AI-written summary · about
chapters (18)
- 0:00Start
- 1:41Outline
- 6:48Lattice Cryptography: a Timeline
- 8:19Lattices: Definition
- 11:17Lattices and Bases
- 14:32Density estimates
- 24:03Distance Function and Covering Radius
- 25:47Smoothing a lattice
- 31:15Minkowski's convex body theorem
- 41:25Shortest Vector Problem
- 43:07Closest Vector Problem
- 46:22Shortest Independent Vectors Problem
- 50:32Coding theory
- 51:12Special Versions of CVP
- 53:50Relations among lattice problems
- 55:19ADD reduces to SIVP
- 57:20Geometry of Lattices
- 57:35Size Reduction
