RUS  ENG
Full version
JOURNALS // Prikladnaya Diskretnaya Matematika. Supplement // Archive

Prikl. Diskr. Mat. Suppl., 2021 Issue 14, Pages 181–184 (Mi pdma561)

Computational methods in discrete mathematics

On a heuristic approach to constructing bijective vector Boolean functions with given cryptographic properties

M. A. Kovrizhnykh, D. B. Fomin

National Research University "Higher School of Economics", Moscow

Abstract: Bijective vector Boolean functions (permutations) are used as nonlinear primitives of many symmetric ciphers. In this paper, we study a generalized construction of $(2m,2m)$-functions using monomial and arbitrary $m$-bit permutations as constituent elements. A heuristic algorithm for obtaining bijective Boolean functions with given nonlinearity and differential uniformity, based on this construction, is proposed. For this, a search is carried out for auxiliary permutations of a lower dimension using the ideas of spectral-linear and spectral-difference methods. 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. The possibility of optimizing the calculation of cryptographic properties at each iteration of the algorithm is investigated; $8$-bit $6$-uniform permutations with nonlinearity $108$ are experimentally obtained.

Keywords: Boolean function, permutation, nonlinearity, differential uniformity.

UDC: 519.719.2

DOI: 10.17223/2226308X/14/42



© Steklov Math. Inst. of RAS, 2024