On the approximation of discrete functions by linear functions

M. M. Glukhov

Matematičeskie voprosy kriptografii, Tome 7 (2016), pp. 29-50.

Résumé

A review of many results on planar, perfect and almost perfect functions is given. Mixing property of PN-functions is proved, new necessary conditions for APN-functions over the field $F_2$ with even number of arguments $n$ are found. A notion of the planar functions on quasigroups is introduced and criterion of planarity of quasigroup mapping is proved.

Bibliographie

[1] Belousov V. D., Osnovy teorii kvazigrupp i lup, M., 1967 | MR

[2] Glukhov M. M., “O metodakh postroeniya sistem ortogonalnykh kvazigrupp s ispolzovaniem grupp”, Matematicheskie voprosy kriptografii, 2:4 (2011), 5–24

[3] Glukhov M. M., “O chislovykh parametrakh, svyazannykh s zadaniem konechnykh grupp sistemami obrazuyuschikh elementov”, Trudy po diskretnoi matematike, v. 1, TVP, M., 1997, 43–66

[4] Gorodilova A. A., “Kharakterizatsiya pochti sovershenno nelineinykh funktsii cherez podfunktsii”, Diskretnaya matematika, 27:3 (2014), 3–16 | DOI

[5] Kuzmin A. S., Nechaev A. A., Shishkin V. A., “Bent- i giperbent-funktsii nad konechnym polem”, Trudy po diskretnoi matematike, v. 10, Fizmatlit, M., 2007, 97–122

[6] Logachev O. A., Salnikov A. A., Yaschenko V. V., Bulevy funktsii v teorii kodirovaniya i kriptografii, MTsNMO, M., 2004

[7] Logachev O. A., Salnikov A. A., Yaschenko V. V., “Bent-funktsii na konechnoi abelevoi gruppe”, Diskretnaya matematika, 9:4 (1997), 3–20 | DOI

[8] Logachev O. A., Salnikov A. A., Yaschenko V. V., “Nekotorye kharakteristiki «nelineinosti gruppovykh otobrazhenii»”, Diskr. analiz i issled. operatsii, 1:8 (2001), 40–54

[9] Sachkov V. N., “Kombinatornye svoistva differentsialno 2-ravnomernykh podstanovok”, Matematicheskie voprosy kriptografii, 6:1 (2015), 159–179

[10] Solodovnikov V. I., “Bent-funktsii iz konechnoi abelevoi gruppy v konechnuyu abelevu gruppu”, Diskretnaya matematika, 14:1 (2002), 99–113 | DOI | Zbl

[11] Solodovnikov V. I., “O primarnykh funktsiyakh, minimalno blizkikh k lineinym”, Matematicheskie voprosy kriptografii, 2:4 (2011), 97–108

[12] Tokareva N. N., Simmetrichnaya kriptografiya. Kratkii kurs, Red.-izd. tsentr NGU, Novosibirsk, 2012

[13] Tokareva N. N., “Obobscheniya bent-funktsii. Obzor rabot”, Diskr. analiz i issled. operatsii, 17:1 (2010), 34–64

[14] Tokareva N. N., Nelineinye bulevy funktsii: bent-funktsii i ikh obobscheniya, Lambert Acad. Publ., Saarbrucken, 2011

[15] Tuzhilin M. E., “Pochti sovershenno nelineinye funktsii”, Prikladnaya diskretnaya matematika, 2009, no. 3, 14–20

[16] Frolova A. A., “Iterativnaya konstruktsiya APN-funktsii”, Prikladnaya diskretnaya matematika, 2013, no. 6, 24–25

[17] Aubry Y., McGuire G., Rodier F., “A few more functions that are not APN infinite often”, Finite Fields: Theory and Appl., Contemp. Math., 518, AMS, Providence, RI, 2010, 23–31 | DOI | MR | Zbl

[18] Berger T., Canteaut A., Charpin P., Laigle-Chapuy Y., “On almost perfect nonlinear power functions over $F_2$”, IEEE Trans. Inform. Theory, 52:9 (2006), 4160–4170 | DOI | MR | Zbl

[19] Beth T., Ding C., “On almost perfect nonlinear permutations”, EUROCRYPT'93, Lect. Notes Comput. Sci., 765, 1994, 65–76 | DOI | MR | Zbl

[20] Bierbrauer J., “New semifields, PN and APN functions”, Des., Codes, and Cryptogr., 54:3 (2010), 189–200 | DOI | MR | Zbl

[21] Bluher A. W., “On $x^{q+1}+ax+b$”, Finite Fields and their Appl., 10:3 (2004), 285–305 | DOI | MR | Zbl

[22] Bracken C., Byrne E., MarkinN., McGuire G., Quadratic almost perfect nonlinear functions with many terms, IACR Cryptology ePrint Archive, , 2007 https://eprint.iacr.org/2007/115

[23] Bracken C., Byrne E., Markin N., McGuire G., An infinite family of quadratic quadrinomial APN functions, 2007, 7 pp., arXiv: 0707.1223 | MR

[24] Bracken C., Byrne E., Markin N., McGuire G., “New families of quadratic almost perfect nonlinear trinomials and multinomials”, Finite Fields and their Appl., 14:3 (2008), 703–714 | DOI | MR | Zbl

[25] Bracken C., Byrne E., Markin N., McGuire G., “A few more APN functions”, Cryptogr. Commun., 3:1 (2011), 43–53 | DOI | MR | Zbl

[26] Bracken C., Tan C. H., Tan Y., “On a class of quadratic polynomials with no zeros and its application to APN functions”, Finite Fields Appl., 25 (2014), 26–36 | DOI | MR | Zbl

[27] Brinkman M., Leander G., “On the classification of APN functions up to dimension five”, Des., Codes and Cryptogr., 49:1 (2008), 273–288 | DOI | MR | Zbl

[28] Browning K., Dillon J. F., McQuistan M. T., “APN polynomials and related codes”, J. Combin., Inform. System Sci., 34:1–4 (2009), 135–159 | Zbl

[29] Browning K., Dillon J. F., McQuistan M. T., Wolfe A. J., “An APN permutations in dimension six”, Finite Fields: Theory and Appl., Contemp. Math., 518, AMS, Providence, RI, 2010, 33–42 | DOI | MR | Zbl

[30] Budaghyan L., Carlet C., Felke P., Leander G., An infinite class of quadratic APN functions which are not equivalent to power mappings, IACR Cryptology ePrint Archive, , 2005 https://eprint.iacr.org/2005/359

[31] Budaghyan L., Carlet C., Pott A., “New classes of of almost bent and almost perfect nonlinear functions”, IEEE Trans. Inf. Theory, IT-52:3 (2006), 1141–1152 | DOI | MR | Zbl

[32] Budaghyan L., Carlet C., Leander G., A class of quadratic APN binomials inequivalent to power functions, IACR Cryptology ePrint Archive, , 2006 https://eprint.iacr.org/2006/445 | MR

[33] Budaghyan L., “The simplest method for constructing APN polynomials EA-inequivalent to power functions”, Arithmetic of Finite Fields, Lect. Notes Comput. Sci., 4547, 2007, 177–188 | DOI | MR | Zbl

[34] Budaghyan L., Carlet C., Leander G., Another class of quadratic APN binomials over $\mathbb{F}_{2^n}$: the case $n$ divisible by 4, IACR Cryptology ePrint Archive, Workshop Coding Cryptogr., , 2007 https://eprint.iacr.org/2006/428

[35] Budaghyan L., Carlet C., Leander G., “Two classes of quadratic APN binomials inequivalent to power functions”, IEEE Trans. Inform. Theory, IT-54:9 (2008), 4218–4229 | DOI | MR | Zbl

[36] Budaghyan L., Carlet C., “Classes of quadratic APN trinomials and hexanomial and related structures”, IEEE Trans. Inf. Theory, IT-54:5 (2008), 2354–2357 | DOI | MR | Zbl

[37] Budaghyan L., Helleset T., “New perfect nonlinear multinomials over $G_p^{2k}$ for any odd prime $p$”, SETA'2008, Lect. Notes Comput. Sci., 5203, 2008, 401–414 | MR

[38] Budaghyan L., Carlet C., Leander G., “Constructing new APN functions from known ones”, Finite Fields their Appl., 15:2 (2009), 150–159 | DOI | MR | Zbl

[39] Budaghyan L., Helleseth T., “New commutative semifields defined by PN multinomials”, Cryptogr. and Commun., 3:1 (2011), 1–16 | DOI | MR | Zbl

[40] Budaghyan L., Construction and analysis of cryptographic functions, Habilitation thesis, Univ. Paris 8, Paris, 2013, 192 pp. | MR

[41] Carlet C., Charpin P., Zinoviev V., “Codes, bent functions and permutations suitable for DES-like cryptosistems”, Des., Codes, and Cryptogr., 15:2 (1998), 125–156 | DOI | MR | Zbl

[42] Carlet C., Ding C., Yuan J., “Linear codes from perfect nonlinear mappings and their secret sharing schemes”, IEEE Trans. Inf. Theory, IT-51:6 (2005), 2088–2102 | MR

[43] Carlet C., “Boolean functions for cryptography and error correcting codes”, Boolean Methods and Models in Mathematics, Computer Science, and Engineering, Encyclopedia of Mathematics and Its Applications, 134, Cambridge Univ. Press, Cambridge, 2010, 257–397 | Zbl

[44] Carlet C., “Vectorial Boolean functions for cryptography”, Boolean Methods and Models in Mathematics, Computer Science, and Engineering, Encyclopedia of Mathematics and Its Applications, 134, Cambridge Univ. Press, Cambridge, 2010, 398–469 | Zbl

[45] Carlet C., “Relating three nonlinearity parameters of vectorial functions and building APN functions from bent functions”, Des., Codes, and Cryptogr., 59:1–3 (2011), 89–109 | DOI | MR | Zbl

[46] Carlet C., “Open questions on nonlinearity and APN functions”, Arithmetic of Finite Fields, Lect. Notes Comput. Sci., 9061, 2015, 83–107 | DOI | MR | Zbl

[47] Caullery F., Polynomial functions of degree 20 which are not APN infinitely often, 2013, 18 pp., arXiv: 1212.4638v2

[48] Chabaud F., Vaudenay S., “Links between differential and linear cryptanalysis”, EUROCRYPT'94, Lect. Notes Comput. Sci., 950, 1994, 356–365 | DOI | MR

[49] Coulter R. S., Henderson M., Kosick P., “Planar polynomials for commutative semifields with specified nuclei”, Des., Codes, and Cryptogr., 44:1–3 (2007), 275–286 | DOI | MR | Zbl

[50] Coulter R. S., Lazebnik F., “On the classification of planar monomials over fields of square order”, Finite Fields and their Appl., 18:2 (2012), 316–336 | DOI | MR | Zbl

[51] Coulter R. S., Matthews R. W., “Planar functions and planes of Lenz–Barlotti class II”, Des., Codes, and Cryptogr., 10:2 (1997), 167–184 | DOI | MR | Zbl

[52] Dembowski P., Ostrom T. G., “Planes of order $n$ with collineation groups of order $n^2$”, Math. Zeitschrift, 103:3 (1968), 239–258 | DOI | MR | Zbl

[53] Dillon J., “APN polynomials: an update, presentation”, 9th Int. Conf. Finite Fields and Appl. (Fq9) (2009) http://mathsci.ucd.ie/g̃mg/Fq9Talks/Dillon.pdf

[54] Ding C., Yuan J., “A new family of skew Paley–Hadamard difference sets”, J. Comb. Theory, Ser. A, 133:7 (2006), 1526–1535 | DOI | MR

[55] Dobbertin H., “One-to-one highly nonlinear power functions over $F_2$”, Appl. Algebra in Eng. Commun. Comput., 9:2 (1998), 139–152 | DOI | MR | Zbl

[56] Dobbertin H., “Almost perfect nonlinear power functions over $GF(2^n)$: the Welch case”, IEEE Trans. Inf. Theory, IT-45:4 (1999), 1271–1275 | DOI | MR | Zbl

[57] Dobbertin H., “Almost perfect nonlinear power functions over $GF(2^n)$: the Niho case”, Inf. and Comput., 151:1–2 (1999), 57–72 | DOI | MR | Zbl

[58] Dobbertin H., “Almost perfect nonlinear power functions over $GF(2^n)$: a new case for $n$ divisible by 5”, Finite Fields and Applications, Fifth Int. Conf. $F_q5$, Springer, 2001, 113–121 | DOI | MR | Zbl

[59] Dobbertin H., Mills D., Muller E. N., Pott A., Willems W., “APN functions in odd characteristic”, Discrete math., 267:1–3 (2003), 95–112 | DOI | MR | Zbl

[60] Edel Y., Kyureghyan G., Pott A., “A new APN functions which is not equivalent to a pover mapping”, IEEE Trans. Inf. Theory, IT-52:2 (2006), 744–747 | DOI | MR | Zbl

[61] Edel Y., “Geometrical and combinatorial aspects APN functions”, presentation, Contact Forum: Coding Teory and Cryptography, III (2009) http://cage.ugent.be/l̃s/website2009/abstracts/slidesyvesedel.pdf

[62] Edel Y., “Quadratic APN functions as subspaces of alternating bilinear forms”, Contact Forum: Coding Theory and Cryptography, III (2009) http://www.mathi.uni-heidelberg.de/~yves/Papers/ContactForum09.pdf

[63] Edel Y., Pott A., “A new almost perfect nonlinear functions which is not quadratic”, Advances in Mathematics of Communications, 3:1 (2009), 59–81 | DOI | MR | Zbl

[64] Gagola S. M. III, Hall J. L., Two families of planar functions on $F_{p^{2r}}$, 2013, 22 pp., arXiv: 1302.3281v1

[65] Gold R., “Maximal recursive sequences with 3-valued recursive cross-correlation functions”, IEEE Trans. Inf. Theory, IT-14:1 (1968), 154–156 | DOI | Zbl

[66] Gologlu F., Pott A., “Almost perfect nonlinear functions: A possible geometric approach”, Proc. of Contact Forum Coding Theory and Cryptography II (2007), 75–100

[67] Golomb S. W., “Theory of transformation groups of polynomials over $GF(2)$ with applications to linear shift register sequences”, Inf. Sci., 1:1 (1968), 87–109 | DOI | MR | Zbl

[68] Helleseth T., Sandberg D., “Some power mappings with low differencial uniformity”, Appl. Algebra in Eng. Commun. Comput., 8:5 (1997), 363–370 | DOI | MR | Zbl

[69] Hernando F., McGuire G., Monserrat F., “On the classification of exceptional planar functions over $F_p$”, Geom. Dedicata, 173:1 (2014), 1–35 | DOI | MR | Zbl

[70] Jedicka D., “APN monomials over $GF(2^n)$ for infinitely many $n$”, Finite Fields and their Appl., 13:4 (2007), 1006–1028 | DOI | MR

[71] Kasami T., “The weight enumerator for several classes of subcodes of the 2nd order binary Reed–Muller codes”, Inf. Control, 18:4 (1971), 369–394 | DOI | MR | Zbl

[72] Kyureghyan G. M., “Crooked maps in $F_{2^n}$”, Finite Fields Appl., 13:3 (2007), 713–726 | DOI | MR | Zbl

[73] Leander G., Rodier F., “Bounds on the degree of APN polynomials: the case of $x^{-1}+g(x)$”, Des., Codes and Cryptogr., 59:1–3 (2011), 207–222 | DOI | MR | Zbl

[74] Leducq E., A proof of two conjecture on APN functions, 2010, arXiv: 1006.4026

[75] Leducq E., “Functions which are PN on infinitely many extensions of $F_p$, $p$ odd”, Des., Codes, and Cryptogr., 75:2 (2015), 281–299 | DOI | MR | Zbl

[76] Ness G. J., Helleseth T., “A new family of ternary almost perfect nonlinear mappings”, IEEE Trans. Inf. Theory, IT-53:7 (2007), 2581–2586 | DOI | MR | Zbl

[77] Niho J., Multi-valued cross-correlation functions between two maximal linear recursive sequences, Ph. D. thesis, Univ. Southern California, Los-Angeles, 1972

[78] Nyberg K., “Perfect non-linear $S$-boxes”, EUROCRYPT'91, Lect. Notes Comput. Sci., 547, 1991, 378–386 | DOI | MR | Zbl

[79] Nyberg K., Knudsen L. R., “Provable security against differential cryptanalysis”, CRYPTO'92, Lect. Notes Comput. Sci., 740, 1992, 566–574 | DOI | MR

[80] Nyberg K., “Differentially uniform mappings for cryptography”, EUROCRYPT'93, Lect. Notes Comput. Sci., 765, 1993, 55–64 | DOI | MR

[81] Pott A., “Nonlinear functions in abelian groups and relative difference sets”, Discrete Appl. Math., 138:1–2 (2004), 177–193 | DOI | MR | Zbl

[82] Rodier F., “Functions of degree 4 that are not APN infinite often”, Cryptogr. Commun., 3:4 (2011), 227–240 | DOI | MR | Zbl

[83] Rothaus O. S., “On bent functions”, J. Comb. Theory, ser. A, 20:3 (1976), 300–305 | DOI | MR | Zbl

[84] Schmidt K.-U., Zhou Y., “Planar functions over field of characteristic two”, J. Algebr. Comb., 40:2 (2014), 503–526 | DOI | MR | Zbl

[85] Tokareva N. N., Bent functions: results and applications to cryptography, Elsevier, Acad. Press, Amsterdam, 2015, 220 pp. | MR | Zbl

[86] Yu Y., Wang M., Li Y., “A matrix approach for constructing quadratic APN functions”, Des., Codes, and Cryptogr., 73:2 (2014), 587–600 | DOI | MR | Zbl

[87] Zha Z., Kyureghyan M., Wang X., A new family of perfect nonlinear binomials, IACR Cryptology ePrint Archive, , 2008 https://eprint.iacr.org/2008/196

[88] Zha Z., Kyureghyan M., Wang X., “Perfect nonlinear binomials and their semifields”, Finite Field and their Appl., 15:2 (2009), 125–133 | DOI | MR | Zbl