Quadratic Modelings of Syndrome Decoding

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

Paper 2024/1975

Quadratic Modelings of Syndrome Decoding

Alessio Caminata

, Università degli Studi di Genova

Ryann Cartor, Clemson University

Alessio Meneghetti, Università di Trento

Rocco Mora, Helmholtz Center for Information Security

Alex Pellegrini, Eindhoven University of Technology

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.
Keywords: syndrome decoding multivariate cryptography Groebner bases degree of regularity solving degree
Contact author(s): alessio caminata @ unige it
rcartor @ clemson edu
Alessio Meneghetti @ unitn it
rocco mora @ cispa de
a pellegrini @ tue nl
History: 2024-12-12: approved; 2024-12-06: received; See all versions
Short URL: https://ia.cr/2024/1975
License: CC BY

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}
}