Teachers: Alice Pellet-Mary and Gilles Zémor.
Program:
Classical public-key cryptography is known to be vulnerable to quantum computers, and post-quantum cryptography is the answer to this threat. In this course, we will study two aspects of post-quantum cryptography: code-based cryptography and lattice-based cryptography. Half the course will be devoted to code-based crypto and the other half will be devoted to lattice-based crypto (the two parts may be interleaved). No prior study of cryptography will be assumed, though we would encourage prospective students to aquire some exposure to the concept of public-key cryptography.
The code part will be organized as follows:
- definition of a linear code and some properties
- algorithms for decoding a code
- construction of public key encryption from codes (McEliece cryptosystem and Alekhnovich cryptosystems)
The lattice part will be organized as follows:
- definition of a lattice and some properties
- algorithms for reducing the basis of a lattice
- construction of hash functions and public key encryption from lattices (Atjai hash function, Regev encryption scheme)
The lectures will be illustrated by exercise sessions and programming sessions using SAGE.
Prerequisites:
Linear algebra.
References:
- M. Sudan, Course Notes on Coding Theory
- G. Zemor. Notes on Code-based Cryptography
- D. Micciancio and S. Goldwasser. Complexity of lattice problems: a cryptographic perspective. Springer Science & Business Media, 2002
- C. Peikert. A Decade of Lattice Cryptography, available here
- D. Dadush and L. Ducas. Lecture notes