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

International 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]

  
  

  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.

International Conferences with proceedings

• 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.

International Conferences and Workshops

• Iterated Power Functions: from Univariate Polynomial Representation to Multivariate Degree - International Conference on Finite Fields and Their Applications, 2023
  Clémence Bouvier, Anne Canteaut and Léo Perrin
  [abstract]

  
  

  Recently many symmetric primitives have been proposed for use in new contexts, such as Multi-Party Computation or Zero-Knowledge Proofs. Our aim is to investigate the security of MiMC against higher-order differential attacks for which the complexity decreases with the multivariate 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 of $\mathbb{F}_{2^n}$, where $n \approx 129$.
  In light of previous work, we carefully study families of exponents appearing or not in the univariate polynomial representation of the block cipher. For instance, we show that for Gold function $x \mapsto x^d$, with $d = 2^j + 1$, the exponents are necessary equal to 0 or 1 modulo $2^j$ , leading to very sparse polynomials for large j. This observation then allows us to propose a more theoretical analysis of the multivariate degree. Overall, we provide a detailed comparison of different instances of MiMC and show that at least one fourth of the exponents never appear in the univariate representation of the cipher.



• Anemoi and Jive : New Arithmetization-Oriented tools for Plonk-based applications - Zero-Knowledge Proofs, 2022
  Clémence Bouvier, Danny Willems
  [abstract]

  
  

  In recent years, new symmetric primitives have been designed to be executed in abstract contexts such as Zero-Knowledge (ZK) proof systems, widely used in crypto-currency applications such as Zcash or Ethereum. 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, e.g. MiMC-Hash, Rescue–Prime, Poseidon, Reinforced Concrete and Griffin to name a few, it is important to better understand the properties of their underlying operations.
  In this talk, we present a family of hash functions: Anemoi, exploiting a link, previously unknown, between AO primitives and CCZ-equivalence. One of the main features that set Anemoi apart from other such families is that it has been designed to be efficient within multiple proof systems (R1CS, Plonk, AIR, etc.) but it has particularly competitive performance for implementation in Plonk constraints (up to 29% constraint reduction in standard Plonk over the most efficient existing primitive Griffin and 28%-48% over a highly optimized Poseidon implementation with custom gates) as well as competitivenative performance, running between two and three times faster than Rescue–Prime, depending on the field size.
  Besides pushing further the frontier in understanding the design principles behind AO hash functions, we also offer two standalone components that can be easily reused in new designs. Namely, we propose a new S-box, called Flystel and a new mode of operation – Jive. We demonstrate that the CCZ-equivalence between the two variants of the Flystel S-box, resp. the Open Flystel and the Closed Flystel, leads to competitive performance and high security in ZK applications. As to the Jive mode of operation, it is designed specifically for application in Merkle trees, where it offers significant improvement in performance. As the name suggests, it is inspired by the “Latin dance” symmetric algorithms (Salsa, ChaCha and derivatives).



• New Approach for Arithmetization-Oriented Symmetric Primitives - CrossFyre, 2022
  Clémence Bouvier
  [abstract]

  
  

  In recent years, new symmetric primitives have been designed to be executed in abstract contexts such as Zero-Knowledge (ZK) proof systems, widely used in crypto-currency applications such as Bitcoin or Ethereum. 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, e.g. MiMC-Hash, Rescue–Prime, Poseidon, Reinforced Concrete and Griffin to name a few, it is important to better understand the properties of their underlying operations.
  After introducing the background and explaining the need to design new primitives, we will present a new approach to ZK-friendliness. More precisely, we will propose a family of hash functions: Anemoi, exploiting a link, previously unknown, between AO primitives and CCZ-equivalence. One of the main features that set Anemoi apart from other such families is that it has been designed to be efficient within multiple proof systems (R1CS, Plonk, AIR, etc.) but it has particularly competitive performance for implementation in Plonk constraints.
  Besides pushing further the frontier in understanding the design principles behind AO hash functions, we also offer two standalone components that can be easily reused in new designs. Our new S-box: the Flystel, is 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. We will also describe a new mode of operation for Merkle trees: Jive, inspired by the “Latin dance” symmetric algorithms (Salsa, ChaCha and derivatives).



• On the Algebraic Degree of Iterated Power Functions - Workshop on Coding and Cryptography, 2022
  Clémence Bouvier, Anne Canteaut and Léo Perrin
  [abstract] [extended-abstract]

  
  

  New symmetric primitives intended to be run in abstract settings such as multi-party computations are being designed to use operations over large finite fields. In this work, 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$ over a large field with characteristic 2. We show that, while the univariate degree increases predictably with the number of rounds, the algebraic degree has a much more complex behaviour, and simply stays constant during some rounds. We present a full investigation of such plateaus that slightly slow down the growth of the algebraic degree. Using these results, we slightly improve the higher-order differential attack presented by the authors of MiMC to cover one or two more rounds. More importantly, our results provide some precise guarantee on the algebraic degree of this cipher, and then on the minimal complexity for a higher-order differential attack.

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).

Thesis

• Cryptanalysis and design of symmetric primitives defined over large finite fields - PhD thesis
  Clémence Bouvier
  [abstract] [HAL-Inria]

  
  

  In recent years, new symmetric cryptographic primitives have been proposed for advanced protocols, like multi-party computation, in combination with a fully homomorphic encryption or in various systems of zero-knowledge proofs. Such protocols are parts of a context marked by the development of cloud and blockchain technologies, and must therefore respond to the growing security concerns of users.
  These protocols have put forward the need to minimize the number of multiplications performed by the primitive in large finite fields. Classical symmetric algorithms are then inappropriate in this context and the new cryptographic protocols must be combined with symmetric primitives (encryption or hash function) with particular properties.
  While the number of designs defined over large fields, called “arithmetization-oriented”, is increasing significantly, few cryptanalysis works have been proposed. The first aim of this manuscript is then to contribute to fill this gap, and hence to better understand the specificities of these new objects. We also propose a new vision to design such primitives, covering both aspects of cryptology, the cryptography and the cryptanalysis.



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

Talks

International Conferences and Workshops

• Crypto 2023 - New Design Techniques for Efficient Arithmetization-Oriented Hash Functions: Anemoi Permutations and Jive Compression Mode.
  Santa Barbara, United-States, August 22nd, 2023
  [slides] [video] [website]
  


• Fq15 - Iterated Power Functions: from Univariate Polynomial Representation to Multivariate Degree.
  Aubervilliers, France, June 20th, 2023
  [slides] [website]
  


• FSE 2023 - Algebraic Attacks against Some Arithmetization-Oriented Primitives.
  Kobe, Japan, March 23rd, 2023
  [slides] [video] [website]
  


• ZKProof5 - Anemoi and Jive: New Arithmetization-Oriented tools for Plonk-based applications.
  Tel Aviv, Israel, November 16th, 2022
  [slides] [video] [website]
  


• CrossFyre 2022 - A New Approach for Arithmetization-Oriented Symmetric Primitives
  Passau, Germany, October 7th, 2022
  [slides] [website]
  
  
  
• WCC 2022 - On the Algebraic Degree of Iterated Power Functions
  Virtual (Rostock, Germany), March 7th, 2022
  [slides] [website]
  

National Conferences and Workshops

• Journées C2 2023 - Anemoi: Exploiting the Link between Arithmetization-Orientation and CCZ-equivalence
  Najac, France, October 19th, 2022
  [slides] [website]
  


• Journées C2 2022 - On the Algebraic Degree of Iterated Power Functions
  Hendaye, France, April 11th, 2022
  [slides] [website]
  

Lectures

• Invited Lecture for master and graduate students - Mathematical tools to design and analyze the security of Arithmetization-Oriented symmetric primitives.
  Rostock, Germany, June 7th, 2023
  [slides]
  

Seminars

• ECO Seminar - On the new generation of symmetric primitives: the AOP (Arithmetization-Oriented Primitives)
  Montpellier, France, March, 2024
  [slides] [website]
  


• CAS3C3 Seminar - Arithmetization-Oriented Primitives (AOP): A need for new design and cryptanalysis tools
  Grenoble, France, January, 2024
  [slides] [website]
  


• ALMASTY Seminar - New tools for designing and analysing MPC/FHE/ZK-friendly primitives
  Paris, France, December, 2023
  [slides] [website]
  


• CARAMBA Seminar - Cryptanalysis and design of Arithmetization-Oriented primitives
  Nancy, France, December, 2023
  [slides] [website]
  


• COSINUS Seminar - Arithmetization-Oriented symmetric primitives: from Cryptanalysis to Design.
  Bergen, Norway, June, 2023
  [slides]
  


• Bochum Seminar - Design and Cryptanalysis of Arithmetization-Oriented Primitives.
  Bochum, Germany, May 15th, 2023
  [slides]
  
  
  
• MDCC Seminar (Paris 8) - Arithmetization-Oriented primitives: A need for mathematical tools.
  Paris, France, October 20th, 2022
  [slides] [website]
  


• IAIK Crypto Seminar - Backstages of Anemoi: A new approach to ZK-friendliness.
  Graz, Austria, August 29th, 2022
  [slides]
  


• LAREMA Seminar - New uses in Symmetric Cryptography: An equation between Practical needs and Mathematical concepts
  Angers, France, June 23rd, 2022
  [slides] [website]
  


• Rennes Crypto Seminar - New uses in Symmetric Cryptography: from Cryptanalysis to Design
  Rennes, France, May 20th, 2022
  [slides] [website]
  


• COSMIQ Seminar - Algebraic properties of the MiMC block cipher
  Virtual (Inria, Paris, France), December 16th, 2020
  [slides]
  

Rump Sessions

• FSE 2022 - Auld Alliance is back
  Athens, Greece, March 23rd, 2022
  [slides] [video] [website]
  


• Eurocrypt 2021 - Let's play music with MiMC
  Zagreb, Croatia, October 19th, 2021
  [slides] [video] [website]
  

Defense

• PhD defense - Cryptanalysis and design of symmetric primitives defined over large finite fields.
  Paris, France, November 27th, 2023
  [slides]
  


• Master defense - Analyse de la sécurité de primitives symétriques dédiées à diverses techniques de preuves.
  Rennes, France, September 2nd, 2020
  [slides]
  

Doctoral school meetings

• Journées EDITE 2023 - Cryptanalyse et conception de primitives symétriques définies sur de grands corps finis.
  Paris, France, December 11th, 2023
  


• Journées EDITE 2022 - Primitives cryptographiques conçues pour des usages émergents.
  Paris, France, November 30th, 2022
  

Awards and Prizes

• 2nd Prize from EDITE - 2023
  Awarded the second PhD prize from my doctoral school EDITE (Ecole Doctorale Informatique, Télécommunications et Electronique).
  


• MT180 Online Prize - 2023
  MT180 (Ma Thèse en 180 secondes) is an outreach competition for French PhD students for which the objective is to make our PhD accessible to the general public in only 3 minutes. I was one of the 18 finalists at Sorbonne University and I won the online audience prize (see outreach section for more details).
  


• Ethereum Challenges - 2021
  Winning team (with A. Bariant, G. Leurent and L. Perrin) of symmetric cryptanalysis challenges for arithmetization-oriented hash-function. Those challenges were proposed by the Ethereum Foundation.
  


• Lebesgue Master scholarship - 2019
  Awarded the Lebesgue Excellence Scholarship for the second year of my Master’s degree
  

Editorial Activities

Commitee Member

• Information Security Conference - 2024 [website]
  

External Reviews

• Crypto - 2023, 2024
  


• Eurocrypt - 2024
  


• Asiacrypt - 2023
  


• Designs, Codes and Cryptography - 2022
  


• ACM Computer and Communications Security - 2022