CSE206A: Lattices Algorithms and Applications (Winter 2004)

Istructor: Daniele Micciancio

Schedule: MWF 4:00-4:50pm in WLH 2110


Course Description

Point lattices are powerful mathematical objects that have been used to efficiently solve many important problems in computer science, including integer programming with constant number of variables, polynomial factorization over the rationals, Diophantine approximation, etc. Lattices have also been extensively used in cryptology. Quite peculiarly, lattices have been used both in cryptanalysis (using lattice approximation algorithms to break cryptosystems) and in cryptography (using computationally hard lattice problems to design robust cryptographic functions).

This course gives a general introduction to the theory of lattices, and covers the main applications of lattices to cryptography, cryptanalysis and various other selected areas. The course is primarily focused on the algorithmic aspects of the theory: which lattice problem can be solved in polynomial time, and which problems seems to be intractable. Specific topics include lattice approximations algorithms (eg. LLL basis reduction), computational complexity of lattice problems (including NP-hardness results and Ajtai's worst-case / average-case connection), and various applications of lattices both from cryptography and other areas of computer science.

If you want to get a flavour of some of the topics covered in this course, read the notes for lecture one below. The examples in these notes are all from cryptanalysis (how to break cryptosystems using lattices) which will be the source of many applications in this course.


Knowledge of computer algorithms, probability theory, linear algebra and basic complexity theory (P, NP, coNP, NP-hardness) is required. Some basic knowledge of cryptography (RSA function, probabilistic encryption, etc.) is recommended, but not strictly necessary. If you are interested in this course, but you are not sure if you have the necessary prerequisites, consult the instructor.


Students will receive a grade based on a homework assignment and either a presentation or a project. The homework assignment is due on Monday February 10.

Presentations will based on 2 or 3 closely related papers. Students are expected to submit a short report summarizing the contributions of the papers, and give a 50 minutes presentation to the class. See below for possible topics and paper links.

Projects involve the experimentation with lattice reduction algorithms to solve some cryptanalysis problem. If you are interested in performing a project, talk to Daniele to decide on a possible topic

Here are some ideas for possible presentation topics:

You can find many other links to papers related to lattice algorithms and applications at the following sites.

Projects tipically involve an experimental component, where you use lattice reduction algorithms to attack a cryptanalitic problem. Lattices are routinely used to attack various kind of cryptographic functions. To get an idea of what can be done using lattices, read some of the papers below. If you want to work on a project, let me know.

Lattice attacks to various kind of cryptographic functions are routinely discovered. The following are two survey papers describing many applications of lattices:

Below is a list of papers describing lattice attacks that appeared in conferences like Crypto, Eurocrypt, Asiacrypt, PKC, SAC, etc. The papers are listed in reverse chronological order, so some of the papers at the bottom of the list contain among the simplest lattice based attacks..

Here are a few more papers about lattice algorithms of applications:

Some papers related to the projects discussed in class:

Additional links to random papers related to lattices:


This is a very preliminary list of related links. I will keep adding links with time. If you know of any relevant link that is not already on the list, please send me email.

Lecture Notes (Fall 1999)

Below are the lecture notes of a prelinimary version of this course, taught as CSE291 in Fall 1999. Most of the topics in the syllabus are covered by the lecture notes.

Valid XHTML 1.0! Daniele Micciancio
Last Midified: January 16th, 2004