On complexity of round transformations (Q1045033)

A block cipher consists of round transformations, which are obtained by alternatively applying permutations (P-boxes) and substitutions (S-boxes). With respect to the hardware implementation, a good block cipher has to have a reasonable complexity. This paper studies complexity of round transformations satisfying some basic security criteria. It turns out, that it is suitable to view a round transformation as a single Boolean function, not separating it into S-boxes and P-boxes. Assuming that the Boolean function \(F\) possesses some fundamental properties imposed on each block cipher for security reasons; namely that the function is a strictly non-linear bijection and that it has a good diffusion, the total number of variables in the normal algebraic form of the component functions of \(F\) is taken as its complexity. The minimum complexity of such functions is found, and this way a lower bound on complexity of all round transformations is established. To show that the lower bound is the best possible, a round transformation \(F'\) attaining the bound is constructed.