New families of perfect nonlinear polynomial functions. (English) Zbl 1209.11107

Let \(f(x)\) be a map from \(\text{GF}(p^n) \rightarrow \text{GF}(p^n)\) and for any \(a,b \in \text{GF}(p^n)\) let \(N(a,b)\) denote the number of solutions \(x \in \text{GF}(p^n)\) of \(f(x+a) - f(x) = b\). We call \(f(x)\) differentially \(k\)-uniform if the maximum value of \(N(a,b)\) is \(k\). In the particular case where \(k = 1\) we call \(f(x)\) a PN or perfect nonlinear (PN) function. For \(p=2\) there do not exist PN functions, but a function with \(k=2\) is known is an APN or almost perfect nonlinear function. These classes of functions have been studied over the past several years for their resistance to differential and linear cryptanalysis, see [K. Nyberg, “Differentially uniform mappings for cryptography”, Lect. Notes Comput. Sci. 765, 55–64 (1994; Zbl 0951.94510)], and also for applications in finite geometry where they have connections to finite projective planes, semifields and difference sets. In fact, R. S. Coulter and M. Henderson [Adv. Math. 217, No. 1, 282–304 (2008; Zbl 1194.12007)] have recently shown that the problems of classifying finite presemifields of odd order and of classifying PN Dembowski-Ostrom polynomials, which are of the form \(\sum_{i,j = 0}^{n-1} a_{i,j} x^{p^i + p^j},\;\;\;a_{i,j} \in \text{GF}(p^n)\) [P. Dembowski and T. Ostrom, Math. Z. 103, 239–258 (1968; Zbl 0163.42402)], are equivalent.
We recall that there are two types of equivalence of functions of \(\text{GF}(p^n)\) which are usually considered, Extended Affine (EA) Equivalence, and the coarser Carlet-Charpin-Zinoviev (CCZ) Equivalence, which coincide for PN functions. There are few known types of EA-inequivalent functions and finding new ones is difficult. The main result of this paper is to give a new family of trinomial PN functions which are inequivalent to known ones, and arise as generalizations to odd characteristic of recently introduced new APN functions of L. Budaghyan and C. Carlet [IEEE Trans. Inf. Theory 54, No. 5, 2354–2357 (2008; Zbl 1177.94134)]. The results of this paper not only add to our knowledge of PN functions but establish the existence of a new presemifield which is not isotopic to any already discovered.


11T71 Algebraic coding theory; cryptography (number-theoretic aspects)
11T06 Polynomials over finite fields
12E20 Finite fields (field-theoretic aspects)
94A55 Shift register sequences and sequences over finite alphabets in information and communication theory
Full Text: DOI


[1] Bracken, C.; Byrne, E.; Markin, N.; McGuire, G., New families of quadratic almost perfect nonlinear trinomials and multinomials, Finite Fields Appl., 14, 703-714 (2008) · Zbl 1153.11058
[2] Budaghyan, L.; Carlet, C., Classes of quadratic APN trinomials and hexanomials and related structures, IEEE Trans. Inform. Theory, 54, 2354-2357 (2008) · Zbl 1177.94134
[3] Budaghyan, L.; Carlet, C.; Leander, G., Two classes of quadratic APN binomials inequivalent to power functions, IEEE Trans. Inform. Theory, 54, 4218-4229 (2008) · Zbl 1177.94135
[4] Budaghyan, L.; Carlet, C.; Pott, A., New classes of almost bent and almost perfect nonlinear polynomials, IEEE Trans. Inform. Theory, 52, 1141-1152 (2006) · Zbl 1177.94136
[5] 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
[6] Coulter, R. S.; Henderson, M., Commutative presemifields and semifields, Adv. Math., 217, 282-304 (2008) · Zbl 1194.12007
[7] Coulter, R. S.; Henderson, M.; Kosick, P., Planar polynomials for commutative semifields with specified nuclei, Des. Codes Cryptogr., 44, 275-286 (2007) · Zbl 1215.12012
[8] Coulter, R. S.; Matthews, R. W., Planar functions and planes of Lenz-Barlotti class II, Des. Codes Cryptogr., 10, 167-184 (1997) · Zbl 0872.51007
[9] Dembowski, P.; Ostrom, T., Planes of order \(n\) with collineation groups of order \(n^2\), Math. Z., 103, 239-258 (1968) · Zbl 0163.42402
[10] Dillon, J. F., APN polynomials and related codes, (Polynomials over Finite Fields and Applications (November, 2006), Banff International Research Station) · Zbl 1269.94035
[11] Ding, C.; Yin, J., Signal sets from functions with optimum nonlinearity, IEEE Trans. Commun., 55, 936-940 (2007)
[12] Ding, C.; Yuan, J., A family of optimal constant-composition codes, IEEE Trans. Inform. Theory, 51, 3668-3671 (2005) · Zbl 1181.94129
[13] Ding, C.; Yuan, J., A new family of skew Paley-Hadamard difference sets, J. Combin. Theory Ser. A, 113, 1526-1535 (2006) · Zbl 1106.05016
[14] Helleseth, T.; Sandberg, D., Some power mappings with low differential uniformity, Appl. Algebra Engrg. Comm. Comput., 8, 363-370 (1997) · Zbl 0886.11067
[15] Kyureghyan, G.; Pott, A., Some remarks on planar mappings, (Proceedings of WAIFI 2008. Proceedings of WAIFI 2008, Lecture Notes in Comput. Sci., vol. 5130 (2008)), 115-122 · Zbl 1180.94056
[16] Ness, G. J.; Helleseth, T., A new family of ternary almost perfect nonlinear mappings, IEEE Trans. Inform. Theory, 53, 2581-2586 (2007) · Zbl 1323.94130
[17] Nyberg, K., Differentially uniform mappings for cryptography, (Advances in Cryptology - EUROCRYPT 93. Advances in Cryptology - EUROCRYPT 93, Lecture Notes in Comput. Sci., vol. 765 (1994), Springer-Verlag: Springer-Verlag New York), 134-144 · Zbl 0951.94510
[18] Weng, G.; Qiu, W.; Wang, Z.; Xiang, Q., Pseudo-Paley graphs and skew Hadamard sets from presemifields, Des. Codes Cryptogr., 44, 49-62 (2007) · Zbl 1126.05026
[19] Zha, Z.; Kyureghyan, G.; Wang, X., Perfect nonlinear binomials and their semifields, Finite Fields Appl., 15, 125-133 (2009) · Zbl 1194.12003
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.