Hybrid genetic algorithm with rank sorting for obtaining bijective S-boxes with good cryptographic properties

An S-box is an essential component in block ciphers, and its cryptography properties play a significant role in the security of the cipher. A good S-box must have high nonlinearity (<i>NL_F</i>) and low differential uniformity (<i>&delta;_F</i>). In this paper, a rank-sorting hybrid genetic algorithm is designed to find S-boxes that possess high nonlinearity and low difference uniformity. Compared with the traditional genetic algorithm, the rank-sorting hybrid genetic algorithm designed in this work was improved in the following aspects. First, the crossover protection strategy was designed and used in the crossover phase, which can assure the bijectivity of offspring. Second, an elite selection strategy based on the value of the fitness function was utilized in the selection step to prevent the loss of excellent individuals. In particular, a sorting method named the rank-sorting algorithm was proposed and implemented on the selected offspring before the next iteration began. The result of using the rank-sorting algorithm is that the differences between individuals for the next crossover increase, the possibility of generating excellent offspring increases, and the risk of the whole algorithm becoming stuck in local optimal solutions decreases. The simulation results show that when the number of variables is even (8 to 12), the bijective S-boxes with almost high nonlinearity and low differential uniformity can be searched by using the rank-sorting hybrid genetic algorithm.