The MinRank and Rank Syndrome Decoding problem are the basis of the security of many cryptographic schemes. Therefore it is important to understand the complexity of solving these problems.

In this project, the goal is to:
1. Understand the the existing solvers for these problems, in particular, [1] and [2].
2. Apply some ideas to slightly improve their complexity.
3. Understand if it affects the security of the existing cryptographic schemes.

[1] Gaborit, Philippe, Olivier Ruatta, and Julien Schrek. 2016. “On the Complexity of the Rank Syndrome Decoding Problem.” IEEE Transactions on Information Theory 62 (2): 1006–19. https://doi.org/10.1109/TIT.2015.2511786.
[2] L. Goubin and N. T. Courtois, “Cryptanalysis of the TTM Cryptosystem,” in Advances in Cryptology — ASIACRYPT 2000, T. Okamoto, Ed., Berlin, Heidelberg: Springer, 2000, pp. 44–57. https://doi.org/10.1007/3-540-44448-3_4.

Voraussetzungen

Given a parity-check matrix H and a syndrome s, the Hamming Syndrome Decoding (SD) problem asks to find a vector e, the "error vector", of Hamming weight at most t. This difficulty of solving this problem has important applications to cryptography and the best solvers are the so-called Information Set Decoding (ISD) algorithms [1], [2, Section 5.3]. When the code is defined over an extension field F_{q^m}, the error vector has the additional property that its rank over the base field F_q is also at most t. Hence, one can see this as an instance of the so-called Rank Syndrome Decoding (RSD) problem, which is also an important problem with many existing solvers [3, 4].

The task of the student will be to:
- understand the existing solvers for RSD
- apply these solvers to the Hamming Syndrome Decoding problem over F_{q^m}
- compare the obtained complexity to the existing solvers in the Hamming-metric, i.e., the ISD algorithms

[1] Peters, Christiane. 2010. “Information-Set Decoding for Linear Codes over Fq.” In Post-Quantum Cryptography, edited by Nicolas Sendrier, 81–94. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer. https://doi.org/10.1007/978-3-642-12929-2_7.
[2] Weger, Violetta, Niklas Gassner, and Joachim Rosenthal. 2022. “A Survey on Code-Based Cryptography.” arXiv. https://doi.org/10.48550/arXiv.2201.07119.
[3] Gaborit, Philippe, Olivier Ruatta, and Julien Schrek. 2016. “On the Complexity of the Rank Syndrome Decoding Problem.” IEEE Transactions on Information Theory 62 (2): 1006–19. https://doi.org/10.1109/TIT.2015.2511786.
[4] Aragon, Nicolas, Philippe Gaborit, Adrien Hauteville, and Jean-Pierre Tillich. 2018. “A New Algorithm for Solving the Rank Syndrome Decoding Problem.” In 2018 IEEE International Symposium on Information Theory (ISIT), 2421–25. https://doi.org/10.1109/ISIT.2018.8437464.

Voraussetzungen

(External Master Thesis) With the emergence of quantum computing, cryptographic protocols like IPsec/IKEv2 must transition to post-quantum cryptographic (PQC) algorithms. This thesis focuses on integrating PQC into IPsec/IKEv2 for embedded systems, leveraging FPGA-based acceleration to optimize performance and resource usage.
Thesis includes evaluation of suitable PQC algorithms to create a hardware/software codesign concept, implementing critical cryptographic operations in FPGA hardware, and integrating them into an embedded software stack. The goal is to achieve a balanced co-design where FPGA handles computationally expensive tasks while maintaining flexibility in software.