The complexity of solving a system of equations of the same degree
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911409463361536 |
|---|---|
| author | Gaggero, Giulia Gorla, Elisa |
| author_facet | Gaggero, Giulia Gorla, Elisa |
| contents | Many systems of interest in cryptography consist of equations of the same degree. Under the assumption that the degree of regularity is finite, we prove upper bounds on the degree of regularity of a system of equations of the same degree, with or without adding the field equations to the system. The bounds translate into upper bounds on the solving degree of the systems, and hence on the complexity of solving them via Gröbner bases methods. Our bounds depend on the number of equations in the system, the number of variables, and the degree of the equations. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2309_03855 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | The complexity of solving a system of equations of the same degree Gaggero, Giulia Gorla, Elisa Cryptography and Security Algebraic Geometry Combinatorics Many systems of interest in cryptography consist of equations of the same degree. Under the assumption that the degree of regularity is finite, we prove upper bounds on the degree of regularity of a system of equations of the same degree, with or without adding the field equations to the system. The bounds translate into upper bounds on the solving degree of the systems, and hence on the complexity of solving them via Gröbner bases methods. Our bounds depend on the number of equations in the system, the number of variables, and the degree of the equations. |
| title | The complexity of solving a system of equations of the same degree |
| topic | Cryptography and Security Algebraic Geometry Combinatorics |
| url | https://arxiv.org/abs/2309.03855 |