Semantic Mutation Operator for Fast and Efficient Design of Bent Boolean Functions

• https://rdcu.be/ds8Zc

Nonlinearity, Bent Boolean Functions, Heuristic Optimization, Genetic
Programming, Semantic Mutation

Boolean functions are important cryptographic primitives with extensive use in
symmetric cryptography. These functions need to possess various properties, such
as nonlinearity to be useful. The main limiting factor of the quality of
a Boolean function is the number of its input variables, which has to be
sufficiently large. The contemporary design methods either scale poorly or are
able to create only a small subset of all functions with the desired properties.
This necessitates the development of new and more efficient ways of Boolean
function design. In this paper, we propose a new semantic mutation operator for
the design of bent Boolean functions via genetic programming. The principle of
the proposed operator lies in evaluating the function's nonlinearity in detail to
purposely avoid mutations that could be disruptive and taking advantage of the
fact that the nonlinearity of a Boolean function is invariant under all affine
transformations. To assess the efficiency of this operator, we experiment with
three distinct variants of genetic programming and compare its performance to
three other commonly used non-semantic mutation operators. The detailed
experimental evaluation proved that the proposed semantic mutation operator is
not only significantly more efficient in terms of evaluations required by genetic
programming but also nearly three times faster than the second-best operator when
designing bent functions with 12 inputs and almost six times faster for functions
with 20 inputs.