Hardness of the Decoding Problem and its Applications in Post-Quantum Cryptography

Nowadays, most of our communications over the Internet are encrypted. However, some cryptographic constructions widely deployed today are vulnerable to quantum attacks, and the goal of post-quantum cryptography is to design classical cryptosystems based on computational problems which remain hard even with the help of quantum computers.

In this talk, I will give an introduction to cryptography based on the hardness of decoding random linear codes, which is, together with lattice-based cryptography, one of the most promising solutions for building post-quantum cryptosystems. I will more specifically focus on variants of this problem for codes endowed with an additional algebraic structure, which allows for more efficient cryptographic constructions, but whose theoretical security is less understood. Finally, I will give an overview of some on-going work on applications to secure multiparty computation (MPC). The goal of MPC is to enable a group of users (for example several smartphones and a remote server), to evaluate together a function over their respective private data, without revealing anything but the result. This is an old goal in cryptography, and deep connections with (structured) variants of the decoding problem have recently been established.