A Complementary Result on the Construction of Quadratic Cyclotomic Classes

Side-channel analysis (SCA) is a general name for cryptanalytic methods based on side information gathered by measuring and analyzing of various physical parameters. Threshold implementation (TI) is one of the successful countermeasure techniques for some types of SCA. Within this scope, Nikova et al. gave an algorithm on the decomposition of power permutations into quadratic power permutations over finite fields F2n in [Cryptogr. Commun. 11, 37-384 (2019)]. Later on, Otal and Tekin gave a sufficient way in [Cryptogr. Commun. 13, 837-845 (2021)] to reduce the precomputation cost in the algorithm of Nikova et al. substantially. In this paper, we prove that this sufficient way is also necessary, in other words, the proposed way is an optimal solution. In that way, we provide a complementary result on the construction of quadratic cyclotomic classes.