An Introduction to Code-Based Cryptography (1ECTS, SSD:MAT02)

Beyond its role in information theory, coding theory plays a crucial role in cryptography, particularly in post-quantum cryptography. Traditional public-key cryptosystems rely on problems such as integer factorization and discrete logarithms on elliptic curves. While these problems are currently intractable for classical computers, Shor’s algorithm allows quantum computers to solve them in polynomial time. Post-quantum cryptography aims to create secure algorithms
based on computationally hard problems that remain resistant to quantum attacks, with a focus on NP-complete problems.
Code-based cryptography refers to any cryptographic system whose security relies on hard problems from algebraic coding theory. Classically, this problem consists of decoding a random linear code, which was proven to be NP-complete in 1978. That same year, McEliece introduced the first code-based cryptosystem. The core idea is to select a code with an underlying algebraic structure that enables efficient decoding, and then disguise it as a seemingly random. Encryp-
tion works by encoding the message into a codeword and then intentionally adding errors. With the knowledge of the secret code, one can efficiently decode and recover the message, while an attacker is left with the challenge of decoding a random linear code.
In this mini-course, we will introduce code-based cryptography, delving into the mathematical foundations of these systems. In particular, we will focus on the main approach to solving the decoding problem, that is, the information set decoding (ISD) algorithms. Lastly, we will discuss how to determine whether a code has a specific algebraic structure or if it is a random code.

Shedule: 18/11 10:30-13:30, 19/11 12:30--14:30, 25/11 10:30-13:30, 26/11 12:30-14:30, 27/11 8:30-10:30