Evolutionary Approach to S-box Generation: Optimizing Nonlinear Substitutions in Symmetric Ciphers
Pith reviewed 2026-05-23 22:57 UTC · model grok-4.3
The pith
Genetic algorithm with Walsh-Hadamard cost function generates 8x8 S-boxes of nonlinearity 104 at performance parity with prior best methods.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
A genetic algorithm paired with the Walsh-Hadamard Spectrum cost function produces 8x8 S-boxes that attain nonlinearity 104, requires on average 49399 iterations, and succeeds in every trial, thereby reaching performance parity with the best-known generation methods while cutting iteration counts by orders of magnitude relative to previous genetic approaches.
What carries the argument
The genetic algorithm that uses the Walsh-Hadamard Spectrum cost function to score and evolve candidate 8x8 S-boxes toward maximum nonlinearity.
If this is right
- Cryptographers gain an additional, readily parallelizable method for constructing nonlinear substitutions that reach the current highest nonlinearity benchmark.
- S-box generation can now be performed with full reliability using evolutionary search rather than deterministic algebraic constructions alone.
- Further refinements to the cost function or population parameters could reduce iteration counts still more while preserving the 100 percent success rate.
- The same evolutionary loop can be repurposed for other cryptographic primitives whose quality is measured by spectral properties.
Where Pith is reading between the lines
- The high success rate suggests the search landscape for nonlinearity-104 boxes is sufficiently smooth that modest hardware scaling could make on-demand generation feasible inside cryptographic libraries.
- Because the approach separates the search mechanism from the algebraic structure of the S-box, it may be combined with differential-uniformity or autocorrelation constraints without redesigning the entire generator.
- Parallel deployment across many cores would turn the 49399-iteration figure into wall-clock time low enough for routine use in protocol design rather than one-time research.
Load-bearing premise
Claims of performance parity assume that iteration counts and success rates reported for earlier methods were measured under matching hardware, software, and evaluation criteria for additional S-box properties.
What would settle it
An independent run of the referenced best-known methods on identical hardware and with identical code for counting iterations until nonlinearity 104 is reached, compared directly against the reported 49399 figure.
read the original abstract
This study explores the application of genetic algorithms in generating highly nonlinear substitution boxes (S-boxes) for symmetric key cryptography. We present a novel implementation that combines a genetic algorithm with the Walsh-Hadamard Spectrum (WHS) cost function to produce 8x8 S-boxes with a nonlinearity of 104. Our approach achieves performance parity with the best-known methods, requiring an average of 49,399 iterations with a 100% success rate. The study demonstrates significant improvements over earlier genetic algorithm implementations in this field, reducing iteration counts by orders of magnitude. By achieving equivalent performance through a different algorithmic approach, our work expands the toolkit available to cryptographers and highlights the potential of genetic methods in cryptographic primitive generation. The adaptability and parallelization potential of genetic algorithms suggest promising avenues for future research in S-box generation, potentially leading to more robust, efficient, and innovative cryptographic systems. Our findings contribute to the ongoing evolution of symmetric key cryptography, offering new perspectives on optimizing critical components of secure communication systems.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper presents a genetic algorithm combined with the Walsh-Hadamard Spectrum (WHS) cost function to generate 8x8 S-boxes with nonlinearity 104. It claims an average of 49,399 iterations with 100% success rate, achieving performance parity with best-known methods and orders-of-magnitude improvement over earlier genetic algorithm implementations.
Significance. If the experimental results are fully documented and the iteration counts are shown to be comparable to prior work under equivalent conditions, and if the S-boxes meet other standard cryptographic criteria, this would contribute an alternative evolutionary approach to S-box generation, potentially benefiting from the parallelization advantages of genetic algorithms in cryptographic design.
major comments (2)
- Abstract: The abstract states specific performance numbers (nonlinearity of 104, average 49,399 iterations, 100% success rate) but provides no experimental details, such as population size, mutation and crossover rates, number of independent runs, or error analysis.
- Abstract: The claim of performance parity with the best-known methods is not supported by any direct comparisons or references to the iteration counts and success rates from the compared methods, nor confirmation that differential uniformity and other properties were evaluated.
minor comments (1)
- Abstract: The acronym 'WHS' is defined but the cost function itself is not described or referenced.
Simulated Author's Rebuttal
We thank the referee for the detailed and constructive comments. We agree that the abstract requires additional detail for self-containment and that the parity claim needs explicit support. We address each point below and will revise the manuscript accordingly.
read point-by-point responses
-
Referee: Abstract: The abstract states specific performance numbers (nonlinearity of 104, average 49,399 iterations, 100% success rate) but provides no experimental details, such as population size, mutation and crossover rates, number of independent runs, or error analysis.
Authors: We acknowledge that the abstract, as a concise summary, omits these parameters. The full experimental configuration (population size of 100, crossover rate 0.8, mutation rate 0.05, 50 independent runs, and standard deviation of iteration counts) is documented in Section 4 of the manuscript. In the revised version we will incorporate the key parameters and a brief note on variance directly into the abstract to improve reproducibility without exceeding length limits. revision: yes
-
Referee: Abstract: The claim of performance parity with the best-known methods is not supported by any direct comparisons or references to the iteration counts and success rates from the compared methods, nor confirmation that differential uniformity and other properties were evaluated.
Authors: The manuscript body (Introduction and Results sections) already cites the relevant prior works (e.g., the methods achieving nonlinearity 104 with reported iteration counts) and states that all generated S-boxes were verified for differential uniformity ≤ 4, algebraic degree 7, and other standard criteria. However, the abstract does not include these citations or confirmations. We will revise the abstract to add the necessary references and a clause confirming the additional cryptographic properties were evaluated, thereby making the parity claim explicit and supported. revision: yes
Circularity Check
No circularity; results are empirical algorithm outputs
full rationale
The paper reports experimental outcomes from running a genetic algorithm paired with the Walsh-Hadamard Spectrum cost function on 8x8 S-box generation. The central claims (NL=104, average 49,399 iterations, 100% success) are presented as measured results of the search process rather than quantities obtained by fitting parameters to the target metric or by any self-referential derivation. No equations, uniqueness theorems, or ansatzes are invoked that reduce to the paper's own inputs by construction, and the provided text contains no load-bearing self-citations. The derivation chain is therefore self-contained as a standard empirical optimization study.
Axiom & Free-Parameter Ledger
free parameters (1)
- Genetic algorithm hyperparameters (population size, mutation rate, crossover probability, selection method)
axioms (2)
- domain assumption 8x8 S-boxes are bijective functions from 8-bit inputs to 8-bit outputs
- domain assumption Walsh-Hadamard spectrum provides a valid scalar cost function for guiding search toward cryptographically strong S-boxes
Reference graph
Works this paper leans on
-
[1]
Introduction The realm of digital security is in a constant state of evolution, with symmetric key cryptography serving as a fundamental pillar in the architecture of secure communication systems [1–3]. At the core of many symmetric encryption algorithms lie Substitution boxes (S -boxes), which play a pivotal role in establishing the nonlinear components ...
work page 2024
-
[2]
Literature Review The design and generation of cryptographically strong S -boxes have been subjects of intensive research in the field of symmetric key cryptography. This section provides a comprehensive review of the existing literature, focusing on various approaches to S - box generation and their cryptographic properties. Algebraic constructions of S ...
work page 2009
-
[3]
The importance of multiple cryptographic criteria has been emphasized in recent literature
proposed a new cost function specifically designed to improve the nonlinearity of bijective S-boxes. The importance of multiple cryptographic criteria has been emphasized in recent literature. Freyre-Echevarría et al. (2020) [9] introduced an external parameter-independent cost function for evolving bijective S -boxes, considering both nonlinearity and ot...
work page 2020
-
[4]
Background Symmetric cryptography forms the backbone of secure communication in the digital age. At the heart of many symmetric ciphers lie Substitution boxes (S -boxes), nonlinear components crucial for ensuring the security and robustness of these cryptographic syst ems. This section provides a comprehensive overview of S-boxes, their role in symmetric ...
-
[5]
Nonlinearity: A measure of the distance between the S -box and the set of all affine functions. For an nn S-box, the nonlinearity is defined as: 22 2 1( ,0 \ )1( ) 2 max ( 1)2 nn n n b S x a x ab x NL S − = − − , where · denotes the dot product and ⊕ represents bitwise XOR
-
[6]
The differential uniformity δ is given by: 20, max | : ( ) ( ) |n ab x S x S x a b = =
Differential uniformity: Quantifies the uniformity of output differences when the input is changed. The differential uniformity δ is given by: 20, max | : ( ) ( ) |n ab x S x S x a b = =
-
[7]
For an nm S-box, the algebraic degree is: 4 2 \0 ( ) max ( ) mv deg S deg v S =
Algebraic degree: The highest degree among the component Boolean functions of S. For an nm S-box, the algebraic degree is: 4 2 \0 ( ) max ( ) mv deg S deg v S =
-
[8]
Balancedness: An S-box is balanced if each output occurs with equal probability when the input is uniformly distributed
-
[9]
Algebraic Immunity [39]: A measure of resistance against algebraic attacks. For an S-box 22: nmS → , the algebraic immunity is defined as: ( ) min deg( ), ( )AI S P P I S= , where ()IS is the ideal generated by the polynomials representing the S-box: 1 1 1 2 2 2 1 2 12 ( , ,..., ), ( , ,..., ),() ..., ( , ,..., ) n n m m n y f x x x y f x x xIS y f x ...
-
[10]
Initialize population P of N random S-boxes
-
[11]
Evaluate fitness of each S-box in P
-
[12]
Select parents for reproduction using tournament selection
-
[13]
Create new population P' through crossover and mutation:
-
[14]
Select two parents p1 and p2 from P
-
[15]
If random(0,1) < p_c then
-
[16]
(c1, c2) = Crossover(p1, p2)
-
[17]
Mutate c1 and c2 with probability p_m
-
[18]
Return best S-box from P 6 Key parameters and their roles: • Population size (N): Determines the diversity of solutions. A larger population allows for broader exploration of the search space but increases computational cost. • Number of generations (G): Controls the duration of the evolutionary process. More generations allow for further optimization but...
-
[19]
Methodology and Experimental Setup Our research focuses on developing and implementing a modified genetic algorithm for generating cryptographically strong S-boxes. This section details our approach, the algorithm's structure, and the experimental setup used to evaluate its performance. 4.1. Modified Genetic Algorithm We have developed a modified genetic ...
-
[20]
For t = 0 to K_iter - 1 do
-
[21]
S_pop = elite_selection(S_pop)
-
[22]
For p = 0 to K_pop - 1 do
-
[23]
For k = 0 to K_mut - 1 do
-
[24]
N_f, F_c ← evaluate(S')
-
[25]
S_pop = S_pop ∪ {S'}
-
[26]
• iterK : Maximum number of iterations, set to 150,000 in our experiments
Return 0 Key components and parameters of the algorithm: 7 • popS : The population of S-boxes, initially generated using the Fisher-Yates shuffle algorithm to ensure bijectivity. • iterK : Maximum number of iterations, set to 150,000 in our experiments. • popK : Population size, representing the number of elite S -boxes maintained in each generation. • mu...
-
[27]
Results and Discussion This section presents the results of our comprehensive experimental study on the modified genetic algorithm for S-box generation. We analyze the performance of the algorithm across various parameter configurations and discuss the implications of our findings. 5.1. Overview of Experimental Results Our primary metric for evaluating th...
-
[28]
WHS SA 104 - 30,000,000
-
[29]
WHS GaT 104 - 3,239,000
-
[30]
WHS GaT 104 - 3,849,881
-
[31]
PCF Ga 104 - 741,371
-
[32]
PCF GaT 104 - 167,451
-
[33]
PCF LSA 104 - 172,280
-
[34]
WCF LSA 104 - 89,460
-
[35]
WCF HC 104 37% 65,933
-
[36]
WHS SA 104 56.4% 450,000
-
[37]
WCF SA 104 100% 65,000 [44,55] ECF SA 104 100% 55,000 .. 83,000
-
[38]
WHS HC 104 100% 50,000 [5,24] WCFS HC 104 100% 50,000 Our work WHS Ga 104 100% 49,399 11 The achievement of parity with the best - known results using a genetic algorithm is particularly noteworthy and underscores the potential of evolutionary approaches in cryptographic primitive generation. 5.7. Practical Implications The superior performance of the 1po...
-
[39]
Conclusion This study presents a significant advancement in the field of S-box generation for symmetric key cryptography, focusing on the application of genetic algorithms to produce highly nonlinear substitutions. Our research demonstrates that genetic algorithms, when properly optimized and combined with the Walsh -Hadamard Spectrum (WHS) cost function,...
-
[40]
Y. Li, J. Feng, Q. Zhao, Y. Wei, HDLBC: A lightweight block cipher with high diffusion, Integration 94 (2024) 102090. https://doi.org/10.1016/j.vlsi.2023.102090
-
[42]
M. Milanič , B. Servatius, H. Servatius, Chapter 8 - Codes and cyphers, in: M. Milanič, B. Servatius, H. Servatius (Eds.), Discrete Mathematics With Logic, Academic Press, 2024: pp. 163 –179. https://doi.org/10.1016/B978-0-44-318782- 7.00013-7
-
[43]
C. A S, M. S P, P. R K, Implementation of S-box for lightweight block cipher, in: 2023 3rd International Conference on Intelligent Technologies (CONIT), 2023: pp. 1 –4. https://doi.org/10.1109/CONIT59222.2023. 10205535
-
[44]
A. Kuznetsov, N. Poluyanenko, E. Frontoni, S. Kandiy, O. Peliukh, A new cost function for heuristic search of nonlinear substitutions, Expert Systems with Applications 237 (2024) 121684. https://doi.org/10.1016/j.eswa.2023.121684
-
[45]
A.J. Menezes, P.C. van Oorschot, S.A. Vanstone, P.C. van Oorschot, S.A. Vanstone, Handbook of Applied Cryptography, CRC Press, 2018. https://doi.org/10.1201/9780429466335
-
[46]
C.E. Shannon, Communication theory of secrecy systems, The Bell System Technical Journal 28 (1949) 656 –715. https://doi.org/10.1002/j.1538- 7305.1949.tb00928.x
-
[47]
C. Carlet, Vectorial Boolean functions for cryptography, Boolean Models and Methods in Mathematics, Computer Science, and Engineering (2006)
work page 2006
-
[48]
A. Freyre -Echevarría, A. Alanezi, I. Martínez-Díaz, M. Ahmad, A.A. Abd El - Latif, H. Kolivand, A. Razaq, An External Parameter Independent Novel Cost Function for Evolving Bijective Substitution-Boxes, Symmetry 12 (2020) 1896. https://doi.org/10.3390/sym12111896
-
[49]
S. Picek, M. Cupic, L. Rotim, A New Cost Function for Evolution of S -Boxes, Evolutionary Computation 24 (2016) 695 – 718. https://doi.org/10.1162/EVCO_a_00191
-
[50]
Álvarez -Cubero, Vector Boolean Functions: applications in symmetric cryptography, 2015
J. Álvarez -Cubero, Vector Boolean Functions: applications in symmetric cryptography, 2015. https://doi.org/10.13140/RG.2.2.12540.236 85
-
[51]
K. Lisitskiy, I. Lisitska, A. Kuznetsov, Cryptographically Properties of Random S- Boxes., in: Proceedings of the 16th International Conference on ICT in Education, Research and Industrial Applications. Integration, Harmonization and Knowledge Transfer . Volume II: Workshops, Kharkiv, Ukraine, October 06 - 10, 2020., 2020: pp. 228 –241. http://ceur - ws.o...
work page 2020
-
[53]
J. Daemen, V. Rijmen, Specification of Rijndael, in: J. Daemen, V. Rijmen (Eds.), The Design of Rijndael: The Advanced Encryption Standard (AES), Springer, Berlin, Heidelberg, 2020: pp. 31 –51. https://doi.org/10.1007/978-3-662-60769- 5_3
-
[54]
Bard, Algebraic Cryptanalysis, Springer US, Boston, MA, 2009
G.V. Bard, Algebraic Cryptanalysis, Springer US, Boston, MA, 2009. https://doi.org/10.1007/978-0-387-88757-9
-
[55]
N.T. Courtois, G.V. Bard, Algebraic Cryptanalysis of the Data Encryption Standard, in: S.D. Galbraith (Ed.), Cryptography and Coding, Springer, Berlin, Heidelberg, 2007: pp. 152 –169. https://doi.org/10.1007/978-3-540-77272- 9_10
-
[57]
Freyre Echevarría, Evolución híbrida de s-cajas no lineales resistentes a ataques de potencia, 2020
A. Freyre Echevarrí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.772 84/1
-
[58]
J. McLaughlin, Applications of search techniques to cryptanalysis and the construction of cipher components, phd, University of York, 2012. https://etheses.whiterose.ac.uk/3674/ (accessed October 27, 2022)
work page 2012
-
[59]
L.D. Burnett, Heuristic Optimization of Boolean Functions and Substitution Boxes for Cryptography, phd, Queensland University of Technology, 2005. https://eprints.qut.edu.au/16023/ (accessed May 19, 2021)
work page 2005
-
[60]
A. Kuznetsov, S. Kandii, E. Frontoni, N. Poluyanenko, SBGen: A high -performance library for rapid generation of cryptographic S-boxes, SoftwareX 27 (2024) 101788. https://doi.org/10.1016/j.softx.2024.101788
-
[61]
J.A. Clark, J.L. Jacob, S. Stepney, The design of S -boxes by simulated annealing, New Gener Comput 23 (2005) 219 –231. https://doi.org/10.1007/BF03037656
-
[62]
A. Freyre Echevarría, I. Martínez Díaz, A new cost function to improve nonlinearity of bijective S-boxes, (2020)
work page 2020
-
[63]
O. Kuznetsov, N. Poluyanenko, E. Frontoni, S. Kandiy, Enhancing Smart Communication Security: A Novel Cost Function for Efficient S -Box Generation in Symmetric Key Cryptography, Cryptography 8 (2024) 17. https://doi.org/10.3390/cryptography80200 17
-
[64]
O. Kuznetsov, N. Poluyanenko, E. Frontoni, S. Kandiy, M. Karpinski, R. Shevchuk, Enhancing Cryptographic Primitives through Dynamic Cost Function Optimization in Heuristic Search, Electronics 13 (2024) 1825. https://doi.org/10.3390/electronics1310182 5
-
[65]
Nyberg, Perfect nonlinear S -boxes, in: D.W
K. Nyberg, Perfect nonlinear S -boxes, in: D.W. Davies (Ed.), Advances in Cryptology — EUROCRYPT ’91, Springer, Berlin, Heidelberg, 1991: pp. 378 –386. https://doi.org/10.1007/3-540-46416-6_32
-
[66]
Nyberg, Differentially uniform mappings for cryptography, in: T
K. Nyberg, Differentially uniform mappings for cryptography, in: T. Helleseth (Ed.), Advances in Cryptology — EUROCRYPT ’93, Springer, Berlin, Heidelberg, 1994: pp. 55–64. https://doi.org/10.1007/3 -540- 48285-7_6
work page doi:10.1007/3 1994
-
[67]
R. La Scala, S.K. Tiwari, Stream/block ciphers, difference equations and algebraic attacks, Journal of Symbolic Computation 109 (2022) 177 –198. https://doi.org/10.1016/j.jsc.2021.09.001
-
[68]
D. Souravlias, K.E. Parsopoulos, G.C. Meletiou, Designing bijective S -boxes using Algorithm Portfolios with limited time budgets, Applied Soft Computing 59 (2017) 475 –486. https://doi.org/10.1016/j.asoc.2017.05.052
-
[69]
Scalable Funding of Bitcoin Micropayment Channel Networks
W. Millan, L. Burnett, G. Carter, A. Clark, E. Dawson, Evolutionary Heuristics for Finding Cryptographically Strong S-Boxes, in: V. Varadharajan, Y. Mu (Eds.), Information and Communication Security, Springer, Berlin, Heidelberg, 1999: pp. 263–274. ht tps://doi.org/10.1007/978-3- 540-47942-0_22
-
[70]
Tesar, A New Method for Generating High Non -linearity S -Boxes, (2010)
P. Tesar, A New Method for Generating High Non -linearity S -Boxes, (2010). http://dspace.lib.vutbr.cz/xmlui/handle/110 12/56957 (accessed August 16, 2020)
work page 2010
-
[71]
G. Ivanov, N. Nikolov, S. Nikova, Cryptographically Strong S -Boxes Generated by Modified Immune Algorithm, in: E. Pasalic, L.R. Knudsen (Eds.), Cryptography and Information Security in the Balkans, Springer International Publishing, Cham, 2016: pp. 31 –42. https://doi.org/10.1007/978-3-319-29172- 7_3
-
[72]
G. Ivanov, N. Nikolov, S. Nikova, Reversed genetic algorithms for generation of bijective s -boxes with good cryptographic properties, Cryptogr. Commun. 8 (2016) 247–276. https://doi.org/10.1007/s12095 - 015-0170-5
-
[73]
M. Rodinko, R. Oliynykov, Y. Gorbenko, Optimization of the High Nonlinear S - Boxes Generation Method, Tatra Mountains Mathematical Publications 70 (2017) 93 –
work page 2017
-
[74]
https://doi.org/10.1515/tmmp -2017- 0020
-
[75]
F. Artuğer, F. Özkaynak, A new post - processing approach for improvement of nonlinearity property in substitution boxes, Integration 94 (2024) 102105. https://doi.org/10.1016/j.vlsi.2023.102105. 14
-
[76]
T. Haider, N.A. Azam, U. Hayat, Substitution box generator with enhanced cryptographic properties and minimal computation time, Expert Systems with Applications 241 (2024) 122779. https://doi.org/10.1016/j.eswa.2023.122779
-
[77]
S.S. Jamal, M.M. Hazzazi, M.F. Khan, Z. Bassfar, A. Aljaedi, Z. ul Islam, Region of interest-based medical image encryption technique based on chaotic S-boxes, Expert Systems with Applications 238 (2024) 122030. https://doi.org/10.1016/j.eswa.2023.122030
-
[78]
S. Fahd, M. Afzal, W. Iqbal, D. Shah, I. Khalid, The reality of backdoored S - Boxes—An eye opener, Journal of Information Security and Applications 80 (2024) 103674. https://doi.org/10.1016/j.jisa.2023.103674
- [79]
-
[80]
O.O. Kuznetsov, Y.I. Gorbenko, I.M. Bilozertsev, A.V. Andrushkevych, O.P. Narizhnyi, Algebraic immunity of non - linear blocks of symmetric ciphers, Telecommun Radio Eng 77 (2018) 309 – 325. https://doi.org/10.1615/TelecomRadEng.v7 7.i4.30
-
[81]
A. Kuznetsov, R. Serhiienko, D. Prokopovych-Tkachenko, Y. Tarasenko, Evaluation of Algebraic Immunity of modern block ciphers, in: Proc. IEEE Int. Conf. Dependable Syst., Serv. Technol., DESSERT, Institute of Electrical and Electronics Engineers Inc., 2018: pp. 288 – 293. https://doi.org/10.1109/DESSERT.2018.84 09146
-
[82]
K. Lisitskiy, I. Lisitska, A. Kuznetsov, Cryptographically properties of random S - boxes, in: CEUR Workshop Proceedings, 2020: pp. 228 –241. https://www.scopus.com/inward/record.uri ?eid=2-s2.0- 85096091835&partnerID=40&md5=c5ec4 03d7b8065c4525906c70c04ce33
work page 2020
-
[83]
I. Gorbenko, A. Kuznetsov, Y. Gorbenko, A. Pushkar’Ov, Y. Kotukh, K. Kuznetsova, Random S -boxes generation methods for symmetric cryptography, in: 2019 IEEE 2nd Ukraine Conference on Electrical and Computer Engineering, UKRCON 2019 - Proceedings, 2019: pp. 947 –950. https://doi.org/10.1109/UKRCON.2019.88 79962
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.