School of Computer Science
Tel Aviv University

Lattices in Computer Science


Fall 2009


Lecture notes (from the 2004 class)

Homework assignments

Some Information


Thursday 15:00-18:00

Oded Regev

Complexity of Lattice Problems, D. Micciancio and S. Goldwasser,
Attendance, homework assignments (will require relatively lots of effort), and possibly a final exam
Mathematical maturity is a must for this class.
Useful links
On the Complexity of Lattice Problems with Polynomial Approximation Factors
Lattice-based Cryptography (and a PowerPoint presentation)


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