# Another Class of Perfect Nonlinear Polynomial Functions

Authors: Menglong Su; Zhengbang Zha; Zhonghai Xu
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

Perfect nonlinear (PN) functions have been an interesting subject of study for a long time and have applications in coding theory, cryptography, combinatorial designs, and so on. In this paper, the planarity of the trinomialsxpk+1+ux2+vx2pk over GF(p2k) are presented. This class of PN functions are all EA-equivalent to x2.


---

## Body

## 1. Introduction

Letpbe a prime andGF(pn)a finite field withpnelements. Letfbe a mapping fromGF(pn)to itself. LetN(a,b)denote the number of solutionsx∈GF(pn)off(x+a)-f(x)=b, wherea,b∈GF(pn), and letΔf=max{N(a,b)∣a,b∈GF(pn),a≠0}. Nyberg [1] defined a mappingfto be differentiallyk-uniform ifΔf=k. For applications in cryptography, one would like to employ functions for whichΔfis as small as possible. The differentially 2-uniform function is called APN function. And we know that APN functions are optimal overGF(2n). This concept is of interest in cryptography since differential and linear cryptanalysis exploit the uniform property of the functions which are used in many block ciphers, such as DES. The differentially 1-uniform function is called PN function. It is interesting to observe that PN functions have also been studied under the name of planar functions which are functions such thatf(x+a)-f(x)is a permutation polynomial for alla∈GF(pn)*=GF(pn)∖{0}. Planar functions were introduced in [2] to describe projective planes with certain properties. In recent papers [3, 4], PN functions were used to describe new finite commutative semifields of odd order. In [5, 6], it was shown that a PN function yields either a skew Hadamard difference set or a Paley type partial difference set depending onpn(mod 4). PN function is one of the most important cryptographic functions [7, 8] and has extensive applications in cryptography and communication. For example, PN and APN functions were used to construct optimal constant-composition codes and signal sets [9, 10].Since PN functions have many applications in coding theory, cryptography, combinatorial designs, and so on, it is interesting to find new PN functions. We call a function “new” only if it is CCZ-inequivalent to the old ones. As we know, there are only three classes of PN monomials. Whether there exists another class of PN monomials is an open problem. In [11], Coulter and Matthews introduced the first family of PN polynomials. Ding and Yuan [5] generalized their results and presented a new skew Hadamard difference set. Helleseth et al. [12] showed a family of PN binomialsuxpk+1+x2overGF(p2k)which is equivalent to the monomialx2. After that, some new methods were used to construct new PN functions (please see [13–17] and references therein), but it is still difficult to find more new PN functions. Many constructions of PN functions are used of the link between quadratic PN functions and commutative semifields. Bierbrauer [18] introduced a general projection method to construct commutative semifields and generalized the known PN functions. Pott and Zhou presented a switching construction of PN functions in [19] and introduced a character theoretic approach to prove the planarity of a function in [20]. Recently, they presented new commutative semifields with two parameters and then get new PN functions [21]. In their paper [22], Kyureghyan and Özbudak constructed some new PN functions by the products of two linearized polynomials.In [12], the binomial composed with inequivalent monomialsx2andxq+1was shown to be equivalent to the monomialx2overGF(q2). What about the planarity of trinomial composed with monomialsx2,x2qandxq+1? In this paper, we will answer this question. In Section 2, we recall some definitions and tools used later in the paper. In Section 3, we characterize the planarity of the trinomialsxpk+1+ux2+vx2pkoverGF(p2k). These PN trinomials are shown to be equivalent to monomialx2in Section 4. We then conclude this paper in Section 5 with some future work.


## 2. Preliminaries

Letpbe an odd prime, and letnbe a positive integer. Letχ(x)be a function onGF(pn)defined byχ(x)=x(pn-1)/2. Then, we get thatχ(x)=0whenx=0,χ(x)=1whenxis a square inGF(pn)∖{0}, andχ(x)=-1whenxis a nonsquare inGF(pn)∖{0}.Thep-weight of a nonnegative integermis the sum of the digits in itsp-adic representation; that is, ifm=∑i‍bipiwith0≤bi<p, then thep-ary weight ofmis∑i‍bi∈ℤ. Recall that any mapping of GF(pn)can be represented by a polynomial overGF(pn)of degree less thanpn. Moreover, different such polynomials define different mappings. This allows us to identify the set of mappings ofGF(pn)with the set of polynomials overGF(pn)with degree less thanpn. The algebraic degree of a polynomial overGF(pn)is the maximalp-weight of the exponents of its nonzero terms. A polynomial is called quadratic if it has algebraic degree 2. The following polynomials of algebraic degree 2
(1)∑i,j=0n-1‍ai,jxpi+pj,ai,j∈GF(pn)
are called Dembowski-Ostrom (DO) polynomials in [2].Letci∈GF(pn). A polynomial of the formL(x)=∑i=0n-1cixpiis called linearized orp-polynomial overGF(pn). The sum of a linear mapping and a constant inGF(pn)is called an affine mapping.Two functionsf,g:GF(pn)→GF(pn)are called extended affine (EA) equivalent, ifg=L1∘f∘L2+L3for some affine permutationsL1,L2and affine functionL3. The functionsfandgare called Carlet-Charpin-Zinoviev (CCZ) equivalent if the graphs offandgare affine equivalent [23]. CCZ-equivalent functions have the same differential uniformity and the same extended Walsh spectrum. It is showed in [24] that the CCZ-equivalence coincides with the EA-equivalence for PN functions. For planar DO polynomials, CCZ-equivalence coincides with linear equivalence [14].In [3], Coulter and Henderson proved that planar DO polynomials are equivalent to commutative semifields with odd characteristic. Many new PN functions are defined by corresponding commutative semifields with no explicit function expressions, such as Dickson semifields and Cohen-Ganley semifileds [4, 25, 26]. In the following, we just list the known EA-inequivalent PN functions which have explicit function expressions:(a)
x2overGF(pn)(folklore);(b)
xpk+1overGF(pn), wherek≤n/2andn/(k,n)is odd ([2, 11]);(c)
x10±x6-x2overGF(3n), wheren≥5is odd ([5, 11]);(d)
xps+1-vxp2k+pk+soverGF(p3k), wherek1=k/gcd(k,s),s1=s/gcd(k,s),k1is odd, ord(v)=q2+q+1, and at least one of the following conditions hold:k1+s1≡0mod 3,pk≡ps≡1mod 3 ([13, 17]);(e)
xps+1-vxp3k+pk+soverGF(p4k), where2k/gcd(2k,s)is odd, ord(v)=q3+q2+q+1, andpk≡ps≡1mod 4 ([13]);(f)
x(3k+1)/2overGF(3n), wherek≥3is odd and(k,n)=1([11]);(g)
xq+1+ωβxps+1+ωβqxq(ps+1)overGF(q2), whereq=pm,ω,β∈GF(q2),ω+ωq=0,sis a positive integer,βis not agcd(q+1,ps+1)th power, and there is no0≠a∈GF(q2)such thataq+a=0andaps=-a([14, 18]);(h)
x2+x2qm+G(xq2+1)overGF(q2m), whereqis a power of an odd primep,m=2k+1,  andG(x)=h(x-xqm)withh(x)=∑i=0k(-1)ixq2i+∑j=0k-1(-1)k+jxq2j+1([18, 27]);(i)
x2+x90overGF(35)([28]).Below, we always letpbe an odd prime andq, n, kpositive integers withn=2kandq=pk.


## 3. A New Family of PN Trinomials overGF(p2k)

In this section, we propose a new family of PN trinomials overGF(p2k)which are composed of inequivalent monomialsx2andxpk+1.Theorem 1.
Letu,v,θ∈GF(q2)withθ=(vq+1-uq+1)2-(u-vq)q+1, and letf:GF(q2)→GF(q2)be given byf(x)=xq+1+ux2+vx2q. Then,f(x)is PN if and only ifθ(q-1)/2=1.Proof.
We need to count the number of solutions off(x+a)-f(x)=bunder the conditions defined above for anya≠0,binGF(q2). The equationf(x+a)-f(x)=bcan be written as
(2)(x+a)q+1+u(x+a)2+v(x+a)2q-xq+1-ux2-vx2q=b.
LetΔ=b-f(a). Then, (2) turns to
(3)axq+aqx+2uax+2vaqxq=Δ.
As (3) is affine, we just need to consider the caseΔ=0. WhenΔ=0, for the functionf(x)to be PN, it is necessary and sufficient thataxq+aqx+2uax+2vaqxq=0hasx=0as its only solution for any nonzeroa∈GF(q2). That is, sayxq-1=-(aq+2ua)/(a+2vaq)≠0has no solution overGF(q2). Therefore,f(x)is PN if and only if the equation(aq+2ua)q+1=(a+2vaq)q+1is not true. It can be written as
(4)(u-vq)a2+2(uq+1-vq+1)aq+1+(uq-v)a2q=0.
Ifu-vq=0, (4) is always true. We assume thatu-vq≠0. Lett=aq-1. Sincea≠0, we can get
(5)(uq-v)t2+2(uq+1-vq+1)t+u-vq=0
from (4). Then, we gett(vq+1-uq+1±θ1/2)/(uq-v)withθ=(vq+1-uq+1)2-(u-vq)q+1. As we knowtq+1=1, then we have
(6)(vq+1-uq+1)2±(θ1/2+θq/2)(vq+1-uq+1)+θ(q+1)/2(u-vq)q+1=1.
Sinceθq=θ, then we getθq/2=±θ1/2. Ifθ(q-1)/2=0or −1, we can obviously find that (6) is true. Ifθ(q-1)/2=1, then we get
(7)(vq+1-uq+1)2±2θ1/2(vq+1-uq+1)+θ=(u-vq)q+1
from (6). It leads toθ1/2=±(vq+1-uq+1)andu-vq=0, which contradicts the first assumptionu-vq≠0. Therefore,f(x)is PN if and only ifθ(q-1)/2=1.We can get the following corollary from Theorem1.Corollary 2.
Letf:GF(q2)→GF(q2)be given byf(x)=xq+1+ux2+vx2q, whereu1+q=v1+q. Then,f(x)is PN if and only ifq≡1 (mod 4),χ(uq-v)=1orq≡3 (mod 4),χ(uq-v)=-1.Proof.
From Theorem1, we get thatf(x)is PN if and only if((vq+1-uq+1)2-(u-vq)q+1)(q-1)/2=1. Sinceu1+q=v1+q, we just need(-(u-vq)q+1)(q-1)/2=1;thatis,0≠-(u-vq)q+1is a2(q+1)th power. Whenχ(uq-v)=1,-(u-vq)q+1is a2(q+1)th power if and only if −1 is a2(q+1)th power, which is equivalent toq≡1 (mod 4). Whenχ(uq-v)=-1, we get that(u-vq)q+1is a(q+1)th power and not2(q+1)th power. In this case,-(u-vq)q+1is a2(q+1)th power if and only ifq≡3 (mod 4).Remark 3.
Iff(x)is PN in Corollary 2, we haveu(1+q)/2=-v(1+q)/2for accuracy. Since((u-vq)/(uq-v))·(v/u)=(uv-vq+1)/(uq+1-uv)=-1, then we get(uq-v)q-1(v/u)=-1. Whetherq≡1 (mod 4),χ(uq-v)=1orq≡3 (mod 4),χ(uq-v)=-1, we get thatv/uis a(q-1)th power and not a2(q-1)th power, which impliesu(1+q)/2=-v(1+q)/2.The PN functions defined in Corollary2 exist. For example, the functionx3k+1-x2+x2·3kis PN overGF(32k), wherekis even.


## 4. The Linear Equivalence of the New PN Trinomials

In this section, we will discuss the linear equivalence between our new PN functions and the known PN monomialx2. First, we give a simple proof to show that the PN functions defined in Corollary 2 are equivalent tox2.Theorem 4.
The PN functionf(x)defined in Corollary 2 is linear equivalent tox2.Proof.
Sinceu(1+q)/2=-v(1+q)/2, we obtain(v/u)1+q=1andv/uis a(q-1)th power. Letθ2=v/u, and letL1(x)=((1-2θvq)/(u-vq))x+((2θu-1)/(u-vq))xq,L2(x)=x+θxqbe linear polynomials onGF(q2). We can getL1(f(x))=L2(x)2.
Assume thatL2(x+a)=L2(x), we obtaina+θaq=0, which implies thata=0oraq-1=-θ. Ifaq-1=-θ, we geta2(q-1)=v/u. Sincev/uis not a2(q-1)th power in Corollary 2 then we haveaq-1≠-θanda=0. Thus,L2(x)=x+θxqis a linear permutation.
If one of1-2θvqand2θu-1equals to 0, we can get thatL1(x)is a linear permutation. If both of1-2θvqand2θu-1equal 0, we can getuq=v. This is not true forχ(uq-v)≠0. Otherwise, we assumeL1(x+a)=L1(x). Then, we geta=0oraq-1=(2θvq-1)/(2θu-1). Ifa≠0, we get(2θvq-1)1+q=(2θu-1)1+q. We can deduce thatθq(uq-v)=-θ(u-vq). It leads to
(8)(vu)(q+1)/2=θq+1=-u-vquq-v·vu=vq+1-uvuq+1-uv=1.
Then, we get thatv/uis a2(q-1)th power which contradicts the known resultu(1+q)/2=-v(1+q)/2. Therefore,L1(x)=((1-2θvq)/(u-vq))x+((2θu-1)/(u-vq))xqis also a linear permutation. This completes the proof.Inspired by the proof of Theorem4, we get a generalized result in the following theorem.Theorem 5.
The PN functionf(x)defined in Theorem 1 is linear equivalent tox2.Proof.
If the PN functionf(x)=xq+1+ux2+vx2qis linear equivalent tox2overGF(q2), there must exist linear permutationsL1(x)=∑j=0n-1bjxpjandL2(x)=∑j=0n-1cjxpjsuch that
(9)∑j=0n-1‍bj(x1+q+ux2+vx2q)pj=∑i,j=0n-1‍cicjxpi+pj.
Wheni-j≠0,k∈ℤ2k, there is no item of the typexpi+pjon the left side of (9). Then, we can get that the coefficient ofxpi+pjequals to 0. It shows that2cicj=0. Assume that cl≠0for somel, we obtain thatcj=0whenj≠l,l+k∈ℤ2k. Then, (9) can be written as
(10)∑j=0n-1‍bj(x1+pk+ux2+vx2pk)pj=cl2x2pl+cl+k2x2pl+k+2clcl+kxpl+pl+k.
Whenj≠l, l+k, we can see that there is no item of typexpj(1+pk)andx2pjon the right side of (10). Then, we havebj+bj+k=0andbjupj+bj+kvpj+k=0. This leads tobj=-bj+kandbj(upj-vpj+k)=0. Sinceu-vpk≠0, then we obtain thatbj=0whenj≠l, l+k. Therefore, (10) can be written as
(11)bl(x1+pk+ux2+vx2pk)pl+bl+k(x1+pk+ux2+vx2pk)pl+k=cl2x2pl+cl+k2x2pl+k+2clcl+kxpl+pl+k.
Comparing the coefficients ofx2pl,x2pl+k, andxpl(1+pk)of (11), we can get the following equations:
(12)bl+bl+k=2clcl+k,(13)blupl+bl+kvpl+k=cl2,(14)blvpl+bl+kupl+k=cl+k2.
From (12) and (13), we obtainbl+k=(cl2-2clcl+kupl)/(vpl+k-upl). We can also obtainbl+k=(cl+k2-2clcl+kvpl)/(upl+k-vpl)from (13) and (14). Then, we have
(15)(upl+k-vpl)(clcl+k)2+2(vpl(1+pk)-upl(1+pk))(clcl+k)+upl-vpl+k=0.
We note thatL2(x)=clxpl+cl+kxpl+kis a permutation if and only ifcl/cl+kis not a(pk-1)th power. Comparing (5) and (15), we havecl/cl+k=-tpl. Under the conditions of Theorem 1,tq+1=1is not true. Then, we get thatcl/cl+kis not a(pk-1)th power andL2(x)is a permutation.
From (12)–(14), we get bl+k=(cl2-2clcl+kupl)/(vpl+k-upl) and bl=(2clcl+kvpl+k-cl2)/(vpl+k-upl). If one ofblandbl+kequals to 0, thenL1(x)=blxpl+bl+kxpl+kis a monomial permutation. If both ofblandbl+kequal to 0, we getu=vpk, which leads to a contradiction. Now, we consider the case that bothblandbl+kare not equal to 0. In this case,L1(x)=blxpl+bl+kxpl+kis a permutation if and only ifbl/bl+kis not a(pk-1)th power. We assume thatbl/bl+k=(2cl+kvpl+k-cl)/(cl-2cl+kupl)is a(pk-1)th power. Then, we have(2cl+kvpl+k-cl)pk+1=(cl-2cl+kupl)pk+1, which implies
(16)(upl-vpl+k)(clcl+k)pk+(upk+l-vpl)clcl+k+2(vpl(1+pk)-upl(1+pk))=0.
From (15), we can getcl/cl+k=(upl(1+pk)-vpl(1+pk)±θpl/2)/(upk+l-vpl)withθdefined in Theorem 1.  Substituting the value ofcl/cl+kinto (16), we have
(17)upl(1+pk)-vpl(1+pk)±θpk+l/2+upl(1+pk)-vpl(1+pk)±θpl/2+2(vpl(1+pk)-upl(1+pk))=0.
Sinceθ(pk-1)/2=1, from (17), we getθpl/2=0, which is a contradiction. Therefore, we get thatbl/bl+kis not a(pk-1)th power andL1(x)is a permutation. The proof is completed.


## 5. Conclusion

In this paper, we present a family of PN trinomials and determine the necessary and sufficient conditions which assure their planarity. All these PN functions are shown to be equivalent to the known PN functionx2by using the definition of linear equivalence. Our results give an answer for the question presented in the introduction. It seems hard to determine the planarity of the linear combination of termsxqi+qj(0≤i,j<n) overGF(qn), wheren≥3andqis an odd prime power. However, it may be possible to determine them in some special cases (e.g., see [15]). We will continue this study and try to find more new PN functions in the future work.



---

*Source: 917507-2013-12-03.xml*