Paper 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.
- Keywords
- Code-Based CryptographyRestricted ErrorsPost-Quantum CryptographyCryptanalysis
- Contact author(s)
-
ward @ beullens com
pierre @ simula no
morten oygarden @ simula no - History
- 2024-04-22: approved
- 2024-04-21: received
- See all versions
- Short URL
- https://ia.cr/2024/611
- License
-
CC BY
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},
note = {\url{https://eprint.iacr.org/2024/611}},
url = {https://eprint.iacr.org/2024/611}
}
