Evolving Constructions for Balanced, Highly Nonlinear Boolean Functions
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Evolutionary AlgorithmsSimilar Papers 제목 키워드 기반
Monotone but Exciting: On Evolving Monotone Boolean Functions with High Nonlinearity
Monotone Boolean functions are a structurally important class of Boolean functions, but their restricted form imposes strong limitations on achievable nonlinearity. In this paper, we investigate whether evolutionary comp…
A Systematic Evaluation of Evolving Highly Nonlinear Boolean Functions in Odd Sizes
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 a…
Evolutionary AlgorithmsIDEM Enough? Evolving Highly Nonlinear Idempotent Boolean Functions
Idempotent Boolean functions form a highly structured subclass of Boolean functions that is closely related to rotation symmetry under a normal-basis representation and to invariance under a fixed linear map in a polynom…
Degree is Important: On Evolving Homogeneous Boolean Functions
Boolean functions with good cryptographic properties like high nonlinearity and algebraic degree play an important in the security of stream and block ciphers. Such functions may be designed, for instance, by algebraic c…
Evolutionary AlgorithmsEvolutionary Construction of Perfectly Balanced Boolean Functions
Finding Boolean functions suitable for cryptographic primitives is a complex combinatorial optimization problem, since they must satisfy several properties to resist cryptanalytic attacks, and the space is very large, wh…
Combinatorial Optimization