Oracle-Based Multistep Strategy for Solving Polynomial Systems Over Finite Fields and Algebraic Cryptanalysis of the Aradi Cipher

Roberto La Scala; Sharwan K. Tiwari

Paper 2025/1097

Oracle-Based Multistep Strategy for Solving Polynomial Systems Over Finite Fields and Algebraic Cryptanalysis of the Aradi Cipher

Roberto La Scala, Department of Mathematics, University of Bari

Sharwan K. Tiwari, Cryptography Research Centre, Technology Innovation Institute

Abstract

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.

Note: 20 pages

Metadata

Available format(s): PDF
Category: Attacks and cryptanalysis
Publication info: Published elsewhere. Advances in Mathematics of Communications
Keywords: Polynomial system solving Finite fields Cryptanalysis
Contact author(s): roberto lascala @ uniba it
sharwan tiwari @ tii ae
History: 2026-02-26: last of 2 revisions; 2025-06-11: received; See all versions
Short URL: https://ia.cr/2025/1097
License: CC BY-NC-ND

BibTeX

@misc{cryptoeprint:2025/1097,
      author = {Roberto La Scala and Sharwan K. Tiwari},
      title = {Oracle-Based Multistep Strategy for Solving Polynomial Systems Over Finite Fields and Algebraic Cryptanalysis of the Aradi Cipher},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/1097},
      year = {2025},
      url = {https://eprint.iacr.org/2025/1097}
}