Optimization of local search algorithm parameters for generating nonlinear substitutions
DOI:
https://doi.org/10.30837/rt.2021.3.206.06Keywords:
symmetric cryptography, nonlinear substitutions, S-boxes, local search algorithm, optimization of parametersAbstract
Nonlinear substitutions (S-boxes) are an important component of modern symmetric cryptography algorithms. They complicate symmetric transformations and introduce nonlinearity into the input-output relationship, which ensures the stability of the algorithms against some cryptanalysis methods. Generation of S-boxes can be done in different ways. However, heuristic techniques are the most promising ones. On the one hand, the generated S-boxes are in the form of random substitutions, which complicates algebraic cryptanalysis. On the other hand, heuristic search allows one to achieve high rates of nonlinearity and δ-uniformity, which complicates linear and differential cryptanalysis. This article studies the simplest local search algorithm for generating S-boxes. To assess the efficiency of the algorithm, the concept of a track of a cost function is introduced in the article. Numerous experiments are carried out, in particular, the influence of the number of internal and external loops of local search on the complexity of generating the target S-box is investigated. The optimal (from the point of view of minimum time consumption) parameters of the local search algorithm for generating S-blocks with a target nonlinearity of 104 and the number of parallel computing threads 30 are substantiated. It is shown that with the selected (optimal) parameters it is possible to reliably form S-blocks with a nonlinearity of 104.
References
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.
Carlet C. Vectorial Boolean functions for cryptography // Boolean Models and Methods in Mathematics, Computer Science, and Engineering (2006).
Carlet C., Ding C. Nonlinearities of S-boxes // Finite Fields and Their Applications. 13, 121–135 (2007). https://doi.org/10.1016/j.ffa.2005.07.003.
Álvarez-Cubero J. Vector Boolean Functions: applications in symmetric cryptography, (2015). https://doi.org/10.13140/RG.2.2.12540.23685.
Burnett L.D. Heuristic Optimization of Boolean Functions and Substitution Boxes for Cryptography, https://eprints.qut.edu.au/16023/, (2005).
Clark A.J. Optimisation heuristics for cryptology, https://eprints.qut.edu.au/15777/ (1998).
Fuller J.E. Analysis of affine equivalent boolean functions for cryptography, https://eprints.qut.edu.au/15828/ (2003).
McLaughlin J. Applications of search techniques to cryptanalysis and the construction of cipher components, http://etheses.whiterose.ac.uk/3674/ (2012).
Battiti R., Brunato M., Mascia F. Reactive Search and Intelligent Optimization : Springer US (2009). https://doi.org/10.1007/978-0-387-09624-7.
Hromkovič J. Algorithmics for Hard Problems // Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics. Springer-Verlag, Berlin Heidelberg (2004). https://doi.org/10.1007/978-3-662-05269-3.
Arya V., Garg N., Khandekar R., Meyerson A., Munagala K., Pandit V. Local search heuristic for k-median and facility location problems // Proceedings of the thirty-third annual ACM symposium on Theory of computing. pp. 21–29. Association for Computing Machinery, New York, NY, USA (2001). https://doi.org/10.1145/380752.380755.
Edelkamp S., Schroedl S. Heuristic Search: Theory and Applications. Morgan Kaufmann, Amsterdam; Boston (2011).
Millan W., Burnett L., Carter G., Clark A., Dawson E. Evolutionary Heuristics for Finding Cryptographically Strong S-Boxes // Varadharajan, V. and Mu, Y. (eds.) Information and Communication Security. pp. 263–274. Springer, Berlin, Heidelberg (1999). https://doi.org/10.1007/978-3-540-47942-0_22.
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.
Clark J.A., Jacob J.L., Stepney S. The design of S-boxes by simulated annealing // New Gener Comput. 23, 219–231 (2005). https://doi.org/10.1007/BF03037656.
Clark J.A., Jacob J.L., Stepney S. Searching for cost functions // Proceedings of the 2004 Congress on Evolutionary Computation (IEEE Cat. No.04TH8753). pp. 1517-1524 Vol.2 (2004). https://doi.org/10.1109/CEC.2004.1331076.
Millan W., Clark A. Smart Hill Climbing Finds Better Boolean Functions. (1997).
Millan W., Clark A., Dawson E. Heuristic design of cryptographically strong balanced Boolean functions // Nyberg, K. (ed.) Advances in Cryptology – EUROCRYPT’98. pp. 489–499. Springer Berlin Heidelberg, Berlin, Heidelberg (1998).
Millan W., Clark A., Dawson E. Boolean Function Design Using Hill Climbing Methods // Pieprzyk, J., Safavi-Naini, R., and Seberry, J. (eds.) Information Security and Privacy. pp. 1–11. Springer, Berlin, Heidelberg (1999). https://doi.org/10.1007/3-540-48970-3_1.
Millan W. How to improve the nonlinearity of bijective S-boxes // Boyd C. and Dawson E. (eds.) Infor-mation Security and Privacy. pp. 181–192. Springer, Berlin, Heidelberg (1998). https://doi.org/10.1007/BFb0053732.
Clark J.A., Jacob J.L., Stepney S. The design of s-boxes by simulated annealing // 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.
Kavut S., Yücel M.D. Improved Cost Function in the Design of Boolean Functions Satisfying Multiple Criteria // Johansson T. and Maitra S. (eds.) Progress in Cryptology – INDOCRYPT 2003. pp. 121–134. Springer, Berlin, Heidelberg (2003). https://doi.org/10.1007/978-3-540-24582-7_9.
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.
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.
Eastlake 3rd, D., Schiller J., Crocker S. Randomness Requirements for Security (2005).
Tesar P. A New Method for Generating High Non-linearity S-Boxes (2010).
Laskari E.C., Meletiou G.C., Vrahatis M.N. Utilizing Evolutionary Computation Methods for the Design of S-Boxes // 2006 International Conference on Computational Intelligence and Security. pp. 1299–1302 (2006). https://doi.org/10.1109/ICCIAS.2006.295267.
Kapuścińsk T., Nowicki R.K., Napoli C. Application of Genetic Algorithms in the Construction of Invertible Substitution Boxes // Rutkowski L., Korytkowski M., Scherer R., Tadeusiewicz R., Zadeh L.A., and Zurada J.M. (eds.). Artificial Intelligence and Soft Computing. pp. 380–391. Springer International Publishing, Cham. (2016). https://doi.org/10.1007/978-3-319-39378-0_33.
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.
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., Martínez Díaz I. A new cost function to improve nonlinearity of bijective S-boxes. (2020).
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).
