Results on symmetric S-boxes constructed by concatenation of RSSBs

Abstract

In this paper, we first present an efficient exhaustive search algorithm to enumerate 6 x 6 bijective S-boxes with the best-known nonlinearity 24 in a class of S-boxes that are symmetric under the permutation (x) = (x(0), x(2), x(3), x(4), x(5), x(1)), where x = (x(0), x1,...,x5)?26. Since any S-box S:?26?26 in this class has the property that S((x)) = (S(x)) for every x, it can be considered as a construction obtained by the concatenation of 5 x 5 rotation-symmetric S-boxes (RSSBs). The size of the search space, i.e., the number of S-boxes belonging to the class, is 2(61.28). By performing our algorithm, we find that there exist 2(37.56) S-boxes with nonlinearity 24 and among them the number of those that are differentially 4-uniform is 2(33.99), which indicates that the concatenation method provides a rich class in terms of high nonlinearity and low differential uniformity. We then classify the S-boxes achieving the best possible trade-off between nonlinearity and differential uniformity in the class with respect to absolute indicator, algebraic degree, and transparency order. Secondly, we extend our construction method to the case of 8 x 8 bijective S-boxes and perform a steepest-descent-like iterative search algorithm in the respective class (of size 2(243.74)), which yields differentially 6-uniform permutations with high nonlinearity and algebraic degree.