CSE207C: Lattices in Cryptography and Cryptanalysis (Winter 2002)

For the most recent offering of this course (and updated webpage) see the CSE206A web page.

Istructor: Daniele Micciancio

Schedule: Tue/Thu 5:30-6:50pm in HSS 2321


Course Description

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 will give a general introduction to the theory of (point) lattices, and cover the main applications of lattices to both cryptography and cryptanalysis. The course will be 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. In presenting the solution to various cryptographic problems, we will cover the essentials of lattice approximations algorithms (eg. LLL basis reduction), present the current state of knowledge on the computational complexity of lattice problems (including NP-hardness results and Ajtai's worst-case / average-case connection), and study practical cryptosystems based on the hardness of lattice problem (e.g., the NTRU cryptosystem).

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 is the topic covered in the first half of the course. In the second half of the course, we'll get more into complexity theory and the design of provably secure cryptographic functions based on lattices.


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.


Below are references to papers related to material covered in class, and covered in the lecture notes below. Some of them pertain extentions or refinements of results presented in class, and are given as hints for further study.


Yes! The first homework is finally available. Have fun! For the programming part you can you the implementation of LLL from Victor Shoup's Number Theory Library (NTL). The library is a pretty easy install. If you have any problem getting the library to work, let me know.


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: December 10th, 2001