Skip to main content
On Complexity of Round Transformations
Discrete Mathematics
  • Otokar Grosek, Slovak University of Technology
  • Peter Horak, University of Washington Tacoma
  • Pavol Zajac, Slovak University of Technology
Publication Date
Document Type

A modern block cipher consists of round transformations, which are obtained by alternatively applying permutations (P-boxes) and substitutions (S-boxes). Clearly, the most important attribute of a block cipher is its security. However, with respect to the hardware implementation, a good block cipher has to have a reasonable complexity as well. In this paper, we study complexity of round transformations satisfying some basic security criteria. There are several ways to define the complexity of a round transformation, and to choose “necessary” security criteria. It turns out, that for our purpose, it is suitable to view a round transformation as a single Boolean function, not separating it into S-boxes and P-boxes. We require that the Boolean function F possesses some fundamental properties imposed on each block cipher for security reasons; namely, we require 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. We find the minimum complexity of such functions, and this way we establish a lower bound on complexity of all round transformations. To show that the lower bound is the best possible, we construct a round transformation F′ attaining the bound. We stress that it is not an aspiration of this paper to construct a round transformation which would be of practical use; F′ is useful only from the theoretical point of view.

pre-print, post-print
Citation Information
Otokar Grosek, Peter Horak and Pavol Zajac. "On Complexity of Round Transformations" Discrete Mathematics Vol. 309 Iss. 18 (2009) p. 5527 - 5534
Available at: