|
Table of Contents
Techniques in Cryptography and CryptanalysisInstructors for 2024 - 2025: Phong Nguyen (DR @ Inria) and Brice Minaud (CR @ Inria) Language of Instruction: English for slides and lecture notes. English or French for lectures, depending on the audience. Schedule for 2024-2025Time: Wednesdays, from 10h15 to 11h45. Location: Room 1002, in the Sophie Germain building. Lecture notes will be put every week.
The midterm exam is scheduled for Wednesday, 27 November 2024, from 10h to 12h in the usual room.
* In previous years, the second half of the course covered Zero-Knowledge Proofs, and Oblivious Algorithms. New in 2024/2025: the course will still cover Zero-Knowledge Proofs, but the section on Oblivious Algorithms will be much shortened, and replaced by a selection of topics related to the first half of the course. This shoud help bridge the two halves of the course. New material (slides or lecture notes) will be added along the way. Slides from previous years on oblivious algorithms, which are more detailed than the shortened version from this year, can be found here. Exams from previous years for Brice's half of the course: 2020 2021 2022 2023 2024. The Final Exam is scheduled for March 12 2025, from 10h15 to 11h45, in the usual room (room 1002). Overview
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). The course is split into two distinct parts. The first half of the course is devoted to 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). 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 the most popular candidate for post-quantum cryptography (three of the four standards selected by NIST in July 2022 are based on lattices), but it is also the key technique for fully-homomorphic encryption, currently implemented in software libraries. 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. 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 zero-knowledge proofs, oblivious algorithms, and searchable encryption. Zero-knowledge proofs are an 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. For the first time, we plan to have some lecture notes. Pre-RequisitesThe main requirement is being comfortable with mathematical proofs. Some knowledge of basic mathematical topics such as probability and number theory will also be assumed. For the second 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: groups, rings, vector spaces, Euclidean spaces and their topology, probability. Students interested in mathematical aspects of cryptography might also wish to attend courses 2-12-2 and 2-13-2: elliptic curves are related to lattices, and there are analogies and connections between lattices and codes. Notes
For the first part of the course on lattice-based cryptography, here are useful external notes on lattices:
Textbooks on Lattices:
Reference articles related to the course, in chronological order: 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 Lecturers
To contact us: firstname.lastname@ens.fr |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||