Post-quantum cryptography

Post-quantum cryptography aims at designing classical (non-quantum) cryptosystems that are secure against possibly quantum attackers. The recent advances towards building quantum computers make its development pressing. As a result, it is a vibrant sub-field of cryptography, raising questions on computational assumptions, models of attackers, cryptographic design, and practical deployment.
In this course, we will cover a wide range of approaches for designing quantum-safe cryptographic primitives, focusing on digital signatures and public-key encryption.

General Information

Lecturers:
Thomas Debris-Alazard (INRIA Paris-Saclay), Damien Stehlé (ENS Lyon) and Benjamin Wesolowski (CNRS, U. Bordeaux).

Evaluation:
For half the grade: a homework and a report on a research article
For the other half: an oral exam with a presentation of the research article and questions on the lectures

Prerequisites:

Probabilities (L3)
Information Theory (M1) may help
Familiarity with elementary algebra (fields, groups, linear algebra), Computer Algebra (M1) may help
Cryptography (M1)

Tentative plan:

I. Hash-based signatures

One-time signatures, Merkle trees, XMSS
Goldreich's signature, SPHINCS

II. Codes

Intractable problems related to codes
Code-based encryption, from McEliece and Alekhnovich to modern schemes
Code-based signatures, from Stern and CFS to modern schemes

III. Lattices

Hardness assumptions: LWE, SIS, PLWE, PSIS
Lyubashevsky's signature
Encryption: Newhope and extensions
NTRU

IV. Isogenies

Elliptic curves and isogenies
The Jao-De Feo key exchange, SIKE
Hard homogenous spaces: post-quantum Diffie-Hellman and other applications