Quadratic Modelings of Syndrome Decoding

Alessio Caminata; Ryann Cartor; Alessio Meneghetti; Rocco Mora; Alex Pellegrini

Paper 2024/1975 Original: eprint.iacr.org/2024/1975 ↗

Quadratic Modelings of Syndrome Decoding

Alessio Caminata

Ryann Cartor

Alessio Meneghetti

Rocco Mora

Alex Pellegrini

Abstract

This paper presents enhanced reductions of the bounded-weight and exact-weight Syndrome Decoding Problem (SDP) to a system of quadratic equations. Over $\mathbb{F}_2$, we improve on a previous work and study the degree of regularity of the modeling of the exact weight SDP. Additionally, we introduce a novel technique that transforms SDP instances over $\mathbb{F}_q$ into systems of polynomial equations and thoroughly investigate the dimension of their varieties. Experimental results are provided to evaluate the complexity of solving SDP instances using our models through Gröbner bases techniques.

Metadata

Available format(s): PDF
Category: Attacks and cryptanalysis
Publication info: Preprint.
History: 2025-01-28: last updated; 2024-12-06: published
Short URL: https://ia.cr/2024/1975
License: https://creativecommons.org/licenses/by/4.0/

BibTeX

@misc{cryptoeprint:2024/1975,
      author = {Alessio Caminata and Ryann Cartor and Alessio Meneghetti and Rocco Mora and Alex Pellegrini},
      title = {Quadratic Modelings of Syndrome Decoding},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/1975},
      year = {2024},
      url = {https://eprint.iacr.org/2024/1975}
}