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\).
05-XX Combinatorics
11-XX Number theory
PDF BibTeX Cite
Full Text: DOI MNR
[1] 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
[2] Gold R., “Maximal recursive sequences with 3-valued recursive crosscorrelation functions”, IEEE Trans. Inform. Theory, 14 (1968), 154-156 · Zbl 0228.62040
[3] Nyberg K., “Differentially uniform mappings for cryptography”, EUROCRYPT’93, LNCS, 765, 1994, 55-64 · Zbl 0951.94510
[4] 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
[5] 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
[6] 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
[7] 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
[8] Dobbertin H., “Almost perfect nonlinear functions over \(\text{GF}(2^n)\): the Niho case”, Inform. Comput., 151 (1999), 57-72 · Zbl 1072.94513
[9] 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
[10] Beth T., Ding C., “On almost perfect nonlinear permutations”, EUROCRYPT’93, LNCS, 765, 1993, 65-76 · Zbl 0951.94524
[11] 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
[12] Glukhov M. M., “On the approximation of discrete functions by linear functions”, Mat. Vopr. Kriptogr., 7:4 (2016), 29-50 (in Russian)
[13] Blondeau C., Nyberg K., “Perfect nonlinear functions and cryptography”, Finite Fields Appl., 32 (2015), 120-147 · Zbl 1372.94413
[14] Carlet C., “Open questions on nonlinearity and on APN Functions”, LNCS, 9061, 2015, 83-107 · Zbl 1400.94133
[15] Pott A., “Almost perfect and planar functions”, Des. Codes Cryptography, 78:1 (2016), 141-195 · Zbl 1351.51004
[16] Tuzhilin M. E., “APN-functions”, Prikladnaya Diskretnaya Matematika, 2009, no. 3, 14-20 (in Russian)
[17] Budaghyan L., Construction and Analysis of Cryptographic Functions, Springer International Publishing, 2014, 168 pp. · Zbl 1367.94001
[18] 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
[19] 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
[20] 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
[21] 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
[22] 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
[23] 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
[24] 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.