| 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 |