A note on the differential spectrum of a class of locally APN functions

Haode Yan1, Ketong Ren1

1School of Mathematics, Southwest Jiaotong University, Chengdu, China.
E-mail: hdyan@swjtu.edu.cn(corresponding author), rkt@my.swjtu.edu.cn,

Abstract

Let ${\mathbb{F}}_{p^{n}}$ denote the finite field containing $p^{n}$ elements, where $n$ is a positive integer and $p$ is a prime. The function $f_{u}(x)=x^{\frac{p^{n}+3}{2}}+ux^{2}$ over ${\mathbb{F}}_{p^{n}}[x]$ with $u\in{\mathbb{F}}_{p^{n}}\setminus\{0,\pm 1\}$ was recently studied by Budaghyan and Pal in [8], whose differential uniformity is at most $5$ when $p^{n}\equiv 3~{}(mod~{}4)$ . In this paper, we study the differential uniformity and the differential spectrum of $f_{u}$ for $u=\pm 1$ . We first give some properties of the differential spectrum of any cryptographic function. Moreover, by solving some systems of equations over finite fields, we express the differential spectrum of $f_{\pm 1}$ in terms of the quadratic character sums.

Keywords: cryptographic function; differential uniformity; differential spectrum; character sum

Mathematics Subject Classification: 11T06, 94A60

I Introduction

Let ${\mathbb{F}}_{q}$ be the finite field with $q$ elements, where $q$ is a prime power. We denote by ${\mathbb{F}}_{q}^{*}:={\mathbb{F}}_{q}\setminus\{0\}$ . Any cryptographic function $F:{\mathbb{F}}_{q}\rightarrow{\mathbb{F}}_{q}$ can be uniquely represented as a univariate polynomial of degree less than $q$ . For a function $F$ , the main tools to study $F$ regarding the differential attack [2] are the difference distribution table (DDT for short) and the differential uniformity introduced by Nyberg [26] in 1994. The DDT entry at point $(a,b)$ for any $a,b\in{\mathbb{F}}_{q}$ , denoted by $\delta_{F}(a,b)$ , is defined as

\delta_{F}(a,b)=\#\{x\in{\mathbb{F}}_{q}:\mathbb{D}_{a}F(x)=b\},

where $\mathbb{D}_{a}F(x)=F(x+a)-F(x)$ is the derivative function of $F$ at the element $a$ . Note that when $a=0$ and $b=0$ , the equation $\mathbb{D}_{a}F(x)=b$ has $q$ solutions in ${\mathbb{F}}_{q}$ , which means $\delta_{F}(0,0)=q$ . Besides, when $a=0$ and $b\in{\mathbb{F}}_{p^{n}}^{*}$ , the equation $\mathbb{D}_{a}F(x)=b$ has no solutions, which means $\delta_{F}(a,b)=0$ . Therefore, for any polynomial, the DDT entries in the line $a=0$ are trivial. The differential uniformity of $F$ , denoted by $\Delta_{F}$ , is defined as

\Delta_{F}=\mathrm{max}\left\{\delta_{F}(a,b):a\in{\mathbb{F}}_{q}^{*},b\in{\mathbb{F}}_{q}\right\}.

Generally speaking, the smaller the value of $\Delta_{F}$ , the stronger the resistance of $F$ used in S-boxes against the differential attack. A cryptographic function $F$ is called differentially $k$ -uniform if $\Delta_{F}=k$ . Particularly when $\Delta_{F}=1$ , $F$ is called a planar function [12] or a perfect nonlinear (abbreviated as PN) function [25]. When $\Delta_{F}=2$ , $F$ is called an almost perfect nonlinear (abbreviated as APN) function [26], which is of the lowest possible differential uniformity over ${\mathbb{F}}_{2^{n}}$ as in such finite fields, no PN functions exist. Readers may refer to [4], [7], [14], [15], [16], [24], [29], [40], [47], [48] and references therein for some of the new developments on PN and APN functions. Apart from the concepts of PN and APN, a power function $F$ over ${\mathbb{F}}_{p^{n}}$ is said to be locally-APN if

\mathrm{max}\left\{\delta_{F}(1,b)|b\in{\mathbb{F}}_{p^{n}}\setminus{\mathbb{F}}_{p}\right\}=2.

This definition was first introduced in [17] for the case $p=2$ and generalized in [37] for odd $p$ . For a general function $F$ , we can also give the concept of locally APN.

Definition 1.

Let $F$ be a function defined on ${\mathbb{F}}_{p^{n}}$ . Then $F$ is called locally-APN if

\mathrm{max}\left\{\delta_{F}(a,b)|a\in{\mathbb{F}}_{p^{n}}^{*},b\in{\mathbb{F}}_{p^{n}}\setminus{\mathbb{F}}_{p}\right\}=2.

In [4], the concept of the differential spectrum of a power function was introduced. The differential spectrum of a cryptographic function, compared with the differential uniformity, provides much more detailed information. In particular, the value distribution of the DDT is given directly by the differential spectrum. What’s more, the differential spectrum has many applications such as in sequences [3], [13], coding theory [9], [10], combinatorial design [32] etc. However, to determine the differential spectrum of a cryptographic function is usually a difficult problem. Power functions with known differential spectra are summarized in Table I.

For a polynomial function that is not a power function, the investigation of its differential spectrum is much more difficult. There are only a few cryptographic functions whose differential spectra were known [22], [27], [34], [36]. One of the focus of this paper is to explore a class of binomials studied in [8]. In [8], the differential uniformity of $f_{u}(x)=x^{\frac{p^{n}+3}{2}}+ux^{2}$ with $u\in{\mathbb{F}}_{p^{n}}\setminus\{0,\pm 1\}$ has been investigated. In this paper, we determine the differential spectrum of such $f_{u}(x)$ when $u\in\{\pm 1\}$ , that is, $f_{\pm 1}(x)=x^{\frac{p^{n}+3}{2}}\pm x^{2}$ .

This paper is organized as follows. Section II presents certain quadratic character sums that are essential for the computation of the aimed differential spectrum. In Section III, properties of the differential spectrum of any function are given. In Section IV, the number of solutions of several systems of equations over finite fields are investigated, which will be used in Section V, in which the differential spectrum of $f_{\pm 1}$ is determined. Section VI concludes this paper.

TABLE I: Power Functions over

{\mathbb{F}}_{p^{n}}

with Known Differential Spectra

$p$	$d$	Condition	$\Delta_{F}$	Ref
$2$	$2^{t}+1$	gcd $(t,n)=s$	$2^{s}$	[4]
$2$	$2^{2t}-2^{t}+1$	gcd $(t,n)=s,\frac{n}{s}\,odd$	$2^{s}$	[4]
$2$	$2^{n}-2$	$n\geqslant 2$	$2\,or\,4$	[4]
$2$	$2^{2k}+2^{k}+1$	$n=4k$	$4$	[4],[38]
$2$	$2^{t}-1$	$t=3,n-2$	$6$ or $8$	[5]
$2$	$2^{t}-1$	$t=\frac{n-1}{2}$ , $\frac{n+3}{2}$ , $n$ odd	$6$ or $8$	[6]
$2$	$2^{m}+2^{(m+1)/2}+1$	$n=2m$ , $m\geqslant 5$ odd	$8$	[39]
$2$	$2^{m+1}+3$	$n=2m$ , $m\geqslant 5$ odd	$8$	[39]
$2$	$2^{3k}+2^{2k}+2^{k}-1$	$n=4k$	$2^{2k}$	[33]
$2$	$\frac{2^{m}-1}{2^{k}+1}+1$	$n=2m$ , gcd $(k,m)=1$	$2^{m}$ (locally APN)	[37]
$3$	$2\cdot 3^{(n-1)/2}+1$	$n$ odd	$4$	[13]
$3$	$\frac{3^{n}-1}{2}+2$	$n$ odd	$4$	[19]
$5$	$\frac{5^{n}-3}{2}$	any $n$	$4$ or $5$	[41]
$5$	$\frac{5^{n}+3}{2}$	any $n$	$3$	[28]
$p$ odd	$p^{2k}-p^{k}+1$	gcd $(n,k)=e$ , $\frac{n}{e}odd$	$p^{e}+1$	[46], [20]
$p$ odd	$\frac{p^{k}+1}{2}$	gcd $(n,k)=e$	$\frac{p^{e}-1}{2}$ or $p^{e}+1$	[11]
$p$ odd	$\frac{p^{n}+1}{p^{m}+1}+\frac{p^{n}-1}{2}$	$p\equiv 3\,(mod\;4)$ , $m\|n$ , $n$ odd	$\frac{p^{m}+1}{2}$	[11]
$p$ odd	$p^{n}-3$	any $n$	$\leqslant 5$	[35], [45]
$p$ odd	$p^{m}+2$	$n=2m$	$2$ or $4$	[15], [23]
$p$ odd	$2p^{\frac{n}{2}}-1$	$n$ even	$p^{\frac{n}{2}}$	[42]
$p$ odd	$\frac{p^{n}-3}{2}$	$p^{n}\equiv 3\,(mod\;4)$ , $p^{n}\geqslant 7$ and $p^{n}\neq 27$	$2$ or $3$	[44]
$p$ odd	$\frac{p^{n}+3}{2}$	$p\geqslant 5$ , $p^{n}\equiv 1\,(mod\;4)$	$3$	[18]
$p$ odd	$\frac{p^{n}+3}{2}$	$p^{n}=11$ or $p^{n}\equiv 3\,(mod\;4)$ , $p\neq 3$ , $p^{n}\neq 11$	$2$ or $4$	[43]
$p$ odd	$\frac{p^{n}+1}{4}$	$p\neq 3$ , $p^{n}>7$ , $p^{n}\equiv 7\,(mod\;8)$	$2$	[31], [15]
$p$ odd	$\frac{3p^{n}-1}{4}$	$p\neq 3$ , $p^{n}>7$ , $p^{n}\equiv 3\,(mod\;8)$	$2$	[31], [15]
$p$ odd	$\frac{p^{n}+1}{4}$ , $\frac{3p^{n}-1}{4}$	$p=3$ or $p>3$ , $p^{n}\equiv 3\,(mod\;4)$	$4$	[1]
any $p$	$k(p^{m}-1)$	$n=2m$ , gcd $(k,p^{m}+1)=1$	$p^{m}-2$ (locally APN)	[17]

II On Quadratic Character Sums

In this section, we will introduce some results on the quadratic character sums over the finite field ${\mathbb{F}}_{q}$ . Let $\chi(\cdot)$ be the quadratic multiplicative character of ${\mathbb{F}}_{q}$ , which is defined as

\chi(x)=\left\{\begin{array}[]{cl}1,&\mbox{if }x\mbox{ is a square in }{\mathbb{F}}_{q}^{*},\\ -1,&\mbox{if }x\mbox{ is a nonsquare in }{\mathbb{F}}_{q}^{*},\\ 0,&\mbox{if }x=0.\end{array}\right.

Let ${\mathbb{F}}_{q}[x]$ be the polynomial ring over ${\mathbb{F}}_{q}$ . We consider the character sum of the form

\displaystyle\sum_{x\in{\mathbb{F}}_{q}}\chi(f(x))

(1)

with $f\in{\mathbb{F}}_{q}[x]$ . The case of $\deg(f)=1$ is trivial, and for $\deg(f)=2$ , the following explicit formula was established in [21].

Lemma 1.

[21, Theorem 5.48] Let $f(x)=a_{2}x^{2}+a_{1}x+a_{0}\in{\mathbb{F}}_{q}[x]$ with $p$ odd and $a_{2}\neq 0$ . Put $d=a_{1}^{2}-4a_{0}a_{2}$ and let $\chi(\cdot)$ be the quadratic character of ${\mathbb{F}}_{q}$ . Then

\sum\limits_{x\in{\mathbb{F}}_{q}}\chi(f(x))=\left\{\begin{array}[]{lcl}-\chi(a_{2}),&if\;d\neq 0,\\ (p^{n}-1)\chi(a_{2}),&if\;d=0.\\ \end{array}\right.

Nevertheless, for a polynomials $f$ with degree $3$ or higher, computing $\sum\limits_{x\in{\mathbb{F}}_{q}}\chi(f(x))$ or deriving a specific formula thereof is generally challenging. The subsequent lemma provides lower and upper bounds for any multiplicative character sum.

Lemma 2.

[30] Let ${\mathbb{F}}_{q}$ be a finite field with $q$ odd. Let $f(x)=ax^{3}+bx^{2}+cx+d\in{\mathbb{F}}_{q}[x]$ be a cubic polynomial with distinct roots in $\overline{{\mathbb{F}}}_{q}$ and $\chi$ be a multiplicative character sum of ${\mathbb{F}}_{q}$ . Then we have

\left|\sum_{x\in{\mathbb{F}}_{q}}\chi\left(f(x)\right)\leqslant 2\sqrt{q}\right|.

However, sometimes we need the exact value of the character sum $\sum\limits_{x\in{\mathbb{F}}_{q}}\chi(f(x))$ . For the case $deg(f(x))=3$ , such a sum can be calculated by considering ${\mathbb{F}}_{p^{n}}$ -rational points of elliptic curves over ${\mathbb{F}}_{p}$ . More precisely, assume that $f$ is a cubic function over ${\mathbb{F}}_{p^{n}}$ and denote

\Gamma_{p,n}=\sum\limits_{x\in{\mathbb{F}}_{p^{n}}}\chi(f(x)).

To evaluate $\Gamma_{p,n}$ , several primary concepts from the theory of elliptic curves shall be taken into consideration. More details on the terminologies and notation can be found in [30]. Let $E/{\mathbb{F}}_{p}$ be the elliptic curve $E:y^{2}=f(x)$ over ${\mathbb{F}}_{p^{n}}$ , and $N_{p,n}$ denote the number of $F_{p^{n}}$ -rational points (with the extra point at infinity) on the curve $E/{\mathbb{F}}_{p}$ . From Subsection 1.3 and Theorem 2.3.1 in [30, Chapter V], $N_{p,n}$ can be assessed by $\Gamma_{p,n}$ . To be more exact, for every $n\geqslant 1$ ,

N_{p,n}=p^{n}+1+\Gamma_{p,n}.

Furthermore,

\Gamma_{p,n}=-\alpha^{n}-\beta^{n},

(2)

where $\alpha$ and $\beta$ are the complex solutions of the quadratic equation $T^{2}+\Gamma_{p,1}T+p=0$ . With an exploration, $\Gamma_{p,n}$ can be determined by $\Gamma_{p,1}$ directly and explicitly. We have

\Gamma_{p,n}=\frac{(-1)^{n+1}}{2^{n-1}}\sum_{k=0}^{\lfloor\frac{n}{2}\rfloor}(-1)^{k}\binom{n}{2k}(\Gamma_{p,1})^{n-2k}(4p-(\Gamma_{p,1})^{2})^{k}.

(3)

Moreover, when $\Gamma_{p,1}=0$ , we have

\Gamma_{p,n}=\left\{\begin{array}[]{ll}(-1)^{\frac{n}{2}+1}\cdot 2\cdot p^{\frac{n}{2}},&n~{}\text{is even};\\ 0,&n~{}\text{is odd}.\\ \end{array}\right.

(4)

We define a specific character sum

\lambda_{p,n}=\sum\limits_{x\in{\mathbb{F}}_{p^{n}}}\chi(x(x^{2}-2x-1)),

which will be used in the sequel. In the following examples, we give the exact value of $\lambda_{p,n}$ for a given $p$ .

Example 1.

Let $p=7$ . For $n=1$ , one has $\lambda_{7,1}=-4$ . By (3), we have

\lambda_{7,n}=\sum_{k=0}^{\lfloor\frac{n}{2}\rfloor}(-1)^{k+1}\binom{n}{2k}2^{n-2k+1}3^{k}.

Example 2.

Let $p=31$ . For $n=1$ , one has $\lambda_{31,1}=0$ . By (4), we have

\lambda_{31,n}=\left\{\begin{array}[]{ll}(-1)^{\frac{n}{2}+1}\cdot 2\cdot 31^{\frac{n}{2}},&n~{}\text{is even};\\ 0,&n~{}\text{is odd}.\\ \end{array}\right.

The key to determine $\lambda_{p,n}$ is to calculate the value of $\lambda_{p,1}$ . For the convenience, we list the values of $\lambda_{p,1}$ for all primes $3\leqslant p\leqslant 1039$ with $p\equiv 3~{}(mod~{}4)$ in Table II, which are computed by MAGMA.

TABLE II: The values of

\lambda_{p,1}

for all primes

3\leqslant p\leqslant 1039

with

p\equiv 3~{}(mod~{}4)

$p$	$3$	$7$	$11$	$19$	$23$	$31$	$43$	$47$	$59$	$67$	$71$	$79$	$83$	$103$	$107$
$\lambda_{p,1}$	$2$	$-4$	$-2$	$2$	$4$	$0$	$6$	$-8$	$14$	$10$	$12$	$-8$	$-6$	$-4$	$-2$
$p$	$127$	$131$	$139$	$151$	$163$	$167$	$179$	$191$	$199$	$211$	$223$	$227$	$239$	$251$	$263$
$\lambda_{p,1}$	$16$	$-6$	$-10$	$4$	$2$	$-20$	$-6$	$-16$	$-4$	$-22$	$0$	$18$	$-24$	$-18$	$12$
$p$	$271$	$283$	$307$	$311$	$331$	$347$	$359$	$367$	$379$	$383$	$419$	$431$	$439$	$443$	$463$
$\lambda_{p,1}$	$8$	$6$	$18$	$-28$	$14$	$-18$	$-4$	$-8$	$-2$	$0$	$26$	$40$	$36$	$6$	$-8$
$p$	$467$	$479$	$487$	$491$	$499$	$503$	$523$	$547$	$563$	$571$	$587$	$599$	$607$	$619$	$631$
$\lambda_{p,1}$	$-14$	$0$	$-20$	$-10$	$-22$	$20$	$14$	$-38$	$18$	$38$	$-34$	$-12$	$-16$	$46$	$-44$
$p$	$643$	$647$	$659$	$683$	$691$	$719$	$727$	$739$	$743$	$751$	$787$	$811$	$823$	$827$	$839$
$\lambda_{p,1}$	$42$	$12$	$-6$	$-42$	$-6$	$24$	$-12$	$18$	$44$	$8$	$-22$	$-18$	$-28$	$22$	$-36$
$p$	$859$	$863$	$883$	$887$	$907$	$911$	$919$	$947$	$967$	$971$	$983$	$991$	$1019$	$1031$	$1039$
$\lambda_{p,1}$	$-50$	$-32$	$34$	$36$	$38$	$-24$	$36$	$-14$	$28$	$38$	$20$	$16$	$6$	$-20$	$40$

At last, we present several results below concerning the exact values of specific character sums used in Section V.

Lemma 3.

When $p^{n}\equiv 3~{}(mod~{}4)$ , we have

1.

$\sum\limits_{x\in{\mathbb{F}}_{p^{n}}}\chi\left(x(x-\frac{1}{2})(x-1)\right)=0$ .
2.

$\sum\limits_{x\in{\mathbb{F}}_{p^{n}}}\chi\left(\left(x-\frac{1}{2}\right)\left(x^{2}-x+\frac{1}{2}\right)\right)=0$ .
3.

$\sum\limits_{x\in{\mathbb{F}}_{p^{n}}}\chi\left(x(x-1)\left(x^{2}-x+\frac{1}{2}\right)\right)=-1$ .
4.

$\sum\limits_{x\in{\mathbb{F}}_{p^{n}}}\chi\left((x-1)\left(x^{2}-x+\frac{1}{2}\right)\right)=\lambda_{p,n}$ .
5.

$\sum\limits_{x\in{\mathbb{F}}_{p^{n}}}\chi\left(x\left(x-\frac{1}{2}\right)\left(x^{2}-x+\frac{1}{2}\right)\right)=-1-\chi(2)\lambda_{p,n}$ .

Proof.

Set $y=x-\frac{1}{2}$ , then $x=y+\frac{1}{2}$ and

\sum\limits_{x\in{\mathbb{F}}_{p^{n}}}\chi\left(x\left(x-\frac{1}{2}\right)(x-1)\right)=\sum\limits_{y\in{\mathbb{F}}_{p^{n}}}\chi\left(\left(y+\frac{1}{2}\right)y\left(y-\frac{1}{2}\right)\right)=\sum\limits_{y\in{\mathbb{F}}_{p^{n}}}\chi\left(y\left(y^{2}-\frac{1}{4}\right)\right).

Let $y=-z$ , then

\sum\limits_{y\in{\mathbb{F}}_{p^{n}}}\chi\left(y\left(y^{2}-\frac{1}{4}\right)\right)=\sum\limits_{z\in{\mathbb{F}}_{p^{n}}}\chi\left(-z\left(z^{2}-\frac{1}{4}\right)\right)=-\sum\limits_{z\in{\mathbb{F}}_{p^{n}}}\chi\left(z\left(z^{2}-\frac{1}{4}\right)\right).

Then $\sum\limits_{y\in{\mathbb{F}}_{p^{n}}}\chi\left(y\left(y^{2}-\frac{1}{4}\right)\right)=0$ . This implies that $\sum\limits_{x\in{\mathbb{F}}_{p^{n}}}\chi\left(x\left(x-\frac{1}{2}\right)(x-1)\right)=0$ .

Set $y=-x+1$ . Then $x=-y+1$ and

	$\displaystyle\sum\limits_{x\in{\mathbb{F}}_{p^{n}}}\chi\left(\left(x-\frac{1}{2}\right)\left(x^{2}-x+\frac{1}{2}\right)\right)$	$\displaystyle=\sum\limits_{y\in{\mathbb{F}}_{p^{n}}}\chi\left(\left(-y+1-\frac{1}{2}\right)\left((-y+1)^{2}-(-y+1)+\frac{1}{2}\right)\right)$
		$\displaystyle=-\sum\limits_{y\in{\mathbb{F}}_{p^{n}}}\chi\left(\left(y-\frac{1}{2}\right)\left(y^{2}-y+\frac{1}{2}\right)\right).$

Hence $\sum\limits_{x\in{\mathbb{F}}_{p^{n}}}\chi\left(\left(x-\frac{1}{2}\right)\left(x^{2}-x+\frac{1}{2}\right)\right)=0$ .

Let $u=x^{2}-x$ . For any $u\in{\mathbb{F}}_{p^{n}}$ , the number of $x$ ’s satisfying $x^{2}-x=u$ is $1+\chi(1+4u)$ . Then

	$\displaystyle\sum\limits_{x\in{\mathbb{F}}_{p^{n}}}\chi\left(x(x-1)\left(x^{2}-x+\frac{1}{2}\right)\right)$	$\displaystyle=\sum\limits_{u\in{\mathbb{F}}_{p^{n}}}\chi\left(u\left(u+\frac{1}{2}\right)\right)(1+\chi(1+4u))$
		$\displaystyle=\sum\limits_{u\in{\mathbb{F}}_{p^{n}}}\chi\left(u\left(u+\frac{1}{2}\right)\right)+\sum\limits_{u\in{\mathbb{F}}_{p^{n}}}\chi\left(u\left(u+\frac{1}{2}\right)(1+4u)\right)$
		$\displaystyle=\sum\limits_{u\in{\mathbb{F}}_{p^{n}}}\chi\left(u\left(u+\frac{1}{2}\right)\right)+\sum\limits_{u\in{\mathbb{F}}_{p^{n}}}\chi\left(u\left(u+\frac{1}{4}\right)\left(u+\frac{1}{2}\right)\right).$

Note that

	$\displaystyle\sum\limits_{u\in{\mathbb{F}}_{p^{n}}}\chi\left(u\left(u+\frac{1}{4}\right)\left(u+\frac{1}{2}\right)\right)$	$\displaystyle=\sum\limits_{v\in{\mathbb{F}}_{p^{n}}}\chi\left(\left(-v-\frac{1}{2}\right)\left(-v-\frac{1}{4}\right)(-v)\right)$
		$\displaystyle=-\sum\limits_{v\in{\mathbb{F}}_{p^{n}}}\chi\left(v\left(v+\frac{1}{4}\right)\left(v+\frac{1}{2}\right)\right).$

Then $\sum\limits_{u\in{\mathbb{F}}_{p^{n}}}\chi\left(u\left(u+\frac{1}{4}\right)\left(u+\frac{1}{2}\right)\right)=0$ . This with Lemma 1 shows that

\sum\limits_{x\in{\mathbb{F}}_{p^{n}}}\chi\left(x(x-1)\left(x^{2}-x+\frac{1}{2}\right)\right)=-1.

Set $y=x-1$ , then $\sum\limits_{x\in{\mathbb{F}}_{p^{n}}}\chi\left((x-1)\left(x^{2}-x+\frac{1}{2}\right)\right)=\sum\limits_{y\in{\mathbb{F}}_{p^{n}}}\chi\left(y\left(y^{2}+y+\frac{1}{2}\right)\right)=\sum\limits_{y\in{\mathbb{F}}_{p^{n}}^{*}}\chi\left(\frac{y^{2}+y+\frac{1}{2}}{y}\right)$ .
Let $t=\frac{y^{2}+y+\frac{1}{2}}{y}$ , then we can obtain a quadratic equation

y^{2}+(1-t)y+\frac{1}{2}=0,

whose discriminant is $\Delta=t^{2}-2t-1$ . For $t\in{\mathbb{F}}_{p^{n}}$ , the number of $y$ satisfying the above quadratic equation is $1+\chi(\Delta)$ . Then

\sum\limits_{y\in{\mathbb{F}}_{p^{n}}^{*}}\chi\left(\frac{y^{2}+y+\frac{1}{2}}{y}\right)=\sum\limits_{t\in{\mathbb{F}}_{p^{n}}}(1+\chi(\Delta))\chi(t)=\sum_{t\in{\mathbb{F}}_{p^{n}}}\chi(t)+\sum\limits_{t\in{\mathbb{F}}_{p^{n}}}\chi(t(t^{2}-2t-1))=\lambda_{p,n}.

It is clear that $x^{2}-x+\frac{1}{2}\neq 0$ , otherwise $\left(x-\frac{1}{2}\right)^{2}=-\left(\frac{1}{2}\right)^{2}$ , which contradicts to $\chi(-1)=-1$ . Then

\sum\limits_{x\in{\mathbb{F}}_{p^{n}}}\chi\left(x\left(x-\frac{1}{2}\right)\left(x^{2}-x+\frac{1}{2}\right)\right)=\sum\limits_{x\in{\mathbb{F}}_{p^{n}}}\chi\left(\frac{x(x-\frac{1}{2})}{x^{2}-x+\frac{1}{2}}\right).

Let $t=\frac{x(x-\frac{1}{2})}{x^{2}-x+\frac{1}{2}}$ , then

\left(t-1\right)x^{2}+\left(\frac{1}{2}-t\right)x+\frac{t}{2}=0.

(5)

Note that $x=1$ if and only if $t=1$ . When $t\neq 1$ , the discriminant of (5) is $-t^{2}+t+\frac{1}{4}$ . Then we have

\begin{array}[]{ll}\sum\limits_{x\in{\mathbb{F}}_{p^{n}}}\chi\left(\frac{x\left(x-\frac{1}{2}\right)}{x^{2}-x+\frac{1}{2}}\right)&=\chi(1)+\sum\limits_{t\in{\mathbb{F}}_{p^{n}},t\neq 1}\left(1+\chi(\Delta)\right)\chi(t)\\ &=1+(-2)+\sum\limits_{t\in{\mathbb{F}}_{p^{n}}}\left(1-\chi\left(t^{2}-t-\frac{1}{4}\right)\right)\chi(t)\\ &=-1-\sum\limits_{t\in{\mathbb{F}}_{p^{n}}}\chi\left(t\left(t^{2}-t-\frac{1}{4}\right)\right).\end{array}

Set $t=\frac{y}{2}$ , then

\sum\limits_{t\in{\mathbb{F}}_{p^{n}}}\chi\left(t\left(t^{2}-t-\frac{1}{4}\right)\right)=\sum\limits_{t\in{\mathbb{F}}_{p^{n}}}\chi\left(\frac{y}{2}\left(\frac{y^{2}}{4}-\frac{y}{2}-\frac{1}{4}\right)\right)=\chi(2)\lambda_{p,n}.

That is desired result follows.

∎

III The properties of the differential spectrum of a general cryptographic function over finite field

First, we give the definition of the differential spectrum of a cryptographic function.

Definition 2.

Let $F$ be a function from ${\mathbb{F}}_{q}$ to ${\mathbb{F}}_{q}$ with differential uniformity $\Delta_{F}$ , and

\omega_{i}=\#\{(a,b)\in{\mathbb{F}}_{q}\times{\mathbb{F}}_{q}:\delta_{F}(a,b)=i\},~{}0\leqslant i\leqslant q,

where $\delta_{F}(a,b)=\#\{x\in{\mathbb{F}}_{q}:F(x+a)-F(x)=b\}$ . The differential spectrum of $F$ is defined as the multiset

\mathbb{S}_{F}=\left[\omega_{0},\omega_{1},...,\omega_{\Delta_{F}},\omega_{\Delta_{F}+1},\cdots,\omega_{q}\right].

Sometimes we ignore the zeros in the differential spectrum. We remark that our definition of the differential spectrum is a little different from that in [34]. In our definition of $\omega_{i}$ , we consider all the pairs $(a,b)\in{\mathbb{F}}_{q}\times{\mathbb{F}}_{q}$ , including $a=0$ . The values of $\omega_{i}(i>\Delta_{F})$ can be obtained easily. That is, $\omega_{\Delta_{F}+1}=\cdots=\omega_{q-1}=0$ and $\omega_{q}=1$ .

From [15], it is known that the differential spectrum of a power function satisfies several identities. It is natural to consider how it behaves with respect to the differential spectrum of any function. In this section, we give some identities of the differential spectrum of a general cryptographic function. Let $f$ be a polynomial over ${\mathbb{F}}_{q}$ with differential uniformity $\Delta_{f}$ . We have the following theorem.

Theorem 1.

We have

\sum\limits_{i=0}^{q}\omega_{i}=q^{2},

(6)

\sum\limits_{i=0}^{q}i\omega_{i}=q^{2},

(7)

and

\sum\limits_{i=0}^{q}i^{2}\omega_{i}=N_{4},

(8)

where

N_{4}=\#\bigg{\{}(x_{1},x_{2},x_{3},x_{4})\in({\mathbb{F}}_{q})^{4}:\left\{\begin{array}[]{l}x_{1}-x_{2}+x_{3}-x_{4}=0,\\ f(x_{1})-f(x_{2})+f(x_{3})-f(x_{4})=0.\\ \end{array}\right.\bigg{\}}.

(9)

Proof.

According to the definition of $\omega_{i}$ , we have

\sum\limits_{i=0}^{q}\omega_{i}=\sum\limits_{i=0}^{q}\#\{(a,b)\in({\mathbb{F}}_{q})^{2}:\delta_{f}(a,b)=i\}=q^{2}.

The last equation holds since when $i$ runs through the integers in the range $[0,q]$ , each $(a,b)\in({\mathbb{F}}_{q})^{2}$ should occur.

Besides, for a fixed $i$ , there are $\omega_{i}$ distinct pairs $(a,b)$ such that $\delta_{f}(a,b)=i$ , then we have

i\omega_{i}=\sum\limits_{\delta_{f}(a,b)=i}\#\{x\in{\mathbb{F}}_{q}:f(x+a)-f(x)=b\}.

And for a given $a\in{\mathbb{F}}_{q}$ ,

\sum\limits_{b\in{\mathbb{F}}_{q}}\#\{x\in{\mathbb{F}}_{q}:f(x+a)-f(x)=b\}=\sum\limits_{x\in{\mathbb{F}}_{q}}1=q

since for any $x\in{\mathbb{F}}_{q}$ , there exists exactly one $b\in{\mathbb{F}}_{q}$ satisfying $f(x+a)-f(x)=b$ . Then

	$\displaystyle\sum\limits_{i=0}^{q}i\omega_{i}$	$\displaystyle=\sum\limits_{i=0}^{q}\sum\limits_{\begin{subarray}{c}(a,b)\in({\mathbb{F}}_{q})^{2}\\ \delta_{f}(a,b)=i\end{subarray}}\#\{x\in{\mathbb{F}}_{q}:f(x+a)-f(x)=b\}$
		$\displaystyle=\sum\limits_{(a,b)\in({\mathbb{F}}_{q})^{2}}\#\{x\in{\mathbb{F}}_{q}:f(x+a)-f(x)=b\}$
		$\displaystyle=\sum\limits_{a\in{\mathbb{F}}_{q}}\sum\limits_{b\in{\mathbb{F}}_{q}}\#\{x\in{\mathbb{F}}_{q}:f(x+a)-f(x)=b\}$
		$\displaystyle=\sum\limits_{a\in{\mathbb{F}}_{q}}\sum\limits_{x\in{\mathbb{F}}_{q}}1$
		$\displaystyle=q^{2}.$

In the following, we prove the last statement. Note that

\delta_{f}(\alpha,\beta)=\#\bigg{\{}(x_{1},x_{2})\in({\mathbb{F}}_{q})^{2}:\left\{\begin{array}[]{l}x_{1}-x_{2}=\alpha,\\ f(x_{1})-f(x_{2})=\beta.\\ \end{array}\right.\bigg{\}},

since the number of solutions of $x_{2}$ of the equation $f(x_{2}+\alpha)-f(x_{2})=\beta$ is $\delta_{f}(\alpha,\beta)$ and $x_{1}$ is uniquely determined by $x_{2}$ .

It is clear that

	$\displaystyle N_{4}$	$\displaystyle=\#\bigg{\{}(x_{1},x_{2},x_{3},x_{4})\in({\mathbb{F}}_{q})^{4}:\left\{\begin{array}[]{l}x_{1}-x_{2}+x_{3}-x_{4}=0,\\ f(x_{1})-f(x_{2})+f(x_{3})-f(x_{4})=0.\\ \end{array}\right.\bigg{\}}$
		$\displaystyle=\sum\limits_{(\alpha,\beta)\in({\mathbb{F}}_{q})^{2}}\#\bigg{\{}(x_{1},x_{2},x_{3},x_{4})\in({\mathbb{F}}_{q})^{4}:\left\{\begin{array}[]{l}x_{1}-x_{2}=x_{4}-x_{3}=\alpha,\\ f(x_{1})-f(x_{2})=f(x_{4})-f(x_{3})=\beta.\\ \end{array}\right.\bigg{\}}$
		$\displaystyle=\sum\limits_{(\alpha,\beta)\in({\mathbb{F}}_{q})^{2}}\#\bigg{\{}(x_{1},x_{2})\in({\mathbb{F}}_{q})^{2}:\left\{\begin{array}[]{l}x_{1}-x_{2}=\alpha,\\ f(x_{1})-f(x_{2})=\beta.\\ \end{array}\right.\bigg{\}}\cdot\#\bigg{\{}(x_{3},x_{4})\in({\mathbb{F}}_{q})^{2}:\left\{\begin{array}[]{l}x_{4}-x_{3}=\alpha,\\ f(x_{4})-f(x_{3})=\beta.\\ \end{array}\right.\bigg{\}}$
		$\displaystyle=\sum\limits_{(\alpha,\beta)\in({\mathbb{F}}_{q})^{2}}(\delta_{f}(\alpha,\beta))^{2}$
		$\displaystyle=\sum\limits_{i=0}^{q}\sum\limits_{\begin{subarray}{c}(\alpha,\beta)\in({\mathbb{F}}_{q})^{2}\\ \delta_{f}(\alpha,\beta)=i\end{subarray}}i^{2}$
		$\displaystyle=\sum\limits_{i=0}^{q}i^{2}\omega_{i}.$

This completes the proof. ∎

IV On the number of solutions of certain systems of equations

In this section, we determine the number of solutions of several systems of equations which are needed in Section V.

Lemma 4.

Let $p^{n}\equiv~{}3(mod~{}4)$ . Let $\dot{N}_{(1,1,1)}$ denote the number of solutions $(y_{1},y_{2},y_{3})\in({\mathbb{F}}_{p^{n}}^{*})^{3}$ of the following system of equations

\left\{\begin{array}[]{l}y_{1}-y_{2}+y_{3}-1=0,\\ y_{1}^{2}-y_{2}^{2}+y_{3}^{2}-1=0,\\ \end{array}\right.

(10)

with $(\chi(y_{1}),\chi(y_{2}),\chi(y_{3}))=(1,1,1)$ . Then we have $\dot{N}_{(1,1,1)}=p^{n}-2$ .

Proof.

The system (10) can be rewritten as

\left\{\begin{array}[]{l}y_{1}-y_{2}=1-y_{3},\\ y_{1}^{2}-y_{2}^{2}=1-y_{3}^{2}.\\ \end{array}\right.

(11)

If $y_{3}=1$ , then we get $(y_{1},y_{2},y_{3})=(y_{2},y_{2},1)$ . Note that $(y_{2},y_{2},1)$ is a desired solution if and only if $\chi(y_{2})=1$ . Therefore, the number of such desired solutions is $\frac{p^{n}-1}{2}$ . If $y_{3}\neq 1$ , then $y_{1}\neq y_{2}$ , we have

\left\{\begin{array}[]{l}y_{1}-y_{2}=1-y_{3},\\ y_{1}+y_{2}=1+y_{3},\\ \end{array}\right.

whose solution is $(y_{1},y_{2},y_{3})=(1,y_{2},y_{2})$ . Similarly, the number of such desired solutions is $\frac{p^{n}-1}{2}$ . Together with the two cases and removing one identical solution $(1,1,1)$ , $\dot{N}_{(1,1,1)}=\frac{p^{n}-1}{2}+\frac{p^{n}-1}{2}-1=p^{n}-2$ . ∎

Lemma 5.

Let $p^{n}\equiv~{}3(mod~{}4)$ . Let $\ddot{N}_{(-1,-1,-1)}$ denote the number of solutions $(y_{1},y_{2},y_{3})\in({\mathbb{F}}_{p^{n}}^{*})^{3}$ of the following system of equations

\left\{\begin{array}[]{l}y_{1}-y_{2}+y_{3}-1=0,\\ y_{1}^{2}-y_{2}^{2}+y_{3}^{2}=0,\\ \end{array}\right.

(12)

with $(\chi(y_{1}),\chi(y_{2}),\chi(y_{3}))=(-1,-1,-1)$ . Then we have $\ddot{N}_{(-1,-1,-1)}=\frac{1}{8}\left(p^{n}+1+(\chi(2)-1)\lambda_{p,n}\right)$ .

Proof.

It is easy to check that $y_{3}\neq 1$ in (12), then we have

\left\{\begin{array}[]{l}y_{1}-y_{2}=1-y_{3},\\ y_{1}+y_{2}=-\frac{y_{3}^{2}}{1-y_{3}}.\\ \end{array}\right.

Thus, we obtain the solutions of (12)

\left\{\begin{array}[]{l}y_{1}=1+\frac{1}{2(y_{3}-1)},\\ y_{2}=y_{3}+\frac{1}{2(y_{3}-1)}.\\ \end{array}\right.

Hence, $(y_{1},y_{2},y_{3})$ is a desired solution if and only if

\chi\left(1+\frac{1}{2(y_{3}-1)}\right)=-1,~{}\chi\left(y_{3}+\frac{1}{2(y_{3}-1)}\right)=-1,~{}\chi(y_{3})=-1.

This implies that

	$\displaystyle\ddot{N}_{(-1,-1,-1)}$	$\displaystyle=\frac{1}{8}\sum\limits_{y_{3}\in{\mathbb{F}}_{p^{n}}^{*},y_{3}\neq 1}\left[1-\chi\left(1+\frac{1}{2(y_{3}-1)}\right)\right]\cdot\left[1-\chi\left(y_{3}+\frac{1}{2(y_{3}-1)}\right)\right]\cdot\left[1-\chi(y_{3})\right]$
		$\displaystyle=\frac{1}{8}\sum\limits_{y_{3}\in{\mathbb{F}}_{p^{n}}^{*},y_{3}\neq 1}\left[1-\chi\left((y_{3}-1)\left(y_{3}-\frac{1}{2}\right)\right)\right]\left[1-\chi\left((y_{3}-1)\left(y_{3}^{2}-y_{3}+\frac{1}{2}\right)\right)\right][1-\chi(y_{3})]$
		$\displaystyle=\frac{1}{8}\Bigg{[}\sum\limits_{y_{3}\in{\mathbb{F}}_{p^{n}}}1-\sum\limits_{y_{3}\in{\mathbb{F}}_{p^{n}}}\chi(y_{3})-\sum\limits_{y_{3}\in{\mathbb{F}}_{p^{n}}}\chi\left((y_{3}-1)\left(y_{3}-\frac{1}{2}\right)\right)-\sum\limits_{y_{3}\in{\mathbb{F}}_{p^{n}}}\chi\left((y_{3}-1)\left(y_{3}^{2}-y_{3}+\frac{1}{2}\right)\right)$
		$\displaystyle~{}~{}~{}~{}~{}~{}~{}+\sum\limits_{y_{3}\in{\mathbb{F}}_{p^{n}}}\chi\left((y_{3}-1)^{2}\left(y_{3}-\frac{1}{2}\right)\left(y_{3}^{2}-y_{3}+\frac{1}{2}\right)\right)+\sum\limits_{y_{3}\in{\mathbb{F}}_{p^{n}}}\chi\left(y_{3}(y_{3}-1)\left(y_{3}^{2}-y_{3}+\frac{1}{2}\right)\right)$
		$\displaystyle~{}~{}~{}~{}~{}~{}~{}+\sum\limits_{y_{3}\in{\mathbb{F}}_{p^{n}}}\chi\left(y_{3}(y_{3}-1)\left(y_{3}-\frac{1}{2}\right)\right)-\sum\limits_{y_{3}\in{\mathbb{F}}_{p^{n}}}\chi\left(y_{3}\left(y_{3}-\frac{1}{2}\right)(y_{3}-1)^{2}\left(y_{3}^{2}-y_{3}+\frac{1}{2}\right)\right)\Bigg{]}$
		$\displaystyle=\frac{1}{8}\Bigg{[}p^{n}-\sum\limits_{y_{3}\in{\mathbb{F}}_{p^{n}}}\chi\left((y_{3}-1)\left(y_{3}-\frac{1}{2}\right)\right)-\sum\limits_{y_{3}\in{\mathbb{F}}_{p^{n}}}\chi\left((y_{3}-1)\left(y_{3}^{2}-y_{3}+\frac{1}{2}\right)\right)$
		$\displaystyle~{}~{}~{}~{}~{}~{}~{}+\sum\limits_{y_{3}\in{\mathbb{F}}_{p^{n}}}\chi\left(\left(y_{3}-\frac{1}{2}\right)\left(y_{3}^{2}-y_{3}+\frac{1}{2}\right)\right)-1+\sum\limits_{y_{3}\in{\mathbb{F}}_{p^{n}}}\chi\left(y_{3}(y_{3}-1)\left(y_{3}^{2}-y_{3}+\frac{1}{2}\right)\right)$
		$\displaystyle~{}~{}~{}~{}~{}~{}~{}+\sum\limits_{y_{3}\in{\mathbb{F}}_{p^{n}}}\chi\left(y_{3}\left(y_{3}-\frac{1}{2}\right)(y_{3}-1)\right)-\sum\limits_{y_{3}\in{\mathbb{F}}_{p^{n}}}\chi\left(y_{3}\left(y_{3}-\frac{1}{2}\right)\left(y_{3}^{2}-y_{3}+\frac{1}{2}\right)\right)+1\Bigg{]}$
		$\displaystyle=\frac{1}{8}(p^{n}+1+(\chi(2)-1)\lambda_{p,n}).$

The last identity holds based on Lemma 1 and Lemma 3. ∎

Lemma 6.

Let $p^{n}\equiv~{}3(mod~{}4)$ . Let $\dddot{N}_{(-1,-1,-1,-1)}$ denote the number of solutions $(y_{1},y_{2},y_{3},y_{4})\in({\mathbb{F}}_{p^{n}}^{*})^{4}$ of the equation

y_{1}-y_{2}+y_{3}-y_{4}=0,

(13)

with $(\chi(y_{1}),\chi(y_{2}),\chi(y_{3}),\chi(y_{4}))=(-1,-1,-1,-1)$ . Then $\dddot{N}_{(-1,-1,-1,-1)}=\frac{1}{16}\left((p^{n}-1)\left(p^{2n}-2p^{n}+5\right)\right)$ .

Proof.

We have

		$\displaystyle\#\left\{(y_{1},y_{2},y_{3},y_{4})\in({\mathbb{F}}_{p^{n}}^{*})^{4}:y_{1}-y_{2}+y_{3}-y_{4}=0\right\}$
	$\displaystyle=$	$\displaystyle\#\left\{(y_{1},y_{2},y_{3},y_{4})\in({\mathbb{F}}_{p^{n}}^{*})^{4}:y_{1}-y_{2}=y_{4}-y_{3}\right\}$
	$\displaystyle=$	$\displaystyle\sum\limits_{\alpha\in{\mathbb{F}}_{p^{n}}}\#\Bigg{\{}(y_{1},y_{2},y_{3},y_{4})\in({\mathbb{F}}_{p^{n}}^{*})^{4}:\left\{\begin{array}[]{l}y_{1}-y_{2}=\alpha,\\ y_{4}-y_{3}=\alpha.\end{array}\right.\Bigg{\}}$
	$\displaystyle=$	$\displaystyle\sum\limits_{\alpha\in{\mathbb{F}}_{p^{n}}}\#\left\{(y_{1},y_{2})\in({\mathbb{F}}_{p^{n}}^{})^{2}:y_{1}-y_{2}=\alpha\right\}\cdot\#\left\{(y_{3},y_{4})\in({\mathbb{F}}_{p^{n}}^{})^{2}:y_{4}-y_{3}=\alpha\right\}$
	$\displaystyle=$	$\displaystyle\sum\limits_{\alpha\in{\mathbb{F}}_{p^{n}}}\left(\#\left\{(y_{1},y_{2})\in({\mathbb{F}}_{p^{n}}^{*})^{2}:y_{1}-y_{2}=\alpha\right\}\right)^{2}.$

In the following, for a given $\alpha\in{\mathbb{F}}_{p^{n}}$ , we discuss the number of solutions $(y_{1},y_{2})$ of the equation

y_{1}-y_{2}=\alpha

with $\chi(y_{1})=\chi(y_{2})=-1$ .

1.

$\alpha=0$ . Then the desired solutions of $y_{1}-y_{2}=\alpha$ should be $(y_{1},y_{2})=(y_{1},y_{1})$ with $\chi(y_{1})=-1$ . Besides, the number of such solutions is $\frac{p^{n}-1}{2}$ .

$\alpha$ is a square element in ${\mathbb{F}}_{p^{n}}^{*}$ . Let $z_{i}=\frac{y_{i}}{\alpha}(i=1,2)$ , then $\chi(z_{1})=\chi(z_{2})=-1$ and the equation $y_{1}-y_{2}=\alpha$ becomes $z_{1}-z_{2}=1$ . Thus, we have

\#\left\{(z_{1},z_{2})\in({\mathbb{F}}_{p^{n}}^{*})^{2}:z_{1}-z_{2}=1,\chi(z_{1})=\chi(z_{2})=-1\right\}=\#\left\{z_{2}\in{\mathbb{F}}_{p^{n}}^{*}:\chi(z_{2}+1)=\chi(z_{2})=-1\right\}

=\frac{1}{4}\sum\limits_{\begin{subarray}{c}z_{2}\in{\mathbb{F}}_{p^{n}}^{*},\\ z_{2}\neq-1\end{subarray}}(1-\chi(z_{2}))(1-\chi(z_{2}+1))=\frac{p^{n}-3}{4}.

3.

$\alpha$ is a nonsquare element in ${\mathbb{F}}_{p^{n}}^{*}$ . The number of solutions $(y_{1},y_{2})$ with $\chi(y_{1})=\chi(y_{2})=-1$ of the equation $y_{1}-y_{2}=\alpha$ is also $\frac{p^{n}-3}{4}$ . The proof is similar with 2) and we omit it.

In summary, we have

\dddot{N}_{(-1,-1,-1,-1)}=\left(\frac{p^{n}-1}{2}\right)^{2}+2\cdot\frac{p^{n}-1}{2}\cdot\left(\frac{p^{n}-3}{4}\right)^{2}=\frac{1}{16}\left((p^{n}-1)(p^{2n}-2p^{n}+5)\right).

∎

V The differential spectrum of $f_{1}$

Let $n$ be an odd integer, $p$ be an odd prime satisfying $p\equiv 3~{}(mod~{}4)$ . Recall that $f_{1}(x)=x^{\frac{p^{n}+3}{2}}+x^{2}$ and $f_{-1}(x)=x^{\frac{p^{n}+3}{2}}-x^{2}$ are binomials over ${\mathbb{F}}_{p^{n}}$ . Note that $f_{-1}(x)=-f_{1}(-x)$ , then we only study the differential properties of $f_{1}(x)$ . In this section, we investigate the differential uniformity and the differential spectrum of $f_{1}$ . The differential uniformity and the differential spectrum of $f_{-1}$ can be obtained directly and we omit them.

V-A The differential uniformity of $f_{1}$

In this subsection, our primary objective is to determine the differential uniformity of $f_{1}$ , accompanied by a discussion of the number of potential solutions associated with the differential equation.

Theorem 2.

Let $n$ be an odd integer, $p$ be an odd prime with $p^{n}\equiv 3~{}(mod~{}4)$ . The differential uniformity of $f_{1}$ is $\frac{p^{n}+1}{4}$ . Moreover, $\delta_{f_{1}}(a,b)\leq 2$ when $(a,b)\in({\mathbb{F}}_{p^{n}}^{*})^{2}$ .

Proof.

It is obvious that $\delta_{f_{1}}(0,0)=p^{n}$ and $\delta_{f_{1}}(0,b)=0$ for $b\neq 0$ . For any $(a,b)\in{\mathbb{F}}_{p^{n}}^{*}\times{\mathbb{F}}_{p^{n}}$ , the differential equation $f_{1}(x+a)-f_{1}(x)=b$ becomes

(\chi(x+a)-\chi(x))x^{2}+2a(1+\chi(x+a))x+(1+\chi(x+a))a^{2}-b=0.

(14)

When $x\notin\{0,-a\}$ , we discuss (14) in four cases shown in Table III, in which $x_{1}$ and $x_{2}$ denote the two solutions of the quadratic equations in Case III and Case IV.

TABLE III: List of Equations and Solutions

Case	I	II	III	IV
$(\chi(x+a),\chi(x))$	$(1,1)$	$(-1,-1)$	$(-1,1)$	$(1,-1)$
$Equation$	$4ax+2a^{2}-b=0$	$b=0$	$2x^{2}+b=0$	$2x^{2}+4ax+2a^{2}-b=0$
$x$	$\frac{b-2a^{2}}{4a}$		$\pm\sqrt{-\frac{b}{2}}$	$\frac{-2a\pm\sqrt{2b}}{2}$
$x+a$	$\frac{b+2a^{2}}{4a}$		$a\pm\sqrt{-\frac{b}{2}}$	$-a\pm a\sqrt{1+\frac{u-1}{ab}}$
$x_{1}x_{2}$			$\frac{b}{2}$	$\frac{2a^{2}-b}{2}$
$(x_{1}+a)(x_{2}+a)$			$a^{2}+\frac{b}{2}$	$-\frac{b}{2}$

1.

When $b=0$ , $x=0$ is a solution of (14) if and only if $\chi(a)=-1$ , and $x=-a$ is a solution of equation (14) if and only if $\chi(a)=1$ . This indicates that for any $a\in{\mathbb{F}}_{p^{n}}^{*}$ , $f_{1}(x+a)-f_{1}(x)=0$ has exactly one solution in $\{0,-a\}$ . For the remaining solutions not in $\{0,-a\}$ , replacing $b$ by $0$ in Table III, it is effortless to check that $f_{1}(x+a)-f_{1}(x)=0$ has no solutions in Case I, Case III or Case IV. And for any $a\in{\mathbb{F}}_{p^{n}}^{*}$ , there are

$\frac{1}{4}\sum\limits_{x\in{\mathbb{F}}_{p^{n}}^{*}\setminus\{-a\}}(1-\chi(x+a))(1-\chi(x))=\frac{p^{n}-3}{4}$

solutions in Case II. In short, the equation $f_{1}(x+a)-f_{1}(x)=0$ has $\frac{p^{n}+1}{4}$ solutions in total and the number of such $(a,0)$ is $p^{n}-1$ .
2.
When $b\neq 0$ ,
1. (a)
  
  it is clear that (14) cannot have solutions in both Cases III and IV simultaneously as $\chi(2b)$ cannot be both $-1$ and $1$ at the same time;
2. (b)
  
  if (14) has two solutions in Case III, then $\chi(-\frac{b}{2})=1$ and $\chi(x_{1}x_{2})=\chi(\frac{b}{2})=1$ , which is a contradiction;
3. (c)
  
  (14) has at most one solution in Case IV, otherwise both $\chi(2b)=1$ and $\chi(x_{1}+a)\chi(x_{2}+a)=\chi(-2b)=1$ would hold simultaneously, which is impossible with $\chi(-1)=-1$ .
From the discussion above, the equation $f_{1}(x+a)-f_{1}(x)=b$ has at most two solutions when $b\neq 0$ .

We finish the proof. ∎

V-B The value of $N_{4}$ pertaining to $f_{1}$

Based on the discussion in Subsection V-A, to determine the differential spectrum of $f_{1}$ , we are required to determine $\omega_{0}$ , $\omega_{1}$ and $\omega_{2}$ . Further, according to Theorem 1 and the fact that $f_{1}(x)=(1+\chi(x))x^{2}$ , we need to examine the solutions of the system of equations

\left\{\begin{array}[]{l}x_{1}-x_{2}+x_{3}-x_{4}=0,\\ (1+\chi(x_{1}))x_{1}^{2}-(1+\chi(x_{2}))x_{2}^{2}+(1+\chi(x_{3}))x_{3}^{2}-(1+\chi(x_{4}))x_{4}^{2}=0.\\ \end{array}\right.

Theorem 3.

Let $N_{4}$ denote the number of solutions of the system of equations:

\left\{\begin{array}[]{l}x_{1}-x_{2}+x_{3}-x_{4}=0,\\ (1+\chi(x_{1}))x_{1}^{2}-(1+\chi(x_{2}))x_{2}^{2}+(1+\chi(x_{3}))x_{3}^{2}-(1+\chi(x_{4}))x_{4}^{2}=0.\\ \end{array}\right.

(15)

Then $N_{4}=\frac{1}{16}\left((p^{n}-1)\left(p^{2n}+34p^{n}+17+4(\chi(2)-1)\lambda_{p,n}\right)\right)+1$ .

Proof.

For a solution $(x_{1},x_{2},x_{3},x_{4})\in({\mathbb{F}}_{p^{n}})^{4}$ of (15), let $\mathcal{N}^{(i)}$ denote the number of solutions containing $i$ zeros, where $0\leqslant i\leqslant 4$ . In the first place, we are trying to evaluate $\mathcal{N}^{(0)}$ . Let $\mathcal{N}_{(i,j,k,l)}$ denote the number of solutions $(x_{1},x_{2},x_{3},x_{4})\in({\mathbb{F}}_{p^{n}}^{*})^{4}$ of the system (15) when $(\chi(x_{1}),\chi(x_{2}),\chi(x_{3}),\chi(x_{4}))=(i,j,k,l),i,j,k,l\in\{\pm 1\}$ . Then we have $\mathcal{N}^{(0)}=\sum\limits_{i,j,k,l\in\{\pm 1\}}\mathcal{N}_{(i,j,k,l)}$ . Next, we compute $\mathcal{N}_{(i,j,k,l)}$ in $16$ cases presented below.

1.

When $(\chi(x_{1}),\chi(x_{2}),\chi(x_{3}),\chi(x_{4}))=(1,1,1,1)$ , the system (15) can be reduced to

$\left\{\begin{array}[]{l}x_{1}-x_{2}+x_{3}-x_{4}=0,\\ x_{1}^{2}-x_{2}^{2}+x_{3}^{2}-x_{4}^{2}=0.\\ \end{array}\right.$

Set $y_{i}=\frac{x_{i}}{x_{4}}$ , then we need to calculate the number of solutions of

$\left\{\begin{array}[]{l}y_{1}-y_{2}+y_{3}-1=0,\\ y_{1}^{2}-y_{2}^{2}+y_{3}^{2}-1=0,\\ \end{array}\right.$

where $\chi(y_{1})=\chi(y_{2})=\chi(y_{3})=1$ . According to Lemma 4, the number of the above system is $p^{n}-2$ . Combined with the condition that $\chi(x_{4})=1$ and noting that the number of such $x_{4}$ is $\frac{p^{n}-1}{2}$ , we can obtain that $\mathcal{N}_{(1,1,1,1)}=\frac{1}{2}(p^{n}-1)(p^{n}-2)$ .
2.
In this case, we consider there is exactly one nonsquare element among $x_{1},x_{2},x_{3}$ and $x_{4}$ .
1. (a)
  
  When $(\chi(x_{1}),\chi(x_{2}),\chi(x_{3}),\chi(x_{4}))=(1,1,1,-1)$ , the system (15) can be reduced to
  
  $\left\{\begin{array}[]{l}x_{1}-x_{2}+x_{3}-x_{4}=0,\\ x_{1}^{2}-x_{2}^{2}+x_{3}^{2}=0.\\ \end{array}\right.$
  
  Set $y_{i}=\frac{x_{i}}{x_{4}}$ , then we need to calculate the number of solutions of
  
  $\left\{\begin{array}[]{l}y_{1}-y_{2}+y_{3}-1=0,\\ y_{1}^{2}-y_{2}^{2}+y_{3}^{2}=0,\\ \end{array}\right.$
  
  with $(\chi(y_{1}),\chi(y_{2}),\chi(y_{3}))=(-1,-1,-1)$ . According to Lemma 5, the number of solutions of the above system is $\frac{1}{8}(p^{n}+1+(\chi(2)-1)\lambda_{p,n})$ . Combined with the condition that $\chi(x_{4})=-1$ and noting that the number of such $x_{4}$ is $\frac{p^{n}-1}{2}$ , we can obtain that $\mathcal{N}_{(1,1,1,-1)}=\frac{1}{16}\left((p^{n}-1)(p^{n}+1+(\chi(2)-1)\lambda_{p,n})\right)$ .
2. (b)
  
  When $(\chi(x_{1}),\chi(x_{2}),\chi(x_{3}),\chi(x_{4}))=(1,1,-1,1)$ , the system (15) can be reduced to
  
  $\left\{\begin{array}[]{l}x_{1}-x_{2}+x_{3}-x_{4}=0,\\ x_{1}^{2}-x_{2}^{2}-x_{4}^{2}=0.\\ \end{array}\right.$
  
  This system of equations is the same as
  
  $\left\{\begin{array}[]{l}x_{2}-x_{1}+x_{4}-x_{3}=0,\\ x_{2}^{2}-x_{1}^{2}+x_{4}^{2}=0.\\ \end{array}\right.$
  
  By a simple comparison, we have $\mathcal{N}_{(1,1,-1,1)}=\mathcal{N}_{(1,1,1,-1)}$ . In the same manner, $\mathcal{N}_{(-1,1,1,1)}=\mathcal{N}_{(1,1,-1,1)}=\mathcal{N}_{(1,-1,1,1)}=\mathcal{N}_{(1,1,1,-1)}$ can be deduced.
In short, we have $\mathcal{N}_{(1,1,1,-1)}=\mathcal{N}_{(1,1,-1,1)}=\mathcal{N}_{(1,-1,1,1)}=\mathcal{N}_{(-1,1,1,1)}=\frac{1}{16}\big{(}(p^{n}-1)(p^{n}+1+(\chi(2)-1)\lambda_{p,n})\big{)}$ .
3.
In this case, we consider there are exactly two nonsquare elements among $x_{1},x_{2},x_{3}$ and $x_{4}$ .
1. (a)
  
  When $(\chi(x_{1}),\chi(x_{2}),\chi(x_{3}),\chi(x_{4}))=(1,1,-1,-1)$ , the system (15) can be reduced to
  
  $\left\{\begin{array}[]{l}x_{1}-x_{2}+x_{3}-x_{4}=0,\\ x_{1}^{2}-x_{2}^{2}=0.\\ \end{array}\right.$
  
  From the second equation above, we can obtain that $x_{1}=x_{2}$ since $\chi(x_{1})=\chi(x_{2})$ and $\chi(-1)=-1$ . Then the solutions of this system of equations is $(x_{1},x_{1},x_{3},x_{3})$ . Combined with the condition that $\chi(x_{1})=1$ and $\chi(x_{3})=-1$ , and noting that the number of such $x_{1}$ and $x_{3}$ is each $\frac{p^{n}-1}{2}$ , we can obtain that $\mathcal{N}_{(1,1,-1,-1)}=\frac{1}{4}(p^{n}-1)^{2}$ .
2. (b)
  
  Since $x_{1}$ and $x_{3}$ have the same status in the system (15) and so do $x_{2}$ and $x_{4}$ , it follows that $\mathcal{N}_{(-1,-1,1,1)}=\mathcal{N}_{(1,-1,-1,1)}=\mathcal{N}_{(-1,1,1,-1)}=\mathcal{N}_{(1,1,-1,-1)}$ .
3. (c)
  
  When $(\chi(x_{1}),\chi(x_{2}),\chi(x_{3}),\chi(x_{4}))=(1,-1,1,-1)$ , the system (15) can be reduced to
  
  $\left\{\begin{array}[]{l}x_{1}-x_{2}+x_{3}-x_{4}=0,\\ x_{1}^{2}+x_{3}^{2}=0.\\ \end{array}\right.$
  
  Obviously, $x_{1}^{2}+x_{3}^{2}=0$ has no solution when $x_{1}\neq 0$ , $x_{3}\neq 0$ , which means $\mathcal{N}_{(1,-1,1,-1)}=0$ . Besides, it is easy to check that $\mathcal{N}_{(-1,1,-1,1)}=0$ .
In short, we have $\mathcal{N}_{(1,1,-1,-1)}=\mathcal{N}_{(-1,-1,1,1)}=\mathcal{N}_{(1,-1,-1,1)}=\mathcal{N}_{(-1,1,1,-1)}=\frac{1}{4}(p^{n}-1)^{2}$ , $\mathcal{N}_{(1,-1,1,-1)}=\mathcal{N}_{(-1,1,-1,1)}=0$ .
4.

In this case, we consider there are exactly three nonsquare elements among $x_{1},x_{2},x_{3}$ and $x_{4}$ . Suppose that $(\chi(x_{1}),\chi(x_{2}),\chi(x_{3}),\chi(x_{4}))=(1,-1,-1,-1)$ , then the second equality in (15) becomes $2x_{1}^{2}=0$ . It follows that $x_{1}=0$ , a contradiction to $x_{i}\neq 0$ for $1\leqslant i\leqslant 4$ . Thus, $\mathcal{N}_{(1,-1,-1,-1)}=0$ . By the same procedure, the desired result follows. Thus, we have $\mathcal{N}_{(1,-1,-1,-1)}=\mathcal{N}_{(-1,1,-1,-1)}=\mathcal{N}_{(-1,-1,1,-1)}=\mathcal{N}_{(-1,-1,-1,1)}=0$ .
5.

When $(\chi(x_{1}),\chi(x_{2}),\chi(x_{3}),\chi(x_{4}))=(-1,-1,-1,-1)$ , the system (15) can be reduced to

$x_{1}-x_{2}+x_{3}-x_{4}=0.$

According to Lemma 6, it follows that $\mathcal{N}_{(-1,-1,-1,-1)}=\frac{1}{16}\left((p^{n}-1)(p^{2n}-2p^{n}+5)\right)$ .

Above all, we have

	$\displaystyle\mathcal{N}^{(0)}$	$\displaystyle=\sum\limits_{(i,j,k,l)\in\{\pm 1\}^{4}}\mathcal{N}_{(i,j,k,l)}$
		$\displaystyle=\mathcal{N}_{(1,1,1,1)}+4\mathcal{N}_{(1,1,1,-1)}+4\mathcal{N}_{(1,1,-1,-1)}+2\mathcal{N}_{(1,-1,1,-1)}+4\mathcal{N}_{(1,-1,-1,-1)}+\mathcal{N}_{(-1,-1,-1,-1)}$
		$\displaystyle=\frac{(p^{n}-1)(p^{n}-2)}{2}+\frac{1}{2}(p^{n}-1)(p^{n}+1+(\chi(2)-1)\lambda_{p,n})+(p^{n}-1)^{2}+\frac{1}{16}\left((p^{n}-1)(p^{2n}-2p^{n}+5)\right)$
		$\displaystyle=\frac{1}{16}\left((p^{n}-1)(p^{2n}+26p^{n}-23+4(\chi(2)-1)\lambda_{p,n})\right).$

In the following, we consider the cases that there exists some $x_{i}=0$ , where $i\in\{1,2,3,4\}$ to evaluate $\mathcal{N}^{(i)}$ with $1\leqslant i\leqslant 4$ as follows.

1.

Obviously, $(0,0,0,0)$ is a solution of (15). Suppose that there are exactly three variables $x_{i}$ taking the value $0$ in a solution, it can be deduced that the solution must be $(0,0,0,0)$ . This implies (15) can not have a solution with exactly three variables being $0$ and the rest one being nonzero. Thus, we have $\mathcal{N}^{(4)}=1$ and $\mathcal{N}^{(3)}=0$ .
2.

In this case, we consider the condition that there are exactly two variables $x_{i}$ taking the value $0$ in a solution. If $x_{1}=x_{2}=0$ , then the system (15) can be reduced to

$\left\{\begin{array}[]{l}x_{3}-x_{4}=0,\\ (1+\chi(x_{3}))x_{3}^{2}-(1+\chi(x_{4}))x_{4}^{2}=0.\\ \end{array}\right.$

Then we obtain the solutions in the form of $(0,0,x,x)$ with $x\in{\mathbb{F}}_{p^{n}}^{*}$ and the number of such solutions is $p^{n}-1$ . By the same token, the quadruples in the form of $(x,x,0,0)$ , $(0,x,x,0)$ and $(x,0,0,x)$ are all solutions and the number of each is $p^{n}-1$ . In short, $\mathcal{N}^{(2)}=4(p^{n}-1)$ .

In this case, we consider the condition that there is exactly one variable $x_{i}$ taking the value 0 in a solution. If $x_{4}=0$ , then the system (15) can be reduced to

\left\{\begin{array}[]{l}x_{1}-x_{2}+x_{3}=0,\\ (1+\chi(x_{1}))x_{1}^{2}-(1+\chi(x_{2}))x_{2}^{2}+(1+\chi(x_{3}))x_{3}^{2}=0.\\ \end{array}\right.

(16)

For a solution $(x_{1},x_{2},x_{3})\in({\mathbb{F}}_{p^{n}}^{*})^{3}$ of (16), let $\mathtt{N}_{(i,j,k)}$ denote the number of solutions $(x_{1},x_{2},x_{3})\in({\mathbb{F}}_{p^{n}}^{*})^{3}$ of the system of equations (16) when $(\chi(x_{1}),\chi(x_{2}),\chi(x_{3}))=(i,j,k),i,j,k\in\{\pm 1\}$ . Next, we examine the solutions of this system (16) in the following eight cases.

(a)

When $(\chi(x_{1}),\chi(x_{2}),\chi(x_{3}))=(1,1,1)$ , the system (16) can be reduced to

$\left\{\begin{array}[]{l}x_{1}-x_{2}+x_{3}=0,\\ x_{1}^{2}-x_{2}^{2}+x_{3}^{2}=0.\\ \end{array}\right.$

Let $y_{i}=\frac{x_{i}}{x_{3}}$ , we shall calculate the number of solutions of

$\left\{\begin{array}[]{l}y_{1}-y_{2}+1=0,\\ y_{1}^{2}-y_{2}^{2}+1=0,\\ \end{array}\right.$

with $\chi(y_{1})=\chi(y_{2})=1$ . Solving the equations above we get $y_{1}=0$ , which contradicts to $\chi(y_{1})=1$ . Therefore, $\mathtt{N}_{(1,1,1)}=0$ .
(b)
Here we discuss that there is exactly one nonsquare element among $x_{1},x_{2},x_{3}$ .
1. i.
  
  When $(\chi(x_{1}),\chi(x_{2}),\chi(x_{3}))=(1,1,-1)$ , (16) can be reduced to
  
  $\left\{\begin{array}[]{l}x_{1}-x_{2}+x_{3}=0,\\ x_{1}^{2}-x_{2}^{2}=0.\\ \end{array}\right.$
  
  Solving the system of equations above we get $x_{3}=0$ , which is a contradiction. Therefore, $\mathtt{N}_{(1,1,-1)}=0$ . Similarly, we have $\mathtt{N}_{(-1,1,1)}=0$ .
2. ii.
  
  When $(\chi(x_{1}),\chi(x_{2}),\chi(x_{3}))=(1,-1,1)$ , the system (16) can be reduced to
  
  $\left\{\begin{array}[]{l}x_{1}+x_{3}=0,\\ x_{1}^{2}+x_{3}^{2}=0.\\ \end{array}\right.$
  
  Since $x_{1}^{2}+x_{3}^{2}=0$ has no solution in $({\mathbb{F}}_{p^{n}}^{*})^{2}$ , we have $\mathtt{N}_{(1,-1,1)}=0$ .
Thus, we have $\mathtt{N}_{(1,1,-1)}=\mathtt{N}_{(1,-1,1)}=\mathtt{N}_{(-1,1,1)}=0$ .
(c)

Here we discuss that there are exactly two nonsquare elements among $x_{1},x_{2},x_{3}$ . When $(\chi(x_{1}),\chi(x_{2}),\chi(x_{3}))=(1,-1,-1)$ , the second equation of (16) becomes $x_{1}^{2}=0$ . It follows that $x_{1}=0$ , a contradiction to $x_{1}\in{\mathbb{F}}_{p^{n}}^{*}$ . Thus, $\mathtt{N}_{(1,-1,-1)}=0$ and similarly, we can get $\mathtt{N}_{(-1,1,-1)}=\mathtt{N}_{(-1,-1,1)}=0$ .

(d)

When $(\chi(x_{1}),\chi(x_{2}),\chi(x_{3}))=(-1,-1,-1)$ , (16) can be reduced to

x_{1}-x_{2}+x_{3}=0.

Set $y_{i}=\frac{x_{i}}{x_{3}}$ , then $\chi(y_{1})=\chi(y_{2})=1$ and we shall consider the equation below for the first step

y_{1}-y_{2}+1=0.

Therefore, $(y_{1},y_{2})$ is a desired solution if and only if

\chi(y_{1})=1~{}\text{and}~{}\chi(y_{1}+1)=1.

And the number of such solutions is

\frac{1}{4}\sum\limits_{y_{1}\in{\mathbb{F}}_{p^{n}}^{*},y_{1}\neq-1}(1+\chi(y_{1}))\cdot(1+\chi(y_{1}+1))=\frac{p^{n}-3}{4}.

Therefore, $\mathtt{N}_{(-1,-1,-1)}=\frac{p^{n}-1}{2}\cdot\frac{p^{n}-3}{4}=\frac{1}{8}(p^{n}-3)(p^{n}-1)$ .

Based on the analysis above, when $x_{4}=0$ , (15) has $\frac{1}{8}(p^{n}-3)(p^{n}-1)$ solutions containing exactly one zero. As $x_{2}$ and $x_{4}$ share the same status in (15), when $x_{2}=0$ , (15) has $\frac{1}{8}(p^{n}-3)(p^{n}-1)$ such solutions. When $x_{3}=0$ , the system (15) can be reduced to

\left\{\begin{array}[]{l}x_{1}-x_{2}-x_{4}=0,\\ (1+\chi(x_{1}))x_{1}^{2}-(1+\chi(x_{2}))x_{2}^{2}-(1+\chi(x_{4}))x_{4}^{2}=0.\end{array}\right.

This system is equivalent to

\left\{\begin{array}[]{l}x_{2}-x_{1}+x_{4}=0,\\ (1+\chi(x_{2}))x_{2}^{2}-(1+\chi(x_{1}))x_{1}^{2}+(1+\chi(x_{4}))x_{4}^{2}=0.\end{array}\right.

By a simple comparison, the number of solutions of (15) when $x_{1}=0$ equals that of (15) when $x_{4}=0$ . Given the equivalent role of $x_{1}$ and $x_{3}$ , the same conclusion holds when any solution features solely $x_{3}=0$ . In short, we have $\mathcal{N}^{(1)}=\frac{1}{2}(p^{n}-3)(p^{n}-1)$ .

In conclusion, we have

	$\displaystyle N_{4}$	$\displaystyle=\sum\limits_{i=0}^{4}\mathcal{N}^{(i)}$
		$\displaystyle=\frac{1}{16}\left((p^{n}-1)\left(p^{2n}+26p^{n}-23+4(\chi(2)-1)\lambda_{p,n}\right)\right)+\frac{1}{2}\left((p^{n}-3)(p^{n}-1)\right)+4(p^{n}-1)+0+1$
		$\displaystyle=\frac{1}{16}\left((p^{n}-1)\left(p^{2n}+34p^{n}+17+4(\chi(2)-1)\lambda_{p,n}\right)\right)+1.$

∎

V-C The differential spectrum of $f_{1}$

Based on the analysis in subsections V-A and V-B, we present the differential spectrum of $f_{1}$ as follows.

Theorem 4.

Let $p^{n}\equiv 3~{}(mod~{}4)$ . The differential spectrum of $f_{1}(x)=x^{2}+x^{\frac{p^{n}+3}{2}}$ over ${\mathbb{F}}_{p^{n}}$ is

	$\displaystyle\mathbb{S}_{f_{1}}=\Big{[}$	$\displaystyle\omega_{0}=\frac{1}{8}\left((p^{n}-1)\left(3p^{n}+3+(\chi(2)-1)\lambda_{p,n}\right)\right),$
		$\displaystyle\omega_{1}=\frac{1}{4}\left((p^{n}-1)\left(2p^{n}-2-(\chi(2)-1)\lambda_{p,n}\right)\right),$
		$\displaystyle\omega_{2}=\frac{1}{8}\left((p^{n}-1)\left(p^{n}+1+(\chi(2)-1)\lambda_{p,n}\right)\right),$
		$\displaystyle\omega_{\frac{p^{n}+1}{4}}=(p^{n}-1),$
		$\displaystyle\omega_{p^{n}}=1\Big{]}.$

Proof.

By Theorem 1, we have the following system of equations pertaining to $f_{1}$

\left\{\begin{array}[]{l}\sum\limits_{i=0}^{q}\omega_{i}=q^{2},\\ \sum\limits_{i=0}^{q}i\omega_{i}=q^{2},\\ \sum\limits_{i=0}^{q}i^{2}\omega_{i}=N_{4}.\end{array}\right.

(17)

It is obvious that $\omega_{q}=1$ . By Theorem 2, we have $\omega_{\frac{p^{n}+1}{4}}=p^{n}-1$ , and $\omega_{i}=0$ for $3\leqslant i\leqslant q-1$ , $i\neq\frac{p^{n}+1}{4}$ . The value of $N_{4}$ was determined in Theorem 3. By substituting certain values, the system (17) can be rewritten as follows

\left\{\begin{array}[]{l}\omega_{0}+\omega_{1}+\omega_{2}=q^{2}-\omega_{\frac{p^{n}+1}{4}}-\omega_{q},\\ \omega_{1}+2\omega_{2}=q^{2}-\left(\frac{p^{n}+1}{4}\right)\omega_{\frac{p^{n}+1}{4}}-q\omega_{q},\\ \omega_{1}+2^{2}\omega_{2}=N_{4}-\left(\frac{p^{n}+1}{4}\right)^{2}\omega_{\frac{p^{n}+1}{4}}q^{2}\omega_{q}.\end{array}\right.

The desired result follows by solving the above system. We finish the proof. ∎

Remark 1.

Note that $n$ is odd when $p^{n}\equiv 3~{}(mod~{}4)$ . Thus, when $p\equiv 7~{}(mod~{}8)$ , we have $\chi(2)=1$ , then the differential spectrum of $f_{1}$ can be expressed without $\lambda_{p,n}$ , which is

\displaystyle\bigg{[}\omega_{0}=\frac{3}{8}\left(p^{2n}-1\right),~{}\omega_{1}=\frac{1}{2}(p^{n}-1)^{2},~{}\omega_{2}=\frac{1}{8}\left(p^{2n}-1\right),~{}\omega_{\frac{p^{n}+1}{4}}=p^{n}-1,~{}\omega_{p^{n}}=1\bigg{]}.

When $p\equiv 3~{}(mod~{}8)$ , we have $\chi(2)=-1$ , then the differential spectrum of $f_{1}$ is

	$\displaystyle\bigg{[}$	$\displaystyle\omega_{0}=\frac{1}{8}\left((p^{n}-1)\left(3p^{n}+3-2\lambda_{p,n}\right)\right),~{}\omega_{1}=\frac{1}{2}\left((p^{n}-1)\left(p^{n}-1+\lambda_{p,n}\right)\right),$
		$\displaystyle\omega_{2}=\frac{1}{8}\left((p^{n}-1)\left(p^{n}+1-2\lambda_{p,n}\right)\right),~{}\omega_{\frac{p^{n}+1}{4}}=p^{n}-1,~{}\omega_{p^{n}}=1\bigg{]}.$

Remark 2.

According to Lemma 2, $\left|\lambda_{p,n}\right|\leqslant 2q^{\frac{1}{2}}$ . With Remark 1 we have $\omega_{2}\geqslant\frac{1}{8}\left[(p^{n}-1)(p^{n}+1-4p^{\frac{n}{2}})\right]$ . This implies $\omega_{2}>0$ if and only if $p^{n}\geqslant 11$ . Consequently,

1.

when $p^{n}=3$ , the differential uniformity of $f_{1}$ is $1$ and based on Table II, the differential spectrum of $f_{1}$ is $[\omega_{0}=2,~{}\omega_{1}=6,~{}\omega_{3}=1]$ , which represents the unique condition of a PN function within class of binomials described in Theorem 4;
2.

when $p^{n}=7$ , the differential uniformity of $f_{1}$ is $2$ and based on Remark 1, the differential spectrum of $f_{1}$ is $[\omega_{0}=18,~{}\omega_{1}=12,~{}\omega_{2}=18,\omega_{7}=1]$ , which represents the unique condition of an APN function within the class of binomials described in Theorem 4;
3.

when $p^{n}\geqslant 11$ , the function in Theorem 4 is exactly a locally APN function.

In what follows, we give some examples to verify our results.

Example 3.

Let $p=3$ , $n=5$ . Then $p^{n}-1=242$ , $\chi(2)=-1$ , $\lambda_{p,n}=2$ . By Theorem 4, the differential spectrum of $f_{1}$ is

\left[\omega_{0}=22022,~{}\omega_{1}=29524,~{}\omega_{2}=7260,~{}\omega_{61}=242,~{}\omega_{243}=1\right],

which coincides with the result calculated directly by MAGMA.

Example 4.

Let $p=7$ , $n=3$ . Then $p^{n}-1=342$ , $\chi(2)=1$ , $\lambda_{p,n}=20$ . By Theorem 4, the differential spectrum of $f_{1}$ is

\left[\omega_{0}=44118,~{}\omega_{1}=58482,~{}\omega_{2}=14706,~{}\omega_{86}=342,~{}\omega_{343}=1\right],

which coincides with the result calculated directly by MAGMA.

Example 5.

Let $p=11$ , $n=3$ . Then $p^{n}-1=1330$ , $\chi(2)=-1$ , $\lambda_{p,n}=58$ . By Theorem 4, the differential spectrum of $f_{1}$ is

\left[\omega_{0}=645050,~{}\omega_{1}=923020,~{}\omega_{2}=202160,~{}\omega_{333}=1330,~{}\omega_{1331}=1\right],

which coincides with the result calculated directly by MAGMA.

VI Concluding remarks

In this paper, we conducted an in-depth investigation of the differential properties of the function $f_{u}(x)=x^{\frac{p^{n}+3}{2}}+ux^{2}$ for $u=\pm 1$ . We expressed the differential spectrum of $f_{\pm 1}$ in terms of quadratic character sums. This complemented the work on the differential properties of the family of the binomial in [8]. In the process of calculating the aimed spectrum, we solved several systems of equations that could be of use in future research or other contexts. Additionally, we extend the properties of the differential spectrum property of a power function to that of any cryptographic function, and it may be used in calculating the differential spectrum of any other polynomial.

References

[1] F. Bao, Y. Xia, S. Chen, C. Li, and T. Helleseth, “The differential spectrum of a power permutation,” Adv. Math. Commun., 2023.
[2] E. Biham and A. Shamir, “Differential cryptanalysis of DES-like cryptosystems,” J. Cryptol., vol. 4, no. 1, pp. 3–72, 1991.
[3] A. Biryukov and C. D. Cannière, Encyclopedia of Cryptography and Security. Springer, 2005.
[4] C. Blondeau, A. Canteaut, and P. Charpin, “Differential properties of power functions,” Int. J. Inf. Coding Theory, vol. 1, no. 2, pp. 149–170, 2010.
[5] ——, “Differential properties of $x\rightarrow x^{2^{t}-1}$ ,” IEEE Trans. Inform. Theory, vol. 57, no. 12, pp. 8127–8137, 2011.
[6] C. Blondeau and L. Perrin, “More differentially 6-uniform power functions,” Des. Codes Cryptogr., vol. 73, no. 2, pp. 487–505, 2014.
[7] L. Budaghyan, M. Calderini, C. Carlet, R. S. Coulter, , and I. Villa, “Constructing APN functions through isotopic shifts,” IEEE Trans. Inform. Theory, vol. 66, no. 8, pp. 5299–5309, 2020.
[8] L. Budaghyan and M. Pal, “Arithmetization-oriented apn permutations,” Des. Codes Cryptogr., 2024.
[9] C. Carlet, P. Charpin, and V. A. Zinoviev, “Codes bent functions and permutations suitable for DES-like cryptosystems,” Des. Codes Cryptogr., vol. 15, no. 2, pp. 125–156, 1998.
[10] P. Charpin and J. Peng, “Differential uniformity and the associated codes of cryptographic functions,” Adv. Math. Commun., vol. 13, no. 4, pp. 579–600, 2019.
[11] S.-T. Choi, S. Hong, J.-S. No, and H. Chung, “Differential spectrum of some power functions in odd prime characteristic,” Finite Fields Appl., vol. 21, pp. 11–29, 2013.
[12] P. Dembowski and T. G. Ostrom, “Planes of order $n$ with collineation groups of order $n^{2}$ ,” Math. Z., vol. 103, no. 2, pp. 239–258, 1968.
[13] H. Dobbertin, T. Helleseth, P. V. Kumar, and H. Martinsen, “Ternary m-sequences with three-valued cross-correlation function: new decimations of welch and niho type,” IEEE Trans. Inform. Theory, vol. 47, no. 4, pp. 1473–1481, 2001.
[14] H. Dobbertin, D. Mills, E. N. Müller, A. Pott, and W. Willems, “APN functions in odd characteristic,” Discrete Math., vol. 267, no. 1-3, pp. 95–112, 2003.
[15] T. Helleseth, C. Rong, and D. Sandberg, “New families of almost perfect nonlinear power functions,” IEEE Trans. Inform. Theory, vol. 45, no. 2, pp. 475–485, 1999.
[16] T. Helleseth and D. Sandberg, “Some power functions with low differential uniformity,” Appl. Algebra Engrg. Comm. Comput., vol. 8, no. 5, pp. 363–370, 1997.
[17] Z. Hu, N. Li, L. Xu, X. Zeng, and X. Tang, “The differential spectrum and boomerang spectrum of a class of locally-APN functions,” Des. Codes Cryptogr., vol. 91, no. 5, pp. 1695–1711, 2023.
[18] S. Jiang, K. Li, Y. Li, and L. Qu, “Differential spectrum of a class of power functions,” J. Cryptology, vol. 9, no. 3, pp. 484–495, 2021.
[19] ——, “Differential and boomerang spectrums of some power permutations,” Cryptogr. Commun., vol. 14, pp. 371–393, 2022.
[20] L. Lei, W. Ren, and C. Fan, “The differential spectrum of a class of power functions over finite fields,” Adv. Math. Commun., vol. 15, no. 3, pp. 525–537, 2021.
[21] R. Lidl and H. Niederreiter, Finite Fields. Cambridge University Press, 1997.
[22] G. Liu, S. Jiang, and K. Li, “On differential spectra of involutions with low differential uniformity over finite fields with even characteristic.” Appl. Algebra Engrg. Comm. Comput., 2024.
[23] Y. Man, Y. Xia, C. Li, and T. Helleseth, “On the differential properties of the power function $x^{p^{m}+2}$ ,” Finite Fields Appl., vol. 84, no. 10, pp. 1–22, 2022.
[24] G. J. Ness and T. Helleseth, “A new family of ternary almost perfect nonlinear mappings,” IEEE Trans. Inform. Theory, vol. 53, no. 7, pp. 2581–2586, 2007.
[25] K. Nyberg, “Perfect nonlinear s-boxes,” Advances in Cryptology-EUROCRYPT 1991, vol. 547, pp. 378–386, 1991.
[26] ——, “Differentially uniform mappings for cryptography,” Advances in Cryptology-EUROCRYPT 1994, vol. 765, pp. 55–64, 1994.
[27] D. Panario, D. Santana, and Q. Wang, “Ambiguity, deficiency and differential spectrum of normalized permutation polynomials over finite fields,” Finite Fields Appl., vol. 47, pp. 330–350, 2017.
[28] T. Pang, N. Li, and X. Zeng, “On the differential spectrum of a differentially 3-uniform power function,” Finite Fields Appl., vol. 87, 2023.
[29] J. Peng, C. H. Tan, and Q. Wang, “A new family of differentially 4-uniform permutations over ${\mathbb{F}}_{2}^{2m}$ for odd $k$ ,” Sci. China Math., vol. 59, no. 6, pp. 1221–1234, 2016.
[30] J. H. Silverman, The arithmetic of elliptic curves, 2nd ed., ser. Graduate Texts in Mathematics. Springer, Dordrecht, 2009, vol. 106.
[31] X. Tan and H. Yan, “Differential spectrum of a class of APN power functions,” Des. Codes Cryptogr., vol. 91, pp. 2755–2768, 2023.
[32] C. Tang, C. Ding, and M. Xiong, “Codes differentially $\delta$ -uniform functions and $t$ -designs,” IEEE Trans. Inform. Theory, vol. 66, no. 6, pp. 3691–3703, 2020.
[33] Z. Tu, N. Li, Y. Wu, X. Zeng, X. Tang, and Y. Jiang, “On the differential spectrum and the apcn property of a class of power functions over finite fields,” IEEE Trans. Inform. Theory, vol. 69, no. 1, pp. 582–597, 2023.
[34] Y. Xia, F. Bao, S. Chen, C. Li, and T. Helleseth, “More differential properties of the Ness-Helleseth function,” IEEE Trans. Inform. Theory, vol. 70, no. 8, pp. 6076–6090, 2024.
[35] Y. Xia, X. Zhang, C. Li, and T. Helleseth, “The differential spectrum of a ternary power function,” Finite Fields Appl., vol. 64, pp. 1–16, 2020.
[36] Y. Xia, C. Li, F. Bao, S. Chen, and T. Helleseth, “Further investigation on differential properties of the generalized ness-helleseth function,” Des. Codes Cryptogr., 2024.
[37] X. Xie, S. Mesnager, N. Li, D. He, and X. Zeng, “On the niho type locally-APN power functions and their boomerang spectrum,” IEEE Trans. Inform. Theory, vol. 69, no. 6, pp. 4056–4064, 2023.
[38] M. Xiong and H. Yan, “A note on the differential spectrum of a differentially 4-uniform power function,” Finite Fields Appl., vol. 48, pp. 117–125, 2017.
[39] M. Xiong, H. Yan, and P. Yuan, “On a conjecture of differentially 8-uniform power functions,” Des. Codes Cryptogr., vol. 86, no. 8, pp. 1601–1621, 2018.
[40] G. Xu, X. Cao, and S. Xu, “Constructing new APN functions and bent functions over finite fields of odd characteristic via the switching method,” Cryptogr. Commun., vol. 8, no. 1, pp. 155–171, 2016.
[41] H. Yan and C. Li, “Differential spectra of a class of power permutations with characteristic 5,” Des. Codes Cryptogr., vol. 89, no. 6, pp. 1181–1191, 2021.
[42] H. Yan and Z. Li, “A note on the differential spectrum of a class of power mappings with niho exponent,” Cryptogr. Commun., vol. 14, no. 5, pp. 1081–1089, 2022.
[43] H. Yan, S. Mesnager, and X. Tan, “The complete differential spectrum of a class of power permutations over odd characteristic finite fields,” IEEE Trans. Inform. Theory, vol. 69, no. 11, pp. 7426–7438, 2023.
[44] ——, “On a class of APN power functions over odd characteristic finite fields: Their differential spectrum and c-differential properties,” Discrete Math., vol. 347, no. 4, 2024.
[45] H. Yan, Y. Xia, C. Li, T. Helleseth, M. Xiong, and J. Luo, “The differential spectrum of the power mapping $x^{p^{n}-3}$ ,” IEEE Trans. Inform. Theory, vol. 68, no. 8, pp. 5535–5547, 2022.
[46] H. Yan, Z. Zhou, J. Weng, J. Wen, T. Helleseth, and Q. Wang, “Differential spectrum of kasami power permutations over odd characteristic finite fields,” IEEE Trans. Inform. Theory, vol. 65, no. 10, pp. 6819–6826, 2019.
[47] Z. Zha, S. S. L. Hu, and Y. Sun, “New constructions of APN polynomial functions in odd characteristic,” Appl. Algebra Eng. Commun. Comput., vol. 25, no. 4, pp. 249–263, 2014.
[48] Z. Zha and X. Wang, “Almost perfect nonlinear power functions in odd characteristic,” IEEE Trans. Inform. Theory, vol. 57, no. 7, pp. 4826–4832, 2011.

A note on the differential spectrum of a class of locally APN functions

Abstract

I Introduction

Definition 1.

II On Quadratic Character Sums

Lemma 1.

Lemma 2.

Example 1.

Example 2.

Lemma 3.

Proof.

III The properties of the differential spectrum of a general cryptographic function over finite field

Definition 2.

Theorem 1.

Proof.

IV On the number of solutions of certain systems of equations

Lemma 4.

Proof.

Lemma 5.

Proof.

Lemma 6.

Proof.

V The differential spectrum of f1f_{1}

V-A The differential uniformity of f1f_{1}

Theorem 2.

Proof.

V-B The value of N4N_{4} pertaining to f1f_{1}

Theorem 3.

Proof.

V-C The differential spectrum of f1f_{1}

Theorem 4.

Proof.

Remark 1.

Remark 2.

Example 3.

Example 4.

Example 5.

VI Concluding remarks

References

V The differential spectrum of $f_{1}$

V-A The differential uniformity of $f_{1}$

V-B The value of $N_{4}$ pertaining to $f_{1}$

V-C The differential spectrum of $f_{1}$