Hybrid Population-Based Hill Climbing Algorithm for Generating Highly Nonlinear S-boxes
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...
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2024-12-01
|
| Series: | Computers |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2073-431X/13/12/320 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850049430962569216 |
|---|---|
| author | Oleksandr Kuznetsov Nikolay Poluyanenko Kateryna Kuznetsova Emanuele Frontoni Marco Arnesano |
| author_facet | Oleksandr Kuznetsov Nikolay Poluyanenko Kateryna Kuznetsova Emanuele Frontoni Marco Arnesano |
| author_sort | Oleksandr Kuznetsov |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-3011243141b24909bc4cd2018b9cae1a |
| institution | DOAJ |
| issn | 2073-431X |
| language | English |
| publishDate | 2024-12-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Computers |
| spelling | doaj-art-3011243141b24909bc4cd2018b9cae1a2025-08-20T02:53:43ZengMDPI AGComputers2073-431X2024-12-01131232010.3390/computers13120320Hybrid Population-Based Hill Climbing Algorithm for Generating Highly Nonlinear S-boxesOleksandr Kuznetsov0Nikolay Poluyanenko1Kateryna Kuznetsova2Emanuele Frontoni3Marco Arnesano4Department of Theoretical and Applied Sciences, eCampus University, Via Isimbardi 10, 22060 Novedrate, ItalyDepartment of Information and Communication Systems Security, V. N. Karazin Kharkiv National University, 4 Svobody Sq., 61022 Kharkiv, UkraineVRAI—Vision, Robotics and Artificial Intelligence Laboratory, Via Brecce Bianche 12, 60131 Ancona, ItalyDepartment of Political Sciences, Communication and International Relations, University of Macerata, Via Crescimbeni, 30/32, 62100 Macerata, ItalyDepartment of Theoretical and Applied Sciences, eCampus University, Via Isimbardi 10, 22060 Novedrate, ItalyThis 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.https://www.mdpi.com/2073-431X/13/12/320S-box generationcryptographic primitivesnonlinear substitutionhybrid optimizationhill climbingevolutionary algorithms |
| spellingShingle | Oleksandr Kuznetsov Nikolay Poluyanenko Kateryna Kuznetsova Emanuele Frontoni Marco Arnesano Hybrid Population-Based Hill Climbing Algorithm for Generating Highly Nonlinear S-boxes Computers S-box generation cryptographic primitives nonlinear substitution hybrid optimization hill climbing evolutionary algorithms |
| title | Hybrid Population-Based Hill Climbing Algorithm for Generating Highly Nonlinear S-boxes |
| title_full | Hybrid Population-Based Hill Climbing Algorithm for Generating Highly Nonlinear S-boxes |
| title_fullStr | Hybrid Population-Based Hill Climbing Algorithm for Generating Highly Nonlinear S-boxes |
| title_full_unstemmed | Hybrid Population-Based Hill Climbing Algorithm for Generating Highly Nonlinear S-boxes |
| title_short | Hybrid Population-Based Hill Climbing Algorithm for Generating Highly Nonlinear S-boxes |
| title_sort | hybrid population based hill climbing algorithm for generating highly nonlinear s boxes |
| topic | S-box generation cryptographic primitives nonlinear substitution hybrid optimization hill climbing evolutionary algorithms |
| url | https://www.mdpi.com/2073-431X/13/12/320 |
| work_keys_str_mv | AT oleksandrkuznetsov hybridpopulationbasedhillclimbingalgorithmforgeneratinghighlynonlinearsboxes AT nikolaypoluyanenko hybridpopulationbasedhillclimbingalgorithmforgeneratinghighlynonlinearsboxes AT katerynakuznetsova hybridpopulationbasedhillclimbingalgorithmforgeneratinghighlynonlinearsboxes AT emanuelefrontoni hybridpopulationbasedhillclimbingalgorithmforgeneratinghighlynonlinearsboxes AT marcoarnesano hybridpopulationbasedhillclimbingalgorithmforgeneratinghighlynonlinearsboxes |