Date |
Class Topic |
Oct 22 |
Basic definitions, Gram-Schmidt orthogonalization, successive minima, lower bound on succ. minima |
Oct 29 |
Minkowski's convex body theorem, Minkowski's first and second theorem, basic computational problems |
Nov 5 |
LLL algorithm, Babai's nearest plane algorithm |
Nov 12 |
Small solutions to low degree polynomials; Integer programming in constant dimension |
Nov 19 |
Basic reductions; Goldreich-Goldwasser proof of GapCVP in coAM using Gaussians |
Nov 26 |
Dual lattices |
Dec 3 |
Dual lattices |
Dec 10 |
Fourier analysis |
Dec 17 |
Banaszczyk's transference theorem; the smoothing parameter |
Dec 24 |
CVP with preprocessing and the [AR] GapCVP in coNP proof; introduction to lattice-based cryptography |
Dec 31 |
Hardness of the SIS problem; construction of CRHF; an ID scheme based on SIS |
Jan 7 |
The GPV Gaussian sampling algorithm and their signature scheme |
Jan 14 |
The LWE problem and a public key cryptosystem; discussion on Homework 3 and 4 |
Jan 21 |
Ideal lattices and their cryptographic applications |