Paper 2021/552

Classical and Quantum algorithms for generic Syndrome Decoding problems and applications to the Lee metric

André Chailloux, Thomas Debris-Alazard, and 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 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.

Available format(s)
Public-key cryptography
Publication info
Preprint. MINOR revision.
code-based cryptographyLee metricinformation set decodingsubset sum algorithmsquantum algorithms
Contact author(s)
andre chailloux @ inria fr
thomas debris @ inria fr
simona etinski @ inria fr
2021-04-27: received
Short URL
Creative Commons Attribution


      author = {André Chailloux and Thomas Debris-Alazard and Simona Etinski},
      title = {Classical and Quantum algorithms for generic Syndrome Decoding problems and applications to the Lee metric},
      howpublished = {Cryptology ePrint Archive, Paper 2021/552},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.