International Association
for Cryptologic Research

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 Gr\"obner basis attacks. Thus, the numbers of security rounds are usually derived through the complexity of solving the system of algebraic equations using Gr\"obner bases. In this paper, we propose a novel framework for algebraic attacks against AO primitives. Instead of using Gr\"obner basis, we use {\it resultants} to solve a system of multivariate equations that can better exploit the algebraic structures of AO primitives. We employ several techniques to redu