# zbMATH — the first resource for mathematics

On constructing APN permutations using subfunctions. (Russian. English summary) Zbl 07311625
Summary: Our subject for investigation is the problem of APN permutation existence for even number of variables. In this work, we consider 2-to-1 functions that are isomorphic to $$(n-1)$$-subfunctions of APN permutations. These 2-to-1 functions can be obtained with a special algorithm which searches for 2-to-1 APN functions that are potentially EA-equivalent to permutations. The algorithm is based on constructing special symbol sequences that are called admissible. It is known that $$(n-1)$$-subfunction of an APN permutation can be represented as a differentially 4-uniform 2-to-1 function that takes values from the half of the Boolean cube. Therefore, the following algorithm can be used to search for APN permutations. On the first step all the possible admissible sequences are constructed and we assign obtained sequences in order to find a differentially 4-uniform 2-to-1 function. Therefore, obtained function can be isomorphic to a $$(n-1)$$-subfunction of an APN permutation, so, this $$(n-1)$$-subfunction can be expanded to bijective APN function. In order to construct an APN permutation, we need to find all possible coordinate Boolean functions $$f$$ such that the bijective function constructed from the given $$(n-1)$$-subfunction $$S$$ and function $$f$$ is APN. Unfortunately, the exhaustive search through the set of potential coordinate functions is computationally hard when $$n\ge7$$, so, we need to estimate the number $$n(S)$$ of such coordinate Boolean functions. For a given bijective vectorial function $$F$$, we introduce an associated permutation $$F^\star$$ as follows. We split the set $$\mathbb{F}_2^n$$ into two disjoint subsets $$\mathcal{F}_1$$ and $$\mathcal{F}_2$$, fix integer $$k$$, indices $$i_1,\dots,i_k$$, and index $$j\not\in\{i_1,\dots,i_k\}$$. Then the value $$F^\star(x)$$ is equal to $$F(x)$$ if $$F(x)\in\mathcal{F}_1$$ and $$F^\star(x)$$ is equal to $$F(x)+e_j$$ otherwise. We prove that $$F^\star$$ is an APN permutation if and only if $$F$$ is an APN permutation. This fact allows us to obtain the necessary bound. We prove that if $$n(S)$$ is not equal to zero, then $$n(S)\ge2^n$$.
##### MSC:
 05-XX Combinatorics 11-XX Number theory
##### Keywords:
vectorial function; APN function; permutation; subfunction
Full Text:
##### References:
  Carlet C., Charpin P., Zinoviev V., “Codes, bent functions and permutations suitable for DES-like cryptosystems”, Des. Codes Cryptogr., 15 (2000), 125-156 · Zbl 0938.94011  Gold R., “Maximal recursive sequences with 3-valued recursive crosscorrelation functions”, IEEE Trans. Inform. Theory, 14 (1968), 154-156 · Zbl 0228.62040  Nyberg K., “Differentially uniform mappings for cryptography”, EUROCRYPT’93, LNCS, 765, 1994, 55-64 · Zbl 0951.94510  Kasami T., “The weight enumerators for several classes of subcodes of the second order binary Reed-Muller codes”, Inform. Control, 18 (1971), 369-394 · Zbl 0217.58802  Janwa H., Wilson R., “Hyperplane sections of Fermat varieties in $$P^3$$ in char. 2 and some applications to cyclic codes”, Proc. AAECC-10, LNCS, 673, 1993, 180-194 · Zbl 0798.94012  Canteaut A., Charpin P., Dobbertin H., “Binary $$m$$-sequences with three-valued crosscorrelation: a proof of Welch conjecture”, IEEE Trans. Inform. Theory, 46 (2000), 4-8 · Zbl 1003.94519  Dobbertin H., “Almost perfect nonlinear functions over $$\text{GF}(2^n)$$: the Welch case”, IEEE Trans. Inform. Theory, 45 (1999), 1271-1275 · Zbl 0957.94021  Dobbertin H., “Almost perfect nonlinear functions over $$\text{GF}(2^n)$$: the Niho case”, Inform. Comput., 151 (1999), 57-72 · Zbl 1072.94513  Hollmann H., Xiang Q., “A proof of the Welch and Niho conjectures on crosscorrelations of binary $$m$$-sequences”, Finite Fields Appl., 7 (2001), 253-286 · Zbl 1027.94006  Beth T., Ding C., “On almost perfect nonlinear permutations”, EUROCRYPT’93, LNCS, 765, 1993, 65-76 · Zbl 0951.94524  Dobbertin H., “Almost perfect nonlinear power functions over $$\text{GF}(2^n)$$: a new case for $$n$$ divisible by 5”, Finite Fields and Applications, eds. D. Jungnickel, H. Niederreiter, Springer, Berlin-Heidelberg, 2001, 113-121 · Zbl 1010.94550  Glukhov M. M., “On the approximation of discrete functions by linear functions”, Mat. Vopr. Kriptogr., 7:4 (2016), 29-50 (in Russian)  Blondeau C., Nyberg K., “Perfect nonlinear functions and cryptography”, Finite Fields Appl., 32 (2015), 120-147 · Zbl 1372.94413  Carlet C., “Open questions on nonlinearity and on APN Functions”, LNCS, 9061, 2015, 83-107 · Zbl 1400.94133  Pott A., “Almost perfect and planar functions”, Des. Codes Cryptography, 78:1 (2016), 141-195 · Zbl 1351.51004  Tuzhilin M. E., “APN-functions”, Prikladnaya Diskretnaya Matematika, 2009, no. 3, 14-20 (in Russian)  Budaghyan L., Construction and Analysis of Cryptographic Functions, Springer International Publishing, 2014, 168 pp. · Zbl 1367.94001  Carlet C., “Vectorial Boolean functions for cryptography”, Ch. 9 of the monograph, Boolean Methods and Models in Mathematics, Computer Science, and Engineering, Cambridge Univ. Press, 2010, 398-472 · Zbl 1209.94036  Hou X.-D., “Affinity of permutations of $$\text F_2^n$$”, Discr. Appl. Math., 154, Special Issue: Coding and Cryptography Archive (2006), 313-325 · Zbl 1089.94020  Browning K. A., Dillon J. F., McQuistan M. T., Wolfe A. J., “An APN permutation in dimension six”, 9-th Intern. Conf. Finite Fields and Their Applications Fq’09, Contemporary Math., 518, AMS, 2010, 33-42 · Zbl 1206.94026  Canteaut A., Duval S., Perrin L., “A generalisation of Dillon”s APN permutation with the best known differential and linear properties for all fields of size $$2^{4k+2}$$”, IEEE Trans. Inform. Theory, 63 (2016), 7575-7591 · Zbl 1390.94813  Perrin L., Udovenko A., Biryukov A., “Cryptanalysis of a theorem: Decomposing the only known solution to the big APN problem”, CRYPTO 2016, Part II, LNCS, 9815, 2016, 93-122 · Zbl 1391.94789  Idrisova V., “On an algorithm generating 2-to-1 APN functions and its applications to ‘the big APN problem’ ”, Cryptography and Communications, 2018, 1-19  Gorodilova A. A., “Characterization of almost perfect nonlinear functions in terms of subfunctions”, Discr. Math. Appl., 26:4 (2016), 193-202 · Zbl 1409.94939
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.