Parisian Master of Research in Computer Science
Master Parisien de Recherche en Informatique (MPRI)


This shows you the differences between two versions of the page.

Link to this comparison view

cours:c-2-12-1 [2020/01/22 00:49]
abdalla [Preliminary schedule for 2019-2020]
cours:c-2-12-1 [2020/09/15 15:50] (current)
phongnguyen [Pre-Requisites]
Line 1: Line 1:
 ==== __Techniques in Cryptography and Cryptanalysis__ ==== ==== __Techniques in Cryptography and Cryptanalysis__ ====
-Instructors for 2019 - 2020: **Michel Abdalla** (DR @ CNRS) and **Brice Minaud** (CR @ INRIA)+Instructors for 2020 - 2021: **Phong Nguyen** (DR @ Inria) and **Brice Minaud** (CR @ Inria)
-Language of Instruction: **English**+Language of Instruction: **English** for slides. **English** or **French** for lectures, depending on the audience. 
 +==== Preliminary schedule for 2020-2021 ====
-==== Preliminary schedule for 2019-2020 ==== +** Time: ** Mondays, from 14h15 to 15h45
- +
-** Time: ** Tuesdays, from 17h45 to 19h15+
 ** Location: ** Room **1013**, [[|Building Sophie Germain]] ** Location: ** Room **1013**, [[|Building Sophie Germain]]
-|10/09  |Brice Minaud| +|21/09  |Phong Nguyen|Overview and Introduction to Lattices
-|17/09  |Brice Minaud+|28/09  |Phong Nguyen|Hard Lattice Problems: SVP, CVP, SIS, LWE, etc.
-|24/09  |**No Class**+|05/10  |Phong Nguyen|Encryption from Lattices
-|01/10  |Brice Minaud+|12/10  |Phong Nguyen|Signature from Lattices
-|08/10  |Brice Minaud+|19/10  |Phong Nguyen|Hermite's inequality and the LLL Algorithm
-|15/10  |Brice Minaud+|26/10  |Phong Nguyen|Applications of LLL: Breaking RSA
-|22/10  |Brice Minaud+|02/11  |Phong Nguyen|Finding Very Short Lattice Vectors: Enumeration and Sieving
-|29/10  |Brice Minaud+|09/11  |Phong Nguyen|Beyond LLL: Blockwise Reduction
-|05/11  |Brice Minaud+|16/11  |Phong Nguyen|Security Estimates for Lattice Cryptography|
-|12/11  |Brice Minaud|+
-|**19/11**  |**Exam**| +|**23/11**  |**Exam**| 
-|**26/11**  |**No Class**|+|**30/11**  |**No Class**|
-The Midterm Exam will take place on Tuesday19 November 2019, from 16h15 to 17h45 in the usual room. +The Midterm Exam will take place on Monday23 November 2020, from 14h15 to 15h45 in the usual room. 
-|03/12  |**No Class**+|07/12  |Brice Minaud|Introduction, Zero-Knowledge Proofs I
-|10/12  |**No Class**| +|14/12  |Brice Minaud|Zero-Knowledge Proofs II| 
-|17/12  |**No Class**| +|21/12  |**No Class**| 
-|07/01  |Michel Abdalla+|04/01  |**No Class**| 
-|14/01  |Michel Abdalla+|11/01  |Brice Minaud|Succint Proofs of Knowledge
-|21/01  |Michel Abdalla+|18/01  |Brice Minaud|An application: Cryptocurrencies
-|28/01  |Michel Abdalla+|25/01  |Brice Minaud|Oblivious Algorithms
-|04/02  |Michel Abdalladouble class: **16h15-19h15** +|01/02  |Brice Minaud|Oblivious RAM
-|11/02  |**No Class**+|08/02  |Brice Minaud|Computing on Encrypted Data
-|18/02  |Michel Abdalladouble class**16h15-19h15** |+|15/02  |Brice Minaud|Searchable Encryption
 +|22/02  |Brice Minaud|An applicationEncrypted Databases|
-|**25/02**  |**Exam**| +|**01/03**  |**Exam**| 
-|**03/03**  |**No Class**|+|**08/03**  |**No Class**|
-The Final Exam will take place on Tuesday25 February 2020, from 16h15 to 17h45 in the usual room. +The Final Exam will take place on MondayFebruary 2021, from 14h15 to 15h45 in the usual room. 
-==== Summary ==== +==== Overview ==== 
-The main objective of the course is to introduce students to cryptographic schemes built using the *provable-security* paradigm and to cryptanalytic techniques.  Throughout the construction part of the course,  +The main objective of the course is to introduce students to a few important tools and techniques relevant to modern cryptography. 
-various schemes (such as authentication, identification, signature, encryption, identity-based encryption, etc.) will be presented whose security is based on  +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)\\
-presumed-to-be-hard mathematical problems such as factoring, discrete log, subset sum, learning parity with noise, and lattice problems; in the cryptanalysis part, algorithmic methods to study or solve some of these presumably hard problems will be presented.  At the end of the  +
-course, students should have the necessary tools to perform research in academic-level cryptography+
-==== Pre-Requisites ==== +During the first half of the course, the main focus will be on lattice-based cryptography. 
-The main requirement is being comfortable with mathematical proofsSome knowledge of basic mathematical topics such as probability, number theory, and linear algebra will also be assumed.+In the past 25 years, lattice-based cryptography has emerged as the most powerful 
 +alternative to classical public-key cryptography based on factoring (RSARabin) 
 +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.
-==== Topics ====+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.
-In the course, we will present constructions of cryptographic primitives whose security depends on the presumed hardness of various mathematical problems.  Below are examples of such primitives and assumptions that we will cover in the course. In the cryptanalysis part, algorithmic techniques related to these assumptions will be presented.+At the end of the course, students should have the necessary tools to conduct research in academic-level cryptography
-__Cryptographic Primitives__  
-1. One-way functions+==== Pre-Requisites ==== 
 +The main requirement is being comfortable with mathematical proofs. Some knowledge of basic mathematical topics such as probability, number theory, and linear algebra will also be assumed.
-2Pseudorandom functions+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: linear algebra, Euclidean spaces, probability. 
 +==== Notes ==== 
 +For the first part of the course on lattice-based cryptography, here are useful external notes on lattices: \\ 
 +- Oded Regev's "Lattices in Computer Science" at NYU: \\ 
 +- Vinod 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: \\
-3. Authentication schemes +Notes below are from previous years, and no longer directly relevant to the courseThey are still provided here for the benefit of curious students.
- +
-4. Digital signatures +
- +
-5. Public-key encryption +
- +
-6. Identity-based encryption +
- +
-__Hardness assumptions__ +
- +
-0. Generic assumptions: one-waynesscollision-resistance, ... +
- +
-1. Factorization and RSA related assumptions +
- +
-2Discrete log and related assumptions +
- +
-3Learning parity with noise +
- +
-4. Subset sum +
- +
-5. Lattice problems +
- +
-6. Code based problems +
- +
- +
- +
- +
- +
-==== Homeworks ==== +
- +
-Homework 1: +
- +
-Homework 2: +
- +
-==== Notes ====+
 Notes 1: Notes 1:
Line 106: Line 89:
 Notes 5: Reference for the BBG scheme: (see Pages 5---8) Notes 5: Reference for the BBG scheme: (see Pages 5---8)
 +Notes 6: Lecture Notes on the Complexity of Some Problems in Number Theory:
 Slides on identity-based encryption: Slides on identity-based encryption:
Line 112: Line 97:
 Slides on identity-based encryption with wildcards: Slides on identity-based encryption with wildcards:
 ==== Equipe pédagogique / Possible lecturers ====  ==== Equipe pédagogique / Possible lecturers ==== 
 |Michel Abdalla | DR @ CNRS | |Michel Abdalla | DR @ CNRS |
-|Georg Fuchsbauer CR @ Inria+|Phong Nguyen [[]] |DR @ Inria| 
-|Antoine Joux | Cryptology Chair @ Fondation UPMC+|Brice Minaud [[]] |CR @ Inria| 
-|Brice Minaud |CR @ Inria|+
Universités partenaires Université Paris-Diderot
Université Paris-Saclay
ENS Cachan École polytechnique Télécom ParisTech
Établissements associés Université Pierre-et-Marie-Curie CNRS INRIA CEA