Pierre Loisel

It has been roughly 30 years since we learned that the mathematical problems underpinning much of deployed cryptography (integer factorisation, discrete logarithms in abelian groups, etc.) can be solved efficiently on a quantum computer. However, we also know of problems that appear to remain hard even for quantum algorithms and can thus serve as the basis for cryptography on classical computers: this is post-quantum cryptography.

One important family in post-quantum cryptography comes from error-correcting codes (vector subspaces of \mathbb{F}_q^n equipped with a metric). The goal of this talk is to present several of these problems, explain why they are (or, more precisely, seem to be) difficult, and survey some of the mathematical techniques used to study them.

The talk is intended to be accessible; it assumes only basic combinatorics, linear algebra, and probability over \mathbb{F}_q^n as well as Fourier analysis over finite abelian groups. No previous knowledge of cryptography is required.