New polynomial method cuts complexity in binary syndrome decoding problem
Symmetric Models for Syndrome Decoding
Cryptography and Security
Summary
Decoding certain types of error-correcting codes involves solving a hard problem called the Syndrome Decoding Problem. This paper introduces a new mathematical approach using special polynomials that better models this problem and reduces how hard it is to solve. The authors also created a version that adapts to specific problem instances, making it even easier to handle. Their method could potentially be applied to different variants of the same decoding challenge.
What this means in practice
- •For cryptography engineers: Improve algorithms that decode error-correcting codes by using the new polynomial models to solve decoding problems more efficiently.
- •For coding theory developers: Develop software tools for decoding binary error-correcting codes using the new symmetric polynomial approach to reduce computation time.
Authors
Elisa Gorla, Simone Trebiani
Abstract
This paper introduces a new polynomial model for the exact variant of the Syndrome Decoding Problem (SDP) in the binary case. The model is based on elementary symmetric polynomials. We estimate the computational complexity of solving the corresponding polynomial system by establishing bounds on the degree of regularity and on the solving degree of the ideal associated to the model. The complexity estimate is lower than for previous polynomial models. We also provide a variant of the model whose complexity depends directly on the specific instance of the SDP and is lower than for the first model. Finally, we discuss how to apply our approach to solve other variants of the SDP.