IGA : An Improved Genetic Algorithm to Construct Weightwise (Almost) Perfectly Balanced Boolean Functions with High Weightwise Nonlinearity

The Boolean functions satisfying secure properties on the restricted sets of inputs are studied recently due to their importance in the framework of the FLIP stream cipher. However, finding Boolean functions with optimal cryptographic properties is an open research problem in the cryptographic community. This paper presents an Improved Genetic Algorithm (IGA) with the directed changes that keep the weightwise balancedness of Boolean functions. A cross-protection strategy is proposed to ensure that the offspring has the same weightwise balancedness characteristics of the parents while implementing crossover. Then, a large number of weightwise (almost) perfectly balanced (W(A)PB) functions with a good nonlinearity profile are obtained based on IGA. Finally, we make comparisons between our constructions and relevant works. The comparisons showthat IGA has a significant advantage for reaching the W(A)PB functions with high weightwise nonlinearity. Moreover, it is the first time to obtain the 8-variable WPB functions with the weightwise nonlinearity of 28 in the restricted sets of inputs with Hamming weight of 4, and list the statistical indicators of the weightwise nonlinearity for W(A)PB functions for input size n = 9, 10.

Automated summary

This study investigates the Boolean functions that satisfy secure properties in the FLIP stream cipher. However, finding Boolean functions with optimal cryptographic properties remains an unsolved problem in the cryptographic community. This paper proposes an Improved Genetic Algorithm (IGA) to find weightwise balanced Boolean functions and obtains a large number of weightwise perfectly balanced functions with good nonlinearity profiles. The comparison of our constructions with relevant works demonstrates the significant advantage of IGA in achieving high weightwise nonlinearity functions.