{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,4]],"date-time":"2026-09-04T22:28:19Z","timestamp":1788560899765,"version":"build-2803163510"},"reference-count":31,"publisher":"MDPI AG","issue":"12","license":[{"start":{"date-parts":[[2024,12,2]],"date-time":"2024-12-02T00:00:00Z","timestamp":1733097600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100010661","name":"European Union\u2019s Horizon 2020 research and innovation program","doi-asserted-by":"publisher","award":["101007820\u2014TRUST"],"award-info":[{"award-number":["101007820\u2014TRUST"]}],"id":[{"id":"10.13039\/100010661","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010661","name":"European Union\u2019s Horizon 2020 research and innovation program","doi-asserted-by":"publisher","award":["ECS00000041-VITALITY-CUP D83C22000710005"],"award-info":[{"award-number":["ECS00000041-VITALITY-CUP D83C22000710005"]}],"id":[{"id":"10.13039\/100010661","id-type":"DOI","asserted-by":"publisher"}]},{"name":"European Union\u2014NextGenerationEU","award":["101007820\u2014TRUST"],"award-info":[{"award-number":["101007820\u2014TRUST"]}]},{"name":"European Union\u2014NextGenerationEU","award":["ECS00000041-VITALITY-CUP D83C22000710005"],"award-info":[{"award-number":["ECS00000041-VITALITY-CUP D83C22000710005"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Computers"],"abstract":"<jats:p>This paper introduces the hybrid population-based hill-climbing (HPHC) algorithm, a novel approach for generating cryptographically strong S-boxes that combines the efficiency of hill climbing with the exploration capabilities of population-based methods. The algorithm achieves consistent generation of 8-bit S-boxes with a nonlinearity of 104, a critical threshold for cryptographic applications. Our approach demonstrates remarkable efficiency, requiring only 49,277 evaluations on average to generate such S-boxes, representing a 600-fold improvement over traditional simulated annealing methods and a 15-fold improvement over recent genetic algorithm variants. We present comprehensive experimental results from extensive parameter space exploration, revealing that minimal populations (often single-individual) combined with moderate mutation rates achieve optimal performance. This paper provides detailed analysis of algorithm behavior, parameter sensitivity, and performance characteristics, supported by rigorous statistical evaluation. We demonstrate that population size should approximate available thread count for optimal parallel execution despite smaller populations being theoretically more efficient. The HPHC algorithm maintains high reliability across diverse parameter settings while requiring minimal computational resources, making it particularly suitable for practical cryptographic applications.<\/jats:p>","DOI":"10.3390\/computers13120320","type":"journal-article","created":{"date-parts":[[2024,12,2]],"date-time":"2024-12-02T09:00:10Z","timestamp":1733130010000},"page":"320","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Hybrid Population-Based Hill Climbing Algorithm for Generating Highly Nonlinear S-boxes"],"prefix":"10.3390","volume":"13","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2331-6326","authenticated-orcid":false,"given":"Oleksandr","family":"Kuznetsov","sequence":"first","affiliation":[{"name":"Department of Theoretical and Applied Sciences, eCampus University, Via Isimbardi 10, 22060 Novedrate, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nikolay","family":"Poluyanenko","sequence":"additional","affiliation":[{"name":"Department of Information and Communication Systems Security, V. N. Karazin Kharkiv National University, 4 Svobody Sq., 61022 Kharkiv, Ukraine"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kateryna","family":"Kuznetsova","sequence":"additional","affiliation":[{"name":"VRAI\u2014Vision, Robotics and Artificial Intelligence Laboratory, Via Brecce Bianche 12, 60131 Ancona, Italy"},{"name":"Department of Political Sciences, Communication and International Relations, University of Macerata, Via Crescimbeni, 30\/32, 62100 Macerata, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8893-9244","authenticated-orcid":false,"given":"Emanuele","family":"Frontoni","sequence":"additional","affiliation":[{"name":"Department of Political Sciences, Communication and International Relations, University of Macerata, Via Crescimbeni, 30\/32, 62100 Macerata, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1700-3075","authenticated-orcid":false,"given":"Marco","family":"Arnesano","sequence":"additional","affiliation":[{"name":"Department of Theoretical and Applied Sciences, eCampus University, Via Isimbardi 10, 22060 Novedrate, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2024,12,2]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Menezes, A.J., van Oorschot, P.C., Vanstone, S.A., van Oorschot, P.C., and Vanstone, S.A. (2018). Handbook of Applied Cryptography, CRC Press.","DOI":"10.1201\/9781439821916"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"102620","DOI":"10.1016\/j.asej.2023.102620","article-title":"An Optimized Chaotic S-Box for Real-Time Image Encryption Scheme Based on 4-Dimensional Memristive Hyperchaotic Map","volume":"15","author":"Vijayakumar","year":"2024","journal-title":"Ain Shams Eng. J."},{"key":"ref_3","first-page":"253","article-title":"Constructions of Correlation Immnue S-Boxes with High Nonlinearity","volume":"2","author":"Ji","year":"2024","journal-title":"J. Inf. Intell."},{"key":"ref_4","unstructured":"Freyre Echevarr\u00eda, A. (2020). Evoluci\u00f3n H\u00edbrida de S-Cajas No Lineales Resistentes a Ataques de Potencia. [Bachelor\u2019s Thesis]."},{"key":"ref_5","unstructured":"\u00c1lvarez-Cubero, J. (2015). Vector Boolean Functions: Applications in Symmetric Cryptography. [Ph.D. Thesis, Universidad Polit\u00e9cnica de Madrid]."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Cusick, T., and St\u0103nic\u0103, P. (2017). Cryptographic Boolean Functions and Applications, Academic Press. [2nd ed.].","DOI":"10.1016\/B978-0-12-811129-1.00005-5"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1007\/BF03037656","article-title":"The Design of S-Boxes by Simulated Annealing","volume":"23","author":"Clark","year":"2005","journal-title":"New Gener. Comput."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Rutkowski, L., Korytkowski, M., Scherer, R., Tadeusiewicz, R., Zadeh, L.A., and Zurada, J.M. (2016, January 12\u201316). Application of Genetic Algorithms in the Construction of Invertible Substitution Boxes. Proceedings of the Artificial Intelligence and Soft Computing, Zakopane, Poland.","DOI":"10.1007\/978-3-319-39378-0"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1007\/s12095-015-0170-5","article-title":"Reversed Genetic Algorithms for Generation of Bijective S-Boxes with Good Cryptographic Properties","volume":"8","author":"Ivanov","year":"2016","journal-title":"Cryptogr. Commun."},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Freyre-Echevarr\u00eda, A., Alanezi, A., Mart\u00ednez-D\u00edaz, I., Ahmad, M., Abd El-Latif, A.A., Kolivand, H., and Razaq, A. (2020). An External Parameter Independent Novel Cost Function for Evolving Bijective Substitution-Boxes. Symmetry, 12.","DOI":"10.3390\/sym12111896"},{"key":"ref_11","unstructured":"Pasalic, E., and Knudsen, L.R. (2014, January 16). Cryptographically Strong S-Boxes Generated by Modified Immune Algorithm. Proceedings of the Cryptography and Information Security in the Balkans, Istanbul, Turkey."},{"key":"ref_12","unstructured":"Carlet, C. (2006). Vectorial Boolean Functions for Cryptography. Boolean Models and Methods in Mathematics, Computer Science, and Engineering, Cambridge, University Press."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Davies, D.W. (1991, January 8\u201311). Perfect Nonlinear S-Boxes. Proceedings of the Advances in Cryptology\u2014EUROCRYPT \u201991, Brighton, UK.","DOI":"10.1007\/3-540-46416-6"},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Daemen, J., and Rijmen, V. (2020). Specification of Rijndael. The Design of Rijndael: The Advanced Encryption Standard (AES), Springer. Information Security and Cryptography.","DOI":"10.1007\/978-3-662-60769-5"},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Boyd, C., and Dawson, E. (1998). How to Improve the Nonlinearity of Bijective S-Boxes. Proceedings of the Information Security and Privacy, Springer.","DOI":"10.1007\/BFb0053715"},{"key":"ref_16","unstructured":"Burnett, L.D. (2005). Heuristic Optimization of Boolean Functions and Substitution Boxes for Cryptography. [Ph.D. Thesis, Queensland University of Technology]."},{"key":"ref_17","unstructured":"Galbraith, S.D. (2023, January 18\u201320). Algebraic Cryptanalysis of the Data Encryption Standard. Proceedings of the Cryptography and Coding, Cirencester, UK."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Bard, G.V. (2009). Algebraic Cryptanalysis, Springer US.","DOI":"10.1007\/978-0-387-88757-9"},{"key":"ref_19","unstructured":"McLaughlin, J. (2012). Applications of Search Techniques to Cryptanalysis and the Construction of Cipher Components. [Ph.D. Thesis, University of York]."},{"key":"ref_20","first-page":"23","article-title":"A New Method for Generating High Non-Linearity S-Boxes","volume":"19","author":"Tesar","year":"2010","journal-title":"Radioengineering"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"116132","DOI":"10.1109\/ACCESS.2020.3004449","article-title":"Particle Swarm Optimization Based Highly Nonlinear Substitution-Boxes Generation for Security Applications","volume":"8","author":"Ahmad","year":"2020","journal-title":"IEEE Access"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"695","DOI":"10.1162\/EVCO_a_00191","article-title":"A New Cost Function for Evolution of S-Boxes","volume":"24","author":"Picek","year":"2016","journal-title":"Evol. Comput."},{"key":"ref_23","first-page":"1896","article-title":"A New Cost Function to Improve Nonlinearity of Bijective S-Boxes","volume":"12","year":"2020","journal-title":"Symmetry"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"121684","DOI":"10.1016\/j.eswa.2023.121684","article-title":"A New Cost Function for Heuristic Search of Nonlinear Substitutions","volume":"237","author":"Kuznetsov","year":"2024","journal-title":"Expert Syst. Appl."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"202728","DOI":"10.1109\/ACCESS.2020.3035163","article-title":"Evolving Nonlinear S-Boxes With Improved Theoretical Resilience to Power Attacks","volume":"8","author":"Rojas","year":"2020","journal-title":"IEEE Access"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"3905","DOI":"10.1007\/s00500-023-09334-y","article-title":"Optimized Simulated Annealing for Efficient Generation of Highly Nonlinear S-Boxes","volume":"28","author":"Kuznetsov","year":"2023","journal-title":"Soft Comput."},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Kuznetsov, O., Poluyanenko, N., Frontoni, E., and Kandiy, S. (2024). Enhancing Smart Communication Security: A Novel Cost Function for Efficient S-Box Generation in Symmetric Key Cryptography. Cryptography, 8.","DOI":"10.3390\/cryptography8020017"},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Laskari, E.C., Meletiou, G.C., and Vrahatis, M.N. (2006, January 3\u20136). Utilizing Evolutionary Computation Methods for the Design of S-Boxes. Proceedings of the 2006 International Conference on Computational Intelligence and Security, Guangzhou, China.","DOI":"10.1109\/ICCIAS.2006.295267"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"475","DOI":"10.1016\/j.asoc.2017.05.052","article-title":"Designing Bijective S-Boxes Using Algorithm Portfolios with Limited Time Budgets","volume":"59","author":"Souravlias","year":"2017","journal-title":"Appl. Soft Comput."},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Kuznetsov, A., Poluyanenko, N., Kandii, S., Zaichenko, Y., Prokopovich-Tkachenko, D., and Katkova, T. (2021, January 5\u20137). WHS Cost Function for Generating S-Boxes. Proceedings of the 2021 IEEE 8th International Conference on Problems of Infocommunications, Science and Technology, PIC S and T 2021-Proceedings, Kharkiv, Ukraine.","DOI":"10.1109\/PICST54195.2021.9772133"},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Kuznetsov, A., Poluyanenko, N., Kandii, S., Zaichenko, Y., Prokopovich-Tkachenko, D., and Katkova, T. (2021, January 5\u20137). Optimizing the Local Search Algorithm for Generating S-Boxes. Proceedings of the 2021 IEEE 8th International Conference on Problems of Infocommunications, Science and Technology, PIC S and T 2021\u2013Proceedings, Kharkiv, Ukraine.","DOI":"10.1109\/PICST54195.2021.9772163"}],"container-title":["Computers"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2073-431X\/13\/12\/320\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T16:44:49Z","timestamp":1760114689000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2073-431X\/13\/12\/320"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,12,2]]},"references-count":31,"journal-issue":{"issue":"12","published-online":{"date-parts":[[2024,12]]}},"alternative-id":["computers13120320"],"URL":"https:\/\/doi.org\/10.3390\/computers13120320","relation":{},"ISSN":["2073-431X"],"issn-type":[{"value":"2073-431X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,12,2]]}}}