Course info

Prerequisites

The main prerequite is mathematical maturity. However, we will assume the students are comfortable with / can quickly pick up the basic concepts in:

1. Algorithms: big O-notation, complexity, ... e.g. at least chapter 1 & 4 of http://is.ptithcm.edu.vn/~tdhuy/Programming/Introduction.to.Algorithms.pdf

2. Linear algebra: vector & dual vector spaces, determinants, gram schmidt orthogonalization, etc.

3. Probability & Probabilistic algorithms: Gaussians, Chernoff bounds, Monte Carlo algorithms, ... e.g. at least chapters 1-4 http://www.mscs.dal.ca/~janssen/5340/ToRead/mitzenmacher-upfal.pdf.

4. Basic number theory: modular arithmetic, polynomials, algebraic extensions, etc.

Aim of the course

The geometry and structure of Euclidean lattices has been studied for centuries to understand the geometry of periodic structures such as dense packings of spheres. Much more recently, lattices have been central in designing cryptographic schemes that are believed much more secure than number theoretic schemes such as RSA, which are compromised if efficient quantum computers are ever built.

The aim of this course is to provide a solid understanding of the geometry of lattices, algorithms for solving central computational problems on lattices, and their applications to lattice based cryptography. Sample topics include: Minkowski's First & Second Theorems, transference theorems in the geometry of numbers, algorithms for the Shortest (SVP) & Closest Vector Problems (CVP), Learning with Errors (LWE), Regev's LWE based public key cryptography scheme, Lattice based signatures, NTRU, Worst-case to average case reductions, and Discrete Gaussian sampling.

Lecture Notes / Literature

Lecturers

D. Dadush (CWI) & L. Ducas (CWI)