# zbMATH — the first resource for mathematics

On an algorithm generating 2-to-1 APN functions and its applications to “The big APN problem”. (English) Zbl 1420.94074
Summary: Almost perfect nonlinear (APN) functions are of great interest to many researchers since they have the optimal resistance to the differential attack. The existence of bijective APN functions in even number of variables is an important open problem, and there is only one known example of such a function at present. In this paper we consider a special subclass of 2-to-1 vectorial Boolean functions that can allow us to search and construct APN permutations. We proved that each 2-to-1 function is potentially EA-equivalent to a permutation and proposed an algorithm that generates special symbol sequences for constructing 2-to-1 APN functions. Also, we described two methods for searching APN permutations, that are based on sequences generated by this algorithm.

##### MSC:
 94A60 Cryptography 06E30 Boolean functions 11T71 Algebraic coding theory; cryptography (number-theoretic aspects)
Full Text:
##### References:
 [1] Agievich, S.; Gorodilova, A.; Kolomeec, N.; Nikova, S.; Preneel, B.; Rijmen, V.; Shushuev, G.; Tokareva, N.; Vitkup, V., Problems, solutions and experience of the first international student’s Olympiad in cryptography, Prikladnaya Diskretnaya Matematika, 3, 5-28, (2015) [2] Berger, T.; Canteaut, A.; Charpin, P.; Laigle-Chapuy, Y., On almost perfect nonlinear mappings over $$\mathbb {F}_{2^{n}}$$ F2n, IEEE Trans. Inform. Theory, 52, 4160-4170, (2006) · Zbl 1184.94224 [3] Beth, T.; Ding, C., On almost perfect nonlinear permutations. Advances in Cryptology, EUROCRYPT’93, Lect. Notes Comput. Sci, 765, 65-76, (1993) · Zbl 0951.94524 [4] Biham, E.; Shamir, A., Differential cryptanalysis of DES-like cryptosystems, J. Cryptol., 4, 3-72, (1991) · Zbl 0729.68017 [5] Blondeau, C.; Canteaut, A.; Charpin, P., Differential properties of $$x x^{2^{t}-1}$$ xx2t − 1, IEEE Trans. Inf. Theory, 57, 8127-8137, (2011) · Zbl 1365.94404 [6] Blondeau, C.; Nyberg, K., Perfect nonlinear functions and cryptography, Finite Fields and Their Applications, 32, 120-147, (2015) · Zbl 1372.94413 [7] Brinkmann, M.; Leander, G., On the classification of APN functions up to dimension five, Des. Codes Cryptogr., 49, 273-288, (2008) · Zbl 1184.94227 [8] Browning, KA; Dillon, JF; McQuistan, MT; Wolfe, AJ, An APN permutation in dimension six. Post-proceedings of the 9-th International Conference on Finite Fields and Their Applications Fq’09, Contemporary Math. AMS, 518, 33-42, (2010) [9] Budaghyan, L.: Construction and Analysis of Cryptographic Functions, vol. VIII, p 168. Springer, Berlin (2014) · Zbl 1367.94001 [10] Calderini, M.; Sala, M.; Villa, I., A note on APN permutations in even dimension, Finite Fields Their Appl., 46, 1-16, (2017) · Zbl 1420.94043 [11] Canteaut, A.; Charpin, P.; Dobbertin, H., Binary m-sequences with three-valued crosscorrelation: a proof of Welch conjecture, IEEE Trans. Inf. Theory., 46, 4-8, (2000) · Zbl 1003.94519 [12] 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}$$ 24k + 2, IACR Cryptology ePrint Archive, 2016, 887, (2016) · Zbl 1390.94813 [13] Carlet, C.: Open Questions on Nonlinearity and on APN Functions. In: Koç, Ç., Mesnager, S., Savaş, E. (eds.) Arithmetic of Finite Fields. WAIFI 2014. Lecture Notes in Computer Science, vol. 9061, pp. 83-107 (2015) · Zbl 1400.94133 [14] Carlet, C.: Vectorial Boolean Functions for Cryptography. Ch. 9 of the monograph Boolean Methods and Models in Mathematics, Computer Science, and Engineering, pp. 398-472. Cambridge University Press, Cambridge (2010) [15] Carlet, C.; Charpin, P.; Zinoviev, V., Codes, bent functions and permutations suitable for DES-like cryptosystems, Des. Codes Cryptogr., 15, 125-156, (1998) · Zbl 0938.94011 [16] Dobbertin, H., One-to-one highly nonlinear power functions on $$GF(2^{n})$$ GF(2n), Appl. Algebra Eng. Commun. Comput., 9, 139-152, (1998) · Zbl 0924.94026 [17] Dobbertin, H., Almost perfect nonlinear power functions on $${{GF}}(2^{n})$$ GF(2n): the Welch case, IEEE Trans. Inf. Theory., 45, 1271-1275, (1999) · Zbl 0957.94021 [18] Dobbertin, H., Almost perfect nonlinear functions over GFGF(2n): the Niho case, Inform. and Comput., 151, 57-72, (1999) · Zbl 1072.94513 [19] Dobbertin, H.: Almost perfect nonlinear power functions over $${{GF}}(2^{n})$$: a new case for $$n$$ divisible by 5. Proceedings of Finite Fields and Applications FQ5, 113-121 (2000) · Zbl 1010.94550 [20] Glukhov, MM, On the approximation of discrete functions by linear functions, Matematicheskie Voprosy Kriptografii, 7, 29-50, (2016) [21] Glukhov, MM, On the matrices of transitions of differences for some modular groups, Matematicheskie Voprosy Kriptografii, 4, 27-47, (2013) [22] Gold, R., Maximal recursive sequences with 3-valued recursive crosscorrelation functions, IEEE Trans. Inform. Theory, 14, 154-156, (1968) · Zbl 0228.62040 [23] Gorodilova, AA, Characterization of almost perfect nonlinear functions in terms of subfunctions, Diskr. Mat., 27, 3-16, (2016) [24] Hollmann, H.; Xiang, Q., A proof of the Welch and Niho conjectures on crosscorrelations of binary m-sequences, Finite Fields Their Appl., 7, 253-286, (2001) · Zbl 1027.94006 [25] Hou, X-D, Affinity of permutations of $${F_{2}^{n}}$$ F2n, Discrete Appl. Math. - Special issue: Coding and Cryptography Archive, 154, 313-325, (2006) · Zbl 1089.94020 [26] Janwa, H., Wilson, R.: Hyperplane Sections of Fermat Varieties in $$p^{3}$$ in char. 2 and some Applications to Cyclic Codes. Proceedings of AAECC-10, Lecture Notes in Computer Science, vol. 673, pp. 180-194. Springer, Berlin (1993) · Zbl 0798.94012 [27] Kasami, T., The weight enumerators for several classes of subcodes of the second order binary Reed-Muller codes, Inform. and Control., 18, 369-394, (1971) · Zbl 0217.58802 [28] Lidl, R., Niederreiter, H.: Finite Fields. Encyclopedia of Mathematics and its Applications, vol. 20, p 772. Addison-Wesley, Reading (1983) [29] Nyberg, K., Differentially uniform mappings for cryptography. Advances in Cryptography, EUROCRYPT’93, Lect. Notes Comput. Sci, 765, 55-64, (1994) · Zbl 0951.94510 [30] Nyberg, K., S-boxes and round functions with controllable linearity and differential uniformity, FSE’94, Lect. Notes Comput. Sci, 1008, 111-130, (1994) [31] Pasalic, E., Charpin, P.: Some results concerning cryptographically significant mappings over $${{GF}}(2^{n})$$. Des. Codes Crypt. 57(3), 257-269 (2010) · Zbl 1197.94201 [32] Perrin, L., Udovenko, A., Biryukov, A.: Cryptanalysis of a theorem: decomposing the only known solution to the big APN problem. In: Robshaw, M., Katz, J. (eds.) Advances in Cryptology - CRYPTO 2016, Part II. Lect. Notes Comput. Sci, vol. 9815, pp. 93-122 (2016) · Zbl 1391.94789 [33] Pott, A., Almost perfect and planar functions, Des. Codes Cryptography, 78, 141-195, (2016) · Zbl 1351.51004 [34] Tuzhilin, ME, APN functions, Prikladnaya Diskretnaya Matematika, 3, 14-20, (2009) [35] Vitkup, V., On symmetric properties of APN functions, J. Appl. Ind. Math., 10, 126-135, (2016) · Zbl 1349.94135
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.