VERY NONLINEAR PERMUTATIONS: SYNTHESIS METHOD FOR S-BOXES WITH MAXIMAL 4-NONLINEARITY

Abstract

One of the most important components of modern block symmetric cryptographic algorithms is the S-box. Thus, the quality of cryptographic transform is in general largely dependent on the properties of used S-box, such as the avalanche effect, correlation immunity, and in particular, nonlinearity. During the development of the theory of cryptography, several methods for determining the nonlinearity of S-boxes have been proposed, such as the algebraic degree of nonlinearity and the distance of nonlinearity. Nevertheless, they all take into account only the description of the S-box using the mathematical apparatus of Boolean functions. But, the cryptanalyst is not constrained in the used cipher description methods, in particular with the application of functions of many-valued logic. In this respect, it is relevant to research the nonlinear properties of the component many-valued functions of S-boxes. In this paper, we propose a technique for estimating the 4-nonlinearity of many-valued logic functions based on the Vilenkin-Chrestensen transform, which considers the degree of uniformity of the Vilenkin-Chrestensen spectrum. The performed research made it possible to understand that many widely used modern constructions of S-boxes do not satisfy the high nonlinearity criterion from the point of view of 4-nonlinearity. This circumstance defined the task of constructing a new method for the synthesis of 4-nonlinear S-boxes, which found its solution in this paper.