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

Prior knowledge of coding theory and especially ISD is advantageous but not required - a solid grasp on linear algebra is probably most important.