Geodesic
On the number of functions that break subspaces of dimension $3$ and higher
Prikladnaya Diskretnaya Matematika. Supplement, no. 17 (2024), pp. 34-37.

Voir la notice de l'article provenant de la source Math-Net.Ru

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 et al., 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}|$ and $|\mathcal{P}_{n}^{3} \cap \ldots \cap \mathcal{P}_{n}^{n - 1}|$ up to $o(2^n!)$ are obtained 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.
Keywords: affine subspaces, invariant subspaces, asymptotic bounds.
Mots-clés : permutations 
@article{PDMA_2024_17_a7,
     author = {N. A. Kolomeets},
     title = {On the number of functions that break subspaces of dimension $3$ and higher},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {34--37},
     publisher = {mathdoc},
     number = {17},
     year = {2024},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2024_17_a7/}
}
TY  - JOUR
AU  - N. A. Kolomeets
TI  - On the number of functions that break subspaces of dimension $3$ and higher
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2024
SP  - 34
EP  - 37
IS  - 17
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDMA_2024_17_a7/
LA  - ru
ID  - PDMA_2024_17_a7
ER  - 
%0 Journal Article
%A N. A. Kolomeets
%T On the number of functions that break subspaces of dimension $3$ and higher
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2024
%P 34-37
%N 17
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDMA_2024_17_a7/
%G ru
%F PDMA_2024_17_a7
N. A. Kolomeets. On the number of functions that break subspaces of dimension $3$ and higher. Prikladnaya Diskretnaya Matematika. Supplement, no. 17 (2024), pp. 34-37. http://geodesic.mathdoc.fr/item/PDMA_2024_17_a7/

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

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

[3] Carlet S., “Open questions on nonlinearity and on APN functions”, LNCS, 9061, 2015, 83–107 | MR | Zbl

[4] Kolomeec N., 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

[5] Kolomeets N. A., “O sokhranenii struktury podprostranstv vektornymi bulevymi funktsiyami”, Prikladnaya diskretnaya matematika. Prilozhenie, 2023, no. 16, 23–26

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

[7] 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

[8] Trifonov D. I., Fomin D. B., “Ob invariantnykh podprostranstvakh v XSL-shifrakh”, Prikladnaya diskretnaya matematika, 2021, no. 54, 58–76 | Zbl

[9] Burov D. A., “O suschestvovanii nelineinykh invariantov spetsialnogo vida dlya raundovykh preobrazovanii XSL-algoritmov”, Diskretnaya matematika, 33:2 (2021), 31–45 | DOI | MR