Instructors for 2021 - 2022: Phong Nguyen (DR @ Inria) and Brice Minaud (CR @ Inria)

Language of Instruction: English for slides. English or French for lectures, depending on the audience.

Time: Wednesdays, from 14h15 to 15h45

Location: Room 1004, in the Sophie Germain building.

For now, the slides given below are from last year (2020-2021). They should give a good idea of the material that will be covered. Of course, there may be minor changes.

List of 2020-2021 slides:

1. Overview
2. Introduction to Lattices (End of Introduction to Lattices)
3. Hard Lattice Problems: SVP, CVP, SIS, LWE (End of Hard Lattice Problems)
4. Encryption from Lattices
5. Signatures from Lattices
6. Hermite's inequality and the LLL Algorithm
7. Applications of LLL: Breaking RSA including Coppersmith's theorem
8. Blockwise reduction Security Estimates, Sieving and Enumeration

The Midterm Exam is tentatively scheduled for Wednesday, 24 November 2021, from 14h15 to 15h45 in the usual room.

The Final Exam is scheduled for Wednesday, 9 March 2022, from 14h15 to 15h45 in the usual room.

The main objective of the course is to introduce students to a few important tools and techniques relevant to modern cryptography. These techniques will 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).

During the first half of the course, the main focus will be on lattice-based cryptography. In the past 25 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 currently the most popular candidate for post-quantum cryptography, but it is also the key technique for homomorphic encryption. Its origins go back to the Merkle-Hellman knapsack cryptosystem from 1978, but it officially started in 1996 with Ajtai's worst-case to average-case reduction and the invention of the NTRU cryptosystem.

The second half of the course will cover zero-knowledge proofs, oblivious algorithms, and searchable encryption. Zero-knowledge proofs are another important technique in modern cryptography. They are both of theoretical interest, and deployed in a variety of applications, ranging from identification protocols to electronic voting and cryptocurrencies. We will then examine several aspects of computing on encrypted data, starting with oblivious algorithms. Oblivious algorithms are algorithms whose memory accesses are independent of their input, and serve as a building block in a variety of cryptographic applications. As a special case of practical interest, we will discuss constructions of Searchable Encryption provable in relevant security models, as well as attacks showcasing the limitations of those models.

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

The main requirement is being comfortable with mathematical proofs. Some knowledge of basic mathematical topics such probability, number theory, and linear algebra will also be assumed.

For the first part of the course on lattice-based cryptography, we plan to adapt to the audience. However, it will be helpful if students are familiar with: group theory, linear algebra, Euclidean spaces, probability.

For the first part of the course on lattice-based cryptography, 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 premiers chapitres de : “Les réseaux parfaits des espaces euclidiens”, Jacques Martinet.
-  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 applications
-  2005, Regev: On Lattices, Learning with Errors, Random Linear Codes, and Cryptography (STOC 2005) The LWE article
-  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
-  2018, Aggarwal and Stephens-Davidowitz: Just Take the Average! An Embarrassingly Simple 2n-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