Substitution boxes are the main nonlinear component of block ciphers. The security of these ciphers against linear, differential, or side-channel attacks is dependent on the design of such component and their intrinsic properties. There are several methods that aim to cryptographically define, generate, or search for strong substitution boxes. The application of combinatorial optimization algorithms is one of the most useful methodologies in this research area. In this paper, we present a novel hybrid method based on the Leaders and Followers and hill-climbing over Hamming Weight Classes metaheuristics, coupled with a new trade-off fitness function that generates 8-bit bijective substitution boxes with good resisting properties towards classical cryptanalysis and side-channel attacks by power consumption. We address the best Pareto optimal solutions for the multi-objective optimization of non-linearity and confusion coefficient variance.

The property of nonlinearity has high importance for the design of strong substitution boxes. Therefore, the development of new techniques to produce substitution boxes with high values of nonlinearity is essential. Many research papers have shown that optimization algorithms are an efficient technique to obtain good solutions. However, there is no reference in the public literature showing that a heuristic method obtains optimal nonlinearity unless seeded with optimal initial solutions. Moreover, the majority of papers with the best nonlinearity reported for pseudo-random seeding of the algorithm(s) often achieve their results with the help of some cost function(s) over the Walsh–Hadamard spectrum of the substitution. In the sense, we proposed to present, in this paper, a novel external parameter independent cost function for evolving bijective s-boxes of high nonlinearity, which is highly correlated to this property. Several heuristic approaches including GaT (genetic and tree), LSA (local search algorithm), and the Hill Climbing algorithm have been investigated to assess the performance of evolved s-boxes. A performance comparison has been done to show the advantages of our new cost function, with respect to cost functions for s-boxes like Clark’s and Picek’s cost functions.

Many research focuses on find S-boxes with good cryptographic properties applying a heuristic method and a balanced, objective function. The design of S-boxes with theoretical resistance against Side-Channel Attacks by power consumption is addressed with properties defined under one of these two models: the Hamming Distance leakage model and the Hamming Weight leakage model. As far as we know, a balanced search criterion that considers properties under both, at the same time, remains an open problem. We define two new optimal objective functions that can be used to obtain S-boxes with good cryptographic properties values, keeping high theoretical resistance for the two leakage models; we encourage using at least one of our objective functions.We apply a Hill Climbing heuristic method over the S-box’s space to measure which objective function is better and to compare the obtained S-boxes with the S-boxes in the actual literature. We also confirm some key relationships between the properties and which property is more suitable to be used.