CSE206A: Lattices Algorithms and Applications (Spring 2007)

Section ID: 588802
Schedule: TuTh 12:30-1:50pm in EBU3b (CSE) 2154

Course description

Point lattices are powerful mathematical objects that have been used to efficiently solve many important problems in computer science, most notably in the areas of cryptography and combinatorial optimization. This course gives a general introduction to the theory of point lattices, and covers a selection of applications of lattices to both cryptography, cryptanalysis and other areas of computer science, mathematics, and communication theory.
Beside a wide range of applications (from cryptanalyzing low-exponent RSA functions, to efficiently solving integer programming problems with constant number of variables, and more), this course will touch several central issues in the theory of computing, like

Hardness of approximation: we will prove that various lattice problems are NP-hard to solve even approximately.
Relations between average- and worst-case complexity: we will show that certain cryptographic functions are as hard to break (on the average) as the worst-case instances of other lattice approximation problems
Randomized algorithms design: we will present the fastest currently known randomized algorithm to solve lattice problems exactly (in exponential time)
Interactive proof systems and limits of NP-hardness results: we will show that certain lattice problems are not NP-hard (under standard complexity assumptions)
List-decoding: we will show how to use lattices to decode CRT codes (a class of error correcting codes based on the Chinese remainder theorem)

Prerequisites: The main prerequisites for the course are knowledge of basic math (e.g., linear algebra, finite fields, modular arithmetic, probability, etc.) and introductory level algorithms and complexity theory (analysis of algorithms, polynomial time solvability, NP-hardness, etc.) In particular, no prior knowledge of cryptography or advanced complexity theory is assumed.

Lecture Notes

Lecture 1: Introduction to lattices and motivating applications (ps,pdf)
Lecture 2: Lattices and bases (ps,pdf)
Lecture 3: Minimum distance (ps,pdf)
Lecture 4: The LLL algorithm (ps,pdf)
Lecture 5: Cryptanalysis I (univariate polynomial equations) Lecture notes (ps,pdf) from previous offering of the course.
Lecture 6: Cryptanalysis II (multivariate linear equations) Lecture notes (ps, pdf) from previous offering of the course.
Lecture 7: SVP and CVP, search versus optimization (ps,pdf)
Lecture 8: Dual lattice and Minkowski's problem (ps,pdf)
Lecture 9: Reducing CVP to SVP. Not ready yet.(ps,pdf)
Lecture 10: Solving SVP exactly. See Oded Regev's lecture notes (pdf)
Lecture 11: The n-dimensional Fourier Transform. See Oded Regev's lecture notes (pdf)
Lecture 12: Transference Theorems. See Oded Regev's lecture notes (pdf)
Lecture 13: Lattice based cryptography. See Oded Regev's lecture notes (pdf)

Coursework

Coursework for students enrolled in the course will include 4 homework assignments, an optional term project (as an alternative to the last two homework assignments), and scribing notes for one lecture.

Homework 1: due April 19 in class (ps,pdf)
Homework 2: due May 8 in class (ps,pdf)
Project

External Links

If you know of any link that you would like to be included, send me email.

Complexity of Lattice problems: a cryptographic perspective: A book on the computational complexity of lattices, and their use in the construction of provably secure cryptographic functions.
Oded Regev's course webpage at Tel Aviv university.
Cynthia Dwork's Lecture Notes on Lattices and their Applications to Cryptography.
David Molnar's page on Parallel Lattice Basis Reduction.
Damien Stehle' links on Algorithmics and Lattices
Helger Lipmaa's links on Lattice Cryptography and Reduction
NTRU webpage. A very efficient commercial cryptosystem based on lattices.
Victor Shoup's Number Theory Library (NTL). A C++ library for lattice basis reduction that has been widely used in cryptanalysis.

Daniele Micciancio
Last Modified: April 5th, 2007