(AGENPARL) – WORLD WIDE, mar 27 aprile 2021
ePrint Report: Classical and Quantum algorithms for generic Syndrome Decoding problems and applications to the Lee metric
André Chailloux, Thomas Debris-Alazard, Simona Etinski
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 Wagners 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.