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

This is an old revision of the document!


Techniques in Cryptography and Cryptanalysis

Instructors for 2019 - 2020: Michel Abdalla (DR @ CNRS) and Brice Minaud (CR @ INRIA)

Language of Instruction: English

Preliminary schedule for 2019-2020

Time: Tuesdays, from 17h45 to 19h15

Location: Room 1013, Building Sophie Germain

10/09 Brice Minaud
17/09 Brice Minaud
24/09 No Class
01/10 Brice Minaud
08/10 Brice Minaud
15/10 Brice Minaud
22/10 Brice Minaud
29/10 Brice Minaud
05/11 Brice Minaud
12/11 Brice Minaud
19/11 Exam
26/11 No Class

The Midterm Exam will take place on Tuesday, 19 November 2019, from 16h15 to 17h45 in the usual room.

03/12 No Class
10/12 No Class
17/12 No Class
07/01 Michel Abdalla
14/01 Michel Abdalla
21/01 Michel Abdalla
28/01 Michel Abdalla
04/02 Michel Abdalla double class: 16h15-19h15
11/02 No Class
18/02 Michel Abdalla double class: 16h15-19h15
25/02 Exam
03/03 No Class

The Final Exam will take place on Tuesday, 25 February 2020, from 16h15 to 17h45 in the usual room.

Summary

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, various schemes (such as authentication, identification, signature, encryption, identity-based encryption, etc.) will be presented whose security is based on 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

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.

Topics

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.

Cryptographic Primitives

1. One-way functions

2. Pseudorandom functions

3. Authentication schemes

4. Digital signatures

5. Public-key encryption

6. Identity-based encryption

Hardness assumptions

0. Generic assumptions: one-wayness, collision-resistance, ...

1. Factorization and RSA related assumptions

2. Discrete log and related assumptions

3. Learning parity with noise

4. Subset sum

5. Lattice problems

6. Code based problems

Homeworks

Notes

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)

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

Equipe pédagogique / Possible lecturers

Michel Abdalla DR @ CNRS
Georg Fuchsbauer CR @ Inria
Antoine Joux Cryptology Chair @ Fondation UPMC
Brice Minaud CR @ Inria
 
Universités partenaires Université Paris-Diderot
Université Paris-Saclay
ENS Cachan École polytechnique Télécom ParisTech
ENS
Établissements associés Université Pierre-et-Marie-Curie CNRS INRIA CEA