A Systematic Evaluation of Evolving Highly Nonlinear Boolean Functions in Odd Sizes
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910332504506368 |
|---|---|
| author | Carlet, Claude Ðurasevic, Marko Jakobovic, Domagoj Picek, Stjepan Mariot, Luca |
| author_facet | Carlet, Claude Ðurasevic, Marko Jakobovic, Domagoj Picek, Stjepan Mariot, Luca |
| contents | Boolean functions are mathematical objects used in diverse applications. Different applications also have different requirements, making the research on Boolean functions very active. In the last 30 years, evolutionary algorithms have been shown to be a strong option for evolving Boolean functions in different sizes and with different properties. Still, most of those works consider similar settings and provide results that are mostly interesting from the evolutionary algorithm's perspective. This work considers the problem of evolving highly nonlinear Boolean functions in odd sizes. While the problem formulation sounds simple, the problem is remarkably difficult, and the related work is extremely scarce. We consider three solutions encodings and four Boolean function sizes and run a detailed experimental analysis. Our results show that the problem is challenging, and finding optimal solutions is impossible except for the smallest tested size. However, once we added local search to the evolutionary algorithm, we managed to find a Boolean function in nine inputs with nonlinearity 241, which, to our knowledge, had never been accomplished before with evolutionary algorithms. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_09937 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Systematic Evaluation of Evolving Highly Nonlinear Boolean Functions in Odd Sizes Carlet, Claude Ðurasevic, Marko Jakobovic, Domagoj Picek, Stjepan Mariot, Luca Neural and Evolutionary Computing Cryptography and Security Boolean functions are mathematical objects used in diverse applications. Different applications also have different requirements, making the research on Boolean functions very active. In the last 30 years, evolutionary algorithms have been shown to be a strong option for evolving Boolean functions in different sizes and with different properties. Still, most of those works consider similar settings and provide results that are mostly interesting from the evolutionary algorithm's perspective. This work considers the problem of evolving highly nonlinear Boolean functions in odd sizes. While the problem formulation sounds simple, the problem is remarkably difficult, and the related work is extremely scarce. We consider three solutions encodings and four Boolean function sizes and run a detailed experimental analysis. Our results show that the problem is challenging, and finding optimal solutions is impossible except for the smallest tested size. However, once we added local search to the evolutionary algorithm, we managed to find a Boolean function in nine inputs with nonlinearity 241, which, to our knowledge, had never been accomplished before with evolutionary algorithms. |
| title | A Systematic Evaluation of Evolving Highly Nonlinear Boolean Functions in Odd Sizes |
| topic | Neural and Evolutionary Computing Cryptography and Security |
| url | https://arxiv.org/abs/2402.09937 |