Threshold Implementations and Permutations’ Decompositions

Abstract: In this talk I will briefly mention about some of the threshold implementation countermeasure to side channel attacks and the need for the decomposition of the permutation primitive in a cipher. In 1953, Carlitz showed that all permutation polynomials over F_q, where q > 2 is a power of a prime, are generated by the special permutation polynomials x^{q−2} (the inversion) and ax + b (affine functions, where 0 ≠ a, b ∈ F_q). Recently, Nikova, Nikov and Rijmen (2019) proposed an algorithm (NNR) to find a decomposition of the inverse function in quadratics, and computationally covered all dimensions n ≤ 16. Petrides (2023) theoretically found a class of integers for which it is easy to decompose the inverse into quadratics, and improved the NNR algorithm, thereby extending the computation up to n ≤ 32. Very recently, we extended Petrides’ result, as well as proposed a new number theoretical approach, which allowed us to easily cover all (surely, odd) exponents up to 250, at least.