I am currently working on symmetric cryptography, and more precisely, my main research interest is the cryptanalysis of arithmetization-friendly symmetric primitives. These new primitives are particularly innovative since they use non-linear functions whose algebraic representation remains very simple on a large finite field. It is therefore not excluded that the implementation constraints that have governed their design have introduced some security flaws.

This is why, during the first year of my PhD, I have especially focused on the study of the algebraic degree of one of these constructions: the block cipher MiMC. In addition to this mathematical analysis, I've also been interested in practical attacks on other primitives like Rescue or Poseidon. Then, I have joined the designer's side in creating Anemoi: our new family of hash functions that exploit the link between arithmetization-orientation and CCZ-equivalence.

Publications

Journals

• On the Algebraic Degree of Iterated Power Functions - Designs, Codes and Cryptography, 2022
  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 the cube. 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.

Preprints

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

  Advanced cryptographic protocols such as Zero-knowledge (ZK) proofs of knowledge, widely used in cryptocurrency applications such as Zcash, Monero, Filecoin, demand new cryptographic hash functions that are efficient not only over the binary field F2, but also over large fields of prime characteristic Fp. 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 28%-48% 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).



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

Talks

Workshops and Conferences

FSE 2023 - Algebraic Attacks against Some Arithmetization-Oriented Primitives. Kobe, Japan, March 23rd, 2023

ZKProof5 - Anemoi and Jive: New Arithmetization-Oriented tools for Plonk-based applications. Tel Aviv, Israel, November 16th, 2022

CrossFyre 2022 - A New Approach for Arithmetization-Oriented Symmetric Primitives Passau, Germany, October 7th, 2022

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

WCC 2022 - On the Algebraic Degree of Iterated Power Functions Virtual (Rostock, Germany), March 7th, 2022

Seminars

MDCC Seminar (Paris 8) - Arithmetization-Oriented primitives: A need for mathematical tools. Paris, France, October 20th, 2022

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

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

Rennes Crypto Seminar - New uses in Symmetric Cryptography: from Cryptanalysis to Designing Rennes, France, May 20th, 2022

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

Rump Sessions

FSE 2022 - Auld Alliance is back Athens, Greece, March 23rd, 2022

Eurocrypt 2021 - Let's play music with MiMC Zagreb, Croatia, October 19th, 2021

Defense

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