CSE206A: Lattices Algorithms and Applications (Winter 2010)

Istructor: Daniele Micciancio

Section ID: 672185
Schedule: TuTh 2:00pm-3:20pm in CENTER 201

Course description

• 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

• 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

• Complexity of Lattice problems: a cryptographic perspective: A bit out of date in terms of cryptographic applications, but stil a good introduction, and basically the only book on the topic. For more recent accounts of lattice based cryptography, see survey chapters in The LLL Algorithm and Post Quantum Cryptography.
• You can find an older sets of lecture notes for this course on the Winter 2002 and Spring 2007 web pages.
• Oded Regev's course webpage at Tel Aviv university.
• Victor Shoup's Number Theory Library (NTL). A C++ library for lattice basis reduction that has been widely used in cryptanalysis.

Schedule

Daniele Micciancio
Last Modified: April 5th, 2007