Evolving Balanced Non-Linear Boolean Functions with Cellular Genetic Algorithms

Luigi Rovito; Andrea De Lorenzo; Mauro Castelli; Luca Manzoni

doi:10.31181/dma412026185

Authors

Luigi Rovito Department of Engineering and Architecture, University of Trieste, via Valerio 12, 34128, Trieste, Italy https://orcid.org/0000-0003-2772-4095
Andrea De Lorenzo Department of Engineering and Architecture, University of Trieste, via Valerio 12, 34128, Trieste, Italy https://orcid.org/0000-0002-7628-7672
Mauro Castelli NOVA Information Management School (NOVA IMS), Universidade Nova de Lisboa, 1070-312 Lisbon, Portugal https://orcid.org/0000-0002-8793-1451
Luca Manzoni Department of Mathematics, Informatics and Geosciences, University of Trieste, via Weiss 2, 34128, Trieste, Italy https://orcid.org/0000-0001-6312-7728

DOI:

https://doi.org/10.31181/dma412026185

Keywords:

Evolutionary Computation, Cybersecurity, Genetic Algorithms, Boolean Functions, Cellular Evolutionary Algorithms, Cryptography

Abstract

Boolean functions are essential building blocks in the design of secure stream ciphers. Finding cryptographically strong Boolean functions is, however, a notoriously difficult optimization problem, owing to the size of the search space and the combinatorial nature of the task. Evolutionary Algorithms (EAs) have proven effective at constructing Boolean functions that are simultaneously balanced and highly nonlinear, two properties that are crucial for resisting correlation and statistical attacks. Nevertheless, these and other heuristic approaches often converge prematurely to local optima because of the complexity of the fitness landscape. Cellular Automata (CA) have been used extensively to represent and analyze Boolean functions, and spatially structured populations arranged on cellular toroidal grids have been shown, in other evolutionary paradigms, to slow the propagation of dominant individuals and to encourage broader exploration. The two ideas have not been brought together: cellular population structures have not previously been used to guide the search for balanced, nonlinear Boolean functions. We therefore investigate the integration of cellular population structures into Genetic Algorithms (GAs) for evolving balanced truth tables with high nonlinearity. We evolve Boolean functions of 8 to 16 variables and compare different neighborhood radii of the cellular grid. Our results show that, for larger numbers of variables, small neighborhoods improve the nonlinearity of the evolved functions relative to a non-spatial GA, and that this improvement is statistically significant. We emphasize that the contribution of this work is an analysis of the search and diversity dynamics induced by the cellular structure: the nonlinearity values obtained remain below the best-known values for balanced Boolean functions, and the study is not intended as a step forward in the construction of cryptographically deployable functions.

Downloads

Download data is not yet available.

References

Katz, J. (2026). Introduction to modern cryptography, revised third edition: Student solutions manual. https://doi.org/10.1201/9781003776994-1

Carlet, C. (2010). Boolean functions for cryptography and error-correcting codes. In Y. Crama & P. L. Hammer (Eds.), Boolean models and methods in mathematics, computer science, and engineering (pp. 257–397). Cambridge University Press. https://doi.org/10.1017/CBO9780511780448.011

Carlet, C. (Ed.). (2020). Boolean functions for cryptography and coding theory. Cambridge University Press. https://doi.org/10.1017/9781108606806

Millan, W., Clark, A., & Dawson, E. (1998). Heuristic design of cryptographically strong balanced Boolean functions. In International Conference on the Theory and Applications of Cryptographic Techniques (pp. 489–499). https://doi.org/10.1007/BFb0054148

Millan, W., Clark, A., & Dawson, E. (1997). An effective genetic algorithm for finding highly nonlinear Boolean functions. In International Conference on Information and Communications Security (pp. 149–158). https://doi.org/10.1007/BFb0028471

Picek, S., Carlet, C., Guilley, S., Miller, J. F., & Jakobovic, D. (2016). Evolutionary algorithms for Boolean functions in diverse domains of cryptography. Evolutionary Computation, 24(4), 667–694. https://doi.org/10.1162/EVCO_a_00190

Picek, S., Jakobovic, D., Miller, J. F., Batina, L., & Cupic, M. (2016). Cryptographic Boolean functions: One output, many design criteria. Applied Soft Computing, 40, 635–653. https://doi.org/10.1016/j.asoc.2015.10.066

Bonin, L., Rovito, L., De Lorenzo, A., & Manzoni, L. (2024). Cellular geometric semantic genetic programming. Genetic Programming and Evolvable Machines, 25(1), 1–32. https://doi.org/10.1007/s10710-024-09480-8

Rovito, L., Bonin, L., Farinati, D., Vanneschi, L., Manzoni, L., Lorenzo, A. D., & Pietropolli, G. (2025). Exploring the integration of cellular structures in genetic programming-based methods. In B. Xue, L. Manzoni, & I. Bakurov (Eds.), Genetic programming – 28th European Conference, EuroGP 2025, held as part of EvoStar 2025, Trieste, Italy, April 23–25, 2025, proceedings (Vol. 15609, pp. 120–138). Springer. https://doi.org/10.1007/978-3-031-89991-1_8

Manzoni, L., Mariot, L., & Menara, G. (2026). Combinatorial designs and cellular automata: A survey. Discrete Applied Mathematics, 379, 656–674. https://doi.org/10.1016/J.DAM.2025.10.014

Von Neumann, J., Burks, A. W., & Burks, A. W. (1966). Theory of self-reproducing automata. https://media-cdn.factba.se/pdf/theory-of-self-replicating-automata-john-vonneumann.pdf

Zhang, M., Tian, N., Palade, V., Ji, Z., & Wang, Y. (2018). Cellular artificial bee colony algorithm with Gaussian distribution. Information Sciences, 462, 374–401. https://doi.org/10.1016/j.ins.2018.06.032

Giacobini, M., Tomassini, M., Tettamanzi, A. G., & Alba, E. (2005). Selection intensity in cellular evolutionary algorithms for regular lattices. IEEE Transactions on Evolutionary Computation, 9(5), 489–505. https://doi.org/10.1109/TEVC.2005.850298

Pietropolli, G., Nichele, S., & Medvet, E. (2024). The role of the substrate in CA-based evolutionary algorithms. In Proceedings of the Genetic and Evolutionary Computation Conference (pp. 768–777). https://doi.org/10.1145/3638529.3654112

Salto, C., & Alba, E. (2019). Cellular genetic algorithms: Understanding the behavior of using neighborhoods. Applied Artificial Intelligence, 33(10), 863–880. https://doi.org/10.1080/08839514.2019.1646005

Moran, P. A. (1950). Notes on continuous stochastic phenomena. Biometrika, 37(1/2), 17–23. https://doi.org/10.2307/2332142

Dimovski, A., & Gligoroski, D. (2003). Generating highly nonlinear Boolean functions using a genetic algorithm. In 6th International Conference on Telecommunications in Modern Satellite, Cable and Broadcasting Service, 2003. TELSIKS 2003. (Vol. 2, pp. 604–607). https://doi.org/10.1109/TELSKS.2003.1246297

Asthana, R., Verma, N., & Ratan, R. (2014). Generation of Boolean functions using genetic algorithm for cryptographic applications. In 2014 IEEE International Advance Computing Conference (IACC) (pp. 1361–1366). https://doi.org/10.1109/IAdCC.2014.6779525

Husa, J. (2019). Comparison of genetic programming methods on design of cryptographic Boolean functions. In L. Sekanina, T. Hu, N. Lourenço, H. Richter, & P. García-Sánchez (Eds.), Genetic programming (pp. 228–244). Springer International Publishing. https://doi.org/10.1007/978-3-030-16670-0_15

Fuller, J., Dawson, E., & Millan, W. (2003). Evolutionary generation of bent functions for cryptography. In The 2003 Congress on Evolutionary Computation, 2003. CEC '03. (Vol. 3, pp. 1655–1661). https://doi.org/10.1109/CEC.2003.1299871

Dick, G., & Whigham, P. A. (2013). Controlling bloat through parsimonious elitist replacement and spatial structure. In European Conference on Genetic Programming (pp. 13–24). https://doi.org/10.1007/978-3-642-37207-0_2

Zheng, Y., & Zhang, X.-M. (1999). Plateaued functions. In International Conference on Information and Communications Security (pp. 284–300). https://doi.org/10.1007/978-3-540-47942-0_24

Cohen, G. D., & Litsyn, S. N. (1992). On the covering radius of Reed-Muller codes. Discrete Mathematics, 106, 147–155. https://doi.org/10.1016/0012-365X(92)90542-N

Hou, X.-d. (1997). On the norm and covering radius of the first-order Reed-Muller codes. IEEE Transactions on Information Theory, 43(3), 1025–1027. https://doi.org/10.1109/18.568715

Rothaus, O. S. (1976). On "bent" functions. Journal of Combinatorial Theory, Series A, 20(3), 300–305. https://doi.org/10.1016/0097-3165(76)90024-8

Mesnager, S. (2016). Bent functions – Fundamentals and results. Springer. https://doi.org/10.1007/978-3-319-32595-8

Berlekamp, E. R. (2015). Algebraic coding theory (revised ed.). World Scientific. https://doi.org/10.1142/9407

Tarannikov, Y. V. (2000). On resilient Boolean functions with maximal possible nonlinearity. In B. K. Roy & E. Okamoto (Eds.), Progress in cryptology – INDOCRYPT 2000, First International Conference in Cryptology in India, Calcutta, India, December 10–13, 2000, proceedings (Vol. 1977, pp. 19–30). Springer. https://doi.org/10.1007/3-540-44495-5_3

Siegenthaler, T. (1984). Correlation-immunity of nonlinear combining functions for cryptographic applications (corresp.). IEEE Transactions on Information Theory, 30(5), 776–780. https://doi.org/10.1109/TIT.1984.1056949

Chen, Y., & Lu, P. (2011). Two classes of symmetric Boolean functions with optimum algebraic immunity: Construction and analysis. IEEE Transactions on Information Theory, 57(4), 2522–2538. https://doi.org/10.1109/TIT.2011.2111810

López-López, I., Sosa-Gómez, G., Segura, C., Oliva, D., & Rojas, O. (2020). Metaheuristics in the optimization of cryptographic Boolean functions. Entropy, 22(9), 1052. https://doi.org/10.3390/e22091052

Clark, J. A., Jacob, J. L., Maitra, S., & Stănică, P. (2004). Almost Boolean functions: The design of Boolean functions by spectral inversion. Computational Intelligence, 20(3), 450–462. https://doi.org/10.1111/j.0824-7935.2004.00245.x

Djurasevic, M., Jakobovic, D., Mariot, L., & Picek, S. (2023). A survey of metaheuristic algorithms for the design of cryptographic Boolean functions. Cryptography and Communications, 15(6), 1171–1197. https://doi.org/10.1007/s12095-023-00662-2

Carlet, C., Djurasevic, M., Jakobovic, D., Mariot, L., & Picek, S. (2022). Evolving constructions for balanced, highly nonlinear Boolean functions. In Proceedings of the Genetic and Evolutionary Computation Conference (pp. 1147–1155). https://doi.org/10.1145/3512290.3528871

Koza, J. R. (1994). Genetic programming as a means for programming computers by natural selection. Statistics and Computing, 4(2), 87–112. https://doi.org/10.1007/BF00175355

Carlet, C., Jakobovic, D., & Picek, S. (2021). Evolutionary algorithms-assisted construction of cryptographic Boolean functions. In Proceedings of the Genetic and Evolutionary Computation Conference (pp. 565–573). https://doi.org/10.1145/3449639.3459362

Picek, S., & Jakobovic, D. (2016). Evolving algebraic constructions for designing bent Boolean functions. In Proceedings of the Genetic and Evolutionary Computation Conference 2016 (pp. 781–788). https://doi.org/10.1145/2908812.2908915

Picek, S., Marchiori, E., Batina, L., & Jakobovic, D. (2014). Combining evolutionary computation and algebraic constructions to find cryptography-relevant Boolean functions. In Parallel Problem Solving from Nature–PPSN XIII: 13th International Conference, Ljubljana, Slovenia, September 13–17, 2014. Proceedings 13 (pp. 822–831). https://doi.org/10.1007/978-3-319-10762-2_81

Holland, J. H. (1973). Genetic algorithms and the optimal allocation of trials. SIAM Journal on Computing, 2(2), 88–105. https://doi.org/10.1137/0202009

Behera, P. K., & Gangopadhyay, S. (2022). An improved hybrid genetic algorithm to construct balanced Boolean function with optimal cryptographic properties. Evolutionary Intelligence, 15(1), 639–653. https://doi.org/10.1007/s12065-020-00538-x

Manzoni, L., Mariot, L., & Tuba, E. (2020). Balanced crossover operators in genetic algorithms. Swarm and Evolutionary Computation, 54, 100646. https://doi.org/10.1016/j.swevo.2020.100646

Mariot, L., & Leporati, A. (2015a). A genetic algorithm for evolving plateaued cryptographic Boolean functions. In International Conference on Theory and Practice of Natural Computing (pp. 33–45). https://doi.org/10.1007/978-3-319-26841-5_3

Mariot, L., & Leporati, A. (2015b). Heuristic search by particle swarm optimization of Boolean functions for cryptographic applications. In Proceedings of the Companion Publication of the 2015 Annual Conference on Genetic and Evolutionary Computation (pp. 1425–1426). https://doi.org/10.1145/2739482.2764674

Miller, J. F. (1999). An empirical study of the efficiency of learning Boolean functions using a Cartesian genetic programming approach. In Proceedings of the 1st Annual Conference on Genetic and Evolutionary Computation – Volume 2 (pp. 1135–1142). https://dl.acm.org/doi/abs/10.5555/2934046.2934074

Hrbacek, R., & Dvorak, V. (2014). Bent function synthesis by means of Cartesian genetic programming. In T. Bartz-Beielstein, J. Branke, B. Filipič, & J. Smith (Eds.), Parallel problem solving from nature – PPSN XIII (pp. 414–423). Springer International Publishing. https://doi.org/10.1007/978-3-319-10762-2_41

Picek, S., Jakobovic, D., Miller, J. F., Marchiori, E., & Batina, L. (2015). Evolutionary methods for the construction of cryptographic Boolean functions. In European Conference on Genetic Programming (pp. 192–204). https://doi.org/10.1007/978-3-319-16501-1_16

Picek, S., Jakobovic, D., & Golub, M. (2013). Evolving cryptographically sound Boolean functions. In Proceedings of the 15th Annual Conference Companion on Genetic and Evolutionary Computation (pp. 191–192). https://doi.org/10.1145/2464576.2464671

Mariot, L., Picek, S., Jakobovic, D., Djurasevic, M., & Leporati, A. (2022). Evolutionary construction of perfectly balanced Boolean functions. In 2022 IEEE Congress on Evolutionary Computation (CEC) (pp. 1–8). https://doi.org/10.1109/CEC55065.2022.9870427

Carlet, C., Djurasevic, M., Jakobovic, D., Mariot, L., & Picek, S. (2025). Degree is important: On evolving homogeneous Boolean functions. In Proceedings of the Genetic and Evolutionary Computation Conference Companion (pp. 795–798). https://doi.org/10.1145/3712255.3726779

Carlet, C., Durasevic, M., Jakobovic, D., Mariot, L., & Picek, S. (2024). Look into the mirror: Evolving self-dual bent Boolean functions. In M. Giacobini, B. Xue, & L. Manzoni (Eds.), Genetic programming (pp. 161–175). Springer Nature Switzerland. https://doi.org/10.1007/978-3-031-56957-9_10

Wang, Y., Gao, G., & Yuan, Q. (2022). Searching for cryptographically significant rotation symmetric Boolean functions by designing heuristic algorithms. Security and Communication Networks, 2022(1), Article 8188533. https://doi.org/10.1155/2022/8188533

Carlet, C., Djurasevic, M., Gasperov, B., Jakobovic, D., Mariot, L., & Picek, S. (2024). A new angle: On evolving rotation symmetric Boolean functions. In S. Smith, J. Correia, & C. Cintrano (Eds.), Applications of evolutionary computation (pp. 287–302). Springer Nature Switzerland. https://doi.org/10.1007/978-3-031-56852-7_19

Carlet, C., Đurasević, M., Jakobović, D., Picek, S., & Mariot, L. (2025). A systematic evaluation of evolving highly nonlinear Boolean functions in odd sizes. In B. Xue, L. Manzoni, & I. Bakurov (Eds.), Genetic programming (pp. 18–34). Springer Nature Switzerland. https://doi.org/10.1007/978-3-031-89991-1_2

Carlet, C., Đurasević, M., Jakobovic, D., Mariot, L., & Picek, S. (2025). The more the merrier: On evolving five-valued spectra Boolean functions. In P. García-Sánchez, E. Hart, & S. L. Thomson (Eds.), Applications of evolutionary computation (pp. 52–67). Springer Nature Switzerland. https://doi.org/10.1007/978-3-031-90062-4_4

Cussat-Blanc, S., Harrington, K., & Pollack, J. (2015). Gene regulatory network evolution through augmenting topologies. IEEE Transactions on Evolutionary Computation, 19(6), 823–837. https://doi.org/10.1109/TEVC.2015.2396199

Martins, T. M., & Neves, R. F. (2020). Applying genetic algorithms with speciation for optimization of grid template pattern detection in financial markets. Expert Systems with Applications, 147, 113191. https://doi.org/10.1016/j.eswa.2020.113191

Wickman, R., Poudel, B., Villarreal, T. M., Zhang, X., & Li, W. (2023). Efficient quality-diversity optimization through diverse quality species. In Proceedings of the Companion Conference on Genetic and Evolutionary Computation (pp. 699–702). https://doi.org/10.1145/3583133.3590581

Xie, H., & Zhang, M. (2012). Impacts of sampling strategies in tournament selection for genetic programming. Soft Computing, 16, 615–633. https://doi.org/10.1007/s00500-011-0760-x

Moraglio, A., Krawiec, K., & Johnson, C. G. (2012). Geometric semantic genetic programming. In C. A. C. Coello, V. Cutello, K. Deb, S. Forrest, G. Nicosia, & M. Pavone (Eds.), Parallel problem solving from nature – PPSN XII (pp. 21–31). Springer Berlin Heidelberg. https://doi.org/10.1007/978-3-642-32937-1_3

Pawlak, T. P., Wieloch, B., & Krawiec, K. (2015). Review and comparative analysis of geometric semantic crossovers. Genetic Programming and Evolvable Machines, 16, 351–386. https://doi.org/10.1007/s10710-014-9239-8

Vanneschi, L., Farinati, D., Rasteiro, D., Rosenfeld, L., Pietropolli, G., & Silva, S. (2025). Exploring non-bloating geometric semantic genetic programming. In Genetic programming theory and practice XXI (pp. 237–258). Springer Nature Singapore. https://doi.org/10.1007/978-981-96-0077-9_12

Mann, H. B., & Whitney, D. R. (1947). On a test of whether one of two random variables is stochastically larger than the other. The Annals of Mathematical Statistics, 18(1), 50–60. https://doi.org/10.1214/aoms/1177730491

Holm, S. (1979). A simple sequentially rejective multiple test procedure. Scandinavian Journal of Statistics, 65–70. https://www.jstor.org/stable/4615733

Garcia, S., & Herrera, F. (2008). An extension on statistical comparisons of classifiers over multiple data sets for all pairwise comparisons. Journal of Machine Learning Research, 9(12). https://www.jmlr.org/papers/volume9/garcia08a/garcia08a.pdf

Derrac, J., García, S., Molina, D., & Herrera, F. (2011). A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms. Swarm and Evolutionary Computation, 1(1), 3–18. https://doi.org/10.1016/j.swevo.2011.02.002

Meissel, K., & Yao, E. S. (2024). Using Cliff's delta as a non-parametric effect size measure: An accessible web app and R tutorial. Practical Assessment, Research, and Evaluation, 29(1). https://doi.org/10.7275/pare.1977