Due to the recent advances in quantum computers, the search for cryptosystems that survive quantum attacks is of great interest. Code-based cryptography is a promising candidate, since it is build on the NP-hard problem of decoding a random code [1].

In order to solve the generic decoding problem, algorithms from the  information set decoding (ISD) family can be used.
During the last 60 years, small improvements to this approach were made. During this time, other algorithms, such as statistical decoding [2], were proposed, but failed to achieve the performance of ISD [3].

Recently, a variant of statistical decoding was proposed that claims to perfom better than the best ISD variants for low code rates [4].

The student should familiarize themselves with the concept of the new approach to statistical decoding presented in [4].
The final report should give a description of the algorithm and a complexity analysis.

Main Paper:

Carrier, K., Debris-Alazard, T., Meyer-Hilfiger, C., & Tillich, J. P. (2022). Statistical Decoding 2.0: Reducing Decoding to LPN. arXiv preprint arXiv:2208.02201.

References:

[1] Weger, V., Gassner, N., & Rosenthal, J. (2022). A Survey on Code-Based Cryptography. arXiv preprint arXiv:2201.07119.

[2] Jabri, A. A. (2001, December). A statistical decoding algorithm for general linear block codes. In IMA International Conference on Cryptography and Coding (pp. 1-8). Springer, Berlin, Heidelberg.

[3] Debris-Alazard, T., & Tillich, J. P. (2017, June). Statistical decoding. In 2017 IEEE International Symposium on Information Theory (ISIT).

[4] Carrier, K., Debris-Alazard, T., Meyer-Hilfiger, C., & Tillich, J. P. (2022). Statistical Decoding 2.0: Reducing Decoding to LPN. arXiv preprint arXiv:2208.02201.

Channel coding

Security in Communications and Storage

Probability theory and statistics

A common assumption for the construction of error correcting codes is that errors occur independently.

However, in many applications errors are actually highly correlated.
Coding in the cover-metric considers correlated errors which occur as 2-dimensional burst errors.

Such errors can be corrected using rank-metric codes.
Originally Gabidulin codes were proposed for this.
In [1], low-rank parity check (LRPC) codes are introduced, which utilize a probabilistic decoding procedure.

The goal of the master thesis is to

• apply LRPC codes to the cover-metric

• derive expressions on the success probability of the decoding by modifying the existing results for the rank metric

• check these results using simulations

Depending on personal preference, this basic idea will be extended into different directions:

•  consider interleaved scenario as in [2]

• consider a modified construction, which utilizes the additional structure of cover-metric errors compared to rank-metric errors (cf. [3])

If you are interested, please write an email, then we'll discuss the details.

[1] Aragon, Gaborit, Hauteville, Ruatta, Zemor, "Low Rank Parity Check Codes: New Decoding Algorithms and Applications to Cryptography", https://arxiv.org/abs/1904.00357

[2] Renner, Jerkovits, Bartz, "Efficient Decoding of Interleaved Low-Rank Parity-Check Codes", https://arxiv.org/abs/1908.10839

[3] Bitzer, Renner, Wachter-Zeh, Weger, "Generic Decoding in the Cover Metric", https://arxiv.org/abs/2205.12738

Channel coding