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.

Prerequisites

(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.