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

• URL: http://arxiv.org/abs/2506.09950v1
• Date: Wed, 11 Jun 2025 17:18:25 GMT
• Title: Oracle-Based Multistep Strategy for Solving Polynomial Systems Over Finite Fields and Algebraic Cryptanalysis of the Aradi Cipher
• Authors: La Scala Roberto, Sharwan Kumar Tiwari,
• Abstract summary: We present a new implementation of the corresponding algorithm based on a Depth-First Search strategy.<n>We apply the multistep solving strategy to the cryptanalysis of the low-latency block cipher Aradi.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• 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 implementation of the corresponding algorithm based on a Depth-First Search strategy, along with a novel complexity analysis leveraging tree structures. We further introduce the notion of an "oracle function" as a general predictive tool for deciding whether the evaluation of a new variable is necessary 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 apply the multistep solving strategy to the cryptanalysis of the low-latency block cipher Aradi, recently introduced by the NSA. We present the first full round algebraic attack, raising concerns about the cipher's actual security with respect to its key length.

Related papers

• Post-Quantum Cryptography: An Analysis of Code-Based and Lattice-Based Cryptosystems [55.49917140500002]
  Quantum computers will be able to break modern cryptographic systems using Shor's Algorithm.<n>We first examine the McEliece cryptosystem, a code-based scheme believed to be secure against quantum attacks.<n>We then explore NTRU, a lattice-based system grounded in the difficulty of solving the Shortest Vector Problem.
  arXiv  Detail & Related papers  (2025-05-06T03:42:38Z)
• VLWE: Variety-based Learning with Errors for Vector Encryption through Algebraic Geometry [1.3824176915623292]
  Lattice-based cryptography is a foundation for post-quantum security.<n>This work introduces Variety-LWE (VLWE), a new structured lattice problem based on algebraic geometry.<n>We prove VLWE's security by reducing it to multiple independent instances, demonstrating resilience against classical and quantum attacks.
  arXiv  Detail & Related papers  (2025-02-11T06:04:24Z)
• Cryptanalysis via Machine Learning Based Information Theoretic Metrics [58.96805474751668]
  We propose two novel applications of machine learning (ML) algorithms to perform cryptanalysis on any cryptosystem.<n>These algorithms can be readily applied in an audit setting to evaluate the robustness of a cryptosystem.<n>We show that our classification model correctly identifies the encryption schemes that are not IND-CPA secure, such as DES, RSA, and AES ECB, with high accuracy.
  arXiv  Detail & Related papers  (2025-01-25T04:53:36Z)
• From Exponential to Polynomial Complexity: Efficient Permutation Counting with Subword Constraints [0.0]
  Counting distinct permutations with replacement, especially when involving multiple subwords, is a longstanding challenge in analysis. This paper introduces a novel framework that presents closed-form formulas for calculating distinct permutations with replacement. We then extend our foundational formula to handle multiple subwords through the development of an additional formula.
  arXiv  Detail & Related papers  (2024-11-23T19:52:11Z)
• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  In this work, we present a robust phase retrieval problem where the task is to recover an unknown signal. Our proposed oracle avoids the need for computationally spectral descent, using a simple gradient step and outliers.
  arXiv  Detail & Related papers  (2024-09-07T06:37:23Z)
• Complementary polynomials in quantum signal processing [0.0]
  To implement a given $P$, one must first construct a corresponding complementary $Q$. Existing approaches to this problem employ numerical methods that are not amenable to explicit error analysis. We present a new approach to complementarys using complex analysis.
  arXiv  Detail & Related papers  (2024-06-06T16:47:11Z)
• Modeling Linear and Non-linear Layers: An MILP Approach Towards Finding Differential and Impossible Differential Propagations [1.5327660568487471]
  We introduce an automatic tool for exploring differential and impossible propagations within a cipher. The tool is successfully applied to five lightweight block ciphers: Lilliput, GIFT64, SKINNY64, Klein, and M.IBS.
  arXiv  Detail & Related papers  (2024-05-01T10:48:23Z)
• A Neural Rewriting System to Solve Algorithmic Problems [47.129504708849446]
  We propose a modular architecture designed to learn a general procedure for solving nested mathematical formulas. Inspired by rewriting systems, a classic framework in symbolic artificial intelligence, we include in the architecture three specialized and interacting modules. We benchmark our system against the Neural Data Router, a recent model specialized for systematic generalization, and a state-of-the-art large language model (GPT-4) probed with advanced prompting strategies.
  arXiv  Detail & Related papers  (2024-02-27T10:57:07Z)
• A multistep strategy for polynomial system solving over finite fields and a new algebraic attack on the stream cipher Trivium [0.3749861135832073]
  We present an implementation of this strategy in an algorithm called Multi which is designed for systems having at most one solution. We prove that an optimal complexity of Multi is achieved by using a full multistep strategy with a maximum number of steps and in turn the standard guess-and-determine strategy, which essentially is a strategy consisting of a single step, is the worst choice.
  arXiv  Detail & Related papers  (2023-04-16T16:09:14Z)
• Multi-Phase Relaxation Labeling for Square Jigsaw Puzzle Solving [73.58829980121767]
  We present a novel method for solving square jigsaw puzzles based on global optimization. The method is fully automatic, assumes no prior information, and can handle puzzles with known or unknown piece orientation.
  arXiv  Detail & Related papers  (2023-03-26T18:53:51Z)
• Optimal Gradient-based Algorithms for Non-concave Bandit Optimization [76.57464214864756]
  This work considers a large family of bandit problems where the unknown underlying reward function is non-concave. Our algorithms are based on a unified zeroth-order optimization paradigm that applies in great generality. We show that the standard optimistic algorithms are sub-optimal by dimension factors.
  arXiv  Detail & Related papers  (2021-07-09T16:04:24Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  We investigate the problem of best-policy identification in discounted Markov Decision (MDPs) when the learner has access to a generative model. The advantages of state-of-the-art algorithms are discussed and illustrated.
  arXiv  Detail & Related papers  (2020-09-28T15:22:24Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.