Paper 2026/705
Cross-Paradigm Models of Restricted Syndrome Decoding with Application to CROSS
, University of Luxembourg, University of LuxembourgAbstract
Restricted Syndrome Decoding (ResSD) is a variant of linear code decoding problem where each of the error's entries must belong to a fixed small set of values. This problem underlies the security of CROSS, a post-quantum signature scheme that is one of the Round~2 candidates of NIST's ongoing additional signatures call. We show that solutions to this problem can be deduced from vectors of a particular structure and a small norm in newly constructed codes, in both Hamming and Euclidean metrics. This allows us to reduce Restricted Syndrome Decoding to both code-based (Regular Syndrome Decoding) and lattice-based problems (Closest Vector Problem, List of Short/Close Vectors), increasing the attack surface and providing new insights into the security of ResSD. We evaluate our attacks on CROSS instances both theoretically and experimentally on reduced parameters.
Metadata
- Available format(s)
-
PDF
- Category
- Attacks and cryptanalysis
- Publication info
- Published elsewhere. PQCRYPTO 2026
- DOI
- 10.1007/978-3-032-22695-2_7
- Keywords
- Post-quantum cryptographyCryptanalysisRestricted Syndrome DecodingCode-basedLattice-basedCROSS
- Contact author(s)
-
etienne burle @ uni lu
aleksei @ affine group - History
- 2026-04-19: revised
- 2026-04-10: received
- See all versions
- Short URL
- https://ia.cr/2026/705
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2026/705,
author = {Étienne Burle and Aleksei Udovenko},
title = {Cross-Paradigm Models of Restricted Syndrome Decoding with Application to {CROSS}},
howpublished = {Cryptology {ePrint} Archive, Paper 2026/705},
year = {2026},
doi = {10.1007/978-3-032-22695-2_7},
url = {https://eprint.iacr.org/2026/705}
}
