Quadratic Modelings of Syndrome Decoding

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

Quadratic Modelings of Syndrome Decoding

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

Coding Theory and Cryptology

Research output: Working paper › Preprint › Academic

Abstract

This paper presents enhanced reductions of the bounded-weight and exact-weight Syndrome Decoding Problem (SDP) to a system of quadratic equations. Over F₂, 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 Fq
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.

Original language	English
Publication status	Submitted - 2024

Publication series

Name	IACR Cryptology ePrint Archive
Publisher	IACR

Keywords

Syndrome Decoding
Multivariate cryptography
Groebner basis
Degree of regularity
Solving degree

Access to Document

https://ia.cr/2024/1975Licence: CC0

Cite this

@techreport{e4abdef74787481084fee53d205b84bf,

title = "Quadratic Modelings of Syndrome Decoding",

abstract = "This paper presents enhanced reductions of the bounded-weight and exact-weight Syndrome Decoding Problem (SDP) to a system of quadratic equations. Over F2, 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 Fq 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{\"o}bner bases techniques.",

keywords = "Syndrome Decoding, Multivariate cryptography, Groebner basis, Degree of regularity, Solving degree",

author = "Alex Pellegrini and Alessio Caminata and Ryann Cartor and Rocco Mora and Alessio Meneghetti",

year = "2024",

language = "English",

series = "IACR Cryptology ePrint Archive",

publisher = "IACR",

type = "WorkingPaper",

institution = "IACR",

}

TY - UNPB

T1 - Quadratic Modelings of Syndrome Decoding

AU - Pellegrini, Alex

AU - Caminata, Alessio

AU - Cartor, Ryann

AU - Mora, Rocco

AU - Meneghetti, Alessio

PY - 2024

Y1 - 2024

N2 - This paper presents enhanced reductions of the bounded-weight and exact-weight Syndrome Decoding Problem (SDP) to a system of quadratic equations. Over F2, 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 Fq 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.

AB - This paper presents enhanced reductions of the bounded-weight and exact-weight Syndrome Decoding Problem (SDP) to a system of quadratic equations. Over F2, 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 Fq 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.

KW - Syndrome Decoding

KW - Multivariate cryptography

KW - Groebner basis

KW - Degree of regularity

KW - Solving degree

M3 - Preprint

T3 - IACR Cryptology ePrint Archive

BT - Quadratic Modelings of Syndrome Decoding

ER -

Quadratic Modelings of Syndrome Decoding

Abstract

Publication series

Keywords

Access to Document

Fingerprint

Cite this