Substantiation of the parameters of the annealing simulation algorithm for searching non-linear substitutions of symmetric ciphers
DOI:
https://doi.org/10.30837/rt.2022.2.209.10Keywords:
simulated annealing, symmetric cryptography, cost function, generation methods, non-linearity, Walsh-Hadamard transform, S-boxAbstract
Cryptographic protection in information and information and communication systems is an important component of cybersecurity. Therefore, the development, research and improvement of means of cryptographic information protection is an urgent and important task. In this paper, we study evolutionary methods for generating non-linear substitutions (S-boxes). These are cryptographic primitives that are an important component of many modern block and stream ciphers with a secret key. However, the problem of generating random highly non-linear substitutions is extremely difficult. In this paper, we study the annealing simulation method. This is an iterative algorithm, the essence of which is the gradual improvement of the current solution (substitution). Special cost functions are used as an improvement criterion. The initial state is formed randomly, and then, at each iteration the current solution is gradually changed. Approaching the target solution means minimizing the cost function. The paper investigates a simple and computationally efficient cost function based on the Walsh-Hadamard transform. Through exploratory research and numerous tests, it was possible to optimize the operation of the annealing simulation algorithm. Optimized algorithm for several parameters (initial temperature, "cooling factor", cost function) allows you to quickly generate highly non-linear bijective substitutions for cryptographic applications. Compared to other well-known implementations of the annealing simulation algorithm, the use of the recommended parameters can significantly reduce the generation time of nonlinear substitutions.
References
Álvarez-Cubero J. Vector Boolean Functions: applications in symmetric cryptography, (2015). https://doi.org/10.13140/RG.2.2.12540.23685.
Cusick T., Stănică P. Cryptographic Boolean Functions and Applications: Second edition. (2017).
Freyre Echevarría A. Evolución híbrida de s-cajas no lineales resistentes a ataques de potencia, (2020). https://doi.org/10.13140/RG.2.2.17037.77284/1.
Schneier B. Applied cryptography: protocols, algorithms, and source code in C. New York : Wiley (1996).
Menezes A.J., Oorschot P.C. van, Vanstone S.A., Oorschot P.C. van, Vanstone S.A. Handbook of Applied Cryptography. CRC Press (2018). https://doi.org/10.1201/9780429466335.
Kuznetsov A.A., Potii O.V., Poluyanenko N.A., Gorbenko Y.I., Kryvinska N. Stream Ciphers in Modern Real-time IT Systems: Analysis, Design and Comparative Studies. Springer International Publishing (2022). https://doi.org/10.1007/978-3-030-79770-6.
Delahaye D., Chaimatanan S., Mongeau M. Simulated annealing: From basics to applications. In: Gendreau, M. and Potvin, J.-Y. (eds.) Handbook of Metaheuristics. pp. 1-35.ISBN 978-3-319-91085–7. Springer (2019). https://doi.org/10.1007/978-3-319-91086-4_1.
Clark J.A., Jacob J.L., Stepney S. The design of s-boxes by simulated annealing. In: Proceedings of the 2004 Congress on Evolutionary Computation (IEEE Cat. No.04TH8753). pp. 1533-1537 Vol.2 (2004). https://doi.org/10.1109/CEC.2004.1331078.
Tesar P. A New Method for Generating High Non-linearity S-Boxes. (2010).
Picek S., Cupic M., Rotim L. A New Cost Function for Evolution of S-Boxes. Evolutionary Computation. 24, 695–718 (2016). https://doi.org/10.1162/EVCO_a_00191.
Freyre-Echevarría A., Alanezi A., Martínez-Díaz I., Ahmad M., Abd El-Latif A.A., Kolivand, H., Razaq, A. An External Parameter Independent Novel Cost Function for Evolving Bijective Substitution-Boxes. Symmetry. 12, 1896 (2020). https://doi.org/10.3390/sym12111896.
Freyre Echevarría A., Martínez Díaz I. A new cost function to improve nonlinearity of bijective S-boxes. (2020).
Kuznetsov A., Poluyanenko N., Kandii S., Zaichenko Y., Prokopovich-Tkachenko D., Katkova T. WHS Cost Function for Generating S-boxes // 2021 IEEE 8th International Conference on Problems of Infocommunications, Science and Technology (PIC S T). pp. 434–438 (2021). https://doi.org/10.1109/PICST54195.2021.9772133.
Ivanov G., Nikolov N., Nikova S. Reversed genetic algorithms for generation of bijective s-boxes with good cryptographic properties. Cryptogr. Commun. 8, 247–276 (2016). https://doi.org/10.1007/s12095-015-0170-5.
Rodinko M., Oliynykov R., Gorbenko Y. Optimization of the High Nonlinear S-Boxes Generation Method. Tatra Mountains Mathematical Publications. 70, 93–105 (2017). https://doi.org/10.1515/tmmp-2017-0020.
Kuznetsov A., Poluyanenko N., Kandii S., Zaichenko Y., Prokopovich-Tkachenko D., Katkova T. Optimizing the Local Search Algorithm for Generating S-Boxes // 2021 IEEE 8th International Conference on Problems of Infocommunications, Science and Technology (PIC S T). pp. 458–464 (2021). https://doi.org/10.1109/PICST54195.2021.9772163.
Chen G. A novel heuristic method for obtaining S-boxes. Chaos, Solitons & Fractals. 36, 1028–1036 (2008). https://doi.org/10.1016/j.chaos.2006.08.003.
Souravlias D., Parsopoulos K.E., Meletiou G.C. Designing bijective S-boxes using Algorithm Portfolios with limited time budgets. Applied Soft Computing. 59, 475–486 (2017). https://doi.org/10.1016/j.asoc.2017.05.052.
McLaughlin J., Clark J.A. Using evolutionary computation to create vectorial Boolean functions with low differential uniformity and high nonlinearity. arXiv (2013). https://doi.org/10.48550/arXiv.1301.6972.
Wang J., Zhu Y., Zhou C., Qi Z. Construction Method and Performance Analysis of Chaotic S-Box Based on a Memorable Simulated Annealing Algorithm. Symmetry. 12, 2115 (2020). https://doi.org/10.3390/sym12122115.
McLaughlin J. Applications of search techniques to cryptanalysis and the construction of cipher components, https://etheses.whiterose.ac.uk/3674/, (2012).
Ivanov G., Nikolov N., Nikova S. Cryptographically Strong S-Boxes Generated by Modified Immune Algorithm // Pasalic, E. and Knudsen, L.R. (eds.) Cryptography and Information Security in the Balkans. pp. 31–42. Springer International Publishing, Cham (2016). https://doi.org/10.1007/978-3-319-29172-7_3.
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).
