Oracle-Based Multistep Strategy for Solving Polynomial Systems Over Finite Fields and Algebraic Cryptanalysis of the Aradi Cipher
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_ | 1866917294544781312 |
|---|---|
| author | La Scala, Roberto Tiwari, Sharwan Kumar |
| author_facet | La Scala, Roberto Tiwari, Sharwan Kumar |
| contents | The multistep solving strategy consists in a divide-and-conquer approach: when a multivariate polynomial system is computationally infeasible to solve directly, one variable is assigned over the elements of the base finite field, and the procedure is recursively applied to the resulting simplified systems. In a previous work by the same authors (among others), this approach proved effective in the algebraic cryptanalysis of the Trivium cipher. In this paper, we present a new formulation of the corresponding algorithm based on a Depth-First Search strategy, along with a novel complexity analysis leveraging tree structures. We also introduce the notion of an ``oracle function'', which is intended to determine whether evaluating a new variable is required to simplify the current polynomial system. This notion allows us to unify all previously proposed variants of the multistep strategy, including the classical hybrid approach, by appropriately selecting the oracle function. Finally, we employ the multistep solving strategy in the cryptanalysis of the NSA's recently introduced low-latency block cipher Aradi, achieving a first full-round algebraic attack that exposes structural features in its symbolic model. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_09950 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Oracle-Based Multistep Strategy for Solving Polynomial Systems Over Finite Fields and Algebraic Cryptanalysis of the Aradi Cipher La Scala, Roberto Tiwari, Sharwan Kumar Cryptography and Security Symbolic Computation Commutative Algebra The multistep solving strategy consists in a divide-and-conquer approach: when a multivariate polynomial system is computationally infeasible to solve directly, one variable is assigned over the elements of the base finite field, and the procedure is recursively applied to the resulting simplified systems. In a previous work by the same authors (among others), this approach proved effective in the algebraic cryptanalysis of the Trivium cipher. In this paper, we present a new formulation of the corresponding algorithm based on a Depth-First Search strategy, along with a novel complexity analysis leveraging tree structures. We also introduce the notion of an ``oracle function'', which is intended to determine whether evaluating a new variable is required to simplify the current polynomial system. This notion allows us to unify all previously proposed variants of the multistep strategy, including the classical hybrid approach, by appropriately selecting the oracle function. Finally, we employ the multistep solving strategy in the cryptanalysis of the NSA's recently introduced low-latency block cipher Aradi, achieving a first full-round algebraic attack that exposes structural features in its symbolic model. |
| title | Oracle-Based Multistep Strategy for Solving Polynomial Systems Over Finite Fields and Algebraic Cryptanalysis of the Aradi Cipher |
| topic | Cryptography and Security Symbolic Computation Commutative Algebra |
| url | https://arxiv.org/abs/2506.09950 |