International Association
for Cryptologic Research

The algebraic degree of a vectorial Boolean function is one of the main parameters driving the cost of its hardware implementation. Thus, finding decompositions of functions into sequences of functions of lower algebraic degrees has been explored to reduce the cost of implementations. In this paper, we consider such decompositions of permutations over $\mathbb{F}_{2^n}$. We prove the existence of decompositions using quadratic and linear power permutations for all permutations when $2^n-1$ is a prime, and we prove the non-existence of such decompositions for power permutations of differential uniformity strictly lower than $16$ when $4|n$. We also prove that any permutation admits a decomposition into quadratic power permutations and affine permutations of the form $ax+b$ if $4 \nmid n$. Furthermore, we prove that any permutation admits a decomposition into cubic power permutations and affine permutations. Finally, we present a decomposition of the PRESENT S-Box using the power permutation $x^7$ and affine permutations.