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

The McEliece cryptosystem is a well-known public-key encryption scheme using Goppa codes in the Hamming metric. The GPT cryptosystem is the rank-metric counterpart of this scheme using Gabidulin codes. While this promises much better message security than McEliece, it has been subject to several successful key attacks, most prominent of which is known as Overbeck's attack [1, 2].

The task of the student is to understand the different proposed versions of the GPT cryptosytem and how they were attacked. Further, the student will look at a more recent version of this scheme [3] which has so far resisted Overbeck's attack.

[1] R. Overbeck, “Public Key Cryptography based on Coding Theory,” phd, Technische Universität Darmstadt, Darmstadt, 2007. Accessed: Oct. 01, 2024. [Online]. Available: https://tuprints.ulb.tu-darmstadt.de/823/
[2] R. Overbeck, “Structural Attacks for Public Key Cryptosystems based on Gabidulin Codes,” J Cryptol, vol. 21, no. 2, pp. 280–301, Apr. 2008, doi: 10.1007/s00145-007-9003-9.
[3] P. Loidreau, “A New Rank Metric Codes Based Encryption Scheme,” in Post-Quantum Cryptography, T. Lange and T. Takagi, Eds., Cham: Springer International Publishing, 2017, pp. 3–17. doi: 10.1007/978-3-319-59879-6_1.

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.