Study of a new cost function for generating random substitutions of symmetric ciphers




symmetric cryptography, cost function, generation methods, nonlinearity, Walsh – Hadamard transform, S-box


Cryptographic transformations with a secret key play an essential role in providing information and cyber security. Block and stream symmetric ciphers are used in various applications both as a separate cryptographic protection mechanism and as part of other applications (pseudo-random sequence generators, hashing algorithms, electronic signature protocols, etc.). Therefore, the design and study of individual components of symmetric ciphers is a relevant and important scientific task. In this paper we consider and investigates iterative algorithms for generating non-linear substitutions (substitutions, S-boxes), which are used in modern block and stream encryption algorithms with a symmetric key. Cryptographic resistance of symmetric ciphers to statistical, differential, linear and other methods of cryptanalysis is provided by the properties of substitutions. In addition, S-boxes must be random from the point of view of the possibility to use algebraic cryptanalysis. Therefore, the task of quickly generating random S-boxes with the desired cryptographic properties is an urgent, but extremely difficult task. For example, the best known generation algorithm requires more than 65 thousand iterations to find a random bijective 8-bit substitution with a non-linearity of 104. In this paper, we study an iterative algorithm for generating substitutions for hill climbing with different cost functions and propose a new cost function, the use of which can significantly reduce the number of search iterations. In particular, the search for a bijective S-box with nonlinearity 104 requires less than 50 thousand iterations.


Menezes A.J. et al. Handbook of Applied Cryptography. CRC Press, 2018.

Delfs H., Knebl H. Introduction to Cryptography. Berlin, Heidelberg: Springer Berlin Heidelberg, 2015.

Kuznetsov A.A. et al. Stream Ciphers in Modern Real-time IT Systems: Analysis, Design and Comparative Studies. Springer International Publishing, 2022. XVI. 611 p.

Daemen J., Rijmen V. Specification of Rijndael // The Design of Rijndael: The Advanced Encryption Standard (AES) / ed. Daemen J., Rijmen V. Berlin, Heidelberg: Springer, 2020. P. 31–51.

Daemen J., Rijmen V. AES proposal: rijndael. 1999.

Shannon C.E. Communication theory of secrecy systems // The Bell System Technical Journal. 1949. Vol. 28, № 4. P. 656–715.

Freyre Echevarría A. Evolución híbrida de s-cajas no lineales resistentes a ataques de potencia. 2020.

Gorbenko I. et al. Random S-Boxes Generation Methods for Symmetric Cryptography // 2019 IEEE 2nd Ukraine Conference on Electrical and Computer Engineering (UKRCON). 2019. P. 947–950.

Moskovchenko I. et al. HEURISTIC METHODS FOR THE DESIGN OF CRYPTOGRAPHIC BOOLEAN FUNCTIONS: 3 // International Journal of Computing. 2019. Vol. 18, № 3. P. 265–277.

Cusick T., Stănică P. Cryptographic Boolean Functions and Applications: Second edition // Cryptographic Boolean Functions and Applications: Second Edition. 2017. P. 2751 p.

Bard G.V. Algebraic Cryptanalysis. Boston, MA: Springer US, 2009.

Courtois N.T., Bard G.V. Algebraic Cryptanalysis of the Data Encryption Standard // Cryptography and Coding / ed. Galbraith S.D. Berlin, Heidelberg: Springer, 2007. P. 152–169.

Courtois N.T., Pieprzyk J. Cryptanalysis of Block Ciphers with Overdefined Systems of Equations // Advances in Cryptology — ASIACRYPT 2002 / ed. Zheng Y. Berlin, Heidelberg: Springer, 2002. P. 267–287.

Technology N.I. of S. and. Advanced Encryption Standard (AES): Federal Information Processing Standard (FIPS) 197. U.S. Department of Commerce, 2001.

Daemen J., Rijmen V. Rijndael/AES // Encyclopedia of Cryptography and Security / ed. van Tilborg H.C.A. Boston, MA: Springer US, 2005. P. 520–524.

Burnett L.D. Heuristic Optimization of Boolean Functions and Substitution Boxes for Cryptography: phd. Queensland University of Technology, 2005.

Ivanov G., Nikolov N., Nikova S. Cryptographically Strong S-Boxes Generated by Modified Immune Algorithm // Cryptography and Information Security in the Balkans / ed. Pasalic E., Knudsen L.R. Cham: Springer International Publishing, 2016. P. 31–42.

Freyre-Echevarría A. et al. An External Parameter Independent Novel Cost Function for Evolving Bijective Substitution-Boxes: 11 // Symmetry. Multidisciplinary Digital Publishing Institute. 2020. Vol. 12, № 11. P. 1896.

Freyre-Echevarría A. et al. Evolving Nonlinear S-Boxes With Improved Theoretical Resilience to Power Attacks // IEEE Access. 2020. Vol. 8. P. 202728–202737.

Kuznetsov A. et al. Optimizing the Local Search Algorithm for Generating S-Boxes // 2021 IEEE 8th International Conference on Problems of Infocommunications, Science and Technology (PIC S T). 2021. P. 458–464.

Kuznetsov A. et al. WHS Cost Function for Generating S-boxes // 2021 IEEE 8th International Conference on Problems of Infocommunications, Science and Technology (PIC S T). 2021. P. 434–438.

Ivanov G., Nikolov N., Nikova S. Reversed genetic algorithms for generation of bijective s-boxes with good cryptographic properties // Cryptogr. Commun. 2016. Vol. 8, № 2. P. 247–276.

Kapuściński T., Nowicki R.K., Napoli C. Application of Genetic Algorithms in the Construction of Invertible Substitution Boxes // Artificial Intelligence and Soft Computing / ed. Rutkowski L. et al. Cham: Springer International Publishing, 2016. P. 380–391.

Mariot L., Leporati A. Heuristic Search by Particle Swarm Optimization of Boolean Functions for Cryptographic Applications // Proceedings of the Companion Publication of the 2015 Annual Conference on Genetic and Evolutionary Computation. New York, NY, USA: Association for Computing Machinery. 2015. P. 1425–1426.

Freyre Echevarría A., Martínez Díaz I. A new cost function to improve nonlinearity of bijective S-boxes. 2020.

Clark J.A., Jacob J.L., Stepney S. The design of S-boxes by simulated annealing // New Gener Comput. 2005. Vol. 23, № 3. P. 219–231.

McLaughlin J. Applications of search techniques to cryptanalysis and the construction of cipher components: phd. University of York, 2012.

Wang J. et al. Construction Method and Performance Analysis of Chaotic S-Box Based on a Memorable Simulated Annealing Algorithm: 12 // Symmetry. Multidisciplinary Digital Publishing Institute, 2020. Vol. 12, № 12. P. 2115.

Picek S., Cupic M., Rotim L. A New Cost Function for Evolution of S-Boxes // Evolutionary Computation. 2016. Vol. 24, № 4. P. 695–718.

Carlet C. Vectorial Boolean functions for cryptography // Boolean Models and Methods in Mathematics, Computer Science, and Engineering. 2006.

Tesar P. A New Method for Generating High Non-linearity S-Boxes. Společnost pro radioelektronické inženýrství, 2010.



How to Cite

Kuznetsov О. ., Poluyanenko М. ., Kandiy, S. ., & Peliukh, O. . (2022). Study of a new cost function for generating random substitutions of symmetric ciphers. Radiotekhnika, 2(209), 71–82.




Most read articles by the same author(s)

1 2 3 4 > >>