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.
Download file
Counter downloads: 51
- Title Heuristic algorithm for obtaining permutations with given cryptographic properties using a generalized construction
- Headline Heuristic algorithm for obtaining permutations with given cryptographic properties using a generalized construction
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 57
- Date:
- DOI 10.17223/20710410/57/1
Keywords
vectorial Boolean function, permutation, differential uniformity, nonlinearityAuthors
References
Biham E. and Shamir A. Differential cryptanalysis of the full 16-round DES // LNCS. 1993. V. 740. P. 487-496.
Biham E. and Shamir A. Differential cryptanalysis of DES-like cryptosystems //j. Cryptology. 1991. No. 4. P.3-72.
Matsui M. Linear cryptanalysis method for DES cipher // LNCS. 1994. V. 765. P. 386-397.
Shannon С. E.Communication theory of secrecy systems // Bell Syst. Techn. J. 1949. V. 28. P. 656-715.
Menyachikhin A. V. Spectral-linear and spectral-differential methods for generating S-boxes having almost optimal cryptographic parameters // Матем. вопр. криптогр. 2017. Т. 8. №2. С. 97-116.
De la Cruz Jimenez R.A. Generation of 8-bit S-Boxes having almost optimal cryptographic properties using smaller 4-bit S-Boxes and finite field multiplication // LNCS. 2019. V. 11368. P. 191-206.
De la Cruz Jimenez 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.
De la Cruz Jimenez R.A. A method for constructing permutations, involutions and orthomorphisms with strong cryptographic properties // Прикладная дискретная математика. Приложение. 2019. №12. С. 145-151.
Фомин Д. Б. О подходах к построению низкоресурсных нелинейных преобразований // Обозрение прикладной и промышленной математики. 2018. Т. 25. Вып.4. С. 379-381.
Fomin D. B. New classes of 8-bit permutations based on a butterfly structure // Матем. вопр. криптогр. 2019. Т. 10. №2. С. 169-180.
Фомин Д. Б. Построение подстановок пространства V2m с использованием (2m, т)-функций // Матем. вопр. криптогр. 2020. Т. 11. №3. С. 121-138.
Фомин Д. Б. Об алгебраической степени и дифференциальной равномерности подстановок пространства V2m, построенных с использованием (2m, т)-функций // Матем. вопр. криптогр. 2020. Т. 11. №4. С. 133-149.
Menyachikhin A. The change in linear and differential characteristics of substitution after the multiplication by transposition // Матем. вопр. криптогр. 2020. Т. 11. №2. С. 111-123.
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.
Ivanov G., Nikolov N., and Nikova S. Reversed genetic algorithms for generation of bijective s-boxes with good cryptographic properties // Cryptogr.Commun. 2016. V. 8. No. 2. P. 247-276.
Biryukov A., Perrin L., and Udovenko A. Reverse-engineering the s-box of Streebog, Kuznyechik and STRIBOBr1 // LNCS. 2016. V.9665. P.372-402.
Canteaut A. and Perrin L. On CCZ-Equivalence, Extended-Affine Equivalence, and Function Twisting. Cryptology ePrint Archive, Report 2018/713. https://eprint.iacr.org/2018/713.
Kazymyrov O. V., Kazymyrova V. N., and Oliynykov R. V. A method for generation of high-nonlinear S-boxes based on gradient descent // Матем. вопр. криптогр. 2014. Т. 5. №2. С. 71-78.
Лидл Р, Нидеррайтер Г. Конечные поля. В 2-х т. М.: Мир, 1988. 430 с.
Кострикин А. И. Введение в алгебру. Ч. I. Основы алгебры: учебник для вузов. 3-е изд. М.: Физматлит, 2004. 272 с.
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. 2010. V. 518. P. 33-42.
Knuth D. Art of Computer Programming. V. 2: Seminumerical Algorithms, 3rd ed. Addison-Wesley Professional, 1997.
Казимиров А. В. Методы и средства генерации нелинейных узлов замены для симметричных криптоалгоритмов: дис.. канд. техн. наук. Харьков, 2013. 190с.
O’Connor L. Properties of linear approximation tables // LNCS. 1995. V. 1008. P. 131-136.
Carlet C. Vectorial Boolean functions for cryptography // Boolean Models and Methods in Mathematics, Computer Science, and Engineering / eds. Y. Crama and P. Hammer. Cambridge: Cambridge University Press, 2010. P.398-469.
Yu Y., Wang M., and Li Y. Constructing differential 4-uniform permutations from know ones. Cryptology ePrint Archive. Report 2011/047. 2011. https://eprint.iacr.org/2011/047
Heuristic algorithm for obtaining permutations with given cryptographic properties using a generalized construction | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2022. № 57. DOI: 10.17223/20710410/57/1
Download full-text version
Counter downloads: 131