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 cryptographyLee metricinformation set decodingsubset sum algorithmsquantum 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},
note = {\url{https://eprint.iacr.org/2021/552}},
url = {https://eprint.iacr.org/2021/552}
}
