Computer Science
Tel-Aviv University

Lattices in Computer Science

Fall 2004



Lecture Notes (please leave comments here)

Administrative Basics



Monday 12:00-15:00


Oded Regev | Schreiber 220 | 5379 | Office hours: Monday 15:00-16:00 or by appointment

Complexity of Lattice Problems, D. Micciancio and S. Goldwasser,
An Algorithmic Theory of Numbers, Graphs, and Convexity, L. Lovasz
Lecture Notes Lattices in Cryptography and Cryptanalysis, a course given by Daniele Micciancio
Lattices and Their Application to Cryptography, a course given by Cynthia Dwork
Algebra and Computation, a course given by Madhu Sudan.
Other Links
Complexity of SVP - A reader's digest, by R. Kumar and D. Sivakumar, nicely explains some of the topics covered in this class
CaLC 2001, a conference on lattices, some papers can be found online
Finding Small Solutions to Small Degree Polynomials, a paper by Coppersmith
Twenty years of attacks on the RSA cryptosystem, a survey by Dan Boneh
Lattice Basis Reduction and Integer Programming, by Karen Aardal, nicely explains fixed-dimension integer programming using LLL basis reduction



Class Topic                                      

Oct 18 Cancelled
Oct 25 Basic definitions, Gram-Schmidt orthogonalization, successive minima, lower bound on succ. minima, Minkowski's convex body theorem
Nov 1 Minkowski's first and second theorem, basic computational problems
Nov 8 LLL algorithm, Babai's nearest plane algorithm
Nov 15 Small solutions to small degree polynomials
Nov 17 Integer programming in constant dimension, basic reductions
Nov 22 Goldreich-Goldwasser proof of GapCVP in coAM
Nov 29 Ajtai-Kumar-Sivakumar SVP algorithm
Dec 6 Dual lattices
Dec 13 Fourier analysis
Dec 20 Cancelled
Dec 27 Transference theorems
Dec 31 Worst-case to average-case reduction
Jan 3 Worst-case to average-case reduction
Jan 10 CVP with preprocessing
Jan 17 Cancelled