Naslov
Evolving Constructions for Balanced, Highly Nonlinear Boolean Functions

Autori
Carlet, Claude ; Djurasevic, Marko ; Jakobovic, Domagoj ; Mariot, Luca ; Picek, Stjepan

Vrsta, podvrsta i kategorija rada
Radovi u zbornicima skupova, cjeloviti rad (in extenso), znanstveni

Skup
Proceedings of the Genetic and Evolutionary Computation Conference (GECCO '22)

Mjesto i datum
Boston (MA), Sjedinjene Američke Države, 09.07.2022. - 13.07.2022

Vrsta sudjelovanja
Predavanje

Vrsta recenzije
Međunarodna recenzija

Ključne riječi
evolutionary algorithms, balancedness, non-linearity, boolean functions, secondary constructions

Sažetak
Finding balanced, highly nonlinear Boolean functions is a difficult problem where it is not known what nonlinearity values are possible to be reached in general. At the same time, evolutionary computation is successfully used to evolve specific Boolean function instances, but the approach cannot easily scale for larger Boolean function sizes. Indeed, while evolving smaller Boolean functions is almost trivial, larger sizes become increasingly difficult, and evolutionary algorithms perform suboptimally. In this work, we ask whether genetic programming (GP) can evolve constructions resulting in balanced Boolean functions with high nonlinearity. This question is especially interesting as there are only a few known such constructions. Our results show that GP can find constructions that generalize well, i.e., result in the required functions for multiple tested sizes. Further, we show that GP evolves many equivalent constructions under different syntactic representations. Interestingly, the simplest solution found by GP is a particular case of the well-known indirect sum construction.

Izvorni jezik
Engleski

Znanstvena područja
Računarstvo

POVEZANOST RADA