New families of perfect nonlinear polynomial functions (Q2267446): Difference between revisions

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 [\textit{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, \textit{R. S. Coulter} and \textit{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)\) [\textit{P. Dembowski} and \textit{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 \textit{L. Budaghyan} and \textit{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.