In this course, we will overview the state of the art on the computational hardness of problems on Euclidean lattices. Euclidean lattices have implications in numerous areas in computer science, communication theory and computational mathematics. We will focus in particular on cryptographic applications of the presumed computational intractability of lattice problems.

**Lecture notes **

**Outline **

- 1- Euclidean lattices: definitions and computational aspects.
- Lattices and lattice invariants.
- The shortest vector problem (SVP).
- The LLL and BKZ algorithms.

- 2- Worst-case lattice problems.
- NP-hardness of the Closest Vector Problem.
- Approx-SVP, Unique-SVP and the Bounded Distance Decoding Problem.
- Limits to inapproximability.

- 3- Average-case lattice problems.
- Gaussian distributions over diverse supports.
- The SIS problem (a.k.a. average-case Approx-SVP).
- The LWE problem (a.k.a. average-case Bounded Distance Decoding).
- Cryptographic applications: encrypting and signing.

**Evaluation**

**Prerequisites**

**Bibliography**

- Lattices in Cryptography and Cryptanalysis, Daniele Micciancio.
- Lattices in Computer Science, Oded Regev.
- Complexity of Lattice Problems, A Cryptographic Perspective, Shafi Goldwasser et Daniele Micciancio, Kluwer Academic Publishers.
- The LLL algorithm: Survey and applications. Phong Nguyen et Brigitte Vallée (Eds), Springer.