# 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:
  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)  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  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  Biham, E.; Shamir, A., Differential cryptanalysis of DES-like cryptosystems, J. Cryptol., 4, 3-72, (1991) · Zbl 0729.68017  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  Blondeau, C.; Nyberg, K., Perfect nonlinear functions and cryptography, Finite Fields and Their Applications, 32, 120-147, (2015) · Zbl 1372.94413  Brinkmann, M.; Leander, G., On the classification of APN functions up to dimension five, Des. Codes Cryptogr., 49, 273-288, (2008) · Zbl 1184.94227  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)  Budaghyan, L.: Construction and Analysis of Cryptographic Functions, vol. VIII, p 168. Springer, Berlin (2014) · Zbl 1367.94001  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  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  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  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  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)  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  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  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  Dobbertin, H., Almost perfect nonlinear functions over GFGF(2n): the Niho case, Inform. and Comput., 151, 57-72, (1999) · Zbl 1072.94513  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  Glukhov, MM, On the approximation of discrete functions by linear functions, Matematicheskie Voprosy Kriptografii, 7, 29-50, (2016)  Glukhov, MM, On the matrices of transitions of differences for some modular groups, Matematicheskie Voprosy Kriptografii, 4, 27-47, (2013)  Gold, R., Maximal recursive sequences with 3-valued recursive crosscorrelation functions, IEEE Trans. Inform. Theory, 14, 154-156, (1968) · Zbl 0228.62040  Gorodilova, AA, Characterization of almost perfect nonlinear functions in terms of subfunctions, Diskr. Mat., 27, 3-16, (2016)  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  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  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  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  Lidl, R., Niederreiter, H.: Finite Fields. Encyclopedia of Mathematics and its Applications, vol. 20, p 772. Addison-Wesley, Reading (1983)  Nyberg, K., Differentially uniform mappings for cryptography. Advances in Cryptography, EUROCRYPT’93, Lect. Notes Comput. Sci, 765, 55-64, (1994) · Zbl 0951.94510  Nyberg, K., S-boxes and round functions with controllable linearity and differential uniformity, FSE’94, Lect. Notes Comput. Sci, 1008, 111-130, (1994)  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  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  Pott, A., Almost perfect and planar functions, Des. Codes Cryptography, 78, 141-195, (2016) · Zbl 1351.51004  Tuzhilin, ME, APN functions, Prikladnaya Diskretnaya Matematika, 3, 14-20, (2009)  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.