We consider the sets Pnkconsisting of invertible functions F : F2n → F2n such that any U ⊆ F2n and its image F(U) are not simultaneously k-dimensional affine subspaces of F2n, where 3 ⩽ k ⩽ n - 1. We present lower bounds for the cardinalities of all such Pkn ∩...∩ Pn-1n that improve the result of W. E. Clark, X. Hou, and A. Mihailovs, 2007, providing that these sets are not empty. We prove that almost all permutations of F2n belong to P4n∩...∩ Pn-1n. Asymptotic lower and upper bounds of |P3n| up to o(2n!) are obtained. They are correct for |P3n ∩...∩ Pn-1n| as well. The number of functions from P4n∩...∩ Pn-1n that map exactly one 3-dimensional affine subspace of F2n to an affine subspace is estimated. The connection between the restrictions of component functions of F and the case when both U and F(U) are affine subspaces of is obtained. The characterization of differentially 4-uniform permutations in the mentioned terms is provided.
Download file
Counter downloads: 12
- Title On permutations that break subspaces of specified dimensions
- Headline On permutations that break subspaces of specified dimensions
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 65
- Date:
- DOI 10.17223/20710410/65/1
Keywords
affine subspaces, asymptotic bounds, nonlinearity, differential uniformity, APN functionsAuthors
References
Clark W. Е., Нои X., and Mihailovs A. The affinity of a permutation of a finite vector space // Finite Fields Their Appl. 2007. V. 13. P.80-112. '.
Tokareva N. Bent Functions: Results and Applications to Cryptography. N.Y.: Academic Press, 2015.
Budaghyan L. Construction and Analysis of Cryptographic Functions. Springer, Cham, 2015.
Carlet C. Boolean Functions for Cryptography and Coding Theory. Cambridge: Cambridge University Press, 2021.
Логачев О. А., Сальников А. А., Смышляев C.B., Ященко В. В. Булевы функции в теории кодирования и криптологии. М.: МЦНМО, 2012.
Панкратова И. А. Булевы функции в криптографии: учеб, пособие. Томск: Издательский Дом Томского государственного университета, 2014.
Carlet С. and Piccione Е. On vectorial functions mapping strict affine subspaces of their domain into strict affine subspaces of their co-domain, and the strong D-propertv // Adv. Math.Commun. 2024. https://www.aimsciences.org/article/doi/10.3934/amc.2024025.
Городилова А. А. Характеризация почти совершенно нелинейных функций через подфункции // Дискретная математика. 2015. Т. 27. УЗ. С. 3-16.
Idrisova V. On an algorithm generating 2-to-l APN functions and its applications to “the big APN problem” // Crvptogr.Commun. 2019. V. 11. No. 1. P.21-39.
Beierle C., Leander G., and Perrin L. Trims and extensions of quadratic APN functions // Des. Codes Crvptogr. 2022. V. 90. P. 1009-1036.
Kolomeec N. and Bykov D. On the image of an affine subspace under the inverse function within a finite field // Des. Codes Crvptogr. 2024. V. 92. P. 467-476.
Leander G., Abdelraheem M. A., AlKhzaimi H., and Zenner E. A cryptanalysis of PRINTcipher: The invariant subspace attack // LNCS. 2011. V. 6841. P. 206-221.
Todo Y., Leander G., and Sasaki Y. Nonlinear invariant attack: practical attack on full SCREAM, iSCREAM, and Midori64 // LNCS. 2016. V. 10032. P.3-33.
Трифонов Д. И., Фомин Д. Б. Об инвариантных подпространствах в XSL-шифрах // Прикладная дискретная математика. 2021. №54. С. 58-76.
Буров Д. А. О существовании нелинейных инвариантов специалвного вида для раун-доввіх преобразований XSL-алгоритмов // Дискретная математика. 2021. Т. 33. №2. С.31-45.
Nyberg К. Differentially uniform mappings for cryptography // LNCS. 1994. V. 765. P. 245-265.
Charpin P. Normal Boolean functions //j.Complexity. 2004. V. 20. No. 2-3. P. 245-265.
Буряков M. Л., Логачев О. А. Об уровне аффинности булевых функций j j Дискретная математика. 2005. Т. 17. №4. С.98-107.
Логачев О. А. О значениях уровня аффинности для почти всех булевых функций // Прикладная дискретная математика. 2010. №3(9). С. 17-21.
Canteaut A., Carlet C., Charpin Р., and Fontaine С. On cryptographic properties of the cosets of R(1, m) j j IEEE Trans. Inform. Theory. 2001. V.47. P. 1494-1513.
Carlet C. and Feukoua S. Three parameters of Boolean functions related to their constancy on affine spaces // Adv. Math.Commun. 2020. V. 14. No. 4. P. 651-676.
Berger T., Canteaut A., Charpin P., and Laigle-Chapuy Y. On almost perfect nonlinear functions // IEEE Trans. Inform. Theory. 2006. V.52. No. 9. P.4160-4170.
Browning K. A., Dillon J.F., McQuistan M. T., and Wolfe A. J. An APN permutation in dimension six // Finite Fields: Theory Appl. 2010. Iss.518. P.33-42.
Li S., Meidl W., Polujan A., et al. Vanishing flats: A combinatorial viewpoint on the planarity of functions and their application // IEEE Trans. Inform. Theory. 2020. V. 66. No. 11. P.7101-7112.
Blondeau C., Canteaut A., and Charpin P. Differential properties of power functions // Int. J. Inform. Coding Theory. 2010. V. 1. No. 2. P. 149-170.
Knuth D. E. Subspaces, subsets, and partitions //j.Combinatorial Theory. Ser.A. 1971. V. 10. No. 2. P.178-180.
On permutations that break subspaces of specified dimensions | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2024. № 65. DOI: 10.17223/20710410/65/1
Download full-text version
Counter downloads: 65