The use of symmetric cryptography enables to provide various security features such as confidentiality, authentication or hashing by combining a low-level primitive (i.e. a permutation or a block cipher), with a mode of operation. In this presentation we will focus on the design and security analysis of some symmetric primitives.
New symmetric primitives are designed to be executed in abstract contexts such as zero-knowledge proof systems (ZK), widely used in crypto-currency applications such as Bitcoin or Ethereum. ZK protocols are algorithms involving several parties that allow a prover to convince a verifier that he knows a secret without revealing it. These protocols have, in particular, 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.
First, we will study the algebraic degree of one of the first such block ciphers, namely MiMC, that is mainly composed a low-degree power permutation (usually the cube). We will 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. In particular, we will provide a precise guarantee on the algebraic degree of this cipher, and then on the minimal complexity for integral attacks. In addition to this mathematical analysis, we will also be interested in practical attacks on other primitives like Rescue or Poseidon.
Finally, from the cryptanalysis of these different designs we will see how we came up with our own family of ZK-friendly hash functions: Anemoi. With this new family, we will push further the frontier in understating the design principles behind AO hash functions. Indeed, we will rely on a mathematical concept, namely the CCZ equivalence, to design our main component: the Flystel.
