Master Thesis
Classical Problem from Coding Theory
Most of the current used public-key cryptosystems are based on the integer factorization or the discrete logarithm problem over finite fields or elliptic curves. However, quantum computers are able to solve these problems in polynomial time using Shor’s algorithm. Therefore, one is interested in finding cryptosystems that are resistant to attacks supported by both classical and quantum computers. This area of research is known as post-quantum cryptography. One promising candidate is code-based cryptography, which is based on hard problems from algebraic coding theory. Classically, this problem is the decoding of a random linear code (syndrome decoding problem), which was shown to be NP-complete by Berlekamp, McEliece and Van Tilborg [1]. By a linear code, we mean a k-dimensional linear subspace of the vector space F_q^n. An approach to solve the syndrome decoding problem is Information set decoding (ISD), which was first proposed by Prange in 1962 [2]. ISD algorithms do not break a code-based cryptosystem since they are not polynomial-time algorithms. However, they determine the choice of parameters for a given security level. Improvements to ISD have been published meanwhile.
In a first step of this thesis, the goal is to understand the basic notions of algebraic coding theory, the syndrome decoding problem and its complexity. In a second step, the goal is to understand the main idea of information set decoding and to consider different ISD algorithms from the literature. The goal is to create an overview of this active research area.
References
[1] On the inherent intractability of certain coding problems
[2] The use of information sets in decoding cyclic codes
[3] A survey on code-based cryptography