CSE206A: Lattices Algorithms and Applications (Winter 2010)
Istructor: Daniele Micciancio
Section ID: 672185
Schedule: TuTh 2:00pm-3:20pm in CENTER 201
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, their algorithms, and a selection of applications of lattices
to both cryptography and other areas of computer science,
mathematics, and communication theory.
Beside covering the best currently known algorithms to solve the
most important lattice problems (both in their exact and approximate
versions), we will touch several related areas:
- Combinatorial Optimization:
The asymptotically fastest Integer Programming
algorithm known to date is based on lattices.
- Cryptography:
Lattices have been used to design a wide range of cryptographic
primitives, including public key encryption, digital signatures,
encryption resistant to key leakage attacks,
identity based encryption,
and fully homomorphic encryption.
- Complexity: Cryptographic applications of lattices have
been in large part stimulated by a connection between the
average-case
and worst-case
complexity of lattice problems that is very interesting
on its own.
- Harmonic Analysis: n-dimensional
Fourier analysis
is one of the most powerful tools currently used in the study of lattices,
both in algorithms, complexity and mathematics.
- Algebraic Number Theory:
Lattices have been used to algorithmically solve many problems in
algebraic number theory, and algebraic number theory
is an imporant tool
in the design of several lattices with special properties
that turn out to be very useful in applications.
Prerequisites: The main
prerequisites for the course are knowledge of basic math (e.g., linear
algebra, finite fields, modular arithmetic, probability, some calculus, etc.)
and introductory level algorithms and complexity theory (analysis of
algorithms, polynomial time solvability, NP-hardness, etc.) In
particular, no prior knowledge of cryptography, advanced complexity
theory, Fourier analysis, or algebraic number theory is assumed.
(Though in this course you will learn a little bit of all of this.)
Lecture Notes
I am planning to cover a different selection of
application from previous versions of this course.
Revised lecture notes will be posted here as we cover the material in class.
As a reference, see pointers to previous lecture notes and other courses
in the externatl links section.
- Lecture Notes 1: Introduction to lattices (Definitions, Gram-Schmidt, determinant,
lower bound on minimum distance, Minkowski's theorems.)
pdf
- Lecture Notes 2: Basic Algorithms (Bounds on Gram-Schmidt, Hermite Normal Form, dual lattice.)
pdf
- Lecture Notes 3: The LLL
algorithm (Approximate SVP and CVP algorithms)
pdf
- Integer Programming: see lecture notes from
Oded Regev's course.
- Cryptanalysis. See lecture notes from 2007.
- Improved approximation algorithms for SVP.
You can refer directly to the original paper
Finding Short Lattice Vectors Within Mordell's Inequality by Gama and Nguyen (STOC 2008).
- Decoding special lattices. Faster algorithms to decode the root lattice
and its generalizations can be found in
Linear-time nearest point algorithms for Coxeter lattices (McKilliam, Smith and Clarkson, to appear in IEEE Trans. on IT).
For the Barnes-Wall lattice, see
Efficient bounded distance decoders for Barnes-Wall lattices (Micciancio and Nicolosi, ISIT 2008).
- Exact SVP algorithms. See Faster exponential time algorithms for the shortest vector problem (Micciancio and Voungaris, SODA 2010)
- Exact CVP algorithms. See A Deterministic Single Exponential Time Algorithm for Most Lattice Problems based on Voronoi Cell Computations (Micciancio and Voulgaris, STOC 2010)
- Hash functions. The analysis of hash functions presented in class is
essentially the one from Worst-case to average-case reductions based on Gaussian measure (Micciancio and Regev),
with some simplificatations from
Trapdoors for Hard Lattices and New Cryptographic Constructions (Gentry, Peikert, Vaikuntanathan) Section 9.
The informal introduction to worst/average case connection follows the book chapter
Cryptographic functions from worst-case complexity assumptions.
For a brief introduction to Fourier analysis as needed in the proofs see
Regev's lecture notes.
Coursework
Coursework for students enrolled in the course will include 4
homework assignments, and an optional term project, and
scribing one set of lecture notes if needed.
- Homework 2: due Feb 16 in class,
hw2.pdf.
- Homework 1: due Jan 21 in class,
hw1.pdf. If you need hints about the last problem, check out
the first homework assignment from
Spring 2007, where
essentially the same problem is broken into parts giving out a solution guideline.
External Links
Schedule
Date |
Class Topic |
Jan 5 |
Basic definitions, Gram-Schmidt orthogonalization, minimum distance |
Jan 7 |
Succesive minima, Minkowski's convex body theorem |
Jan 12 |
Basic Algorithms:
Running time of Gram-Schmidt, Hermite Normal Form, Dual lattice |
Jan 14 |
Lattice approximation algorithms, LLL algorithm,
nearest plane algorithm |
Jan 19 |
Cancelled |
Jan 21 |
Running time of LLL, Approximating CVP |
Jan 26 |
Integer Programming |
Jan 28 |
Cryptanalysis |
Feb 2 |
Approximating SVP within subexponential factors. |
Feb 4 |
Decoding algorithms for special lattices |
Feb 9 |
Exact algorithms for SVP |
Feb 11 |
Exact algorithms for CVP |
Feb 16 |
|
Feb 18 |
|
Feb 23 |
|
Feb 25 |
|
Mar 2 |
|
Mar 4 |
|
Mar 9 |
|
Mar 11 |
|
Daniele Micciancio
Last Modified: April 5th, 2007