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 [2].

Recently, different variants of the classical syndrome decoding problem (SDP) in the Hamming metric have been proposed [1,3].
The main reason for this is that it appears hard to build an efficient digital signature scheme around the classical SDP.

One such variant is the ternary syndrome decoding with large weight, in which the error has few or no zero-entries [1].

The goal of this topic is understanding the properties of the decoding problem and analyzing the cost of existing solvers such as Sterns algorithm [2].

Main Paper:

[1] Bricout, R., Chailloux, A., Debris-Alazard, T., & Lequesne, M. (2020). Ternary syndrome decoding with large weight. In Selected Areas in Cryptography–SAC 2019: 26th International Conference, Waterloo, ON, Canada, August 12–16, 2019, Revised Selected Papers 26 (pp. 437-466). Springer International Publishing.

can be found here: https://arxiv.org/pdf/1903.07464.pdf

References:

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

[3] Baldi, M., Bitzer, S., Pavoni, A., Santini, P., Wachter-Zeh, A., & Weger, V. (2023). Generic Decoding of Restricted Errors. arXiv preprint arXiv:2303.08882.

Security in Communications and Storage

Arising applications, such as machine-to-maschine communication require error-correction codes with short information length.The design of such codes and efficient decoders is an open problem [1].

Recently, Reed-Muller codes have gained a lot of interest, because of thier good error-correction capability and their structure, which allows for low-complexity decoders, see, e.g., [2].

It has been known for quite some time that Reed-Muller codes belong to a more general class of codes: the Generalized Concatenated (GC) Codes [3].
This class allows for more flexible code design, e.g., with respect to the information rate of the code.
Hence, by transfering and refining results for Reed-Muller codes to GC codes, one could improve over existing solutions.

Another approach to obtain good results in the short-length regime is using the best-known codes [4].
Since these codes do usually not have a structure that enables efficient decoding, one has to perform decoding of a general linear code. The most efficient approaches are variants of Ordered Statistics Decoding (OSD) [5]. The idea for improving over state-of-the-art varaints is to encorporate recent improvements from another field of research: Information Set Decoding.

If you are interested in either of the directions (or have some other direction in mind), please write an email, then we'll discuss the details.

References:

[1] Co?kun, M. C., Durisi, G., Jerkovits, T., Liva, G., Ryan, W., Stein, B., & Steiner, F. (2019). Efficient error-correcting codes in the short blocklength regime. Physical Communication, 34, 66-79.

[2] Geiselhart, M., Elkelesh, A., Ebada, M., Cammerer, S., & ten Brink, S. (2021). Automorphism ensemble decoding of Reed–Muller codes. IEEE Transactions on Communications, 69(10), 6424-6438.

[3] Schnabl, G., & Bossert, M. (1995). Soft-decision decoding of Reed-Muller codes as generalized multiple concatenated codes. IEEE Transactions on Information Theory, 41(1), 304-308.

[4] Markus Grassl. "Bounds on the minimum distance of linear codes and quantum codes." Online available at http://www.codetables.de.

[5] Fossorier, M. P., & Lin, S. (1995). Soft-decision decoding of linear block codes based on ordered statistics. IEEE Transactions on Information Theory, 41(5), 1379-1396.

Channel coding

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

The McEliece cryptosystem is a promising candidate for asymmetric encryption.
However, many attempts at constructing a code-based signature scheme have resulted in impractical parameters or security problems.

NIST's announcement of a competetion dedicated to standardizing post-quantum signatures has lead to the publication of several new code-based schemes

In this work we pick one of the proposals and analyse its (in)security [2,3,4].
If you are interested, please write an email, then we'll discuss the details.

References:

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

[2] Cho, J., No, J. S., Lee, Y., Koo, Z., & Kim, Y. S. (2022). Enhanced pqsigRM: Code-Based Digital Signature Scheme with Short Signature and Fast Verification for Post-Quantum Cryptography. Cryptology ePrint Archive.

[3] Baldi, M., Chiaraluce, F., & Santini, P. (2022). SPANSE: combining sparsity with density for efficient one-time code-based digital signatures. arXiv preprint arXiv:2205.12887.

[4] Barenghi, A., Biasse, J. F., Persichetti, E., & Santini, P. (2022). On the computational hardness of the code equivalence problem in cryptography. Cryptology ePrint Archive.

Channel coding

Security in Communications and Storage

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.

Recently, new variants of the classical decoding problem were proposed [2,3,4].
This work adapts strategies for the classical problem to one of the new settings.
The goal is to develop decoding algorithms, analyse their complexity and do a (proof of concept) implementation.
There is also a webpage which provides instances that we can attempt to solve.

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

References:

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

[2] Bricout, R., Chailloux, A., Debris-Alazard, T., & Lequesne, M. (2020). Ternary syndrome decoding with large weight. In Selected Areas in Cryptography–SAC 2019: 26th International Conference, Waterloo, ON, Canada, August 12–16, 2019, Revised Selected Papers 26 (pp. 437-466). Springer International Publishing.

[3] Weger, V., Khathuria, K., Horlemann, A. L., Battaglioni, M., Santini, P., & Persichetti, E. (2020). On the hardness of the Lee syndrome decoding problem. arXiv preprint arXiv:2002.12785.

[4] Baldi, M., Battaglioni, M., Chiaraluce, F., Horlemann-Trautmann, A. L., Persichetti, E., Santini, P., & Weger, V. (2020). A new path to code-based signatures via identification schemes with restricted errors. arXiv preprint arXiv:2008.06403.

Channel coding

Security in Communications and Storage

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

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

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

In this research internship, the three hash-based digital signature schemes LMS, XMSS, and SPHINCS+ are discussed and compared. Their performance is evaluated on an Arm-based Adva Network Security platform, which uses FreeRTOS as operating system. The performance parameters investigated include key and signature sizes, key generation, signing and verification speed, memory efficiency, number of signatures that can be generated per key pair, available hash functions that can be used in the implementations, and the security level. The goal of this work is to make a recommendation on which scheme to use, considering hardware constraints and possible applications.

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

The McEliece cryptosystem is a promising candidate for asymmetric encryption.
However, many attempts at constructing a code-based signature scheme have resulted in impractical parameters or security problems.

NIST's announcement of a competetion dedicated to standardizing post-quantum signatures has lead to the publication of several new code-based schemes

In this work we consider LESS [2] a signature scheme based on the hardness of the code equivalence problem [3].
State-of-the-art solvers of the problem [4] are analysed and modifications are made to improve their performance.

References:

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

[2] Barenghi, A., Biasse, J. F., Persichetti, E., & Santini, P. (2021). LESS-FM: fine-tuning signatures from the code equivalence problem. In Post-Quantum Cryptography: 12th International Workshop, PQCrypto 2021, Daejeon, South Korea, July 20–22, 2021, Proceedings 12 (pp. 23-43). Springer International Publishing.

[3] Barenghi, A., Biasse, J. F., Persichetti, E., & Santini, P. (2022). On the computational hardness of the code equivalence problem in cryptography. Cryptology ePrint Archive.

[4] Beullens, W. (2021, July). Not enough LESS: An improved algorithm for solving code equivalence problems over F q. In Selected Areas in Cryptography: 27th International Conference, Halifax, NS, Canada (Virtual Event), October 21-23, 2020, Revised Selected Papers (pp. 387-403). Cham: Springer International Publishing.

Channel coding

Security in Communications and Storage