Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2412.04848 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909468302770176 |
|---|---|
| author | Caminata, Alessio Cartor, Ryann Meneghetti, Alessio Mora, Rocco Pellegrini, Alex |
| author_facet | Caminata, Alessio Cartor, Ryann Meneghetti, Alessio Mora, Rocco Pellegrini, Alex |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_04848 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Quadratic Modelings of Syndrome Decoding Caminata, Alessio Cartor, Ryann Meneghetti, Alessio Mora, Rocco Pellegrini, Alex Cryptography and Security Optimization and Control 94A60, 08-08 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. |
| title | Quadratic Modelings of Syndrome Decoding |
| topic | Cryptography and Security Optimization and Control 94A60, 08-08 |
| url | https://arxiv.org/abs/2412.04848 |