Paper 2023/1632

On Decompositions of Permutations in Quadratic Functions

Samuele Andreoli, University of Bergen
Enrico Piccione, University of Bergen
Lilya Budaghyan, University of Bergen
Pantelimon Stănică, Naval Postgraduate School
Svetla Nikova, KU Leuven, University of Bergen

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.

Available format(s)
Publication info
power functionvectorial Boolean functiondecompositionpermutation
Contact author(s)
samuele andreoli @ uib no
enrico piccione @ uib no
lilya budaghyan @ uib no
pstanica @ nps edu
svetla nikova @ esat kuleuven be
2023-10-23: approved
2023-10-20: received
See all versions
Short URL
Creative Commons Attribution


      author = {Samuele Andreoli and Enrico Piccione and Lilya Budaghyan and Pantelimon Stănică and Svetla Nikova},
      title = {On Decompositions of Permutations in Quadratic Functions},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1632},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.