On Decompositions of Permutations in Quadratic Functions

Abstract 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}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>F</mml:mi> <mml:msup> <mml:mn>2</mml:mn> <mml:mi>n</mml:mi> </mml:msup> </mml:msub> </mml:math> . We prove the existence of a decomposition of the inverse using quadratic and linear power permutations for all permutations when $$2^n-1$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msup> <mml:mn>2</mml:mn> <mml:mi>n</mml:mi> </mml:msup> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:math> 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$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>a</mml:mi> <mml:mi>x</mml:mi> <mml:mo>+</mml:mo> <mml:mi>b</mml:mi> </mml:mrow> </mml:math> if $$4 \not \mid n$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>4</mml:mn> <mml:mo>∤</mml:mo> <mml:mi>n</mml:mi> </mml:mrow> </mml:math> . 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$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mi>x</mml:mi> <mml:mn>7</mml:mn> </mml:msup> </mml:math> and affine permutations.