The regular multivariate quadratic problem
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913728052592640 |
|---|---|
| author | Joux, Antoine Mora, Rocco |
| author_facet | Joux, Antoine Mora, Rocco |
| contents | In this work, we introduce a novel variant of the multivariate quadratic problem, which is at the core of one of the most promising post-quantum alternatives: multivariate cryptography. In this variant, the solution of a given multivariate quadratic system must also be regular, i.e. if it is split into multiple blocks of consecutive entries with the same fixed length, then each block has only one nonzero entry. We prove the NP-completeness of this variant and show similarities and differences with other computational problems used in cryptography. Then we analyze its hardness by reviewing the most common solvers for polynomial systems over finite fields, derive asymptotic formulas for the corresponding complexities and compare the different approaches. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_07342 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The regular multivariate quadratic problem Joux, Antoine Mora, Rocco Symbolic Computation In this work, we introduce a novel variant of the multivariate quadratic problem, which is at the core of one of the most promising post-quantum alternatives: multivariate cryptography. In this variant, the solution of a given multivariate quadratic system must also be regular, i.e. if it is split into multiple blocks of consecutive entries with the same fixed length, then each block has only one nonzero entry. We prove the NP-completeness of this variant and show similarities and differences with other computational problems used in cryptography. Then we analyze its hardness by reviewing the most common solvers for polynomial systems over finite fields, derive asymptotic formulas for the corresponding complexities and compare the different approaches. |
| title | The regular multivariate quadratic problem |
| topic | Symbolic Computation |
| url | https://arxiv.org/abs/2503.07342 |