Time: Wednesdays, from 10:15 to 11:45.

Location: Room 1002, in the Sophie Germain building.

Lecture notes are available. Some contents will be changed.

The midterm exam is tentatively scheduled for …, from 10h to 12h in the usual room.

A large chunk of the second half of the course will be new in 2025-2026. This is partly because the course used to focus on zero-knowledge proofs, but this is now covered in more depth in the new course FIP. Instead, the course will refocus on lattices. This also helps bring the two halves of the courses closer together. There will still be a short introdution to zero-knowledge proofs, just enough to be able to present some lattice-based proofs and their applications, while keeping the overlap with FIP to a minimum (less than one lecture).

Because this material is new, the exact contents may change somewhat.

Exams from previous years for Brice's half of the course: 2020 2021 2022 2023 2024.

The Final Exam is tentatively scheduled for Wednesday, March 11th, 2026, from 10:15 to 11:45, in the usual room. (This is subject to change, to avoid conflicts with exams of other courses.)

(This is a significant evolution from past years.)

The main objective of the course is to introduce students to lattice-based cryptography. The contents belong both to the constructive side of cryptography (building cryptographic schemes whose security is mathematically proven based on hardness assumptions), and the cryptanalytic side (how to attack and evaluate the security of these schemes).

In the past 30 years, lattice-based cryptography has emerged as the most powerful alternative to classical public-key cryptography based on factoring (RSA, Rabin) and discrete logarithm (Diffie-Hellman, El Gamal, DSA, ECDSA). It is the most popular candidate for post-quantum cryptography (three of the four standards selected by NIST in July 2022 are based on lattices: two of them are now available in the OpenSSL library), but it is also the key technique for fully-homomorphic encryption, currently implemented in various software libraries. Its origins go back to the Merkle-Hellman knapsack cryptosystem from 1978, but it officially started in 1996 with two completely different result: a complexity result (Ajtai's worst-case to average-case reduction) and a bold proposal (the NTRU cryptosystem).

• The first half of the course is devoted to core results of lattice-based cryptography and related topics: it will present fundamental lattice results related to algorithms (LLL and Babai's algorithms), complexity (worst-case to average-case reductions), public-key cryptography (encryption and signature) and cryptanalysis (Coppersmith's theorem and the ROCA attack). We will also explain how lattices are used in cryptanalysis, by presenting the famous real-world ROCA attack: how to factor efficiently an RSA modulus N=pq when p and q are powers of 65537 modulo many small prime numbers.

• The second half of the course will cover Fully Homomorphic Encryption (FHE), and provaby secure lattice-based signatures. FHE is a very active research topic, both in academia and in industry (following very large investments over the past few years). It offers the ability to compute over encrypted data, for example to train a neural network on private data without the need for the trainer to learn the actual data. We will also cover Dilithium and Falcon, two leading post-quantum signature schemes, selected by NIST for large-scale deployment. They are each a representative of the two main approaches for building cryptographic signatures (Hash-and-Sign, and zero-knowledge proofs via Fiat-Shamir). This makes them useful as a way to introduce and explain important modern cryptographic techniques.

At the end of the course, students should have the necessary tools to conduct research in academic-level lattice-based cryptography.

The main requirement is being comfortable with mathematical proofs. Some knowledge of basic mathematical topics such as probability and number theory will also be assumed. It will be helpful if students are familiar with groups, rings, and linear algebra.

Students interested in mathematical aspects of cryptography might also wish to attend CRYPTALG and CODES: elliptic curves are related to lattices, and there are analogies and connections between lattices and codes. FIP will present another cornerstone of modern cryptography, zero-knowledge proofs, which will make an appearance in the second half of this course. The course is also (more tangentially) related to SECURE, which will cover security proofs in much more detail, with a view towards tool-assisted formal methods. Lattices have important algorithmic applications outside cryptography; as such, they also appear in COMPALG.

Here are useful external notes on lattices:
- Lattices and Complexity: Regev's "Lattices in Computer Science" at NYU
- Lattices and Cryptography: Vaikuntanathan's "Learning with Errors and Post-Quantum Cryptography" at MIT
- My 2008 lecture notes on public-key cryptanalysis
- My 2010 survey on lattice algorithms
- For an advanced mathematical point of view, see Venkatesh's lecture notes and le séminaire Bourbaki de Bost

Textbooks on Lattices:
- Siegel's Lectures on the Geometry of Numbers  
- Les deux premiers chapitres de : “Les réseaux parfaits des espaces euclidiens”, Jacques Martinet. (also available in English)
-  Micciancio-Goldwasser's Complexity of Lattice Problems
- Cassels's An Introduction to the Geometry of Numbers.

Reference articles related to the course, in chronological order:
- 1982, Lenstra, Lenstra and Lovasz: Factoring polynomials with rational coefficients The famous 1982 article introducing the LLL algorithm as a subroutine for factoring rational polynomials.
-  1996. Ajtai: Generating Hard Instances of Lattice Problems (STOC 1996) The first worst-case to average-case reduction for lattice problems
-  1996, Coppersmith: Small Solutions to Polynomial Equations, and Low Exponent RSA Vulnerabilities (Journal version of EUROCRYPT 1996 articles) Lattice Attacks on RSA
-  1997, Ajtai and Dwork: A Public-Key Cryptosystem with Worst-Case/Average-Case Equivalence (STOC 1997) The ancestor of LWE
-  1999, Ajtai: Generating Hard Instances of the Short Basis Problem (ICALP 1999) Trapdoors for SIS Lattices
-  2004, Micciancio and Regev: Worst-case to Average-case Reductions based on Gaussian Measures∗ (FOCS 2004) Using the discrete Gaussian distribution for worst-case to average-case reductions
-  2005, Regev: On Lattices, Learning with Errors, Random Linear Codes, and Cryptography (STOC 2005) The LWE article which earned Regev a Gödel prize
-  2006, Nguyen and Regev: Learning a Parallelepiped: Cryptanalysis of GGH and NTRU Signatures (Journal version of EUROCRYPT 2006)
-  2008, Gentry, Peikert and Vaikuntanathan: How to Use a Short Basis: Trapdoors for Hard Lattices and New Cryptographic Constructions (STOC 2008) The GPV08 article on Gaussian sampling and applications to digital signatures and identity-based encryption
-  2009, Gentry: Fully Homomorphic Encryption Using Ideal Lattices (STOC 2009)
-  2010, Micciancio and Voulgaris: A Deterministic Single Exponential Time Algorithm for Most Lattice Problems based on Voronoi Cell Computations (STOC 2010) Solving Hard Lattice Problems with the Voronoi Cell
-  2012, Micciancio and Peikert: Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller (EUROCRYPT 2012) Simpler Provable Trapdoors for SIS and LWE
-  2015, Aggarwal, Dadush, Regev, Stephens-Davidowitz: Solving the Shortest Vector Problem in 2^n Time via Discrete Gaussian Sampling (STOC 2015) Gaussian sampling from Mordell's algorithm
-  2016, Micciancio and Walter: Practical, Predictable Lattice Basis Reduction (EUROCRYPT 2016) The DBKZ Reduction Algorithm
-  2017, Nemec et al: The Return of Coppersmith’s A‚ack: Practical Factorization of Widely Used RSA Moduli (ACM CCS 2017) Factoring Real-World RSA Moduli using LLL
-  2018, Aggarwal and Stephens-Davidowitz: Just Take the Average! An Embarrassingly Simple 2^n-Time Algorithm for SVP (and CVP) (SOSA 2018)A simpler variant of ADRS

Notes below are from previous years, and no longer directly relevant to the course. They are still provided here for the benefit of curious students.

Notes 1: http://www.di.ens.fr/~mabdalla/coursedocs/provablesecurity.pdf

Notes 2: Reference for the Goldreich-Levin Theorem: http://www-cse.ucsd.edu/users/mihir/papers/gl.pdf

Notes 3: References for the Naor-Reingold PRF: Original paper, Game-based proof (see Appendix A)

Notes 4: Reference for the CHK transform: https://eprint.iacr.org/2003/182.pdf (see Sections 1—3)

Notes 5: Reference for the BBG scheme: https://eprint.iacr.org/2005/015.pdf (see Pages 5—8)

Notes 6: Lecture Notes on the Complexity of Some Problems in Number Theory: https://people.csail.mit.edu/vinodv/6892-Fall2013/Angluin.pdf

Slides on identity-based encryption: http://www.di.ens.fr/~mabdalla/coursedocs/IBE.pdf

Slides on hierarchical identity-based encryption: http://www.di.ens.fr/~mabdalla/coursedocs/HIBE.pdf

Slides on identity-based encryption with wildcards: http://www.di.ens.fr/~mabdalla/coursedocs/WIBE.pdf

To contact us: firstname.lastname@ens.fr