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

Bibliographie

[1] Biham E. and Shamir A., “Differential cryptanalysis of the full 16-round DES”, LNCS, 740, 1993, 487–496 | MR | Zbl

[2] Biham E. and Shamir A., “Differential cryptanalysis of DES-like cryptosystems”, J. Cryptology, 1991, no. 4, 3–72 | DOI | MR | Zbl

[3] Matsui M., “Linear cryptanalysis method for DES cipher”, LNCS, 765, 1994, 386–397 | Zbl

[4] Shannon S. E., “Communication theory of secrecy systems”, Bell Syst. Techn. J., 28 (1949), 656–715 | DOI | MR | Zbl

[5] Menyachikhin A. V., “Spectral-linear and spectral-differential methods for generating S-boxes having almost optimal cryptographic parameters”, Mat. Vopr. Kriptogr., 8:2 (2017), 97–116 | MR | Zbl

[6] De la Cruz Jiménez R.A., “Generation of 8-bit S-Boxes having almost optimal cryptographic properties using smaller 4-bit S-Boxes and finite field multiplication”, LNCS, 11368, 2019, 191–206 | MR | Zbl

[7] De la Cruz Jiménez R.A., On Some Methods for Constructing Almost Optimal S-Boxes and their Resilience against Side-Channel Attacks, , 2018 https://eprint.iacr.org/2018/618

[8] De la Cruz Jiménez R.A., “A method for constructing permutations, involutions and orthomorphisms with strong cryptographic properties”, Prikladnaya Diskretnaya Matematika. Prilozhenie, 2019, no. 12, 145–151

[9] Fomin D. B., “On approaches to constructing low-resource nonlinear transformations”, Obozrenie Prikladnoy i Promyshlennoy Matematiki, 25:4 (2018), 379–381 (in Russian) | MR

[10] Fomin D. B., “New classes of 8-bit permutations based on a butterfly structure”, Mat. Vopr. Kriptogr., 10:2 (2019), 169–180 | MR | Zbl

[11] Fomin D. B., “Construction of permutations on the space $V_{2m}$ by means of $(2m,~m)$-functions”, Mat. Vopr. Kriptogr., 11:3 (2020), 121–138 (in Russian) | MR | Zbl

[12] Fomin D. B., “On the algebraic degree and differential uniformity of permutations on the space $V_{2m}$ constructed via $(2m,~m)$-functions”, Mat. Vopr. Kriptogr., 11:4 (2020), 133–149 (in Russian) | MR | Zbl

[13] Menyachikhin A., “The change in linear and differential characteristics of substitution after the multiplication by transposition”, Mat. Vopr. Kriptogr., 11:2 (2020), 111–123 | MR | Zbl

[14] Fomin D. and Kovrizhnykh M., “On differential uniformity of permutations derived using a generalized construction”, CTCrypt 2021 https://ctcrypt.ru/files/files/2021/Fomin_Kovrizhnylh.pdf | MR

[15] Ivanov G., Nikolov N., and Nikova S., “Reversed genetic algorithms for generation of bijective s-boxes with good cryptographic properties”, Cryptogr. Commun., 8:2 (2016), 247–276 | DOI | MR | Zbl

[16] Biryukov A., Perrin L., and Udovenko A., “Reverse-engineering the s-box of Streebog, Kuznyechik and STRIBOBr1”, LNCS, 9665, 2016, 372–402 | MR | Zbl

[17] Canteaut A. and Perrin L., On CCZ-Equivalence, Extended-Affine Equivalence, and Function Twisting, Cryptology Archive, Report 2018/713, , 2018 https://eprint.iacr.org/2018/713 | MR | Zbl

[18] Kazymyrov O. V., Kazymyrova V. N., and Oliynykov R. V., “A method for generation of high-nonlinear S-boxes based on gradient descent”, Mat. Vopr. Kriptogr., 5:2 (2014), 71–78 | Zbl

[19] Lidl R. and Niederreiter H., Finite Fields, 2nd ed., Cambridge University Press, Cambridge, 1997, 755 pp. | MR | MR

[20] Kostrikin A. I., Introduction to Algebra, Springer Verlag, N.Y., 1982, 577 pp. | MR | Zbl

[21] Browning K. A., Dillon J. F., McQuistan M. T., and Wolfe A. J., “An APN permutation in dimension six”, 9th Int. Conf. Finite Fields Appl. 2009, Contemp. Math., 518, 2010, 33–42 | DOI | MR | Zbl

[22] Knuth D., Art of Computer Programming, v. 2, Seminumerical Algorithms, 3rd ed., Addison-Wesley Professional, 1997 | MR

[23] Kazymyrov O.V., Methods and tools for generating nonlinear replacement nodes for symmetric cryptographic algorithms, PhD Thesis, Kharkiv, 2013, 190 pp. (in Russian)

[24] O'Connor L., “Properties of linear approximation tables”, LNCS, 1008, 1995, 131–136 | Zbl

[25] Carlet C., “Vectorial Boolean functions for cryptography”, Boolean Models and Methods in Mathematics, Computer Science, and Engineering, eds. Y. Crama and P. Hammer, Cambridge University Press, Cambridge, 2010, 398–469 | DOI | MR | Zbl

[26] Yu Y., Wang M., and Li Y., Constructing differential 4-uniform permutations from know ones, Cryptology Archive, Report 2011/047, , 2011 https://eprint.iacr.org/2011/047