In recent years, new symmetric primitives have been proposed to be executed in abstract contexts such as Zero-Knowledge proof systems (ZK), widely used in crypto- currency applications. ZK protocols are algorithms involving several parties that allow a prover to convince a verifier that he knows a secret without revealing it. In particular, these protocols have highlighted the need to minimise the number of multiplications performed by the primitive in large finite fields. As the number of the so-called Arithmetization-Oriented (AO) designs increases, it is important to better understand the properties of their underlying operations.
In this presentation, we will propose two perspectives. First, we will investigate the security of MiMC, one of the first such block ciphers, against higher-order differential attacks, for which the complexity decreases with the multivariate degree (aka algebraic degree). MiMC consists of many iterations of a simple round function: the addition of a key and round constants and a low-degree power permutation (usually the cube). We will show that, while the univariate degree increases predictably with the number of rounds, the multivariate degree has a much more complex behaviour, and simply stays constant during some rounds. We will also exhibit some specific power functions for which the univariate polynomial representation is sparse and then allows us to propose a more theoretical analysis of the multivariate degree.
Then, we will switch to the designer's point of view to propose a family of hash functions: Anemoi, exploiting a link, previously unknown, between AO primitives and CCZ-equivalence. Besides pushing the limits in understanding the principles behind AO hash functions, we will also offer one standalone component that can be easily reused in other designs: a new S-box, the Flystel, highly inspired by the well-studied Butterfly structure. We will see how the CCZ-equivalence between its two variants (the Open Flystel and the Closed Flystel) leads to good ZK performances and high security level.