Cross-Paradigm Models of Restricted Syndrome Decoding with Application to CROSS
2026-04-10 • Cryptography and Security
Cryptography and SecurityInformation Theory
AI summaryⓘ
The authors study a special decoding problem called Restricted Syndrome Decoding (ResSD), which is important for the security of a cryptographic signature scheme named CROSS. They show that this problem can be connected to known decoding and lattice problems by looking at vectors with certain properties in new codes. This connection gives new ways to attack the problem, which they tested both theoretically and with experiments on smaller versions of CROSS. Their work helps better understand the security of ResSD-based signatures.
Restricted Syndrome Decodinglinear codespost-quantum cryptographyCROSS signature schemeHamming metricEuclidean metricsyndrome decodinglattice problemsClosest Vector Problemcode-based cryptography
Authors
Étienne Burle, Aleksei Udovenko
Abstract
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.