# zbMATH — the first resource for mathematics

On complexity of round transformations. (English) Zbl 1190.94025
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.
##### MSC:
 94A60 Cryptography 68P25 Data encryption (aspects in computer science)
Full Text:
##### References:
 [1] Adams, C.; Tavares, S., Good S-boxes are easy to find, (), 612-615 [2] Adams, C.; Tavares, S., The structured design of cryptographically good S-boxes, Journal of cryptology, 3, 1, 27-42, (1990) · Zbl 0711.94016 [3] Beth, T.; Ding, C., On almost perfect nonlinear permutations, (), 65-76 · Zbl 0951.94524 [4] Brualdi, R.A.; Ryser, H.J., Combinatorial matrix theory, (1991), Cambridge University Press Cambridge · Zbl 0746.05002 [5] Daemen, J.; Rijmen, V., The design of rijndael, (2002), Springer Verlag Berlin, Heidelberg · Zbl 1065.94005 [6] Füredi, Z.; Horák, P.; Pareek, M.; Xuding, Zhu, Oriented graphs of diameter 2, Graphs and combinatorics, 14, 345-350, (1998) · Zbl 0917.05033 [7] Grošek, O.; Magliveras, S.; Ťapuška, J.; Wei, W., Is rijndael really independent of the field polynomial?, Tatra mt. math. publ., 33, 51-61, (2006) · Zbl 1174.68406 [8] Pieprzyk, J.; Hardjono, T.; Seberry, J., Fundamentals of computer security, (2003), Springer-Verlag Berlin, Heidelberg · Zbl 1011.68034 [9] Pieprzyk, J., (), 80-92 [10] Shannon, C.E., Communication theory of secrecy systems, Bstj, 28, Oct., 656-715, (1949) · Zbl 1200.94005 [11] Šimovcová, M.; Vojvoda, M., Symmetric and complementary Boolean functions, (), 89-90 [12] Webster, A.F.; Tavares, S.E., On the design of S-boxes, (), 523-534 [13] Xiyong, Zhang; Wenbao, Han; Shuqin, Fan, On perfect nonlinear functions, Journal of combinatorial designs, 13, 349-362, (2005) · Zbl 1092.94026
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.