List decoding of random sum-rank metric codes
coding theory, list decoding, rank metric
Description
In this thesis, we want to investigate the list decoding complexity of random (linear) codes in the sum-rank metric.
List decoding is a technique to decode beyond the unique decoding radius of a code at the cost of obtaining a list of candidate solutions. The sum-rank metric [1] is a relatively novel metric where the weight of a vector is given by the sum of the ranks of its component blocks.
As a starting point, the student should familiarize themselves with the concept of the sum-rank metric. Then, the list decoding behavior of a random SR code should be investigated, perhaps along the lines of these papers [2,3] that have some similar results on random rank metric codes. It would also be nice to investigate if this other technique [4] can be applied to the sum-rank metric.
Resources:
[1] https://arxiv.org/pdf/2102.02244 (this is not the paper where this metric was first studied, but it has a very nice overview of existing results)
[2] https://arxiv.org/abs/1401.2693
Prerequisites
Channel coding lecture or similar (i.e., basics of linear codes and their decoding)
strong background in linear algebra
An interest in combinatorics is beneficial, it is at the core of many of the related papers
Contact
anna.baumeister@tum.de
Supervisor:
Number-Theoretic Transform
Description
The number-theoretic transform (NTT) is a generalization of the discrete Fourier transform over a ring or finite field. In a similar fashion to the FFT algorithm, the NNT efficiently computes the circular convolution of an integer sequence. An application of the NTT is the multiplication of two polynomials over a finite field, which is often used in cryptosystems based on lattices like CRYSTALS-KYBER.
Tasks:
- Understand the NTT and inverse NTT and how it relates to the FFT,
- study applications of NTT in post-quantum cryptosystems using the paper provided
Main papers:
Number Theoretic Transform and Its Applications in Lattice-based Cryptosystems: A Survey
Conceptual Review on Number Theoretic Transform and Comprehensive Review on Its Implementations
A nice primer on the NTT with examples can also be found in this blog
Contact
anna.baumeister@tum.de