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

[3] https://arxiv.org/abs/1710.11516

[4] https://arxiv.org/abs/1704.02420

Prerequisites

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 

Modern vehicles boast advanced infotainment systems, delivering a range of services encompassing entertainment, navigation, comfort, and connectivity. These applications require extensive real-time data, necessitating efficient and reliable data processing from vehicle sensors and control units. With every vehicle launch and OS release, new sensors and APIs are introduced, which serve as important data points for high-level analytics and applications. Currently, these changes must be monitored and integrated manually, which is a demanding task prone to errors. The objective of this internship is to develop tools that automatically generate a data collector access layer for the platform APIs in every major OS release. This is done by analyzing the available APIs, followed by the creation of a data dependency tree based on the JSON format. An appropriate graph reduction algorithm is then applied to generate a data structure with minimum edge dependencies while preserving analyzability of the data points. An appropriate lookup schema is then created based on the reduced data points, which calls the requested API based on the supplied configuration. Python and C++ are the languages used within the scope of this project.

Whenever an automobile manufacturer develops a new car model, the aim is to surpass its predecessors in terms of performance, efficiency, safety, and overall user experience. In order to do so, logged data has to be analyzed to find out where improvements can be made. Whenever a vehicle returns from a test drive, the collected data will be stored as an MDF (Measurement Data Format) file. These files are then read and analyzed with a software tool, but as of now, only a few files can be processed simultaneously due to hardware limitations. This research internship explores how data can be efficiently organized to maximize analyzability. Eventually, a program should be created which allows users to analyze all MDF files a vehicle has produced in parallel. 

Information set decoding (ISD) is the best known strategy to solve generic instances of the syndrome decoding problem. ISD was introduced by Prange in 1962 and has since been improved upon numerous times, usually by adding an enumeration step to the original permutation-based algorithm. Some of the most recent algorithms use nearest-neighbor search to speed up this enumeration step.

The student should first familiarize themselves with the original information set decoding algorithm by Prange which is based solely on permutation.

Next, enumeration-based ISD algorithms (e.g. the original one by Dumer) should be studied. Modern algorithms like MMT and BJMM (sometimes referred to as enumeration-dominated ISD algorithms) use the representation technique to speed up the enumeration step. It is not necessary to study them in detail for the scope of this seminar topic, but they provide a good point of comparison.

Finally, the student should investigate how nearest-neighbor search can be used in ISD to speed up enumeration (e.g. in the Both-May algorithm) and compare to other existing ISD algorithms in terms of runtime and memory consumption.

Resources:

An overview of current ISD algorithms for different applications as well as some theoretical background can be found in these excellent papers: 

[1] https://eprint.iacr.org/2022/1328.pdf

[2] https://eprint.iacr.org/2021/1634.pdf

There's an ongoing online competition for syndrome decoding where you can check which algorithms are used in practice and get a feel for sizes and runtime complexities:

https://decodingchallenge.org/syndrome

Prerequisites