Paper 2023/1865 Original: eprint.iacr.org/2023/1865 ↗
Projective Space Stern Decoding and Application to SDitH
Abstract
We show that here standard decoding algorithms for generic linear codes over a finite field can speeded up by a factor which is essentially the size of the finite field by reducing it to a low weight codeword problem and working in the relevant projective space. We apply this technique to SDitH and demonstrate that the parameters of the original submission fail to meet the security requirements set by NIST. However, the updated version, released after the discovery of this attack, is no longer challenged by our attack.
Metadata
- Available format(s)
PDF- Category
- Attacks and cryptanalysis
- Publication info
- Preprint.
- History
- 2025-04-17: last updated
- 2023-12-05: published
- Short URL
- https://ia.cr/2023/1865
- License
- https://creativecommons.org/licenses/by/4.0/
BibTeX
@misc{cryptoeprint:2023/1865,
author = {Kevin Carrier and Valérian Hatey and Jean-Pierre Tillich},
title = {Projective Space Stern Decoding and Application to SDitH},
howpublished = {Cryptology {ePrint} Archive, Paper 2023/1865},
year = {2023},
url = {https://eprint.iacr.org/2023/1865}
}