TY - GEN
T1 - Classical and Quantum Algorithms for Generic Syndrome Decoding Problems and Applications to the Lee Metric
AU - Chailloux, André
AU - Debris-Alazard, Thomas
AU - Etinski, Simona
N1 - Publisher Copyright:
© 2021, Springer Nature Switzerland AG.
PY - 2021/1/1
Y1 - 2021/1/1
N2 - The security of code-based cryptography usually relies on the hardness of the Syndrome Decoding (SD) problem for the Hamming weight. The best generic algorithms are all improvements of an old algorithm by Prange, and they are known under the name of Information Set Decoding (ISD) algorithms. This work aims to extend ISD algorithms’ scope by changing the underlying weight function and alphabet size of SD. More precisely, we show how to use Wagner’s algorithm in the ISD framework to solve SD for a wide range of weight functions. We also calculate the asymptotic complexities of ISD algorithms, both for the classical and quantum case. We then apply our results to the Lee metric, which is currently receiving a significant amount of attention. By providing the parameters of SD for the Lee weight for which decoding seems to be the hardest, our study could have several applications for designing code-based cryptosystems and their security analysis, especially against quantum adversaries.
AB - The security of code-based cryptography usually relies on the hardness of the Syndrome Decoding (SD) problem for the Hamming weight. The best generic algorithms are all improvements of an old algorithm by Prange, and they are known under the name of Information Set Decoding (ISD) algorithms. This work aims to extend ISD algorithms’ scope by changing the underlying weight function and alphabet size of SD. More precisely, we show how to use Wagner’s algorithm in the ISD framework to solve SD for a wide range of weight functions. We also calculate the asymptotic complexities of ISD algorithms, both for the classical and quantum case. We then apply our results to the Lee metric, which is currently receiving a significant amount of attention. By providing the parameters of SD for the Lee weight for which decoding seems to be the hardest, our study could have several applications for designing code-based cryptosystems and their security analysis, especially against quantum adversaries.
U2 - 10.1007/978-3-030-81293-5_3
DO - 10.1007/978-3-030-81293-5_3
M3 - Conference contribution
AN - SCOPUS:85112688487
SN - 9783030812928
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 44
EP - 62
BT - Post-Quantum Cryptography - 12th International Workshop, PQCrypto 2021, Proceedings
A2 - Cheon, Jung Hee
A2 - Tillich, Jean-Pierre
PB - Springer Science and Business Media Deutschland GmbH
T2 - 12th International Conference on post-quantum cryptography, PQCrypto 2021
Y2 - 20 July 2021 through 22 July 2021
ER -