Differential spectrum of a class of APN power functions

Abstract

APN power functions are fundamental objects as they are used in various theoretical and practical applications in cryptography, coding theory, combinatorial design, and related topics. Let p be an odd prime and n be a positive integer. Let $F(x)=x^d$ be a power function over ${\mathbb {F}}_{p^n}$, where $d=\frac{3p^n-1}{4}$ when $p^n\equiv 3\pmod 8$ and $d=\frac{p^n+1}{4}$ when $p^n\equiv 7\pmod 8$. When $p^n>7$, F is an APN function, which is proved by Helleseth et al. (IEEE Trans Inform Theory 45(2):475–485, 1999). In this paper, we study the differential spectrum of F. By investigating some system of equations, the number of solutions of certain system of equations and consequently the differential spectrum of F can be expressed by quadratic character sums over ${\mathbb {F}}_{p^n}$. By the theory of elliptic curves over finite fields, the differential spectrum of F can be investigated by a given p. It is the fourth infinite family of APN power functions with nontrivial differential spectrum.

1 Introduction

Let ${\mathbb {F}}_{p^n}$ be the finite field with $p^n$ elements and ${\mathbb {F}}_{p^n}^*={\mathbb {F}}_{p^n}\setminus \{0\}$, where p is a prime number and n is a positive integer. Let F be a function from ${\mathbb {F}}_{p^n}$ to itself. The derivative function, denoted by $\mathbb {D}_aF$, of F at an element a in ${\mathbb {F}}_{p^n}$ is given by

$$\begin{aligned} \mathbb {D}_aF(x)=F(x+a)-F(x). \end{aligned}$$

Main tools to measure the ability of a function F to resist differential attack are the difference distribution table (DDT for short) and the differential uniformity of F [27]. For any $a\in {\mathbb {F}}_{p^n}^*,b \in {\mathbb {F}}_{p^n}$, the DDT entry at (a, b), denoted by $\delta _F(a,b)$, is defined as

$$\begin{aligned}\delta _F(a,b)=\big |\{x \in {\mathbb {F}}_{p^n}:\mathbb {D}_{a}F(x)=b\}\big |,\end{aligned}$$

where |S| denotes the cardinality of a set S. The differential uniformity of the function F, denoted by $\varDelta _F$, is defined as

$$\begin{aligned}\varDelta _F=\max \limits _{a \in {\mathbb {F}}_{p^n}^*}\max \limits _{b \in {\mathbb {F}}_{p^n}} \delta _F(a,b).\end{aligned}$$

A function F is said to be differentially $\delta$-uniform if and only if $\varDelta _F=\delta$, and $\delta$ is called the differential uniformity of F (see e.g. [27]). When F is used as an S-box inside a cryptosystem, the smaller the value $\varDelta _F$ is, the better the contribution of F to the resistance against differential attack. A survey on the differential uniformity of vectorial Boolean functions can be found in [10] (Chapter 8 by Carlet) and the recent book [11]. When $\varDelta _{F}=1$, F is called planar or perfect nonlinear (PN for short) function. Note that PN functions over even characteristic finite fields do not exist. When $\varDelta _F=2$, F is called an almost perfect nonlinear (APN for short) function. APN functions are not only important in cryptography, but also in coding theory, projective geometry and theory of commutative semifields. Recent progress on PN and APN functions can be found in [1, 5,6,7,8,9, 13,14,15,16,17, 19, 20, 27, 29, 40,41,43].

Power mappings with low differential uniformity serve as good candidates for the design of S-boxes because of their strong resistance to differential attacks and the usually low implementation cost in hardware. When F is a power mapping, i.e., $F(x)=x^d$ for an integer d, one can easily see that $\delta _F(a,b)=\delta _F(1,{b/{a^d}})$ for all $a\in {\mathbb {F}}_{p^n}^*$ and $b\in {\mathbb {F}}_{p^n}$. That is to say, the differential properties of F is completely determined by the values of $\delta _F(1,b)$ as b runs through ${\mathbb {F}}_{p^n}$. The definition of the differential spectrum of a power function was proposed as follows.

Definition 1

[3] Assume that a power function $F(x)=x^d$ over ${\mathbb {F}}_{p^n}$ has differential uniformity $\varDelta _F$ and denote

$$\begin{aligned} \omega _i=\big |\left\{ b\in {\mathbb {F}}_{p^n}:\delta _F(1, b)=i\right\} \big |,\,\,0\le i\le \varDelta _F. \end{aligned}$$

The differential spectrum of F is defined to be the multiset

$$\begin{aligned} DS_F=\{\omega _{i}:\omega _{i}>0,\ 0\le i \le \varDelta _{F}\}. \end{aligned}$$

The study of differential spectrum (and their connection to Walsh spectrum) can be traced backed to [18] by Dobbertin et al. Moreover, it has been shown in [3] that the elements in the differential spectrum of F satisfy

$$\begin{aligned} \sum _{i=0}^{\varDelta _{F}}\omega _{i}=\sum _{i=0}^{\varDelta _{F}}(i\cdot \omega _{i})=p^n. \end{aligned}$$

(1)

The identities in (1) are very useful to compute the differential spectrum of F. In the following three cases, the differential spectrum of the power function can be obtained from (1) directly.

• (1) When F is PN, the differential spectrum of F is $DS_F=\{\omega _1=p^n\}$.

• (2) When F is APN over ${\mathbb {F}}_{{2^{n}}}$, the differential spectrum of F is $DS_F=\{\omega _0=2^{n-1}, \omega _2=2^{n-1}\}$.

• (3) When $F(x)=x^d$ is APN over ${\mathbb {F}}_{{p^{n}}}$, where d is odd and p is an odd prime, the differential spectrum of F is $DS_F=\{\omega _0=\frac{p^n-1}{2}, \omega _1=1, \omega _2=\frac{p^n-1}{2}\}$.

If the differential spectrum of the power function is one of the above three categories, then we call that the differential spectrum of this power function is trivial. Otherwise, its differential spectrum is nontrivial. To determine the nontrivial differential spectrum of the power function $F(x)=x^d$ over ${\mathbb {F}}_{{p^{n}}}$ with differential uniformity $\varDelta _F$, the following lemma plays a crucial role, which is established in [21].

Lemma 1

[21, Theorem 10] With the notation introduced in Definition 1, let $N_4$ denote the number of solutions $(x_1,x_2,x_3,x_4)\in ({\mathbb {F}}_{p^n})^4$ of the following system of equations

$$\begin{aligned} \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{aligned}$$

(2)

Then we have

$$\begin{aligned} \sum _{i=0}^{\varDelta _F}(i^2\cdot \omega _i)=\frac{N_4-p^{2n}}{p^n-1}. \end{aligned}$$

(3)

For the convenience, we give a short proof here. Let $n(\alpha ,\beta )=\#\{(x,y)\in ({\mathbb {F}}_{p^n})^2: x-y=\alpha ~\textrm{and}~ x^d-y^d=\beta \}$. Then $n(0,0)=p^n$, and $n(0,\beta )=0$ for $\beta \ne 0$. Moreover, for a fixed $\alpha \ne 0$, $n(\alpha ,\beta )=n(1,\frac{\beta }{\alpha ^d})$. When $\beta$ runs through ${\mathbb {F}}_{p^n}$, so does $\frac{\beta }{\alpha ^d}$. By the definitions of $\delta _F(1,b)$ and $\omega _i$, we have

$$\begin{aligned} N_4&=\sum _{\alpha ,\beta \in {\mathbb {F}}_{p^n}}(n(\alpha ,\beta ))^2\\&=(n(0,0))^2+\sum _{\alpha \in {\mathbb {F}}_{p^n}^*}\sum _{\beta \in {\mathbb {F}}_{p^n}}(n(\alpha ,\beta ))^2\\&=p^{2n}+\sum _{\alpha \in {\mathbb {F}}_{p^n}^*}\sum _{\beta \in {\mathbb {F}}_{p^n}}(n(1,\frac{\beta }{\alpha ^d}))^2\\&=p^{2n}+\sum _{\alpha \in {\mathbb {F}}_{p^n}^*}\sum _{b\in {\mathbb {F}}_{p^n}}(n(1,b))^2\\&=p^{2n}+(p^n-1)\sum _{b\in {\mathbb {F}}_{p^n}}(\delta _F(1,b))^2\\&=p^{2n}+(p^n-1)\sum _{i=0}^{\varDelta _F}(i^2\cdot \omega _{i}). \end{aligned}$$

The desired result follows.

Table 1 Known power function $F(x)=x^d$ over ${\mathbb {F}}_{p^n}$ with nontrivial differential spectrum

The identity (3) gives the third relationship between the elements in the differential spectrum. If a power function’s differential spectrum has three nonzero elements, we can solve it by (1) and (3). In addition, if the differential spectrum of $F(x)=x^d$ is given, the number of solutions of the system of equations (2) follows, which plays a significant role in calculating the cross-correlation distribution of sequences and the weight distribution of codes. Therefore, it is an interesting topic to completely determine the differential spectrum of a power function with low differential uniformity. However, it is challenging to determine a power function’s differential spectrum ultimately. The known classes of power functions with nontrivial differential spectra are listed in Table 1.

Let us focus on APN functions. When p is an odd prime and d is even, APN power function $F(x)=x^d$ over ${\mathbb {F}}_{p^n}$ is the power function with the lowest differential uniformity and nontrivial differential spectrum. As far as we know, there are only three infinite families of APN power function $x^d$ over ${\mathbb {F}}_{p^n}$ have nontrivial differential spectra. The first one is $x^{d}$ over ${\mathbb {F}}_{3^n}$, where n is odd, $\gcd (n,k)=1$ and $d(3^k+1)\equiv 2\pmod {3^n-1}$, which is reported by [12] ($k=1$) and [30] (a general k), respectively. In 2020, Xia et al. determined the differential spectrum of the power function $x^{3^n-3}$ over ${\mathbb {F}}_{3^n}$ in [31], which is APN when n is odd. In [20], Helleseth et al. showed that $x^{\frac{p^n-3}{2}}$ is APN if $p^n>7$, $p^n\ne 27$ and 5 is a nonsquare in ${\mathbb {F}}_{p^n}$. The differential spectrum of this family of power functions was determined by Yan et al. recently [38].

Throughout this paper, let $F(x)=x^d$ be a power function over ${\mathbb {F}}_{p^n}$, where p is an odd prime and

$$\begin{aligned} d=\left\{ \begin{array}{ll} \frac{3p^n-1}{4},&{}\quad \textrm{if}~p^n \equiv 3 (\textrm{mod}~8), \\ \frac{p^n+1}{4},&{}\quad \textrm{if}~p^n \equiv 7 (\textrm{mod}~8) \end{array} \right. \ \ \end{aligned}$$

(4)

is an even integer. It was proved in [21] that F is an APN function when $p^n>7$. We mainly study the differential spectrum of F in this paper. When $p=3$, F becomes $x^{\frac{3^{n+1}-1}{4}}$, whose differential spectrum was investigated in [12]. Hence, keeping the above notation, we always assume that $p\ne 3$. By investigating some system of equations and certain character sums over ${\mathbb {F}}_{p^n}$, the differential spectrum of F is expressed by character sums. The rest of this paper is organized as follows. In Sect. 2, we introduce the basic concept of quadratic multiplicative character sums. Some results on two specific quadratic multiplicative character sums are also given in this section, which will be employed in the sequel. We investigate the number of solutions of certain systems of equations in Sect. 3. The differential spectrum of F is determined in Sect. 4, some examples are also given. Section 5 concludes this paper.

2 On quadratic character sums

In this section, we mainly introduce some basic results on quadratic multiplicative character sums. Let ${\mathbb {F}}_{p^n}$ be the finite field with $p^n$ elements, where p is an odd prime and n is a positive integer. And let ${\mathbb {F}}_{p^n}^{*}={\mathbb {F}}_{p^n}\setminus \{0\}$. Let $\chi$ denote the quadratic multiplicative character over ${\mathbb {F}}_{p^n}$, i.e.,

$$\begin{aligned} \chi (x):=x^{\frac{p^{n}-1}{2}}=\left\{ \begin{array}{ll} 1,&{}\quad \hbox {if }\,x \, \hbox {is a square,}\\ 0, &{}\quad \hbox {if}\, x=0,\\ -1,&{}\quad \hbox {if}\, x \,\hbox {is a nonsquare.} \end{array}\right. \end{aligned}$$

The quadratic multiplicative character $\chi (\cdot )$ will appear naturally in our study of the differential spectrum of the function $F(x)=x^d$ over the finite field ${\mathbb {F}}_{p^n}$, where d is defined in (4).

Let ${\mathbb {F}}_{{p^{n}}}[x]$ be the polynomial ring over ${\mathbb {F}}_{{p^{n}}}$. We consider the sum involving the quadratic multiplicative character sums of the form

$$\begin{aligned} \sum _{x\in {\mathbb {F}}_{{p^{n}}}}\chi (f(x)) \end{aligned}$$

with $f(x)\in {\mathbb {F}}_{{p^{n}}}[x]$. The case of $\deg (f(x))=1$ is trivial, since the number of squares and nonsquares in ${\mathbb {F}}_{{p^{n}}}^*$ are both $\frac{p^n-1}{2}$. For $\deg (f(x))=2$, let $f(x)=a_{2}x^{2}+a_{1}x+a_{0}$, $a_2\ne 0$ and $\varDelta =a_{1}^{2}-4a_{0}a_{2}$, then the following explicit formula

$$\begin{aligned} \sum _{x\in {\mathbb {F}}_{{p^{n}}}}\chi (f(x))=\left\{ \begin{array}{ll} -\chi (a_{2}), &{} \hbox {if }\,\varDelta \ne 0,\\ (p^{n}-1)\chi (a_{2}), &{} \hbox {if }\,\varDelta =0 \end{array}\right. \end{aligned}$$

(5)

was established in [25].

For $\deg (f(x))\ge 3$, it is challenging to derive an explicit and general formula for the character sum $\sum \limits _{x\in {\mathbb {F}}_{p^{n}}}\chi (f(x))$. However, when $\deg (f(x))=3$, such a sum can be computed by considering ${\mathbb {F}}_{p^{n}}$-rational points of elliptic curves over ${\mathbb {F}}_{p}$ [28]. More specifically, we denote $\varGamma _{p,n}$ as

$$\begin{aligned} \varGamma _{p,n}=\sum _{x\in {\mathbb {F}}_{p^{n}}}\chi (f(x)). \end{aligned}$$

To evaluate $\varGamma _{p,n}$, we shall use some elementary concepts from the theory of elliptic curves. Most of the terminologies and notation we use come from [28]. Let $E/{\mathbb {F}}_{p}$ be the elliptic curve over ${\mathbb {F}}_{p}$:

$$\begin{aligned} E:y^{2}=f(x). \end{aligned}$$

Let $N_{p,n}$ denote the number of ${\mathbb {F}}_{p^{n}}$-rational points (remember the extra point at infinity) on the curve $E/{\mathbb {F}}_{p}$. From Sect. 1.3 in [28, p. 139, Chap. V], and [28, Theorem 2.3.1, p. 142, Chap. V], $N_{p,n}$ can be computed from $\varGamma _{p,n}$. More precisely, for every $n\ge 1$,

$$\begin{aligned} N_{p,n}=p^n+1+\varGamma _{p,n}. \end{aligned}$$

Moreover,

$$\begin{aligned} \varGamma _{p,n}=-\alpha ^{n}-\beta ^{n}, \end{aligned}$$

where $\alpha$ and $\beta$ are the complex solutions of the quadratic equation $T^{2}+\varGamma _{p,1}T+p=0$. Although it is hard to give an explicit formula of $\varGamma _{p,n}$, $\varGamma _{p,n}$ can be determined by $\varGamma _{p,1}$ directly. More precisely, we have

$$\begin{aligned} \varGamma _{p,\,n}=\frac{(-1)^{n+1}}{2^{n-1}}\sum _{k=0}^{\lfloor \frac{n}{2}\rfloor }(-1)^k\left( {\begin{array}{c}n\\ 2k\end{array}}\right) (\varGamma _{p,\,1})^{n-2k}(4p-(\varGamma _{p,\,1})^2)^k. \end{aligned}$$

(6)

When $\varGamma _{p,1}=0$, (6) becomes

$$\begin{aligned} \varGamma _{p,\,n}=\left\{ \begin{array}{ll} (-1)^{\frac{n}{2}+1}\cdot 2\cdot {p}^{\frac{n}{2}},&{}\quad ~n~ \textrm{is}~\textrm{even},\\ 0,&{}\quad ~n~ \textrm{is}~\textrm{odd}. \end{array}\right. \end{aligned}$$

(7)

Now we define

$$\begin{aligned} \varGamma ^{(1)}_{p,n}=\sum _{x\in {\mathbb {F}}_{p^{n}}}\chi (x(x+1)(x-3)) \end{aligned}$$

(8)

and

$$\begin{aligned} \varGamma ^{(2)}_{p,n}=\sum _{x\in {\mathbb {F}}_{p^{n}}}\chi (x(x+1)(x-2)). \end{aligned}$$

(9)

These two specific character sums play an important role in our main result. In the following examples, we give the exact values of $\varGamma ^{(1)}_{p,n}$ and $\varGamma ^{(2)}_{p,n}$, respectively, over prime fields (for specific values of p).

Example 1

Let $p=7$. For $n=1$, one has $\varGamma ^{(1)}_{7,1}=0$. From (7), we have

$$\begin{aligned} \varGamma ^{(1)}_{7,n}&=\left\{ \begin{array}{ll} (-1)^{\frac{n}{2}+1}\cdot 2\cdot {7}^{\frac{n}{2}},&{}\quad ~{n}~ \textrm{is}~\textrm{even},\\ 0,&{}\quad ~{n}~ \textrm{is}~\textrm{odd}. \end{array}\right. \end{aligned}$$

Example 2

Let $p=11$. For $n=1$, we have $\varGamma ^{(2)}_{11,1}=4$. From (6), we obtain

$$\begin{aligned} \varGamma ^{(2)}_{11,n}&=(-1)^{n+1}\cdot \sum \limits _{k = 0}^{\left\lfloor {\frac{n}{2}} \right\rfloor } {{{\left( { - 1} \right) }^{k}} \left( {\begin{array}{c}n\\ 2k\end{array}}\right) {2^{n-2k+1}}\cdot {7^{k}}}. \end{aligned}$$

According to [39], we list the following lemma which will be applied to Theorem 1 of this article.

Lemma 2

[39, Lemma 5] Let $\varGamma _{p,n}^{(1)}$ and $\varGamma _{p,n}^{(2)}$ be character sums we defined before. When $p^n \equiv 3\pmod 4$, we have

$$\begin{aligned} (1)&\sum _{x\in {\mathbb {F}}_{p^{n}}}\chi (x(x^2+x+1))=\varGamma ^{(1)}_{p,n},\\ (2)&\sum _{x\in {\mathbb {F}}_{p^{n}}}\chi ((x+1)(x^2+x+1))=-\varGamma ^{(1)}_{p,n},\\ (3)&\sum _{x\in {\mathbb {F}}_{{p^{n}}}}\chi ((x^2+x)(x^2+x+1))=-\varGamma ^{(1)}_{p,n}-1. \end{aligned}$$

Moreover, when $p^n \equiv 3\pmod 4$ and $p\ne 3$, we have

$$\begin{aligned} (4)&\sum _{x\in {\mathbb {F}}_{p^{n}}}\chi (x(3x^2+2x+3))=\varGamma ^{(2)}_{p,n},\\ (5)&\sum _{x\in {\mathbb {F}}_{{p^{n}}}}\chi ((x^2+x+1)(3x^2+2x+3))=\varGamma ^{(2)}_{p,n}-\chi (3),\\ (6)&\sum _{x\in {\mathbb {F}}_{p^{n}}}\chi (x(x^2+x+1)(3x^2+2x+3))=-2\varGamma ^{(1)}_{p,n}. \end{aligned}$$

3 The number of solutions of certain systems of equations

In this section, we aim to determine the number of solutions in $({\mathbb {F}}_{p^n}^*)^3$ of the following system of equations (10), which will be used in determining the differential spectrum of F.

Theorem 1

Denote by $n_4$ the number of solutions $(y_1,y_2,y_3)\in ({\mathbb {F}}_{p^n}^*)^3$ of the following system of equations

$$\begin{aligned} \left\{ \begin{array}{lllll} y_1-y_2+y_3-1 &{}=&{}0\\ y_1^d-y^d_2+y^d_3-1 &{}=&{}0, \end{array} \right. \ \ \end{aligned}$$

(10)

where d is defined in (4) and $p\ne 3$. We have

$$\begin{aligned} n_4=\frac{1}{8}(21p^n-\varGamma ^{(1)}_{p,n}+2\varGamma ^{(2)}_{p,n}-51), \end{aligned}$$

where $\varGamma ^{(1)}_{p,n}$ and $\varGamma ^{(2)}_{p,n}$ are defined in (8) and (9), respectively.

Proof

We denote by $n_{(i,j,k)}$ the number of solutions $(y_1,y_2,y_3)\in ({\mathbb {F}}_{p^n}^*)^3$ of (10) with $(\chi (y_1), \chi (y_2), \chi (y_3))=(i,j,k)$, where $i,j,k\in \{\pm 1\}$. By Proposition 5 in [38], we know that $n_{(1,1,-1)}=n_{(1,-1,1)}=n_{(-1,1,1)}=n_{(-1,-1,-1)}$ and $n_{(1,-1,-1)}=n_{(-1,-1,1)}$. Then

$$\begin{aligned} n_4=n_{(1,1,1)}+4n_{(1,1,-1)}+2n_{(1,-1,-1)}+n_{(-1,1,-1)}. \end{aligned}$$

(11)

For each $y_i\in {\mathbb {F}}_{p^n}^*$, $y_i/\chi (y_i)$ is a square since $\chi (-1)=-1$. Then there exist a unique element, namely $z_i$, such that $y_i=\chi (y_i)z^2_i$ and $\chi (z_i)=1$. Consequently,

$$\begin{aligned}y^d_i=z^{2d}_i=\chi (z_i)z_i=z_i\end{aligned}$$

since d is even and $2d\equiv \frac{p^n-1}{2}+1 (\textrm{mod}~(p^n-1))$. We discuss (10) in the following cases.

Case 1 $(\chi (y_1),\chi (y_2), \chi (y_3))=(1,1,1)$. Then there exist $z_1,z_2$ and $z_3$ such that $y_i=z^2_i$ and $\chi (z_i)=1$, where $i=1,2,3$. (10) becomes

$$\begin{aligned} \left\{ \begin{array}{lllll} z^2_1-z^2_2+z^2_3-1 &{}=&{}0\\ z_1-z_2+z_3-1 &{}=&{}0. \end{array} \right. \ \ \end{aligned}$$

(12)

Next we determine $n_{(1,1,1)}$. If $z_3=1$, then $z_2=z_1$, hence $(z_1, z_1, 1)$ is a solution of (12) when $z_1$ is a square element. If $z_3\ne 1$, then $z_1\ne z_2$, moreover,

$$\begin{aligned} z_1+z_2=(z^2_1-z^2_2)(z_1-z_2)^{-1}=z_3+1. \end{aligned}$$

We obtain $z_1=1$ and $z_2=z_3$. Then (12) has solutions with type $(1,z_3,z_3)$, where $\chi (z_3)=1$ and $z_3\ne 1$. We have, $n_{(1,1,1)}=2\cdot \frac{p^n-1}{2}-1=p^n-2$.

Case 2 $(\chi (y_1),\chi (y_2), \chi (y_3))=(1,1,-1)$. Then there exist $z_1,z_2$ and $z_3$ such that $y_1=z^2_1$, $y_2=z^2_2$, $y_3=-z^2_3$ and $\chi (z_i)=1$, where $i=1,2,3$. Then (10) becomes

$$\begin{aligned} \left\{ \begin{array}{lllll} z^2_1-z^2_2-z^2_3-1&{}=&{}0\\ z_1-z_2+z_3-1&{}=&{}0. \end{array} \right. \ \ \end{aligned}$$

(13)

Next we determine $n_{(1,1,-1)}$. Note that $z_3\ne 1$. Therefore we can divide by $z_3-1$ and obtain $z_1-z_2=-(z_3-1)$ and $z_1+z_2=-\frac{z^2_3+1}{z_3-1}$. Then $z_1=-\frac{z^2_3-z_3+1}{z_3-1}$ and $z_2=-\frac{z_3}{z_3-1}$. If $(z_1, z_2, z_3)$ is a solution of (13) with $\chi (z_i)=1$ ($i=1,2,3$), we conclude that $\chi (z_3-1)=-1$ and $\chi (z^2_3-z_3+1)=1$. We have,

$$\begin{aligned} n_{(1,1,-1)}&=\#\{z_3\in {\mathbb {F}}_{{p^{n}}}\setminus \{1\}: \chi \left( -\frac{z^2_3-z_3+1}{z_3-1}\right) =\chi \left( -\frac{z_3}{z_3-1}\right) =\chi (z_3)=1\}\\&=\#\{z_3\in {\mathbb {F}}_{{p^{n}}}:\chi (z_3)=1, \chi (z_3-1)=-1, \chi (z^2_3-z_3+1)=1 \}\\&=\frac{1}{8}\sum _{\begin{array}{c} z_3\ne 0,1,\\ z^2_3-z_3+1\ne 0 \end{array}}\big ((1+\chi (z_3))(1-\chi (z_3-1))(1+\chi (z^2_3-z_3+1))\big )\nonumber \\&=\frac{1}{8}\left( \sum _{z_3\in {\mathbb {F}}_{p^n}}-\sum _{z_3=0}-\sum _{z_3=1}-\sum _{z^2_3-z_3+1=0}\right) \Bigg ((1+\chi (z_3))\left( 1-\chi \left( z_3-1\right) \right) \nonumber \\&\quad \cdot (1+\chi (z^2_3-z_3+1))\big )\nonumber \\&=-1+\frac{1}{8}\sum _{z_3\in {\mathbb {F}}_{p^n}}\big ((1+\chi (z_3))(1-\chi (z_3-1))(1+\chi (z^2_3-z_3+1))\big ). \end{aligned}$$

The above identities hold since if $z_{3}^{2}-z_{3}+1=0$, then $z_3\ne 0, 1$ and $z_3$ satisfies $\chi (z_3)=\chi (-(z_3-1)^2)=-1$ and $\chi (z_3-1)=\chi (z^2_3)=1$. Hence $\sum _{z_{3}^2-z_{3}+1=0}\big ((1+\chi (z_3))(1-\chi (z_3-1))(1+\chi (z^2_3-z_3+1))\big )=0$. By Lemma 2 and (5), we have

$$\begin{aligned} n_{(1,1,-1)}&= -1+\frac{1}{8}\sum _{z_3\in {\mathbb {F}}_{p^n}}\big ((1+\chi (z_3))(1-\chi (z_3-1))(1+\chi (z^2_3-z_3+1))\big )\nonumber \\&=-1+\frac{1}{8}\sum _{z_3\in {\mathbb {F}}_{p^n}}\big ((1-\chi (z_3))(1+\chi (z_3+1))(1+\chi (z^2_3+z_3+1))\big )\nonumber \\&=-1+\frac{1}{8}\sum _{z_{3}\in {\mathbb {F}}_{p^n}}[1-\chi (z_3)+\chi (z_{3}+1)+\chi (z^2_3+z_3+1)\nonumber \\&\quad -\chi (z_3(z_3-1))-\chi (z_3(z^2_3+z_3+1))+\chi ((z_3+1)\nonumber \\&\quad \cdot (z^2_3+z_3+1))-\chi (z_3(z_3+1)(z^2_3+z_3+1))] \nonumber \\&=\frac{1}{8}(p^n-\varGamma ^{(1)}_{p,n}-7). \end{aligned}$$

Case 3 $(\chi (y_1),\chi (y_2), \chi (y_3))=(1,-1,-1)$. Then there exist $z_1,z_2$ and $z_3$ such that $y_1=z^2_1$, $y_2=-z^2_2$, $y_3=-z^2_3$ and $\chi (z_i)=1$, where $i=1,2,3$. Then (10) becomes

$$\begin{aligned} \left\{ \begin{array}{lllll} z^2_1+z^2_2-z^2_3-1 &{}=&{}0\\ z_1-z_2+z_3-1 &{}=&{}0. \end{array} \right. \ \ \end{aligned}$$

(14)

Next we determine $n_{(1,-1,-1)}$. If $z_1=1$, then $z_3=z_2$, hence $(1, z_2, z_2)$ is a solution of (14) when $\chi (z_2)=1$. If $z_1\ne 1$, then $z_3\ne z_2$, moreover,

$$\begin{aligned}z_2+z_3=\left( z^2_2-z^2_3\right) \left( z_2-z_3\right) ^{-1}=-z_1-1.\end{aligned}$$

Then we obtain $z_2=-1$, which is a contradiction. We conclude that $n_{(1,-1,-1)}=\frac{p^n-1}{2}$.

Case 4 $(\chi (y_1),\chi (y_2), \chi (y_3))=(-1,1,-1)$. Then there exist $z_1,z_2$ and $z_3$ such that $y_1=-z^2_1$, $y_2=z^2_2$, $y_3=-z^2_3$ and $\chi (z_i)=1$, where $i=1,2,3$. Then (10) becomes

$$\begin{aligned} \left\{ \begin{array}{lllll} -z^2_1-z^2_2-z^2_3-1 &{}=&{}0\\ z_1-z_2+z_3-1 &{}=&{}0. \end{array} \right. \ \ \end{aligned}$$

(15)

From (15), we obtain $z_1-z_2=-z_3+1$ and

$$\begin{aligned} -z_1z_2=\frac{1}{2}\left( \left( z_1-z_2\right) ^2-\left( z^2_1+z^2_2\right) \right) =z^2_3-z_3+1. \end{aligned}$$

We know that $z_1$ and $-z_2$ are the two nonzero solutions of the following quadratic equation on the variable t.

$$\begin{aligned} t^2+(z_{3}-1)t+z^2_3-z_3+1=0. \end{aligned}$$

(16)

The discriminant of (16) is $\varDelta =-3z^2_3+2z_3-3$. On one hand, if (15) has a solution $(z_1,z_2,z_3)$ with $\chi (z_i)=1$ for $i=1,2,3$, then $\chi (\varDelta )=1$ ($z_1\ne -z_2$) and $\chi (-z_1z_2)=\chi (z^2_3-z_3+1)=-1$. One the other hand, if $\chi (\varDelta )=1$ and $\chi (z^2_3-z_3+1)=-1$ for some $z_3$ with $\chi (z_3)=1$, then (16) has two distinct nonzero solutions and their product is a nonsquare. We assert that one of the two solutions is a square and the other is a nonsquare, the square solution is $z_1$ while the nonsquare solution is $-z_2$. We obtain

$$\begin{aligned} n_{(-1,1,-1)}&=\#\{z_3\in {\mathbb {F}}_{p^n}:\chi (z_3)=1, \chi (-3z^2_3+2z_3-3)=1, \chi (z^2_3-z_3+1)=-1\}\\&=\#\{z_3\in {\mathbb {F}}_{p^n}:\chi (z_3)=1, \chi (3z^2_3-2z_3+3)=-1, \chi (z^2_3-z_3+1)=-1\}. \end{aligned}$$

Then

$$\begin{aligned} n_{(-1,1,-1)}&=\frac{1}{8}\sum _{\begin{array}{c} z_3\ne 0,\\ 3z^2_3-2z_3+3\ne 0,\\ z^2_3-z_3+1\ne 0\\ \end{array}}\big ((1+\chi (z_{3}))(1-\chi (3z^2_3-2z_3+3))\nonumber \\&\quad \cdot (1-\chi (z^2_3-z_3+1))\big ). \end{aligned}$$

Note that when $3z^2_3-2z_3+3$ and $z^2_3-z_3+1$ can not be 0 simultaneously. For each $z_3$ satisfied $3z^2_3-2z_3+3=0$, we have $z_3\ne 1$ and $-4z_3=3(z_3-1)^2$, then $\chi (z_3)=-\chi (3)$. Moreover, $z^2_3-z_3+1=\frac{1}{3}(3z^2_3-2z_3+3)-\frac{1}{3}z_3$, then $\chi (z^2_3-z_3+1)=\chi (-\frac{1}{3}z_3)=\chi (-\frac{1}{3})\chi (z_3)=1$. Consequently,

$$\begin{aligned}\sum _{3z^2_3-2z_3+3=0}\big ((1+\chi (z_{3}))(1-\chi (3z^2_3-2z_3+3))(1-\chi (z^2_3-z_3+1))\big )=0.\end{aligned}$$

Similarly, when $z^2_3-z_3+1=0$, we have $z_3\ne -1$ and $z_3=\frac{1}{3}(z_3+1)^2$. Then $\chi (z_3)=\chi (3)$, $\chi (3z^2_3-2z_3+3)=\chi (z_3)=1$. We obtain

$$\begin{aligned}\sum _{z^2_3-z_3+1=0}\big ((1+\chi (z_{3}))(1-\chi (3z^2_3-2z_3+3))(1-\chi (z^2_3-z_3+1))\big )=0.\end{aligned}$$

Hence

$$\begin{aligned}n_{(-1,1,-1)}=\frac{1}{8}\sum _{{z_{3}\in {\mathbb {F}}_{p^n}}}\big ((1+\chi (z_{3}))(1-\chi (3z^2_3-2z_3+3))(1-\chi (z^2_3-z_3+1))\big ).\end{aligned}$$

By Lemma 2 and (5), we have

$$\begin{aligned} n_{(-1,1,-1)}&= \frac{1}{8}\sum _{{z_{3}\in {\mathbb {F}}_{p^n}}}\big ((1+\chi (z_{3}))(1-\chi (3z^2_3-2z_3+3))(1-\chi (z^2_3-z_3+1))\big )\nonumber \\&= \frac{1}{8}\sum _{{z_{3}\in {\mathbb {F}}_{p^n}}}\big ((1-\chi (z_{3}))(1-\chi (3z^2_3+2z_3+3))(1-\chi (z^2_3+z_3+1))\big )\nonumber \\&=\frac{1}{8}\sum _{z_{3}\in {\mathbb {F}}_{p^n}}[1-\chi (z_3)-\chi (3z^2_3+2z_3+3)-\chi (z^2_3+z_3+1)\nonumber \\&\quad +\chi (z_3(3z^2_3+2z_3+3))+\chi (z_3(z^2_3+z_3+1))+\chi ((3z^2_3+2z_3+3)\nonumber \\&\quad \cdot (z^2_3+z_3+1))-\chi (z_3(3z^2_3+2z_3+3)(z^2_3+z_3+1))] \nonumber \\&=\frac{1}{8}\left( p^n+3\varGamma ^{(1)}_{p,n}+2\varGamma ^{(2)}_{p,n}+1\right) . \end{aligned}$$

By (11), the desired result follows. This completes the proof.

$\square$

4 The differential spectrum of F

In this section, we shall focus on studying the differential spectrum of the power function F. Recall that $\delta _F(1,b)=\{x\in {\mathbb {F}}_{p^n}:F(x+1)-F(x)=b\}$, we have the following lemma on $\delta _F(1,1)$.

Lemma 3

The equation $(x+1)^d-x^d=1$ has only one solution $x=0$ in ${\mathbb {F}}_{p^n}$, i.e., $\delta _F(1,1)=1$.

Proof

We consider

$$\begin{aligned} (x+1)^d-x^d=1. \end{aligned}$$

(17)

It is easy to see that $x=0$ is a solution of (17) and $x=-1$ is not a solution of (17) since d is even. For $x\ne 0$ and $x\ne -1$, we discuss in the following four cases.

Case 1 $(\chi (x+1),\chi (x))=(1,1)$. Let $x+1=u^2$ and $x=v^2$ for some $u,v\in {\mathbb {F}}_{p^n}^*$ with $\chi (u)=\chi (v)=1$. Since $\chi (-1)=-1$, such u and v are uniquely determined by $x+1$ and x, respectively. We obtain $u^2-v^2=1$. Moreover, since $2d\equiv \frac{p^n-1}{2}+1\pmod {(p^n-1)}$, (17) becomes $u^{2d}-v^{2d}=\chi (u)u-\chi (v)v=u-v=1$. We obtain $u+v=1$ and then $v=0$, which is a contradiction. Hence (17) has no solution in this case.

Case 2 $(\chi (x+1),\chi (x))=(1,-1)$. Let $x+1=u^2$ and $x=-v^2$ for some $u,v\in {\mathbb {F}}_{p^n}^*$ with $\chi (u)=\chi (v)=1$. Then $u^2+v^2=1$ and (17) becomes $u-v=1$. We obtain $2uv=u^2+v^2-(u-v)^2=0$, which is a contradiction. Hence (17) has no solution in this case.

Case 3 $(\chi (x+1),\chi (x))=(-1,1)$. Let $x+1=-u^2$ and $x=v^2$ for some $u,v\in {\mathbb {F}}_{p^n}^*$ with $\chi (u)=\chi (v)=1$. Then $u^2+v^2=-1$ and (17) becomes $u-v=1$. We obtain $uv=\frac{1}{2}(u^2+v^2-(u-v)^2)=-1$, which contradicts to $\chi (uv)=\chi (u)\chi (v)=1$. Hence (17) has no solution in this case.

Case 4 $(\chi (x+1),\chi (x))=(-1,-1)$. Let $x+1=-u^2$ and $x=-v^2$ for some $u,v\in {\mathbb {F}}_{p^n}^*$ with $\chi (u)=\chi (v)=1$. Then $u^2-v^2=-1$ and (17) becomes $u-v=1$. We obtain $u+v=-1$ and then $u=0$. Hence (17) has no solution in this case.

By discussions as above, we conclude that $x=0$ is the unique solution of (17) and therefore $\delta _F(1,1)=1$. $\square$

Recall that $N_4$ denotes the number of solutions in $({\mathbb {F}}_{p^n})^4$ of the system of equations

$$\begin{aligned} \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{aligned}$$

(18)

Since F is APN, there are at most three nonzero elements $\omega _0$, $\omega _1$ and $\omega _2$ in its differential spectrum. To determine the differential spectrum of F, it is sufficient to determine $N_4$. And the value of $\delta _F(1,1)$ will help determine the number of solutions of the specific system of equations (18) in the following main result.

Theorem 2

Let $p\ne 3$, we have $N_4=1+\frac{1}{8}(p^n-1)(21p^n-\varGamma ^{(1)}_{p,n}+2\varGamma ^{(2)}_{p,n}-19)$, where $\varGamma _{p,n}^{(1)}$ and $\varGamma _{p,n}^{(2)}$ are defined in (8) and (9), respectively.

Proof

For a solution $(x_1,x_2,x_3,x_4)$ of (18), first we consider that there exists $x_i=0$ for some $1\le i\le 4$. It is easy to see that (0, 0, 0, 0) is a solution of (18), and (18) has no further solution containing only three zeros. If there are only two zeros in $(x_1,x_2,x_3,x_4)$, we can easily obtain that the solutions are $(x_0,x_0,0,0)$, $(0,0,x_0,x_0)$, $(x_0,0,0,x_0)$ and $(0,x_0,x_0,0)$, where $x_0\in {\mathbb {F}}_{p^n}^*$. Then (18) has $4(p^n-1)$ solutions containing exactly two zeros. If there is only one zero in $(x_1,x_2,x_3,x_4)$, without loss of generality, we assume that $x_4=0$, then $x_1,x_2$ and $x_3$ satisfy $x_1-x_2+x_3=0$ and $x^d_1-x^d_2+x^d_3=0$. Let $y_i=\frac{x_i}{x_3}$ for $i=1,2$, we have $y_1-y_2+1=0$ and $y^d_1-y^d_2+1=0$ with $y_1,y_2\ne 0$. Then $y_2=-y_1-1$ and $(y_1+1)^d-y^d_1=1$. By Lemma 3, we know that equation $(y_1+1)^d-y^d_1=1$ has only one solution $y_1=0$ in ${\mathbb {F}}_{p^n}$. Then (18) has no solution containing only one zero. We conclude that (18) has $1+4(p^n-1)$ solutions containing zeros. Next we consider $x_i\ne 0$ for $1\le n \le 4$. Let $y_i=\frac{x_i}{x_4}$ for $i=1,2,3$. Then $y_i\ne 0$ and satisfy

$$\begin{aligned} \left\{ \begin{array}{lllll} y_1-y_2+y_3-1 &{}=&{}0\\ y_1^d-y^d_2+y^d_3-1 &{}=&{}0. \end{array} \right. \ \ \end{aligned}$$

We denote by $n_4$ the number of solutions $(y_1,y_2,y_3)\in ({\mathbb {F}}_{p^n}^*)^3$ of the above system of equations. By Theorem 1, the value of $n_4$ is $\frac{1}{8}(21p^n-\varGamma ^{(1)}_{p,n}+2\varGamma ^{(2)}_{p,n}-51)$, where $\varGamma ^{(1)}_{p,n}$ and $\varGamma ^{(2)}_{p,n}$ are defined in (8) and (9). Consequently,

$$\begin{aligned}N_4=1+4(p^n-1)+(p^n-1)n_4.\end{aligned}$$

The desired result follows. This completes the proof. $\square$

Now we are ready to determine the differential spectrum of F. The main result of this paper is as follows.

Theorem 3

Let $p\ne 3$, $p^n>7$ and $F(x)=x^d$ be the power function over ${\mathbb {F}}_{p^n}$, where $d=\frac{3p^n-1}{4}$ if $p^n\equiv 3\pmod 8$, and $d=\frac{p^n+1}{4}$ if $p^n\equiv 7\pmod 8$. Then the differential spectrum of F is

$$\begin{aligned} DS_F=\Bigg \{\omega _0= & {} \frac{1}{16}\left( 5p^n-\varGamma ^{(1)}_{p,n}+2\varGamma ^{(2)}_{p,n}-27\right) ,\\ \omega _1= & {} \frac{1}{8}\left( 3p^n+\varGamma ^{(1)}_{p,n}-2\varGamma ^{(2)}_{p,n}+27\right) ,\\ \omega _2= & {} \frac{1}{16}\left( 5p^n-\varGamma ^{(1)}_{p,n}+2\varGamma ^{(2)}_{p,n}-27\right) \Bigg \}, \end{aligned}$$

where $\varGamma ^{(1)}_{p,n}$ and $\varGamma ^{(2)}_{p,n}$ are defined in (8) and (9), respectively.

Proof

By (3) and Theorem 2, the elements $\omega _{i}$ ($i\in \{0, 1, 2\}$) in the differential spectrum satisfy the following equation

$$\begin{aligned} \sum _{i=0}^{2}(i^2\cdot \omega _i)=\frac{1}{8}\left( 13p^n-\varGamma ^{(1)}_{p,n}+2\varGamma ^{(2)}_{p,n}-27\right) . \end{aligned}$$

(19)

By (1) and (19), $\omega _0$, $\omega _1$ and $\omega _2$ satisfy system of equations

$$\begin{aligned} \left\{ \begin{array}{lllll} \omega _0+\omega _1+\omega _2 &{}=&{}p^n\\ \omega _1+2\omega _2 &{}=&{}p^n\\ \omega _1+4\omega _2 &{}=&{}\frac{1}{8}(13p^n-\varGamma ^{(1)}_{p,n}+2\varGamma ^{(2)}_{p,n}-27). \end{array} \right. \ \ \end{aligned}$$

By solving the above system of equations, the differential spectrum of F can be obtained. This completes the proof.

$\square$

Below, we compute the differential spectrum of F over ${\mathbb {F}}_{p^{n}}$ for some specific values of p and n.

Example 3

When $p=7$ and $n=3$, the power function $F(x)=x^{86}$ over ${\mathbb {F}}_{7^3}$ is APN whose differential spectrum is

$$\begin{aligned} DS_F=\{\omega _0=108,\omega _2=127, \omega _2=108\}.\end{aligned}$$

Example 4

When $p=11$ and $n=3$, the power function $F(x)=x^{998}$ over ${\mathbb {F}}_{11^3}$ is APN whose differential spectrum is

$$\begin{aligned}DS_F=\{\omega _0=410,\omega _2=511, \omega _2=410\}.\end{aligned}$$

Example 5

When $p=19$ and $n=1$, the power function $F(x)=x^{14}$ over ${\mathbb {F}}_{19}$ is APN whose differential spectrum is

$$\begin{aligned}DS_F=\{\omega _0=4,\omega _2=11, \omega _2=4\}.\end{aligned}$$

5 Conclusion

In this paper, we studied the differential spectrum of the APN power function $F(x)=x^d$ over ${\mathbb {F}}_{p^n}$, where $d=\frac{3p^n-1}{4}$ when $p^n\equiv 3\pmod 8$ and $d=\frac{p^n+1}{4}$ when $p^n\equiv 7\pmod 8$. We expressed the differential spectrum of F in terms of quadratic character sums over ${\mathbb {F}}_{p^n}$, and the character sums can be evaluated by the theory of elliptic curves for a given p. It is the fourth infinite class of APN power functions with nontrivial differential spectrum. It would be interesting to find some applications of the differential spectrum in related areas, such as sequence design, coding theory and combinatorial design.