Symmetric Models for Syndrome Decoding

Elisa Gorla; Simone Trebiani

Paper 2026/1995

Symmetric Models for Syndrome Decoding

Elisa Gorla

, University of Neuchatel

Simone Trebiani

, University of Neuchatel

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 ap- proach to solve other variants of the SDP.

Metadata

Available format(s): PDF
Category: Attacks and cryptanalysis
Publication info: Preprint.
Keywords: Syndrome Decoding Problem Code-based cryptography Solving degree Elementary symmetric polynomials Degree of regularity
Contact author(s): elisa gorla @ unine ch
simone trebiani @ unine ch
History: 2026-09-14: approved; 2026-09-12: received; See all versions
Short URL: https://ia.cr/2026/1995
License: CC BY

BibTeX

@misc{cryptoeprint:2026/1995,
      author = {Elisa Gorla and Simone Trebiani},
      title = {Symmetric Models for Syndrome Decoding},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/1995},
      year = {2026},
      url = {https://eprint.iacr.org/2026/1995}
}