Properties of the cost function in the iterative algorithm for generating nonlinear substitution
DOI:
https://doi.org/10.30837/rt.2022.2.209.02Keywords:
symmetric cryptography, cost function, generation methods, nonlinearity, Walsh – Hadamard transform, S-boxAbstract
To ensure the security of information technology, cryptographic information protection tools are used, in particular block and stream encryption algorithms with a symmetric key. Reliability and cryptographic strength of cryptoalgorithms is provided by the properties of the applied primitives. For example, non-linear substitutions (S-boxes) are used as the main component of modern symmetric ciphers. Therefore, generation of substitutions is an important scientific task directly related to the security of information technology and improvement of modern symmetric ciphers. The paper investigates the properties of iterative algorithms for generating non-linear substitutions and special cost functions, which play a decisive role in the heuristic search for S-boxes with the required properties. We consider the cost function of the WCF (Cost Function of the content of the Walsh-Hadamard spectrum) and optimize its parameters. The obtained optimization results in combination with the Hill Climbing iterative search algorithm can reduce significantly the number of iterations. In particular, we show that for a substitution search with a non-linearity of 104, on average, we reduce the computational complexity of generation by more than 20%. In addition, it is possible to increase the success rate of the heuristic search. In particular, for the selected settings, in 100% of cases, a beaktive S-box with a non-linearity of 104 was found.
References
Freyre Echevarría A. Evolución híbrida de s-cajas no lineales resistentes a ataques de potencia. 2020.
McLaughlin J. Applications of search techniques to cryptanalysis and the construction of cipher components: phd. University of York, 2012.
Álvarez-Cubero J. Vector Boolean Functions: applications in symmetric cryptography. 2015.
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.
Rodinko M., Oliynykov R., Gorbenko Y. Optimization of the High Nonlinear S-Boxes Generation Method // Tatra Mountains Mathematical Publications. Sciendo, 2017. Vol. 70, № 1. P. 93–105.
Kuznetsov A.A. et al. Stream Ciphers in Modern Real-time IT Systems. Cham: Springer Nature, 2022. 593 p.
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., Martínez Díaz I. A new cost function to improve nonlinearity of bijective S-boxes. 2020.
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.
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. Evolving Nonlinear S-Boxes With Improved Theoretical Resilience to Power Attacks // IEEE Access. 2020. Vol. 8. P. 202728–202737.
Kazymyrov O., Kazymyrova V., Oliynykov R. A Method For Generation Of High-Nonlinear S-Boxes Based On Gradient Descent: 578. 2013.
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.
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.
Picek S., Cupic M., Rotim L. A New Cost Function for Evolution of S-Boxes // Evolutionary Computation. 2016. Vol. 24, № 4. P. 695–718.
Clark A.J. Optimisation heuristics for cryptology: phd. Queensland University of Technology, 1998.
Cusick T., Stănică P. Cryptographic Boolean Functions and Applications: Second edition // Cryptographic Boolean Functions and Applications: Second Edition. 2017. P. 2751 p.
Downloads
Published
How to Cite
Issue
Section
License
Authors who publish with this journal agree to the following terms:
1. Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
