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

André Chailloux; Thomas Debris-Alazard; Simona Etinski

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

Abstract

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.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint. MINOR revision.
Keywords: code-based cryptography Lee metric information set decoding subset sum algorithms quantum algorithms
Contact author(s): andre chailloux @ inria fr
thomas debris @ inria fr
simona etinski @ inria fr
History: 2021-04-27: received
Short URL: https://ia.cr/2021/552
License: CC BY

BibTeX

@misc{cryptoeprint:2021/552,
      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},
      url = {https://eprint.iacr.org/2021/552}
}