On complexity of round transformations |
| |
Authors: | Otokar Grošek Pavol Zajac |
| |
Institution: | a Department of Applied Informatics and Information Technology, Slovak University of Technology, Bratislava, Slovakia b IAS, University of Washington, Tacoma, USA |
| |
Abstract: | 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. |
| |
Keywords: | Block ciphers design Round function |
本文献已被 ScienceDirect 等数据库收录! |
|