On permutations that break subspaces of~specified~dimensions

N. A. Kolomeec

Prikladnaâ diskretnaâ matematika, no. 3 (2024), pp. 5-20.

Résumé

We consider the sets $\mathcal{P}_{n}^{k}$ consisting of invertible functions $F: \mathbb{F}_2^n \to \mathbb{F}_2^n$ such that any $U \subseteq \mathbb{F}_2^n$ and its image $F(U)$ are not simultaneously $k$-dimensional affine subspaces of $\mathbb{F}_2^n$, where $3 \leq k \leq n - 1$. We present lower bounds for the cardinalities of all such $\mathcal{P}_{n}^{k}$ and $\mathcal{P}_{n}^{k} \cap \ldots \cap \mathcal{P}_{n}^{n - 1}$ 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 $\mathbb{F}_2^n$ belong to $\mathcal{P}_{n}^{4} \cap \ldots \cap \mathcal{P}_{n}^{n - 1}$. Asymptotic lower and upper bounds of $|\mathcal{P}_{n}^{3}|$ up to $o(2^n!)$ are obtained: $o(1) \leq |\mathcal{P}_{n}^{3}|/2^n! - (1 - \rho) \leq \rho^2/2 + o(1)$, where $\rho = 5/224$. They are correct for $|\mathcal{P}_{n}^{3} \cap \ldots \cap \mathcal{P}_{n}^{n - 1}|$ as well. The number of functions from $\mathcal{P}_{n}^{4} \cap \ldots \cap \mathcal{P}_{n}^{n - 1}$ that map exactly one $3$-dimensional affine subspace of $\mathbb{F}_2^n$ 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 $\mathbb{F}_2^n$ is obtained. The characterization of differentially 4-uniform permutations in the mentioned terms is provided.

Détail

Keywords: affine subspaces, asymptotic bounds, nonlinearity, differential uniformity, APN functions.

Bibliographie

[1] Clark W. E., Hou X., and Mihailovs A., “The affinity of a permutation of a finite vector space”, Finite Fields Their Appl., 13 (2007), 80–112 | DOI | MR | Zbl

[2] Tokareva N., Bent Functions: Results and Applications to Cryptography, Academic Press, N.Y., 2015 | MR | Zbl

[3] Budaghyan L., Construction and Analysis of Cryptographic Functions, Springer, Cham, 2015 | MR

[4] Carlet C., Boolean Functions for Cryptography and Coding Theory, Cambridge University Press, Cambridge, 2021 | MR | Zbl

[5] Logachev O. A., Salnikov A. A., and Yashchenko V. V., Boolean Functions in Coding Theory and Cryptography, AMS, Providence, Rhode Island, 2012 | MR | Zbl

[6] Pankratova I. A., Boolean Functions in Cryptography, TSU Publ., Tomsk, 2014 (in Russian)

[7] Carlet C. and Piccione E., “On vectorial functions mapping strict affine subspaces of their domain into strict affine subspaces of their co-domain, and the strong D-property”, Adv. Math. Commun., 2024 | DOI | MR | Zbl

[8] Gorodilova A. A., “Characterization of almost perfect nonlinear functions in terms of subfunctions”, Discrete Math. Appl., 26:4 (2016), 193–202 | DOI | DOI | MR | Zbl

[9] Idrisova V., “On an algorithm generating 2-to-1 APN functions and its applications to “the big APN problem””, Cryptogr. Commun., 11:1 (2019), 21–39 | DOI | MR | Zbl

[10] Beierle C., Leander G., and Perrin L., “Trims and extensions of quadratic APN functions”, Des. Codes Cryptogr., 90 (2022), 1009–1036 | DOI | MR | Zbl

[11] Kolomeec N. and Bykov D., “On the image of an affine subspace under the inverse function within a finite field”, Des. Codes Cryptogr., 92 (2024), 467–476 | DOI | MR

[12] Leander G., Abdelraheem M. A., AlKhzaimi H., and Zenner E., “A cryptanalysis of PRINTcipher: The invariant subspace attack”, LNCS, 6841, 2011, 206–221 | MR | Zbl

[13] Todo Y., Leander G., and Sasaki Y., “Nonlinear invariant attack: practical attack on full SCREAM, iSCREAM, and Midori64”, LNCS, 10032, 2016, 3–33 | MR | Zbl

[14] Trifonov D. I. and Fomin D. B., “Invariant subspaces in SPN block cipher”, Prikladnaya Diskretnaya Matematika, 2021, no. 54, 58–76 (in Russian) | Zbl

[15] Burov D. A., “On the existence of special nonlinear invariants for round functions of XSL-ciphers”, Discrete Math. Appl., 33:2 (2023), 65–75 | DOI | DOI | MR | MR | Zbl

[16] Nyberg K., “Differentially uniform mappings for cryptography”, LNCS, 765, 1994, 245–265 | MR

[17] Charpin P., “Normal Boolean functions”, J. Complexity, 20:2–3 (2004), 245–265 | DOI | MR | Zbl

[18] Buryakov M. L. and Logachev O. A., “On the affinity level of Boolean functions”, Discrete Math. Appl., 15:5 (2005), 479–488 | DOI | DOI | MR | Zbl

[19] Logachev O. A., “On values of affinity level for almost all Boolean functions”, Prikladnaya Diskretnaya Matematika, 2010, no. 3(9), 17–21 (in Russian) | Zbl

[20] Canteaut A., Carlet S., Charpin P., and Fontaine S., “On cryptographic properties of the cosets of $R(1, m)$”, IEEE Trans. Inform. Theory, 47 (2001), 1494–1513 | DOI | MR | Zbl

[21] Carlet S. and Feukoua S., “Three parameters of Boolean functions related to their constancy on affine spaces”, Adv. Math. Commun., 14:4 (2020), 651–676 | DOI | MR | Zbl

[22] Berger T., Canteaut A., Charpin P., and Laigle-Chapuy Y., “On almost perfect nonlinear functions”, IEEE Trans. Inform. Theory, 52:9 (2006), 4160–4170 | DOI | MR | Zbl

[23] Browning K. A., Dillon J. F., McQuistan M. T., and Wolfe A. J., “An APN permutation in dimension six”, Finite Fields: Theory Appl., 2010, no. 518, 33–42 | DOI | MR | Zbl

[24] 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, 66:11 (2020), 7101–7112 | DOI | MR | Zbl

[25] Blondeau C., Canteaut A., and Charpin P., “Differential properties of power functions”, Int. J. Inform. Coding Theory, 1:2 (2010), 149–170 | MR | Zbl

[26] Knuth D. E., “Subspaces, subsets, and partitions”, J. Combinatorial Theory. Ser. A, 10:2 (1971), 178–180 | DOI | MR | Zbl