Об эвристическом алгоритме построения подстановок с заданными криптографическими характеристиками с использованием обобщённой конструкции

Прикладная дискретная математика. 2022. № 57. С. 5–21.

М. А. Коврижных, Д. Б. Фомин

In this paper, we study a generalized construction of (2m, 2m)-functions using monomial and arbitrary m-bit permutations as constituent elements. We investigate the possibility of constructing bijective vectorial Boolean functions (permutations) with specified cryptographic properties that ensure the resistance of encryption algorithms to linear and differential methods of cryptographic analysis. We propose a heuristic algorithm for obtaining permutations with the given nonlinearity and differential uniformity based on the generalized construction. For this purpose, we look for auxiliary permutations of a lower dimension using the ideas of the genetic algorithm, spectral-linear, and spectral-difference methods. In the case of m = 4, the proposed algorithm consists of iterative multiplication of the initial randomly generated 4-bit permutations by transposition, selecting the best ones in nonlinearity, the differential uniformity, and the corresponding values in the linear and differential spectra among the obtained 8-bit permutations. We show how to optimize the calculation of cryptographic properties at each iteration of the algorithm. Experimental studies of the most interesting, from a practical point of view, 8-bit permutations have shown that it is possible to construct 6-uniform permutations with nonlinearity 108.

Keywords: нелинейность, nonlinearity, permutation, подстановка, vectorial Boolean function, векторная булева функция, differential uniformity, дифференциальная равномерность