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}$$ F 2 n . We prove the existence of a decomposition of the inverse using quadratic and linear power permutations for all permutations when $$2^n-1$$ 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$$ a x + b if $$4 \not \mid n$$ 4 ∤ 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$$ x 7 and affine permutations.

Threshold implementation is a method based on secret sharing to secure cryptographic ciphers (and in particular S-boxes) against differential power analysis side-channel attacks which was proposed by Nikova, Rechberger, and Rijmen in 2006. Until now, threshold implementations were only constructed for specific types of functions and some small S-boxes, but no generic construction was ever presented. In this paper, we present the first universal threshold implementation with$t+2$shares that is applicable to any bijective S-box, where$t$is its algebraic degree (or is larger than the algebraic degree). While being universal, our construction is also optimal with respect to the number of shares, since the theoretically smallest possible number,$t+1$, is not attainable for some bijective S-boxes. Our results enable low latency secure hardware implementations without the need for additional randomness. In particular, we apply this result to find two uniform sharings of the AES S-box. The first sharing is obtained by using the threshold implementation of the inversion in$\mathbb {F}_{2^{8}}$and the second by using two threshold implementations of two cubic power permutations that decompose the inversion. Area and performance figures for hardware implementations are provided.