An External Parameter Independent Novel Cost Function for Evolving Bijective Substitution-Boxes

Abstract

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.

Keywords

• substitution boxes
• cost function
• nonlinearity
• Walsh–Hadamard spectrum
• optimization