# CSE206A: Lattices Algorithms and Applications (Spring 2007)

Istructor: Daniele Micciancio

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