Symmetric Models for Syndrome Decoding

A new polynomial model based on elementary symmetric polynomials for the exact binary Syndrome Decoding Problem, with improved complexity bounds and an instance-adaptive variant.

Elisa Gorla; Simone Trebiani· 2026· DOI 10.48550/arXiv.2609.14052

The core problem

The Syndrome Decoding Problem (SDP) is a fundamental problem in coding theory and cryptography, particularly in the context of code-based cryptography. The exact variant of SDP asks to find a vector of a given Hamming weight that satisfies a linear system over a finite field. This paper focuses on the binary case and introduces a new polynomial model for the exact SDP based on elementary symmetric polynomials. The authors aim to provide a model that leads to lower computational complexity for solving the associated polynomial system compared to previous approaches. The paper estimates the complexity by bounding the degree of regularity and the solving degree of the ideal generated by the model's polynomials. Furthermore, they propose a variant whose complexity depends on the specific instance of the SDP, yielding even lower complexity. Finally, they discuss how to apply the approach to other variants of SDP.

The authors establish bounds on the degree of regularity and solving degree for the ideal associated with the new model. They show that these bounds are lower than those for previous polynomial models for the exact binary SDP. Specifically, the complexity estimate for the new model is lower than that of the model based on the Support Minors modeling or the model using the Walsh-Hadamard transform. The exact bounds depend on parameters such as n, r, and w, but the asymptotic behavior indicates an improvement. For the instance-adaptive variant, the complexity is even lower and depends on the specific instance, potentially allowing for more efficient solving in practice. The paper provides theoretical complexity estimates but does not include experimental results; however, the theoretical analysis suggests that the new model is superior to existing ones in terms of the degree of regularity and solving degree.

The Syndrome Decoding Problem (SDP) is a fundamental problem in coding theory and cryptography, particularly in the context of code-based cryptography. The exact variant of SDP asks to find a vector of a given Hamming weight that satisfies a linear system over a finite field. This paper focuses on the binary case and introduces a new polynomial model for the exact SDP based on elementary symmetric polynomials. The authors aim to provide a model that leads to lower computational complexity for solving the associated polynomial system compared to previous approaches. The paper estimates the complexity by bounding the degree of regularity and the solving degree of the ideal generated by the model's polynomials. Furthermore, they propose a variant whose complexity depends on the specific instance of the SDP, yielding even lower complexity. Finally, they discuss how to apply the approach to other variants of SDP.

The authors construct a polynomial system whose solutions correspond to the solutions of the exact binary SDP. The model is based on elementary symmetric polynomials. Let H \in F_{2}^{r \times n} be a parity-check matrix and s \in F_{2}^{r} a syndrome. The exact SDP asks for e \in F_{2}^{n} with He = s and wt (e) = w . The new model introduces variables representing the elementary symmetric polynomials of the error vector. Specifically, for i = 1, \dots, w, let σ_{i} denote the i -th elementary symmetric polynomial evaluated at the support of e . The model consists of:

The new model leverages the structure of elementary symmetric polynomials to create a polynomial system with lower degree of regularity. This is achieved by introducing variables that capture the symmetric properties of the error vector, reducing the number of high-degree equations. The instance-adaptive variant further tailors the model to the specific SDP instance, potentially by incorporating additional information about the syndrome or the parity-check matrix. The authors discuss how the approach can be extended to other variants of SDP, such as the case where the weight is not fixed or the field is not binary. The complexity estimates are based on the assumption that the polynomial system is solved using Gröbner basis algorithms, and the bounds on the solving degree directly translate to the complexity of these algorithms. The paper concludes that the new models offer a significant improvement over previous polynomial models for the exact binary SDP, and the instance-adaptive variant is particularly promising for practical applications. Future work includes experimental validation and further optimizations.

CS practitioners and researchers

Opening member content…