I am currently working on symmetric cryptography, and more specifically, my main research interest is the cryptanalysis of arithmetization-oriented symmetric primitives. In particular, I've been trying to better understand the mathematical properties of such primitives. During my PhD, I've also had the opportunity to design Anemoi, exploiting a link between arithmetization-orientation and CCZ equivalence.

Publications

Journals

• On the Algebraic Degree of Iterated Power Functions - Designs, Codes and Cryptography, 2023
  Clémence Bouvier, Anne Canteaut and Léo Perrin
  [abstract] [Springer] [ePrint] [extended-abstract-WCC]

  
  

  New symmetric primitives are being designed to address a novel set of design criteria. Instead of being executed on regular processors or smartcards, they are instead intended to be run in abstract settings such as multi-party computations or zero-knowledge proof systems. This implies in particular that these new primitives are described using operations over large finite fields. As the number of such primi- tives grows, it is important to better understand the properties of their underlying operations.
  In this paper, we investigate the algebraic degree of one of the first such block ciphers, namely MiMC. It is composed of many iterations of a simple round function, which consists of an addition and of a low-degree power permutation applied to the full state, usually $x \mapsto x^3$. We show in particular that, while the univariate degree increases predictably with the number of rounds, the algebraic degree (a.k.a multivariate degree) has a much more complex behaviour, and simply stays constant during some rounds. Such plateaus slightly slow down the growth of the algebraic degree.
  We present a full investigation of this behaviour. First, we prove some lower and upper bounds for the algebraic degree of an arbitrary number of iterations of MiMC and of its inverse. Then, we combine theoretical arguments with simulations to prove that the upper bound is tight for up to 16265 rounds. Using these results, we slightly improve the higher-order differential attack presented at Asiacrypt 2020 to cover one or two more rounds. More importantly, our results provide some precise guarantees on the algebraic degree of this cipher, and then on the minimal complexity for a higher-order differential attack.



• Algebraic Attacks against Some Arithmetization-Oriented Primitives - IACR Transactions on Symmetric Cryptology, 2022(3)
  Augustin Bariant, Clémence Bouvier, Gaëtan Leurent and Léo Perrin
  [abstract] [ToSC]

  
  

  Recent advanced Zero-Knowledge protocols, along with other high-level constructions such as Multi-Party Computations (MPC), have highlighted the need for a new type of symmetric primitives that are not optimized for speed on the usual platforms (desktop computers, servers, microcontrollers, RFID tags...), but for their ability to be implemented using arithmetic circuits.
  Several primitives have already been proposed to satisfy this need. In order to enable an efficient arithmetization, they operate over large finite fields, and use round functions that can be modelled using low degree equations. The impact of these properties on their security remains to be completely assessed. In particular, algebraic attacks relying on polynomial root-finding become extremely relevant. Such attacks work by writing the cryptanalysis as systems of polynomial equations over the large field, and solving them with off-the-shelf tools (SageMath, NTL, Magma, ...). The need for further analysis of these new designs has been recently highlighted by the Ethereum Foundation, as it issued bounties for successful attacks against round-reduced versions of several of them.
  In this paper, we show that the security analysis performed by the designers (or challenge authors) of four such primitives is too optimistic, and that it is possible to improve algebraic attacks using insights gathered from a careful study of the round function.
  First, we show that univariate polynomial root-finding can be of great relevance in practice, as it allows us to solve many of the Ethereum Foundation’s challenges on Feistel–MiMC. Second, we introduce a trick to essentially shave off two full rounds at little to no cost for Substitution-Permutation Networks (SPN). This can be combined with univariate (resp. multivariate) root-finding, which allowed to solve some challenges for Poseidon (resp. Rescue–Prime). Finally, we also find an alternative way to set up a system of equations to attack Ciminion, leading to much faster attacks than expected by the designers.

Conferences

• New Design Techniques for Efficient Arithmetization-Oriented Hash Functions: Anemoi Permutations and Jive Compression Mode - Crypto 2023
  Clémence Bouvier, Pierre Briaud, Pyrros Chaidos, Léo Perrin, Robin Salen, Vesselin Velichkov and Danny Willems
  [abstract] [Springer] [ePrint] [GitHub] [webpage]

  
  

  Advanced cryptographic protocols such as Zero-knowledge (ZK) proofs of knowledge, widely used in cryptocurrency applications such as Zcash, Monero, Filecoin, Tezos, Topos, demand new cryptographic hash functions that are efficient not only over the binary field $\mathbb{F}_2$, but also over large fields of prime characteristic $\mathbb{F}_p$. This need has been acknowledged by the wider community and new so-called Arithmetization-Oriented (AO) hash functions have been proposed, e.g. MiMC-Hash, Rescue-Prime, Poseidon, Reinforced Concrete and Griffin to name a few.
  In this paper we propose Anemoi: a new family of ZK-friendly permutations, that can be used to construct efficient hash functions and compression functions. The main features of these algorithms are that 1) they are designed to be efficient within multiple proof systems (e.g. Groth16, Plonk, etc.), 2) they contain dedicated functions optimised for specific applications (namely Merkle tree hashing and general purpose hashing), 3) they have highly competitive performance e.g. about a factor of 2 improvement over Poseidon and Rescue-Prime in terms of R1CS constraints, a 21%-35% Plonk constraint reduction over a highly optimized Poseidon implementation, as well as competitive native performance, running between two and three times faster than Rescue-Prime, depending on the field size.
  On the theoretical side, Anemoi pushes further the frontier in understanding the design principles that are truly entailed by arithmetization-orientation. In particular, we identify and exploit a previously unknown relationship between CCZ-equivalence and arithmetization-orientation. In addition, we propose two new standalone components that can be easily reused in new designs. One is a new S-box called Flystel, based on the well-studied butterfly structure, and the second is Jive -- a new mode of operation, inspired by the ``Latin dance'' symmetric algorithms (Salsa, ChaCha and derivatives). Our design is a conservative one: it uses a very classical Substitution-Permutation Network structure, and our detailed analysis of algebraic attacks highlights can be of independent interest.



• Coefficient Grouping for Complex Affine Layers - Crypto 2023
  Fukang Liu, Lorenzo Grassi, Clémence Bouvier, Willi Meier, Takanori Isobe
  [abstract] [Springer] [ePrint]

  
  

  Designing symmetric-key primitives for applications in Fully Homomorphic Encryption (FHE) has become important to address the issue of the ciphertext expansion. In such a context, cryptographic primitives with a low-AND-depth decryption circuit are desired. Consequently, quadratic nonlinear functions are commonly used in these primitives, including the well-known $\chi$ function over $\mathbb{F}_2^n$ and the power map over a large finite field $\mathbb{F}_{p^n}$. In this work, we study the growth of the algebraic degree for an SPN cipher over $\mathbb{F}_{2^n}^m$, whose S-box is defined as the combination of a power map $x \mapsto x^{2^d+1}$ and an $\mathbb{F}_2$-linearized affine polynomial $x \mapsto c_0 + \sum_{i=1}^w c_i x^{2^{h_i}}$ where $c_1, \ldots, c_w \neq 0$. Specifically, motivated by the fact that the original coefficient grouping technique published at EUROCRYPT 2023 becomes less efficient for $w > 1$, we develop a variant technique that can efficiently work for arbitrary $w$. With this new technique to study the upper bound of the algebraic degree, we answer the following questions from a theoretic perspective:
  1. can the algebraic degree increase exponentially when $w=1$?
  2. what is the influence of $w$, $d$ and $(h_1, \ldots h_w)$ on the growth of the algebraic degree?
  Based on this, we show (i) how to efficiently find $(h_1, \ldots h_w)$ to achieve the exponential growth of the algebraic degree and (ii) how to efficiently compute the upper bound of the algebraic degree for arbitrary $(h_1, \ldots h_w)$. Therefore, we expect that these results can further advance the understanding of the design and analysis of such primitives.

Preprints

• Practical Algebraic Attacks against some Arithmetization-oriented Hash Functions - Report
  Augustin Bariant, Clémence Bouvier, Gaëtan Leurent and Léo Perrin
  [abstract] [HAL-Inria]

  
  

  Several challenges have been announced on arithmetization-oriented hash functions, with bounties funded by the Ethereum Foundation. In this note, we report on our work to solve several of these challenges, on Feistel-MiMC, Rescue Prime and Poseidon. Our results are obtained by writing the challenges as systems of polynomial equations over the large field, and solving them with off-the-shelf tools (SageMath, NTL, Magma).

Memoir

• Analyse de la sécurité de primitives symétriques dédiées à diverses techniques de preuves - Master thesis
  Clémence Bouvier
  [HAL-Inria]