Paper 2024/611 Original: eprint.iacr.org/2024/611 ↗
A Security Analysis of Restricted Syndrome Decoding Problems
Abstract
Restricted syndrome decoding problems (R-SDP and R-SDP($G$)) provide an interesting basis for post-quantum cryptography. Indeed, they feature in CROSS, a submission in the ongoing process for standardizing post-quantum signatures. This work improves our understanding of the security of both problems. Firstly, we propose and implement a novel collision attack on R-SDP($G$) that provides the best attack under realistic restrictions on memory. Secondly, we derive precise complexity estimates for algebraic attacks on R-SDP that are shown to be accurate by our experiments. We note that neither of these improvements threatens the updated parameters of CROSS.
Metadata
- Available format(s)
PDF- Category
- Attacks and cryptanalysis
- Publication info
- Preprint.
- History
- 2024-04-21: last updated
- 2024-04-21: published
- Short URL
- https://ia.cr/2024/611
- License
- https://creativecommons.org/licenses/by/4.0/
BibTeX
@misc{cryptoeprint:2024/611,
author = {Ward Beullens and Pierre Briaud and Morten Øygarden},
title = {A Security Analysis of Restricted Syndrome Decoding Problems},
howpublished = {Cryptology {ePrint} Archive, Paper 2024/611},
year = {2024},
url = {https://eprint.iacr.org/2024/611}
}