Arithmetization-Orientation Primitives (AOP): A need for new design and cryptanalysis tools

In recent years, new symmetric primitives have been proposed for advanced protocols such as Multi-Party Computation (MPC), in combination with Fully Homomorphic Encryption (FHE), or in various Zero-Knowledge (ZK) proof systems. Such protocols have put forward the need to minimize the number of multiplications performed by the primitive in large finite fields. Traditional symmetric algorithms are then inappropriate in this context, and the advanced protocols must be combined with new symmetric primitives with particular properties, the so-called "Arithmetization-Oriented Primitives" (AOP).

In this talk, we will present new tools for the design and the cryptanalysis of these new primitives. First, we will introduce a new family of AOP, Anemoi, and its main component, the Flystel, exploiting a previously unknown link with the CCZ-equivalence. While the number of AOP is increasing significantly, only a few cryptanalysis works have been proposed. Therefore, we will also propose a security analysis of one of the first block cipher proposed in this new context, namely MiMC. We will give a detailed understanding of the evolution of the algebraic degree of this cipher.