An Effective Algorithm to Increase the Nonlinearity of S-boxes
提高S盒非线性度的有效算法

A S-box is the important nonlinear eonponent of block cipher algorithms, William Millian provied the Hill Climbing algorithm for improving the nonlinearity of S-boxes, which can increase the nonlinearity of a S-box by swapping two output vectors, Under the algorithm, the nonlinearity will reach a local maximum,which means that swapping any two output vectors can not increase the nonlinearity any more. In this paper, how to improve the nonlinearity of Sboxes by changing the positions of three output vectors simultaneously is explored. The MHC algorithm is given which can increase the nonlinearity on the basis of the Hill Climbing algorithm. The experimental results show that, the MHC algorithm is apparently more effective than the Hill Climbing to improve the nonlinearity of random S-boxes.