Paper 2024/886

A New Security Evaluation Method Based on Resultant for Arithmetic-Oriented Algorithms

Abstract

The rapid development of advanced cryptographic applications like multi-party computation (MPC), fully homomorphic encryption (FHE), and zero-knowledge (ZK) proofs have motivated the designs of the so-called arithmetic-oriented (AO) primitives. Efficient AO primitives typically build over large fields and use large S-boxes. Such design philosophy brings difficulties in the cryptanalysis of these primitives as classical cryptanalysis methods do not apply well. The generally recognized attacks against these primitives are algebraic attacks, especially Groebner basis attacks. Thus, the numbers of security rounds are usually derived through the complexity of solving the system of algebraic equations using Groebner bases. In this paper, we propose a novel framework for algebraic attacks against AO primitives. Instead of using Groebner basis, we use resultants to solve a system of multivariate equations that can better exploit the algebraic structures of AO primitives. We employ several techniques to reduce the dimensions of the resultants and avoid rapid increases in degrees, including meet-in-the-middle modeling, variable substitutions, and fast Lagrange interpolation. We apply our attack to three mainstream AO cryptographic primitives: Rescue-Prime, Anemoi, and Jarvis. For Rescue-Prime, we theoretically prove that the final univariate equation has a degree of at most a specific power of three and practically attack five rounds for the first time. We attack the full-round of Anemoi with complexity 2^110.10, which has been claimed to provide 127 bits of security. We also give the first practical attack against eight rounds of Anemoi over a 55-bit prime field. For Jarvis, we improve the existing practical attack by a factor of 100. Therefore, we point out that our analysis framework can be used as a new evaluation method for AO designs.