**Istructor:** Daniele Micciancio

**Section ID:** 735465**Schedule:** TuTh 12:30pm-1:50pm in SSB 106

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

Revised lecture notes and pointers to research papers and other reading material 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 external links section below.

**Introduction**to lattices (Definitions, Gram-Schmidt, determinant, lower bound on minimum distance, Minkowski's theorems.) pdf**Dual Lattice**. Revised lecture notes on the dual lattice. pdf**Basic Algorithms**. Analysis of Gram-Schmidt orthogonalization, Hermite Normal Form computation, the dual lattice, efficient algorithms for lattice membership, equality, union, intersection, etc. pdf (Preliminary version)**The LLL Algorithm**. pdf**Enumeration Algorithms**. These notes cover many standard algorithms for exact or approximate solution of the Closest Vector Problem: the nearest plane (greedy) algorithm, enumeration (branch and bound) algorithms, and Klein's randomized rounding with a brief introduction to Fourier analysis. pdf For additional material on harmonic analysis and the smoothing parameter, see Worst-case to Average-case Reductions based on Gaussian Measure**Public Key Encryption**pdf. For more details on Fully Homomorphic Encryption, see the recent paper Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP

Coursework for students enrolled in the course will include a number of individual homework assignments, and an optional group project to be executed in groups of 2 or 3 students. We will discuss possible projects later in the course.

- Homework 1 pdf due on Tuesday Jan. 24, 2012.
- Homework 2 pdf due on Tuesday Feb. 7, 2012.
- Homework 3 pdf due on Tuesday Feb. 14, 2012.

- Complexity of Lattice problems: a cryptographic perspective: A bit out of date in terms of cryptographic applications, but still 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 older sets of lecture notes for this course on webpages from previous quarters Winter 2002, Spring 2007, Winter 2010,
- 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.