We present a study on the algebraic degree of iterated permutations seen as multivariate polynomials. The main result shows that this degree depends on the algebraic degree of the inverse of the permutation which is iterated. This result is also extended to noninjective balanced vectorial functions where the relevant quantity is the minimal degree of the inverse of a permutation expanding the function. This property has consequences in symmetric cryptography since several attacks or distinguishers exploit a low algebraic degree, like higher order differential attacks, cube attacks, and cube testers, or algebraic attacks. Here, we present some applications of this improved bound to a higher degree variant of the block cipherKN, to the block cipher Rijndael-256 and to the inner permutations of the hash functions ECHO and JH.

A new type of distinguishing property, named the zero-sum property has been recently presented by Aumasson and Meier. It has been applied to the inner permutation of the hash function KECCAK and it has led to a distinguishing property for the KECCAK-f permutation up to 16 rounds, out of 24 in total. Here, we additionally exploit some spectral properties of the KECCAK-f permutation and we improve the previously known upper bounds on the degree of the inverse permutation after a certain number of rounds. This result enables us to extend the zero-sum property to 18 rounds of the KECCAK-f permutation, which was the number of rounds in the previous version of KECCAK submitted to the SHA-3 competition.