# CSE206A: Lattices Algorithms and Applications (Winter 2004)

Istructor: Daniele Micciancio

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

## Announcements

• Lecture notes from the first part of the course are available.
• Most of the page below is recycled from a previous version of the course and will be updated soon. So, some of the links below might be broken, and will be fixed as the page gets updated.

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

## Prerequisites

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.

## Assignments

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:

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.

• Lecture 1 (Oct 21): Introduction, Some problems in cryptanalysis, Lattices and linear algebra. (ps)
• Lecture 2 (Oct 26): Orthogonal bases, Hermite normal form and determinant. (ps)
• Lecture 3 (Oct 28): Polynomial time HNF algorithm. (ps)
• Lecture 4 (Nov 2): Shortest vector problem (SVP), Minkowski's convex body theorem. (ps)
• Lecture 5 (Nov 4): Applications of Minkowski's theorem. Successive minima. Reduced basis for 2-dimensional lattices. (ps)
• Lecture 6 (Nov 9): Solving SVP in 2-dimensional lattices: the generalized Gauss algorithm. (ps)
• Lecture 7 (Nov 11): Approximating SVP in n-dimensional lattices: the LLL algorithm. (ps)
• Lecture 8 (Nov 16): Finding small solutions to univariate polynomial equations. (ps)
• Lecture 9 (Nov 18): Finding small solutions to multivariate linear equations. (ps)
• Lecture 10 (Nov 23): The Closest Vector Problem (CVP): algorithms and complexity. (ps)
• Problem Set (Nov 23, Due Dec 7). (ps)
• Lecture 11 (Nov 30): Private key cryptosystems based on subset-sum (ps)
• Lecture 12 (Dec 2): The dual lattice. (ps)
• Lecture 13 (Dec 7): Embedding trapdoors in the subset sum function (ps)
• Lecture 14 (Dec 9): Conclusion
• Bibliography (ps)

Daniele Micciancio
Last Midified: January 16th, 2004