**Istructor:** Daniele Micciancio

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

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

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