Picture of Sebastian Bitzer

M.Sc. Sebastian Bitzer

Technical University of Munich

Associate Professorship of Coding and Cryptography (Prof. Wachter-Zeh)

Postal address

Postal:
Theresienstr. 90
80333 München

Biography

I received my B.Sc and M.Sc degree in Electrical Engineering  in 2018 and 2021, respectively.
During my studies, I started to collaborate with Prof. Martin Bossert in order to develop efficient hard- and soft-decision decoding algorithms for for algebraic codes.
Under the supervision of Prof. Antonia Wachter-Zeh, I am conducting research on code-based cryptography.

Available Theses

Post-Quantum Cyptography based on Codes: Ternary Syndrome Decoding

Keywords:
code-based cryptography, ternary syndrome decoding with large weight, decoding attack

Description

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.

Prerequisites

Security in Communications and Storage

 

 

 

Supervisor:

Theses in Progress

Code Construction for Restricted Errors

Keywords:
code-based cryptography, restricted errors, code construction

Description

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.

Prerequisites

Security in Communications and Storage

Channel Coding

 

 

 

Supervisor:

Code-based Cryptography: digital signatures from QC-LDPCs

Keywords:
code-based cryptography, digital signatures

Description

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 a proposals based on quasi-cyclic low-density parity-check codes [2].
We investigate possible information leakage through the signatures, since for related signature schemes, such leakages have lead to efficient key recovery attacks.

 

References:

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

[2] Picozzi, C., Meneghetti, A., & Tognolini, G. (2022). A Post-Quantum Digital Signature Scheme from QC-LDPC Codes. Cryptology ePrint Archive.

[3] Persichetti, E. (2018). Efficient one-time signatures from quasi-cyclic codes: A full treatment. Cryptography, 2(4), 30

[4] Santini, P., Baldi, M., & Chiaraluce, F. (2019, July). Cryptanalysis of a one-time code-based digital signature scheme. In 2019 IEEE International Symposium on Information Theory (ISIT) (pp. 2594-2598). IEEE.

 

Prerequisites

Channel coding

Security in Communications and Storage

 

 

 

Supervisor:

Solvers for the Code Equivalence Problem

Keywords:
code-based cryptography, digital signatures, code equivalence

Description

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.

 

 

 

Prerequisites

Channel coding

Security in Communications and Storage

 

 

 

Supervisor:

Publications

2022

  • Bitzer, Sebastian; Bossert, Martin: On Multibasis Information Set Decoding. 2022 IEEE International Symposium on Information Theory (ISIT), 2022 more…
  • Bitzer, Sebastian; Renner, Julian; Wachter-Zeh, Antonia; Weger, Violetta: Generic Decoding in the Cover Metric. arXiv preprint arXiv:2205.12738, 2022 more…
  • Bossert, Martin; Schulz, Rebekka; Bitzer, Sebastian: On Hard and Soft Decision Decoding of BCH Codes. IEEE Transactions on Information Theory 68 (11), 2022, 7107--7124 more…

2019

  • Müelich, Sven; Bitzer, Sebastian; Sudarshan, Chirag; Weis, Christian; Wehn, Norbert; Bossert, Martin; Fischer, Robert FH: Channel Models for Physical Unclonable Functions based on DRAM Retention Measurements. 2019 XVI International Symposium" Problems of Redundancy in Information and Control Systems"(REDUNDANCY), 2019 more…