Evolving Highly Nonlinear Balanced Boolean Functions Using Genetic Algorithm with Variable Neighborhood Search

Cryptographic Boolean functions are building blocks of stream and block ciphers based symmetric cryptosystems. These functions should possess high nonlinearity, low autocorrelation, and balancedness to resist attacks like linear and differential cryptanalysis. The exponential search space of size 22n exhibits significant optimization challenges. This paper proposes an enhanced hybrid genetic algorithm (HGA) integrated with variable neighborhood search (VNS) to address optimization issues. The HGA employs a dynamic fitness function, spectrum-aware crossover, VNS perturbations, and tabu list enforcement, guided by Fast Walsh-Hadamard Transform (FWHT) spectral analysis. For even n, it produces balanced functions with nonlinearity near theoretical limits and imbalanced near-bent functions with maximal nonlinearity, suitable for stream and block ciphers, respectively. For odd n, it consistently generates balanced functions with robust cryptographic properties. Experimental results validate the algorithm’s effectiveness across various input sizes, enhancing resistance to cryptanalytic attacks.