A note on the differential spectrum of a class of power mappings with Niho exponent

Abstract

Let GF(q²) be the finite field containing q² elements, where q is an odd prime power. In this paper, we study the differential properties of the power mapping F(x) = x^d over GF(q²), where d = 2q − 1 is a Niho exponent [14]. The differential spectrum of F is given by

$\mathbb {S}=\{\omega _{0}=\frac {q^{2}+q-2}2, \omega _{2}=\frac {q^{2}-q}2, \omega _{q}=1\}$.

1 Introduction

Let GF(q) be the finite field with q elements, where q is a prime power. For any function f : GF(q) →GF(q), the derivative of f in respect to any given a ∈ GF(q) is a function from GF(q) to GF(q) defined by

$$D_{a}f(x)=f(x+a)-f(x),\forall x\in {\mathrm{G}\mathrm{F}}(q).$$

For any b ∈ GF(q) and a ∈ GF(q)^∗ := GF(q)$\setminus${0}, we denote

$$\delta(a,b)=\#\{x\in {\mathrm{G}\mathrm{F}}(q)~|~D_{a}f(x)=b\}.$$

The differential uniformity of f is defined as

$$\delta=\underset{a\in{\mathrm{G}\mathrm{F}}(q)^{*},\:b\in {\mathrm{G}\mathrm{F}}(q)}{\max}\delta(a,b),$$

and f is said to be differentially δ-uniform [15]. Differential uniformity is an important concept in cryptography since it quantifies the degree of security of a Substitution box (S-box) used in the cipher with respect to differential attacks [1]. Clearly, δ ≥ 1 for any f over GF(q). In particular, a function f with the lowest differential uniformity δ = 1 is called a perfect nonlinear (PN) function, which only exists in odd characteristic finite fields. Functions with differential uniformity δ = 2 are called almost perfect nonlinear (APN) functions, which have the lowest differential uniformity over even characteristic finite fields. For more information on PN and APN functions, the readers are referred to [5] and [6].

Power functions with low differential uniformity serve as good candidates for the design of S-boxes not only because of their strong resistance to differential attacks but also for the usually low implementation cost in hardware. Therefore, it is worthy to study power functions with low differential uniformity. When f (x) = x^d is a power function over GF(q), it is easy to see that $\delta (a,b)=\delta \left (1,\frac b{a^{d}}\right )$ for any a ∈ GF(q)^∗. This implies that the differential properties of f are completely determined by the values of δ(1, b) when b runs through GF(q). In [2], the differential spectrum of a power function is defined as follows.

Definition 1

[2] Let f (x) = x^d be a power function over GF(q) with differential uniformity δ. Denote

$$\omega_{i}=\#\{b\in {\mathrm{G}\mathrm{F}}(q)~|~\delta(1,b)=i\},$$

where 0 ≤ i ≤ δ. The differential spectrum of f is defined to be the multiset

$$\mathbb{S}=\{\omega_{i}~|~0\leq i\leq \delta\}.$$

Sometimes the zeros in $\mathbb {S}$ can be omitted. The differential spectrum of f over GF(q) satisfies the following identities (see [2]).

$$\sum\limits_{i=0}^{\delta}\omega_{i}=\sum\limits_{i=0}^{\delta}i\omega_{i}=q.$$

(1)

The identities (1) are useful in computing the differential spectrum of f. From (1), it is easy to see that all PN functions over GF(q) have the same differential spectrum $\mathbb {S}=\{\omega _{1}=q\}$, and all APN functions over GF(2ⁿ) have the same differential spectrum $\mathbb {S}=\{\omega _{0}=2^{n-1}, \omega _{2}=2^{n-1}\}$. Moreover, we have the following relationship between the differential spectrum and the number of solutions of a system of equations with four variables.

Lemma 1

[11] With the notation introduced in Definition 1, let N₄ denote the number of solutions (x₁, x₂, x₃, x₄) ∈ (GF(q))⁴ of the system of equations

$$\begin{array}{@{}rcl@{}} \left\{ \begin{array}{lllll} x_{1}-x_{2}+x_{3}-x_{4}&=&0,\\ {x^{d}_{1}}-{x^{d}_{2}}+{x^{d}_{3}}-{x^{d}_{4}}&=&0. \end{array} \right.\ \ \end{array}$$

Then we have

$$\sum\limits_{i=0}^{\delta}i^{2}\omega_{i}=\frac{N_{4}-q^{2}}{q-1}.$$

As pointed out in [2], the differential spectrum of S-boxes is useful to analyze the resistance of the cipher to the differential attacks and to its variations. For example, the inverse function x^− 1 over GF(2ⁿ) with even n has the best resistance to differential cryptanalysis for 4-uniform S-boxes, since it has the differential spectrum $\mathbb {S}=\{\omega _{0}=2^{n-1}+1,\omega _{2}=2^{n-1}-2,\omega _{4}=1\}$. However, it seems difficult to determine the differential spectrum of a power function. Only a few power mappings over GF(2ⁿ) have known differential spectrum, the readers are referred to [2,3,4, 17, 18]. For the power mappings over odd characteristic finite fields, the known results are introduced as follows. Dobbertin et al. determined the differential spectrum of the ternary Welch power mapping $x^{2\cdot 3^{\frac {n-1}{2}}+1}$ over GF(3ⁿ) with odd n, which was used in the study of the cross-correlation function of an m-sequence and its decimated sequence [9]. In [7], Choi et al. computed the differential spectra of two classes of power mappings. The differential spectrum of p-ary Kasami power function was studied in [21] and [12]. Recently, the differential spectrum of $x^{p^{n}-3}$ over GF(pⁿ) was determined in [16] and [20]. Yan and Li investigated the differential spectrum of $x^{\frac {5^{n}-3}{2}}$ over GF(5ⁿ), which was an involution function with algebraic degree n [19]. We summarize the known results in Table 1. By the main result in [8], the power mappings in Table 1 are pairwise CCZ-inequivalent.

Table 1 Power mappings x^d over GF(pⁿ) with known differential spectrum (p is odd)

Niho exponents were introduced by Yoji Niho, who investigated the cross-correlation function between an m-sequence and its decimation sequence in 1972 [14]. Since then, Niho exponents have been widely used in other research areas such as cryptography and coding theory. For the recent progress in the application of Niho exponents, the readers are referred to [13]. We focus on the power mapping F(x) = x^2q− 1 over GF(q²), where q is an prime power. Herein 2q − 1 is a Niho exponent. This exponent was first studied by Niho in [14]. which was used to construct m-sequences with four-valued cross-correlation function. Helleseth found the distribution of the cross-correlation function when q ≢ 2(mod 3) [10]. When q is a power of 2, the differential spectrum of F was computed by Blondeau et al. in 2011. It is rational to consider the differential spectrum of F for the case that q is an odd prime power. In this paper, we mainly study the differential spectrum of F(x) = x^2q− 1 over GF(q²), where q is an odd prime power. By solving certain differential equations over finite fields, we determine the differential spectrum of F in Section 2. The number of solutions of a system of equations with four variables is obtained from the differential spectrum. Section 3 concludes this paper.

2 The differential spectrum of F(x) = x ^2q− 1 over GF(q ²)

This section is devoted to study the differential spectrum of F(x) = x^2q− 1 over GF(q²), where q is an odd prime power. Before we investigate the differential spectrum of F, a useful lemma will be introduced first. For any x ∈ GF(q²)^∗, if there exist y ∈ GF(q²)^∗ such that y² = x, we call x a square element in GF(q²). Otherwise, we call x a nonsquare element in GF(q²). We have the following observation.

Lemma 2

Define $\mathbb {U}=\{z\in {\mathrm {G}\mathrm {F}}(q^{2})~|~z^{q+1}=1\}$. For any square element x ∈ GF(q²)^∗, there exist exactly two pairs, namely (y,z) and (−y,−z), such that x = yz = (−y)(−z), ± y ∈ GF(q)^∗ and $\pm z\in \mathbb {U}$.

Proof

Let 𝜖 be a primitive element in GF(q²). Since x is a square, then x = 𝜖^2u for some integer u in the range $0\leq u \leq \frac {q^{2}-3}{2}$. Note that (q + 1, q − 1) = 2, then there exist integers s and t such that s(q + 1) + t(q − 1) = 2. Then

$$x=\epsilon^{2u}=\epsilon^{(s(q+1)+t(q-1))u}=\epsilon^{su(q+1)}\epsilon^{tu(q-1)}.$$

Put y = 𝜖^su(q+ 1) and z = 𝜖^tu(q− 1), it can be checked that y ∈ GF(q)^∗ and $z\in \mathbb {U}$. Moreover, if there exist $y^{\prime }\neq y$ and $z^{\prime }\neq z$, such that $x=y^{\prime }z^{\prime }$, $y^{\prime }\in \mathrm {G}\mathrm {F}(q)^{*}$ and $z^{\prime }\in \mathbb {U}$, then we have

$$\frac{y^{\prime}}{y}=\frac{z}{z^{\prime}}\in \mathbb{U}.$$

We conclude that $y^{\prime }=-y$ since ${\mathrm {G}\mathrm {F}}(q)\cap \mathbb {U}=\{\pm 1\}$. The desired result follows.

To determine the differential spectrum of F, we mainly study the derivative equation

$$(x+1)^{2q-1}-x^{2q-1}=b$$

(2)

for some b ∈ GF(q²). Denote by δ(b) the number of solutions of (2) in GF(q²). We have the following lemma.

Lemma 3

With the notation introduced above, we have

(i):

δ(1) = q,

(ii):

δ(b) is either 0 or 2 for b ≠ 1.

Proof

When b = 1, (2) becomes

$$(x+1)^{2q-1}-x^{2q-1}=1.$$

(3)

It is obvious that x = 0 and x = − 1 are both solutions of (3). Now we assume that x ≠ 0,− 1. The (3) becomes

$$x(x+1)^{2q}-(x+1)x^{2q}=x(x+1),$$

then

$$x(x^{q}+1)^{2}-(x+1)x^{2q}=x(x+1),$$

i.e.,

$$(x^{q}-x)^{2}=0.$$

We assert that x is a solution of (3) if and only if x ∈ GF(q). Hence δ(1) = q.

Note that 2q − 1 is odd, then the solutions of (2) come in pairs, i.e., x is a solution of (2) if and only if − x − 1 is a solution of (2). Hence the value of δ(b) is even except when x = −x − 1, i.e., $x=-\frac {1}{2}$. In this latter case, the corresponding b equals to 1 since $-\frac {1}{2}\in \mathrm {G}\mathrm {F}(q)$. Thus δ(b) is even for b ≠ 1. In the rest of this proof, we will show δ(b) ≤ 2, for b ≠ 1. If b ≠ 1, then x ≠ 0. We discuss the solutions of (2) in the following two disjoint cases.

Case 1 x is a square element in GF(q²)^∗.

By Lemma 2, there exist y ∈ GF(q)^∗ and $z\in \mathbb {U}$ such that x = yz. Then (2) becomes

$$(yz+1)^{2q-1}-(yz)^{2q-1}=b.$$

Note that y^q = y and z^q = z^− 1, we obtain

$$y(bz-2z^{-1}+z^{-3})=1-b.$$

(4)

Raising both sides of (4) into the power q, we have

$$y(b^{q}z^{-1}-2z+z^{3})=1-b^{q}.$$

(5)

The (4) and (5) lead to

$$(bz-2z^{-1}+z^{-3})(1-b^{q})-(b^{q}z^{-1}-2z+z^{3})(1-b)=0,$$

which can be rewritten as

$$(z-z^{-1})\big((1-b)z^{2}-(1-b^{q+1})+(1-b^{q})z^{-2}\big)=0.$$

(6)

Note that z − z^− 1≠ 0. Otherwise, z = ± 1, then x = yz ∈ GF(q), which leads to b = 1, a contradiction. We then conclude that

$$(1-b)z^{2}-(1-b^{q+1})+(1-b^{q})z^{-2}=0.$$

(7)

Multiplying both sides of (7) by z² and denoting z² by u, we obtain

$$(1-b)u^{2}-(1-b^{q+1})u+(1-b^{q})=0,$$

(8)

which is a quadratic equation of u. There exist at most two u’s for a given b ≠ 1. Moreover, from (4) we obtain

$$x=yz=\frac{1-b}{b-2z^{-2}+z^{-4}}=\frac{1-b}{b-2u^{-1}+u^{-2}},$$

(9)

which means x is uniquely determined by u. Recall that x = yz = (−y)(−z), z and − z correspond to the same u. We conclude that (2) has at most two solutions in this case.

Case 2 x is a nonsquare element in GF(q²).

Let 𝜖 be a primitive element in GF(q²), let

$$\lambda=\left\{ \begin{array}{ll} \epsilon^{\frac{q+1}2}, & \text{if } \text{q }\equiv 1(\text{mod }4), \\ \epsilon^{\frac{q-1}2}, & \text{if } \text{q }\equiv 3(\text{mod }4). \end{array} \right.$$

Obviously, λ is a nonsquare element in GF(q²)^∗. Moreover, if q ≡ 1(mod 4), we have λ^q = −λ. If q ≡ 3(mod 4), we have λ^q = −λ^− 1.

Subcase 2.1. q ≡ 1(mod 4).

Since x is a nonsquare element, then xλ^− 1 is a square element. By Lemma 2, there exist y ∈ GF(q)^∗ and $z\in \mathbb {U}$ such that xλ^− 1 = yz, i.e., x = λyz. The (2) becomes

$$\lambda y(bz+2z^{-1}+z^{-3})=1-b.$$

(10)

Raising both sides of (10) into the power q, we have

$$-\lambda y(b^{q}z^{-1}+2z+z^{3})=1-b^{q}.$$

(11)

The (10) and (11) lead to

$$(z+z^{-1})\big((1-b)z^{2}+(1-b^{q+1})+(1-b^{q})z^{-2}\big)=0$$

(12)

If z + z^− 1 = 0, then z^− 1 = −z, we have (λz)^q = (−λ)(−z) = λz, i.e., λz ∈ GF(q). Therefore, x = λz ⋅ y ∈ GF(q), which indicates b = 1, a contradiction. We assert that z + z^− 1≠ 0, then the following identity holds.

$$(1-b)z^{2}+(1-b^{q+1})+(1-b^{q})z^{-2}=0.$$

(13)

Let u = z², then (13) becomes

$$(1-b)u^{2}+(1-b^{q+1})u+(1-b^{q})=0,$$

(14)

which is a quadratic equation of u. There exist at most two u’s for a given b≠ 1. Moreover, from (10) we obtain

$$x=\lambda yz=\frac{1-b}{b+2z^{-2}+z^{-4}}=\frac{1-b}{b+2u^{-1}+u^{-2}},$$

(15)

which means x is uniquely determined by u. Recall that x = λyz = λ(−y)(−z), z and − z correspond to the same u. We conclude that (2) has at most two solutions in this subcase.

Subcase 2.2. q ≡ 3(mod 4).

Note that λ^q = −λ^− 1 in this subcase. Similar to Subcase 2.1, there also exist y ∈ GF(q)^∗ and $z\in \mathbb {U}$ such that x = λyz. Then (2) becomes

$$y(\lambda^{-3}z^{-3}+2\lambda^{-1}z^{-1}+b\lambda z)=1-b.$$

(16)

Raising both sides of (16) into the power q, we have

$$y(-\lambda^{3}z^{3}-2\lambda z-b^{q}\lambda^{-1} z^{-1})=1-b^{q}.$$

(17)

The (16) and (17) lead to

$$(\lambda z+\lambda^{-1}z^{-1})\big((1-b)\lambda^{2}z^{2}+(1-b^{q+1})+ (1-b^{q})\lambda^{-2}z^{-2}\big)=0.$$

(18)

If λz + λ^− 1z^− 1 = 0, then λz = −λ^− 1z^− 1 = λ^qz^q, which means λz ∈ GF(q). We have x = λyz ∈ GF(q) and then b = 1, which is a contradiction. Thus we conclude that

$$(1-b)\lambda^{2}z^{2}+(1-b^{q+1})+(1-b^{q})\lambda^{-2}z^{-2}=0.$$

(19)

Let u = λ²z², (19) becomes

$$(1-b)u^{2}+(1-b^{q+1})u+(1-b^{q})=0,$$

(20)

which is a quadratic equation of u. Note that (14) and (20) are the same. There exist at most two u’s for a given b ≠ 1. Moreover, from (16) we obtain

$$x=\lambda yz=\frac{1-b}{b+2\lambda^{-2}z^{-2}+\lambda^{-4}z^{-4}}=\frac{1-b}{b+2u^{-1}+u^{-2}},$$

(21)

which means x is uniquely determined by u. Recall that x = λyz = λ(−y)(−z), z and − z correspond to the same u. We conclude that (2) has at most two solutions in this subcase (Table 2).

Table 2 Possible solutions of the (2) for a given b ≠ 1

In the following, we will show that δ(b) ≠ 4 for b ≠ 1. Otherwise, if δ(b) = 4, (2) has two square solutions and two nonsquare solutions. The square solutions are

$$x_{i}=\frac{1-b}{b-2u^{-1}_{i}+u^{-2}_{i}},i=1,2,$$

where u₁ and u₂ are the two roots of the quadratic (8). Moreover, it can be easily seen that the roots of (14) and (20) are − u₁ and − u₂. Then by (15) and (21), the nonsquare solutions of (2) are

$$\frac{1-b}{b+2(-u_{i})^{-1}+(-u_{i})^{-2}}=\frac{1-b}{b-2u^{-1}_{i}+u^{-2}_{i}}=x_{i}, i=1,2,$$

which is a contradiction. Hence, (2) cannot have four solutions, i.e., δ(b) = 0 or 2 for b≠ 1 since δ(b) is even. We complete the proof. □

By Lemma 3, the nonzero elements in the differential spectrum of F are ω₀, ω₂ and ω_q. We determine the differential spectrum of F in the following theorem.

Theorem 1

Let q be an odd prime power. Let F(x) = x^2q− 1 be a power mapping defined over GF(q²). The differential spectrum of F is given by

$$\mathbb{S}=\{\omega_{0}=\frac{q^{2}+q-2}2,\omega_{2}=\frac{q^{2}-q}2,\omega_{q}=1\}.$$

Proof

From Lemma 3 and (1), we obtain the following system of equations.

$$\begin{array}{@{}rcl@{}} \left\{ \begin{array}{lllllll} \omega_{0}&+&&\omega_{2}&+&&\omega_{q} = q^{2}, \\ &&2&\omega_{2}&+&q&\omega_{q} =q^{2},\\ &&&&&&\omega_{q}=1. \end{array} \right. \end{array}$$

Solving the previous system of equations, we obtain the differential spectrum of F.

By Theorem 1 and Lemma 1, one can immediately deduce the following corollary.

Corollary 1

Let q be an odd prime power and GF(q²) be the finite field with q² element. The number of solutions (x₁, x₂, x₃, x₄) ∈ (GF(q²))⁴ of the system of equations

$$\begin{array}{@{}rcl@{}} \left\{ \begin{array}{lllll} x_{1}-x_{2}+x_{3}-x_{4}&=&0,\\ {x^{d}_{1}}-{x^{d}_{2}}+{x^{d}_{3}}-{x^{d}_{4}}&=&0 \end{array} \right.\ \ \end{array}$$

is 4q⁴ − 2q³ − 3q² + 2q, where d = 2q − 1.

3 Concluding remarks

Let F(x) = x^2q− 1 be a power mapping over GF(q²), where 2q − 1 is a Niho exponent. When q is a power of 2, the differential spectrum of F was computed in [3]. In this paper, we studied the differential spectrum of F when q is an odd prime power. The differential spectrum of F was determined, and the number of solutions of a related system of equations followed. The application of the differential spectrum of F in sequence design, coding theory and combinatorial design is of great significance.