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

Recently, different variants of the classical syndrome decoding problem (SDP) in the Hamming metric have been proposed [2,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 restricted syndrome decoding which was introduced in [2].

The goal of this the construction of codes for this error model, which has not been done before.
For this, a first approach is to follow the general idea given in [4].

Open questions are:

- discussion of the appropriate choice of the error set of a McEliece-type cryptosystem
- optimality bounds for codes in the restricted setting
- construction of short codes that are efficiently decodable and/or optimal
- construction of longer codes from short codes and the evaluation of their perfomance

References:

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

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

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

[4] Rohweder, D., Freudenberger, J., & Shavgulidze, S. (2018). Low-density parity-check codes over finite Gaussian integer fields. In ISIT.

Security in Communications and Storage

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 [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