nach oben

Cryptography and Communications

Erschienen in:

11.05.2018

On an algorithm generating 2-to-1 APN functions and its applications to “the big APN problem”

verfasst von: Valeriya Idrisova

Erschienen in: Cryptography and Communications | Ausgabe 1/2019

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

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.

Vorheriger Artikel On APN functions L1(x3) + L2(x9) with linear L1 and L2

Nächster Artikel Cellular automata based S-boxes

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

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(29), 5–28 (2015)

Berger, T., Canteaut, A., Charpin, P., Laigle-Chapuy, Y.: On almost perfect nonlinear mappings over \(\mathbb {F}_{2^{n}}\). IEEE Trans. Inform. Theory 52(9), 4160–4170 (2006)MathSciNetMATHCrossRef

Beth, T., Ding, C.: On almost perfect nonlinear permutations. Advances in Cryptology, EUROCRYPT’93. Lect. Notes Comput. Sci 765, 65–76 (1993)CrossRef

Biham, E., Shamir, A.: Differential cryptanalysis of DES-like cryptosystems. J. Cryptol. 4(1), 3–72 (1991)MathSciNetMATHCrossRef

Blondeau, C., Canteaut, A., Charpin, P.: Differential properties of \(x x^{2^{t}-1}\). IEEE Trans. Inf. Theory 57(12), 8127–8137 (2011)MATHCrossRef

Blondeau, C., Nyberg, K.: Perfect nonlinear functions and cryptography. Finite Fields and Their Applications 32, 120–147 (2015)MathSciNetMATHCrossRef

Brinkmann, M., Leander, G.: On the classification of APN functions up to dimension five. Des. Codes Cryptogr. 49(1–3), 273–288 (2008)MathSciNetMATHCrossRef

Browning, K.A., Dillon, J.F., McQuistan, M.T., Wolfe, A.J.: 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)CrossRef

Budaghyan, L.: Construction and Analysis of Cryptographic Functions, vol. VIII, p 168. Springer, Berlin (2014)MATH

10.

Calderini, M., Sala, M., Villa, I.: A note on APN permutations in even dimension. Finite Fields Their Appl. 46, 1–16 (2017)MathSciNetMATHCrossRef

11.

Canteaut, A., Charpin, P., Dobbertin, H.: Binary m-sequences with three-valued crosscorrelation: a proof of Welch conjecture. IEEE Trans. Inf. Theory. 46(1), 4–8 (2000)MathSciNetMATHCrossRef

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}\). IACR Cryptology ePrint Archive 2016, 887 (2016)MATH

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)CrossRef

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)CrossRef

15.

Carlet, C., Charpin, P., Zinoviev, V.: Codes, bent functions and permutations suitable for DES-like cryptosystems. Des. Codes Cryptogr. 15, 125–156 (1998)MathSciNetMATHCrossRef

16.

Dobbertin, H.: One-to-one highly nonlinear power functions on \(GF(2^{n})\). Appl. Algebra Eng. Commun. Comput. 9(2), 139–152 (1998)MATHCrossRef

17.

Dobbertin, H.: Almost perfect nonlinear power functions on \({{GF}}(2^{n})\): the Welch case. IEEE Trans. Inf. Theory. 45(4), 1271–1275 (1999)MathSciNetMATHCrossRef

18.

Dobbertin, H.: Almost perfect nonlinear functions over GFGF(2ⁿ): the Niho case. Inform. and Comput. 151, 57–72 (1999)MathSciNetMATHCrossRef

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)

20.

Glukhov, M.M.: On the approximation of discrete functions by linear functions. Matematicheskie Voprosy Kriptografii 7(4), 29–50 (2016). (in Russian)MathSciNetCrossRef

21.

Glukhov, M.M.: On the matrices of transitions of differences for some modular groups. Matematicheskie Voprosy Kriptografii 4(4), 27–47 (2013). (in Russian)CrossRef

22.

Gold, R.: Maximal recursive sequences with 3-valued recursive crosscorrelation functions. IEEE Trans. Inform. Theory 14, 154–156 (1968)MATHCrossRef

23.

Gorodilova, A.A.: Characterization of almost perfect nonlinear functions in terms of subfunctions. Diskr. Mat. 27(3), 3–16 (2016). Discrete Math. Appl. 26(4), 193–202MathSciNetMATHCrossRef

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)MathSciNetMATHCrossRef

25.

Hou, X.-D.: Affinity of permutations of \({F_{2}^{n}}\). Discrete Appl. Math. - Special issue: Coding and Cryptography Archive 154(2), 313–325 (2006)MathSciNetMATHCrossRef

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)MATH

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)MATHCrossRef

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)MATHCrossRef

30.

Nyberg, K.: S-boxes and round functions with controllable linearity and differential uniformity, FSE’94. Lect. Notes Comput. Sci 1008, 111–130 (1994)MATHCrossRef

31.

Pasalic, E., Charpin, P.: Some results concerning cryptographically significant mappings over \({{GF}}(2^{n})\). Des. Codes Crypt. 57(3), 257–269 (2010)

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)

33.

Pott, A.: Almost perfect and planar functions. Des. Codes Cryptography 78(1), 141–195 (2016)MathSciNetMATHCrossRef

34.

Tuzhilin, M.E.: APN functions. Prikladnaya Diskretnaya Matematika 3, 14–20 (2009). (in Russian)CrossRef

35.

Vitkup, V.: On symmetric properties of APN functions. J. Appl. Ind. Math. 10(1), 126–135 (2016)MathSciNetMATHCrossRef

Titel: On an algorithm generating 2-to-1 APN functions and its applications to “the big APN problem”
verfasst von: Valeriya Idrisova
Publikationsdatum: 11.05.2018
Verlag: Springer US
Erschienen in: Cryptography and Communications / Ausgabe 1/2019
Print ISSN: 1936-2447
Elektronische ISSN: 1936-2455
DOI: https://doi.org/10.1007/s12095-018-0310-9

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 1/2019

Cellular automata based S-boxes

New classes of p-ary bent functions

On APN functions L1(x3) + L2(x9) with linear L1 and L2

Small low-depth circuits for cryptographic applications

Editorial: Special Issue on Boolean functions and their applications

The multiplicative complexity of 6-variable Boolean functions

Premium Partner