Cross-Paradigm Models of Restricted Syndrome Decoding with Application to CROSS

Computer Science > Cryptography and Security [Submitted on 10 Apr 2026] Cross-Paradigm Models of Restricted Syndrome Decoding with Application to CROSS Étienne Burle, Aleksei Udovenko 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. Comments: 35 pages, 0 figures, PQ Crypto 2026 Subjects: Cryptography and Security (cs.CR); Information Theory (cs.IT) Cite as: arXiv:2604.09292 [cs.CR]   (or arXiv:2604.09292v1 [cs.CR] for this version)   https://doi.org/10.48550/arXiv.2604.09292 Focus to learn more Submission history From: Étienne Burle [view email] [v1] Fri, 10 Apr 2026 13:03:00 UTC (6,660 KB) Access Paper: view license Current browse context: cs.CR < prev   |   next > new | recent | 2026-04 Change to browse by: cs cs.IT math math.IT References & Citations NASA ADS Google Scholar Semantic Scholar Export BibTeX Citation Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer (What is the Explorer?) Connected Papers Toggle Connected Papers (What is Connected Papers?) Litmaps Toggle Litmaps (What is Litmaps?) scite.ai Toggle scite Smart Citations (What are Smart Citations?) Code, Data, Media Demos Related Papers About arXivLabs Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)