Master Thesis
Using polynomial systems to decode binary linear codes.
Suppose we want to send a message over a noisy channel (where some errors may occur e.g. some bits are changed during transmission). We encode the message in such a way that the receiver can correct the errors, retrieve the original sent codeword, and decode it to the original message.
This decoding problem with maximum likelihood (MLD) is known to be NP-complete. We constructed a reduction to a system of multivariate quadratic equations (MQ), which is NP-complete too. Both problems are suitable for quantum-secure cryptographic systems. We also have a transformation that given a solution of the system, outputs a solution of the decoding problem. This means that given a linear code, it is possible to decode it by solving the associated polynomial system.
A reduction between two problems is, generally speaking, a map that transforms an instance of the first problem into an instance of the second problem.
The goal of this project is to implement such reduction from MLD to MQ and the solution transformation. A reference programming language is Sage, written in Python. The project consists of implementing the reduction, analysing its computational complexity, and evaluating its performances.
This project requires good familiarity with linear algebra concepts.
Aims • Present the basic concepts of coding theory (i.e. error correcting codes) • Practical work with algebraic objects • Give a practical insight into complexity theory
References
[2] MLD
[3] MQ
[3] Sage