Paper 2011/503

On the influence of the algebraic degree of $F^{−1}$ on the algebraic degree of $G \circ F$

Christina Boura and Anne Canteaut


We present a study on the algebraic degree of iterated permutations seen as multivari- ate polynomials. Our 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 non-injective 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 cipher KN , to the block cipher Rijndael-256 and to the inner permutations of the hash functions ECHO and JH.

Available format(s)
Secret-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Contact author(s)
christina boura @ inria fr
2011-09-18: revised
2011-09-18: received
See all versions
Short URL
Creative Commons Attribution


      author = {Christina Boura and Anne Canteaut},
      title = {On the influence of the algebraic degree of $F^{−1}$ on the algebraic degree of $G \circ F$},
      howpublished = {Cryptology ePrint Archive, Paper 2011/503},
      year = {2011},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.