A Novel S-Box Construction Technique Based on the Improved Genetic Algorithms through 2 N-Round Searching

S-box is the main nonlinear component of block ciphers. In order to efficiently construct 8-bit S-boxes with excellent cryptographic properties, a novel 8-bit S-box construction technique based on the improved genetic algorithm is proposed. Firstly, a mixed population samples is generated to improve the nature of the initial population. Secondly, a segmented fitness function, taking into account differential uniformity, nonlinearity, and the strict avalanche criterion, is designed to evaluate individual candidate population. Note that the bijectivity of S-box populations can be ensured during the crossover operation. During the mutation operation, a reverse search method based on the properties of the linear approximation table (LAT) and the differential distribution table (DDT) of an S-box is proposed, and a 2 N-round searching strategy, combined with the hill-climbing algorithm, the random search and the reverse search technique, is designed to search mutation points to optimize the cryptographic properties of the constructed S-boxes. Additionally, multi-threading technology is used for parallel computing to optimize the computational efficiency. Experimental results demonstrate that the proposed technique can construct S-boxes with excellent cryptographic properties efficiently, achieving a differential uniformity of 4, a nonlinearity of 112, while also satisfying the bijectivity property.