This thesis is concerned with developing code constructions for a new weight function (and associated metric) on (Z/qZ)^n called the unit-burst weight, suitable for measuring same-symbol burst errors. A unit burst is defined as a vector that has some consecutive positions of ones and is zero otherwise.

Any vector v in (Z/qZ)^n can be written as a (not necessarily unique) linear combination of these bursts. The burst weight is then the minimum number of bursts that need to be added or subtracted to produce v.

This metric has a connection to the A_n root lattice, a special lattice in Z^n+1 of vectors whose entries sum to zero. More precisely, the unit bursts relate to the shortest vectors of A_n called roots, and the burst weight corresponds to the smallest decomposition of a lattice point into roots.

We have already derived some basic properties and algorithms for this new metric and now would like to find some bounds and code constructions achieving those bounds. 

The security of cryptosystems is often evaluated by how hard it is to break them (forge a valid plaintext/ciphertext or message/signature pair) under the assumption that the secret key remains hidden.

In this seminar topic, we study leakage robustness, i.e., the property of a cryptosystem to remain secure even when part of the secret key is revealed. 

The student should read and understand the main paper by D'Alconzo et al., which studies the leakage robustness of three signature schemes in the rank metric that are currently under consideration for standardization by NIST.

Main Paper:

Sneaking up the Ranks: Partial Key Exposure Attacks on Rank-Based Schemes, https://eprint.iacr.org/2024/2070.pdf

Additional Reading:

Elena Kirshanova and Alexander May. Breaking Goppa-Based McEliece with Hints, https://eprint.iacr.org/2022/525.pdf

Don Coppersmith. Small solutions to polynomial equations, and low exponent RSA vulnerabilities, https://link.springer.com/article/10.1007/s001459900030

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

Voraussetzungen