Improved Upper Bound of Algebraic Degrees for Some Arithmetization-Oriented Ciphers

Recently, the practical applications of advanced cryptographic protocols, such as Multi-Party Computation (MPC), Fully Homomorphic Encryption (FHE), and Zero Knowledge Proofs (ZKP), have spurred the development of a series of new symmetric encryption primitives. These novel symmetric encryption primitives, referred to as Arithmetization-Oriented (AO) ciphers, aim to minimize the number of field multiplications in large finite fields, including F₂n or Fp . In order to evaluate the algebraic degrees of AO ciphers over F₂n, the general monomial prediction technique was proposed by Cui et al. at ASIACRYPT 2022. However, when using their searching tool to evaluate the algebraic degrees of AO ciphers with complex affine layers, the efficiency is low, preventing solutions within a predetermined timeframe. In this study, we extend the propagation rules of monomials for field-based operations and present an automatic searching tool based on Mixed Integer Linear Programming (MILP) and Boolean Satisfiability (SAT) Problem for evaluating the upper bound of the algebraic degrees. Moreover, to accurately calculate the algebraic degrees of monomials in the SAT model, we improve the sequence encoding method, enabling it to accurately determine whether the monomials of degree d exist in the output. We apply our new searching tool to various AO ciphers, including Chaghri, MiMC, and Ciminion. For Chaghri, we compare our results with the Coefficient Grouping technique proposed by Liu et al. at EUROCRYPT 2023, and our results yield tighter upper bounds compared to Liu et al.’s findings. Additionally, we evaluate the algebraic degrees of Chaghri and MiMC with arbitrary complex affine layers and obtain tighter bounds compared to the results from Liu et al. at CRYPTO 2023. Regarding Ciminion, we have observed that starting from the 4-th round, the upper bound on the algebraic degrees for each round actually 1 degree lower than the previous bound. Our searching tool enables a more precise evaluation of the algebraic degrees of AO ciphers, contributing to a deeper understanding of the design and analysis of such primitives.