Heuristic algorithm for obtaining permutations with~given cryptographic properties using~a~generalized construction

M. A. Kovrizhnykh ; D. B. Fomin

Prikladnaâ diskretnaâ matematika, no. 3 (2022), pp. 5-21

Résumé

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$.

Détail

Keywords: vectorial Boolean function, differential uniformity, nonlinearity.
Mots-clés : permutation