Post-Quantum Cyptography based on Codes: Ternary Syndrome Decoding
code-based cryptography, ternary syndrome decoding with large weight, decoding attack
Beschreibung
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.
Voraussetzungen
Security in Communications and Storage
Betreuer:
Channel Coding: Efficient Decoding for GC Codes and General Codes
channel coding, efficient decoding, generalized concatenated codes
We develop efficient decoders for short block codes.
Beschreibung
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.
Voraussetzungen
Channel coding
Betreuer:
Code-based Cryptography: digital signatures
code-based cryptography, digital signatures
Beschreibung
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.
Voraussetzungen
Channel coding
Security in Communications and Storage
Betreuer:
Code-based Cryptography: Information Set Decoding
code-based cryptography, information set decoding
Beschreibung
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.
Voraussetzungen
Channel coding
Security in Communications and Storage
Betreuer:
Statistical Decoding
code-based cryptography, decoding attack
Beschreibung
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.
Voraussetzungen
Channel coding
Security in Communications and Storage
Probability theory and statistics