Propagation of Subspaces in Primitives with Monomial Sboxes: Applications to Rescue and Variants of the AES

Motivated by progress in the field of zero-knowledge proofs, Arithmetization-Oriented (AO) symmetric primitives such as MiMC, Poseidon or Rescue are defined using simple operations over large fields. Many rely on simple low-degree monomials for their non-linear layers, essentially using x -> x^3 as an S-box. In this talk, we show that the structure of the material injected in each round could allow a specific pattern, whereby a well-defined affine space is mapped to another by the round function, and then to another, etc. As a consequence, for several ciphers like Rescue, or a variant of AES with a monomial Sbox, there exist some round-key sequences for which the cipher has an abnormally high differential uniformity, exceeding the size of the Sbox alphabet. Well-known security arguments have been reused in the AO setting by many designers. Our results show that such a traditional study may not be sufficient to guarantee security. To illustrate this, we present new primitives that are built using state-of-the-art security arguments, but which are actually deeply flawed.