# A new construction of differentially 4-uniform permutations over
$F_{2^{2k}}$

Jie Peng J. Peng is with the School of Mathematics and Statistics, Central
China Normal University, Luoyu Road #152, Wuhan 430079, P. R. China (e-mail:
jiepeng@mail.ccnu.edu.cn). Now he is visiting Temasek Laboratories, National
University of Singapore. Chik How Tan and Qichun Wang C. H. Tan and Q. C. Wang
are with Temasek Laboratories, National University of Singapore, 5A
Engineering Drive 1, 09-02, 117411 Singapore. (e-mails:
{tsltch,tslwq}@nus.edu.sg).

###### Abstract

Permutations over $F_{2^{2k}}$ with low differential uniform, high algebraic
degree and high nonlinearity are of great cryptographical importance since
they can be chosen as the substitution boxes (S-boxes) for many block ciphers.
A well known example is that the Advanced Encryption Standard (AES) chooses a
differentially 4-uniform permutation, the multiplicative inverse function, as
its S-box. In this paper, we present a new construction of differentially
4-uniformity permutations over even characteristic finite fields and obtain
many new CCZ-inequivalent functions. All the functions are switching neighbors
in the narrow sense of the multiplicative inverse function and have the
optimal algebraic degree and high nonlinearity.

Keywords: Differentially 4-uniform function, Permutation, Algebraic degree,
Nonlinearity.

##  1 Introduction

An S-box with $n$ input bits and $m$ output bits is an $(n,m)$-function
$f:F_{2^{n}}\rightarrow F_{2^{m}}$. For ease of implementation, they are
usually chosen to be permutations over $F_{2^{n}}$ for even integer $n$. The
concept of differential uniformity is used to measure the ability of the
function to resist the so called differential attack on the design of block
encryption algorithm, which was presented by Biham and Shamir [1]. The value
of differential uniformity of S-boxes should be as low as possible. It is well
known that the minimal value of differential uniformity equals 2 for an
$(n,n)$-function, and if this value is achieved, then the function is called
almost perfect nonlinear (APN). Several classes of APN functions are found
when $n$ is odd (see [2, 8] and the references therein). But when $n$ is even,
only one sporadic example $x^{3}+Tr(x^{9})$ of APN permutation for $n=6$ has
been found in reference [7] and it is still an open problem whether there
exist APN permutations for even $n\geq 8$. However, S-boxes are often required
to be permutations over finite fields with even characteristic for efficient
software implementation. Therefore, differentially 4-uniform permutations
become ideal candidates for S-boxes. For example, AES chooses the
multiplicative inverse function $x^{2^{n}-2}$ as its S-box, which is
differentially 4-uniform with optimal algebraic degree and known maximum
nonlinearity. Up to now, several classes of differentially 4-uniform
permutations over finite fields with even characteristic have been presented,
which are listed below for the readers’ convenience.

  * 1)

Gold function [9]: $x^{2^{i}+1}$, where $n=2k$, $k$ is odd and $\gcd(n,i)=2$;

  * 2)

Kasami function [10]: $x^{2^{2i}-2^{i}+1}$, where $n=2k$, $k$ is odd and
$\gcd(n,i)=2$;

  * 3)

Multiplicative inverse function [16]: $x^{-1}$ (as usual $0^{-1}:=0$), where
$n$ is even;

  * 4)

Bracken-Leander function [3]: $x^{2^{2k}+2^{k}+1}$, where $n=4k$ and $k$ is
odd;

  * 5)

Binomial function [4]: $\alpha x^{2^{s}+1}+\alpha^{2^{k}}x^{2^{-k}+2^{k+s}}$,
where $n=3k$, $k$ even, $k/2$ odd, $\gcd(n,s)=2$, $3|k+s$ and $\alpha$ is a
primitive element of $F_{2^{n}}$;

  * 6)

Qu-Tan-Tan-Li function [17]: The 1st class: $x^{-1}+Tr(x+(x+1)^{-1})$; The 2nd
class: $x^{-1}+Tr(x^{-d}+(x^{-1}+1)^{d})$, where $d=3(2^{t}+1)$ and $2\leq
t\leq n/2-1$;

  * 7)

Zha-Hu-Sun function [21]: The 1st class: $x^{-1}+t(x^{2^{s}}+x)^{2^{n}-1}+t$,
where $t\in F_{2^{s}}$, $s|n$, and $s$ is even, or $s=1,3$ and $n/2$ is odd;
The 2nd class:
$t_{1}x^{-1}+(t_{1}+1)x^{-1}(x^{2^{s}}+x)^{2^{n}-1}+t_{2}(x^{2^{s}}+x)^{2^{n}-1}+t_{2}$,
where $t_{1},t_{2}\in F_{2^{s}}$ with $Tr(t_{1}^{-1})=1$, $s|n$, $s$ is even
and $n/s$ is odd.

  * 8)

Tang-Carlet-Tang function [19]: $(x+\delta_{T}(x))^{-1}$, where $\delta_{T}$
is the indicator function of the set $T\subseteq F_{2^{2k}}$ with $k\geq 3$,
which satisfies

(1) if $x\in T$, then $x+1\in T$, and

(2) if $x\in T$, then
$Tr\bigg{(}\frac{1}{x}\bigg{)}=Tr\bigg{(}\frac{1}{x+1}\bigg{)}=1$.

Furthermore, functions used as S-boxes should have other good cryptographic
properties as well in order to resist other types of attacks. For instance, to
resist the higher order differential attack [11] and linear attack [15], the
algebraic degree and nonlinearity of S-boxes should be as high as possible. It
is known that for an $(n,n)$ permutation polynomial, the highest possible
degree is $n-1$. However, as is mentioned in some papers (such as [17, 19]),
though the first 5 classes of functions all have the known highest
nonlinearity, except the Kasami and multiplicative inverse functions, the
algebraic degrees of the other 3 classes are only 2 or 3, which are too low to
be used as S-boxes. Moreover, only the multiplicative inverse function exists
for any even integer $n$. Though the multiplicative inverse function has
optimal algebraic degree, and has been used as the S-box of the AES, it may
also risk a threat for algebraic attacks [19]. Therefore, it is urgent to find
more classes of differentially 4-uniform permutations, which have high
nonlinearity and algebraic degree simultaneously.

A powerful secondary construction method called switching method was presented
to obtain new APN functions by changing some of the coordinate functions of a
given function. For instance, the famous APN function $x^{3}+Tr(x^{9})$ was
obtained via changing one of the coordinate function of the Kasami function.
Besides, this method can be used to construct cryptographic significant
differentially 4-uniform permutations as well (see [17, 19, 20, 21] and the
references therein). In [21], the authors succeeded to construct
differentially 4-uniform permutations via modifying the multiplicative inverse
function on some subfield of $F_{2^{n}}$. In [17], it was proved that given a
so called preferred function $R(x)$, then $x^{-1}+Tr(R(x^{-1})+R(x^{-1}+1))$
is a differentially 4-uniform permutation. This construction was further
investigated in [18]. In [19], the authors presented a new construction by
permuting the multiplicative inverse function, which could produce many CCZ-
inequivalent differentially 4-uniform permutations. The functions in these
references were proved to have optimal algebraic degree and high nonlinearity.
The purpose of this paper is to construct more classes of differentially
4-uniform permutations with high nonlinearity and algebraic degree for any
even integer $n\geq 6$, which can provide more choices for S-boxes.

In [17], the authors obtained the roots $x_{1},x_{2}$ of a quadratic equation
$x^{2}+\frac{1}{b}x+\frac{1}{b(b+1)}=0$ given that it did have a solution, and
used some properties of $x_{1},x_{2}$ to help construct differentially
4-uniform functions. In this paper, we study and get some relationships on the
values $Tr(x)$ and $Tr\bigg{(}\frac{1}{x+1}\bigg{)}$ of these two roots. Based
on that, we modify the multiplicative inverse function on some subsets of
$F_{2^{n}}$ and obtain a new construction of differentially 4-uniform
permutations. Moreover, all the newly discovered functions have optimal
algebraic degree and high nonlinearity.

The rest of this paper is organized as follows. In the next section we give
some basic knowledge and results. In section 3 we present our new construction
of differentially 4-uniform permutations. And we analyze the other
cryptography of the new functions in Section 4. Finally, Section 5 concludes
the paper.

##  2 Preliminaries

An $(n,n)$-function $F:F_{2^{n}}\rightarrow F_{2^{n}}$ can be uniquely
represented as a polynomial

$\displaystyle F(x)=\sum_{i=0}^{2^{n}-1}a_{i}x^{i},a_{i}\in F_{2^{n}}.$

We denote the algebraic degree of $F$ by $\deg(F)$, which is defined to be the
maximum 2-weight of $i$ (i.e., the number of 1’s in the 2-adic representation
of $i$) such that $a_{i}\neq 0$. $F$ is called an affine function if
$\deg(F)\leq 1$. It is well known that $\deg(F)\leq n-1$ when $F$ is a
permutation over $F_{2^{n}}$. And if the equality holds, we say $F$ has
optimal algebraic degree.

Let $Tr_{k}^{n}(x)$ be the trace map from $F_{2^{n}}$ to its subfield
$F_{2^{k}}$, i.e., $Tr_{k}^{n}(x)=\sum_{i=0}^{n/k-1}x^{2^{ik}}$. And the
absolute trace function ($k=1$) is denoted by $Tr(x)$ for simplicity.

For an $(n,n)$-function $F$, its Walsh transform is defined by

$\displaystyle F^{\mathcal{W}}(a,b):=\sum_{x\in
F_{2^{n}}}(-1)^{Tr(ax+bF(x))},a\in F_{2^{n}},b\in F_{2^{n}}^{*}.$

And the multisets $\\{*~{}F^{\mathcal{W}}(a,b)~{}|~{}(a,b)\in F_{2^{n}}\times
F_{2^{n}}^{*}~{}*\\}$ and $\\{*~{}|F^{\mathcal{W}}(a,b)|~{}|~{}(a,b)\in
F_{2^{n}}\times F_{2^{n}}^{*}~{}*\\}$ are called Walsh spectrum and extended
Walsh spectrum of $F$. The nonlinearity of $F$, denoted by $NL(F)$, is related
to its extended Walsh spectrum:

$\displaystyle NL(F)=2^{n-1}-\frac{1}{2}\max_{(a,b)\in F_{2^{n}}\times
F_{2^{n}}^{*}}|F^{\mathcal{W}}(a,b)|.$

When $n$ is odd, it has been proved that $NL(F)\leq
2^{n-1}-2^{\frac{n-1}{2}}$; and when $n$ is even, $2^{n-1}-2^{\frac{n}{2}}$ is
the maximum known nonlinearity, and it is conjectured that $NL(F)\leq
2^{n-1}-2^{\frac{n}{2}}$. It is well known that the inverse function has the
known maximum nonlinearity. Particularly, its Walsh spectrum is characterized
by the following lemma.

Lemma 2.1. [12] For any positive integer $n$ and any $(a,b)\in F_{2^{n}}\times
F_{2^{n}}^{*}$, the value of $|\sum_{x\in F_{2^{n}}}(-1)^{Tr(ax+bx^{-1})}|$
can be any integer divisible by 4 in the range $[-2^{n/2+1}+1,2^{n/2+1}+1]$.

Now we give the definition of the differential uniformity of a function $F$.

Definition 2.2. For an $(n,n)$-function $F$ and $(a,b)\in F_{2^{n}}^{*}\times
F_{2^{n}}$, we denote by $\delta_{F}(a,b)$ the number of solutions of the
equation $F(x+a)+F(x)=b$. The multiset $\\{*~{}\delta_{F}(a,b)~{}|~{}(a,b)\in
F_{2^{n}}^{*}\times F_{2^{n}}~{}*\\}$ is called the differential spectrum of
$F$, and the maximum value $\delta$ of this set is called the differential
uniformity of $F$, or call $F$ differentially $\delta$-uniform.

Particularly, $F$ is called almost perfect nonlinear (APN) if $\delta=2$. Note
that the possible minimum value of $\delta$ equals 2 when $n$ is even, since
both or neither $x$ and $x+a$ are solutions of $F(x+a)+F(x)=b$, for any $x\in
F_{2^{n}}$.

Dillon proposed the switching method to obtain differentially low uniform
functions from the known ones [6]. Some new APN functions were found following
this method [5, 8]. For a permutation $F$ of $F_{2^{n}}$ and $\nu\in
F_{2^{n}}$, the functions with the form $F(x)+\nu f(x)$, where $f$ is a
Boolean function (that is, an $(n,1)$-function), are called switching
neighbors of $F$ in the narrow sense. Recently, some new differentially
4-uniform permutations were found in the switching neighbors of the
multiplicative inverse function in the narrow sense. For instance, the Qu-Tan-
Tan-Li function [17], the compositional inverse of the Tang-Carlet-Tang
function [19] and the first class of the Zha-Hu-Sun function [21] listed
before are all of this type. In this paper, we shall present a new class of
such differentially 4-uniform permutations.

Let $F,G$ be two $(n,n)$-functions. $F$ and $G$ are called to be extended
affine (EA) equivalent if $F=L_{2}\circ G\circ L_{1}+A$ for some affine
permutations $L_{1},L_{2}$ over $F_{2^{n}}$ and some affine function $A$. $F$
and $G$ are called to be Carlet-Charpin-Zinoviev (CCZ) equivalent if there
exists some affine automorphism $L=(L_{1},L_{2})$ of $F_{2^{n}}\times
F_{2^{n}}$, where $L_{1},L_{2}:F_{2^{n}}\times F_{2^{n}}\rightarrow F_{2^{n}}$
are affine functions, such that $y=G(x)$ if and only if
$L_{2}(x,y)=F(L_{1}(x,y))$. It is well known that EA equivalence implies CCZ
equivalence, but not for the converse. Moreover, CCZ equivalence and EA
equivalence preserve the extended Walsh spectrum and the differential
spectrum, and EA equivalence also preserves the algebraic degree when $n\geq
2$.

For a permutation $G:F_{2^{n}}\rightarrow F_{2^{n}}$, its compositional
inverse function $F$ is defined by $G\circ F=F\circ G=id,$ where $id$
represents the identity mapping on $F_{2^{n}}$. And it has been proved that
$G$ and $F$ are CCZ-equivalent.

Below we present some lemmas which are needed in the sequel.

Lemma 2.3.[14] Let $n$ be a positive integer. For any $a,b,c\in
F_{2^{n}},ab\neq 0,$ the equation

$\displaystyle ax^{2}+bx+c=0$

has 2 solutions in $F_{2^{n}}$ if and only if $tr_{1}^{n}(ac/b^{2})=0$.

Lemma 2.4.[12] Let $b\in F_{2^{n}}\setminus F_{2}$. Then
$Tr\bigg{(}\frac{1}{b}\bigg{)}=0$ if and only if there exists some $\alpha\in
F_{2^{n}}^{*}$ such that $b=\alpha+\alpha^{-1}$.

Lemma 2.5.[17] If $b=1+\alpha+\alpha^{-1}$ for some $\alpha\in F_{2^{n}}^{*}$,
then the equation

$\displaystyle x^{2}+\frac{1}{b}x+\frac{1}{b(b+1)}=0$

has two roots

$\displaystyle
x_{1}=\frac{1}{1\\!+\\!\alpha\omega\\!+\\!(\alpha\omega)^{-1}},~{}x_{2}=\frac{1}{1\\!+\\!\alpha\omega^{2}\\!+\\!(\alpha\omega^{2})^{-1}},$

where $\omega\in F_{2^{n}}$ with order 3.

##  3 New differentially 4-uniform permutations

Let $n\geq 6$ be an even integer and $V\subseteq F_{2^{n}}$ be a union of some
pairs of elements $x$ and $\frac{x}{x+1}$ such that
$Tr(x)=Tr\bigg{(}\frac{1}{x+1}\bigg{)}=1$ (here $V$ can be empty).

Let

$\displaystyle W=\bigg{\\{}x\in
F_{2^{n}}~{}\bigg{|}~{}Tr(x)=Tr\bigg{(}\frac{1}{x+1}\bigg{)}=0\bigg{\\}}$

and $U=V\cup W$. Define an $(n,n)$-function $G$ on $F_{2^{n}}$ as follows:

$\displaystyle G(x)=\begin{cases}x^{-1}+1,x\in U;\\\ x^{-1},x\in
F_{2^{n}}\setminus U.\end{cases}$

Then the function $G$ can be written as $G(x)=x^{-1}+\delta_{U}(x),$ where

$\displaystyle\delta_{U}(x)=\begin{cases}1,x\in U;\\\ 0,x\in
F_{2^{n}}\setminus U.\end{cases}$

Proposition 3.1. The function $G(x)$ is a permutation over $F_{2^{n}}$.

Proof. Let

$\displaystyle\varphi(x)=\begin{cases}\frac{1}{x^{-1}\\!+\\!1},x\in U;\\\
x,x\in F_{2^{n}}\setminus U.\end{cases}$

Note that we have

$\displaystyle\frac{1}{x^{-1}\\!+\\!1}=\begin{cases}1,x=0;\\\
\frac{x}{x+1},x\neq 0\end{cases}$

and thus

$\displaystyle
Tr\bigg{(}\frac{1}{x^{-1}\\!+\\!1}\bigg{)}=Tr\bigg{(}\frac{1}{x\\!+\\!1}\bigg{)},$
$\displaystyle
Tr\bigg{(}\frac{1}{\frac{1}{x^{-1}\\!+\\!1}\\!+\\!1}\bigg{)}=Tr(x\\!+\\!1)=Tr(x),$

then it is easy to see that $\frac{1}{x^{-1}+1}\in U$ for any $x\in U$. Hence
$\varphi$ permutes $U$ and $F_{2^{n}}\setminus U$ respectively. Therefore,
$\varphi(x)$ is a permutation over $F_{2^{n}}$, and thus
$G(x)=\varphi(x)^{-1}$ is also a permutation over $F_{2^{n}}$. This completes
the proof.

Denote by $V_{M}$ the union of all possible sets $V$, which is the largest
such set. Then it is clear that

$\displaystyle V_{M}=\bigg{\\{}x\in
F_{2^{n}}~{}\bigg{|}~{}Tr(x)=Tr\bigg{(}\frac{1}{x\\!+\\!1}\bigg{)}=1\bigg{\\}}.$

Remark 3.2. Let $U=V_{M}\cup W$, then it is easy to see that
$G_{M}(x)=x^{-1}+\delta_{U}(x)=x^{-1}+Tr(x+(x+1)^{-1})+1$, which is a
translation of the 1st class function in [17].

Remark 3.3. Let $U=V$, then the function $G=x^{-1}+\delta_{U}(x)$ is the
compositional inverse of some function constructed by [19].

Now we consider the differentially uniformity of function $G$. For any
$(a,b)\in F_{2^{n}}^{*}\times F_{2^{n}}$, the equation

$\displaystyle G(x+a)+G(x)=b$ (1)

is equivalent to the following two cases:

Case 1: Both or neither of $x$ and $x+a$ belong to $U$. In this case we get

$\displaystyle x^{-1}+(x+a)^{-1}=b,$ (2)

Case 2: Exactly one of $x$ and $x+a$ belongs to $U$. In this case we get

$\displaystyle x^{-1}+(x+a)^{-1}=b+1.$ (3)

Moreover, if $x\neq 0,a$, then Equation (2) is equivalent to

$\displaystyle bx^{2}+abx+a=0,$ (4)

and Equation (3) is equivalent to

$\displaystyle(b+1)x^{2}+a(b+1)x+a=0.$ (5)

To prove that the function $G(x)=x^{-1}+\delta_{U}(x)$ is differentially
4-uniform, we need the following results.

Lemma 3.4. Let $n$ be an even integer, then
$Tr\bigg{(}\frac{1}{x+1}\bigg{)}=0$ if and only if
$x=\frac{1}{1+\alpha+\alpha^{-1}}$ for some $\alpha\in F_{2^{n}}$, i.e.,

$\displaystyle\bigg{\\{}\frac{1}{1\\!+\\!\alpha\\!+\\!\alpha^{-1}}~{}\bigg{|}~{}\alpha\in
F_{2^{n}}\bigg{\\}}=\bigg{\\{}x\in
F_{2^{n}}~{}\bigg{|}~{}Tr\bigg{(}\frac{1}{x\\!+\\!1}\bigg{)}=0\bigg{\\}}.$

Proof. On the one hand, for any $\frac{1}{1+\alpha+\alpha^{-1}}$ in the left
hand side set, one calculates

$\displaystyle
Tr\bigg{(}\frac{1}{\frac{1}{1\\!+\\!\alpha\\!+\\!\alpha^{-1}}\\!+\\!1}\bigg{)}$
$\displaystyle=$ $\displaystyle
Tr\bigg{(}\frac{1\\!+\\!\alpha\\!+\\!\alpha^{-1}}{\alpha\\!+\\!\alpha^{-1}}\bigg{)}$
$\displaystyle=$ $\displaystyle
Tr(1)\\!+\\!Tr\bigg{(}\frac{1}{\alpha\\!+\\!\alpha^{-1}}\bigg{)}$
$\displaystyle=$ $\displaystyle 0,$

where the last identity is due to $n$ being even and Lemma 2.4. So the left
hand side set is contained in the right hand side set.

On the other hand, note that both sets must have the same number of elements,
i.e. $2^{n-1}$, since the mapping $x+x^{-1}:F_{2^{n}}\rightarrow F_{2^{n}}$ is
2-to-1. Hence the two sets must be the same. This completes the proof.

Proposition 3.5. With the preceding notations as in Lemma 2.5, one has:

(1)
$Tr\bigg{(}\frac{1}{x_{1}+1}\bigg{)}=Tr\bigg{(}\frac{1}{x_{2}+1}\bigg{)}=0$,
and

(2)
$Tr(x_{1})+Tr(x_{2})=Tr\bigg{(}\frac{1}{1+\alpha+\alpha^{-1}}\bigg{)}=Tr(b^{-1})$.

Proof. (1) can be immediately obtained by Lemma 3.4.

For (2), one computes

$\displaystyle Tr(x_{1})\\!+\\!Tr(x_{2})$ $\displaystyle=$ $\displaystyle
Tr\bigg{(}\frac{1}{1\\!+\\!\alpha\omega\\!+\\!(\alpha\omega)^{-1}}\\!+\\!\frac{1}{1\\!+\\!\alpha\omega^{2}\\!+\\!(\alpha\omega^{2})^{-1}}\bigg{)}$
$\displaystyle=$ $\displaystyle
Tr\bigg{(}\frac{1}{1\\!+\\!\alpha\\!+\\!\alpha^{-1}}\bigg{)}$ $\displaystyle=$
$\displaystyle Tr(b^{-1}),$

where the second identity is based on

$\displaystyle\frac{1}{1\\!+\\!\alpha\omega\\!+\\!(\alpha\omega)^{-1}}\\!+\\!\frac{1}{1\\!+\\!\alpha\omega^{2}\\!+\\!(\alpha\omega^{2})^{-1}}=\frac{1}{1\\!+\\!\alpha\\!+\\!\alpha^{-1}}.$

This completes the proof.

Now we give our main result.

Theorem 3.6. The permutation $G$ is differentially 4-uniform.

Proof. Need to prove that Equation (1) has at most 4 solutions.

Firstly, suppose $a\in U$. Then we have
$Tr(a)=Tr\bigg{(}\frac{1}{a+1}\bigg{)}=1$ or
$Tr(a)=Tr\bigg{(}\frac{1}{a+1}\bigg{)}=0$, according to $a\in V$ or $a\in W$
respectively.

When $ab=1$, then $0,a$ are two solutions of Case 1, and Case 1 has at most 4
solutions. In Case 2, Equation (3) is equivalent to Equation (5), we have

$\displaystyle x^{2}+ax+\frac{a^{2}}{a+1}=0,$

or equivalently

$\displaystyle x^{2}+\frac{1}{b}x+\frac{1}{b(b+1)}=0.$

If $a\in V$, then according to Lemma 2.3, Equation (5) has no root, since
$Tr\bigg{(}\frac{a^{2}}{a+1}\cdot\frac{1}{a^{2}}\bigg{)}=Tr\bigg{(}\frac{1}{a+1}\bigg{)}=1$.
Else if $a\in W$, then $Tr(a)=Tr\bigg{(}\frac{1}{a+1}\bigg{)}=0$, equivalently
$Tr\bigg{(}\frac{1}{b}\bigg{)}=Tr\bigg{(}\frac{b}{b+1}\bigg{)}=Tr\bigg{(}\frac{1}{b+1}\bigg{)}=0$,
and thus Equation (5) has two roots. Moreover, by Lemma 2.4 there exists some
$\alpha\in F_{2^{n}}^{*}$ such that

$\displaystyle b=1+\alpha+\alpha^{-1}.$

According to Lemma 2.5, the two roots of Equation (5) are exactly

$\displaystyle
x_{1}=\frac{1}{1\\!+\\!\alpha\omega\\!+\\!(\alpha\omega)^{-1}},~{}x_{2}=x_{1}\\!+\\!a=\frac{1}{1\\!+\\!\alpha\omega^{2}\\!+\\!(\alpha\omega^{2})^{-1}},$

where $\omega\in F_{2^{n}}$ with order 3. By Proposition 3.5 we have

$\displaystyle
Tr\bigg{(}\frac{1}{x_{1}\\!+\\!1}\bigg{)}=Tr\bigg{(}\frac{1}{x_{2}\\!+\\!1}\bigg{)}=0,$

and

$\displaystyle Tr(x_{1})\\!+\\!Tr(x_{2})=Tr(b^{-1})=Tr(a)=0.$

As a result, we get $Tr(x_{1})=Tr(x_{2})$, thus $x_{1}$ and $x_{2}$ are not
solutions of Case 2. In fact, if $Tr(x_{1})=Tr(x_{2})=0$, then both $x_{1}$
and $x_{2}$ belong to $U$. While if $Tr(x_{1})=Tr(x_{2})=1$, then neither of
$x_{1}$ and $x_{2}$ belongs to $U$.

When $ab\neq 1$, then Equations (2) and (3) are equivalent to Equations (4)
and (5). Therefore, Equation (1) has at most 4 solutions, since the sum of
numbers of solutions of Equations (4) and (5) is at most 4.

Secondly, suppose $a\not\in U$.

When $a(b+1)=1$, then $0,a$ are two solutions of Case 2, and Case 2 has at
most 4 solutions. In Case 1, Equation (2) is equivalent to Equation (4), we
have

$\displaystyle x^{2}+ax+\frac{a^{2}}{a+1}=0,$

or equivalently

$\displaystyle x^{2}+\frac{1}{b+1}x+\frac{1}{b(b+1)}=0.$

If $Tr\bigg{(}\frac{1}{a+1}\bigg{)}=1$, then according to Lemma 2.3, Equation
(4) has no root, since
$Tr\bigg{(}\frac{a^{2}}{a+1}\cdot\frac{1}{a^{2}}\bigg{)}=Tr\bigg{(}\frac{1}{a+1}\bigg{)}=1$.
Else if $Tr\bigg{(}\frac{1}{a+1}\bigg{)}=0$, equivalently
$Tr\bigg{(}\frac{1}{b}\bigg{)}=0$, then Equation (4) has two roots, and it
holds $Tr(a)=1$, since $a\not\in W$.

Moreover, by Lemma 2.4 there exists some $\alpha\in F_{2^{n}}^{*}$ such that

$\displaystyle b=\alpha+\alpha^{-1}.$

According to Lemma 2.5, the two roots of Equation (4) are exactly

$\displaystyle
x_{1}=\frac{1}{1\\!+\\!\alpha\omega\\!+\\!(\alpha\omega)^{-1}},~{}x_{2}=\frac{1}{1\\!+\\!\alpha\omega^{2}\\!+\\!(\alpha\omega^{2})^{-1}}.$

Again from Proposition 3.5 we can get

$\displaystyle
Tr\bigg{(}\frac{1}{x_{1}\\!+\\!1}\bigg{)}=Tr\bigg{(}\frac{1}{x_{2}\\!+\\!1}\bigg{)}=0,$

and also

$\displaystyle Tr(x_{1})+Tr(x_{2})=Tr((b+1)^{-1})=Tr(a)=1.$

As a result, one has $Tr(x_{1})=Tr(x_{2})+1$, which indicates that exactly one
of $x_{1}$ and $x_{2}$ belongs to $U$, hence $x_{1}$ and $x_{2}$ are not
solutions of Case 1. Therefore, Equation (1) has at most 4 solutions.

When $a(b+1)\neq 1$, then Equations (2) and (3) are equivalent to Equations
(4) and (5). Therefore, Equation (1) has at most 4 solutions, since the sum of
numbers of solutions of Equations (4) and (5) is at most 4.

##  4 Other Cryptographic Properties

###  4.1 Enumeration

First we give the following estimation on $|V_{M}|$ and $|W|$, the cardinality
of the sets $V_{M}$ and $W$.

Proposition 4.1. For even $n\geq 6$, we have
$2^{n-2}-2^{n/2-1}\leq|V_{M}|=|W|\leq 2^{n-2}+2^{n/2-1}$.

Proof. On the one hand, note that both $Tr(x)$ and $Tr((x+1)^{-1})$ are
balanced Boolean functions, then we immediately get $|V_{M}|=|W|$, since for
any two balanced Boolean functions $f,g:F_{2^{n}}\rightarrow F_{2}$, it holds
${\rm wt}(fg)={\rm wt}((f+1)(g+1))$, where ${\rm wt}(f)$ represents the
Hamming weight of $f$.

On the other hand, we have

$\displaystyle V_{M}\cup W=\bigg{\\{}x\in
F_{2^{n}}~{}\bigg{|}~{}Tr(x)+Tr\bigg{(}\frac{1}{x+1}\bigg{)}=0\bigg{\\}},$

and by Lemma 2.1, one gets that $|\sum_{x\in
F_{2^{n}}}(-1)^{Tr(x+x^{-1})}|\leq 2^{n/2+1}$, or equivalently that
$|\sum_{x\in F_{2^{n}}}(-1)^{Tr(x)+Tr((x+1)^{-1})}|\leq 2^{n/2+1}$ by changing
$x$ to $x+1$. Therefore, we obtain

$\displaystyle 2^{n-1}-2^{n/2}\leq|V_{M}|+|W|\leq 2^{n-1}+2^{n/2}.$

Combining with $|V_{M}|=|W|$, then the result follows. This completes the
proof.

It is obvious then from Proposition 4.1 that in our construction the
cardinality of $U$ satisfies $2^{n-2}-2^{n/2-1}\leq|U|\leq 2^{n-1}+2^{n/2}$.
And since the size of $V$ can be any even integer ranging from 0 to $|V_{M}|$,
so according to Proposition 4.1, there are at least $2^{2^{n-3}-2^{n/2-2}}$
different sets $V$, and thus there are at least $2^{2^{n-3}-2^{n/2-2}}$
different sets $U$. Moreover, in [19] the authors computed the exact numbers
of sets $V$ by computer for even integer $n$ ranging from 6 to 20. Therefore,
we can also obtain the corresponding numbers of sets $U$ in our construction
for even integer $n$ ranging from 6 to 20, and we list them in Table 1.

Table 1: The exact numbers N of functions in our construction [19] $n$ | 6 | 8 | 10 | 12 | 14 | 16 | 18 | 20
---|---|---|---|---|---|---|---|---
N | $2^{7}$ | $2^{36}$ | $2^{121}$ | $2^{518}$ | $2^{2059}$ | $2^{8136}$ | $2^{32893}$ | $2^{130922}$

###  4.2 Algebraic degree

In [17], the authors characterized the algebraic degree of a large number of
functions:

Lemma 4.2.[17] Let $n$ be an integer, and $G(x)=x^{-1}+Tr(F(x))$ be a
permutation over $F_{2^{n}}$. Then $G$ has optimal algebraic degree, i.e.
$\deg(F)=n-1.$

According to Lemma 4.2, we immediately arrive at

Corollary 4.3. For every even integer $n\geq 6,$ all the functions $G$ in our
construction have optimal algebraic degree $n-1.$

###  4.3 Nonlinearity

It has been proved that a special class of functions all have high
nonlinearity:

Theorem 4.4.[17] Let $n\geq 4$ be an integer, and $F(x)=x^{-1}+f(x)$, where
$f:F_{2^{n}}\rightarrow F_{2}$ is a Boolean function such that
$f\bigg{(}\frac{1}{x}\bigg{)}=f\bigg{(}\frac{1}{x+1}\bigg{)}$ holds for any
$x\in F_{2^{n}}$. Then we have

$\displaystyle NL(F)\geq 2^{n-2}-\frac{1}{4}\lfloor
2^{\frac{n}{2}+1}\rfloor-1.$

We can use the above theorem to obtain the following corollary.

Corollary 4.5. For every even integer $n\geq 6,$ all the functions $G$ in our
construction satisfy

$\displaystyle NL(G)\geq 2^{n-2}-2^{\frac{n}{2}-1}-1.$

Proof. By definition, all the functions $G$ in our construction satisfy
$G(x)=x^{-1}+\delta_{U}(x)$, where $\delta_{U}:F_{2^{n}}\rightarrow F_{2}$ is
a Boolean function such that $\delta_{U}(x)=1$ if and only if $x\in U$.
Besides, we have proved that the set $U$ satisfies $\frac{1}{x^{-1}+1}\in U$
for any $x\in U$. Therefore, it holds
$\delta_{U}(x)=\delta_{U}\bigg{(}\frac{1}{x^{-1}+1}\bigg{)}$, or equivalently
$\delta_{U}\bigg{(}\frac{1}{x}\bigg{)}=\delta_{U}\bigg{(}\frac{1}{x+1}\bigg{)}$,
for any $x\in F_{2^{n}}$, and thus the result follows by Theorem 4.4.

We define two subsets of $V_{M}$. Let $V_{0}=\\{x\in
V_{M}~{}|~{}Tr\bigg{(}\frac{1}{x}\bigg{)}=0\\}$, $V_{1}=\\{x\in
V_{M}~{}|~{}Tr\bigg{(}\frac{1}{x}\bigg{)}=1\\}$. It is obvious that
$V_{M}=V_{0}\cup V_{1}$. In what follows, we will give some improved lower
bounds for the special cases $V=V_{0},V_{1}$ and $\emptyset$ respectively.

We need the following results:

Lemma 4.6. [19] For any positive integer $n$, any $b\in F_{2^{n}}$ and any
Boolean function $f$ defined on $F_{2^{n}}$, it holds

$\displaystyle|\sum_{x\in F_{2^{n}},Tr(x)=c}(-1)^{f(x)+Tr(bx)}|\leq\max_{a\in
F_{2^{n}}}|\sum_{x\in F_{2^{n}}}(-1)^{f(x)+Tr(ax)}|,$

where $c\in F_{2}$.

Lemma 4.7. [17] For any positive integer $n$ and any $(a,b)\in F_{2^{n}}\times
F_{2^{n}}^{*}$, it holds

$\displaystyle|\sum_{x\in F_{2^{n}}}(-1)^{Tr(ax+bx^{-1}+(x+1)^{-1})}|\leq
2\lfloor 2^{n/2+1}\rfloor\\!+\\!4.$

Lemma 4.8. For any even integer $n$ and any $(a,b)\in F_{2^{n}}^{*}\times
F_{2^{n}}^{*}$, it holds

$\displaystyle|\sum_{x\in
F_{2^{n}},Tr(x)=c}(-1)^{Tr(ax+bx^{-1}+(x+1)^{-1})+Tr(x^{-1})Tr((x+1)^{-1})}|\leq
6\cdot 2^{n/2}\\!+\\!4,$

where $c\in F_{2}$.

Proof. For any fixed $(a,b)\in F_{2^{n}}^{*}\times F_{2^{n}}^{*}$, by Lemma
4.6, we have

$\displaystyle|\sum_{x\in
F_{2^{n}},Tr(x)=c}(-1)^{Tr(ax+bx^{-1}+(x+1)^{-1})+Tr(x^{-1})Tr((x+1)^{-1})}|$
$\displaystyle\leq$ $\displaystyle\max_{\widetilde{a}\in F_{2^{n}}}|\sum_{x\in
F_{2^{n}}}(-1)^{Tr(\widetilde{a}x+bx^{-1}+(x+1)^{-1})+Tr(x^{-1})Tr((x+1)^{-1})}|,$

while

$\displaystyle|\sum_{x\in
F_{2^{n}}}(-1)^{Tr(\widetilde{a}x+bx^{-1}+(x+1)^{-1})+Tr(x^{-1})Tr((x+1)^{-1})}|$
$\displaystyle=$ $\displaystyle|\sum_{x\in
F_{2^{n}}}(-1)^{Tr(\widetilde{a}x^{-1}+bx+(x+1)^{-1})+Tr(x)Tr((x+1)^{-1})}|$
$\displaystyle=$ $\displaystyle|\sum_{x\in
F_{2^{n}},Tr(x)=0}(-1)^{Tr(\widetilde{a}x^{-1}+bx+(x+1)^{-1})}$
$\displaystyle~{}~{}~{}~{}+\sum_{x\in
F_{2^{n}},Tr(x)=1}(-1)^{Tr(\widetilde{a}x^{-1}+bx)}|$ $\displaystyle\leq$
$\displaystyle(2^{\frac{n}{2}\\!+\\!2}\\!+\\!4)\\!+\\!2^{\frac{n}{2}\\!+\\!1}~{}({\rm
by~{}Lemmas~{}4.7~{}and~{}2.1~{}resp.})$ $\displaystyle=$ $\displaystyle
6\cdot 2^{\frac{n}{2}}\\!+\\!4.$

This completes the proof.

Let $V=V_{0}$, then the function in our construction is

$\displaystyle
G_{1}(x)=x^{-1}\\!+\\!1\\!+\\!Tr\bigg{(}x\\!+\\!\frac{1}{x\\!+\\!1}\bigg{)}+Tr(x)Tr\bigg{(}\frac{1}{x}\bigg{)}Tr\bigg{(}\frac{1}{x\\!+\\!1}\bigg{)}.$

And we have

Theorem 4.9. For every even integer $n\geq 6,$ it holds

$\displaystyle NL(G_{1})\geq 2^{n-1}-5\cdot 2^{\frac{n}{2}}-4.$

Proof. It suffices to show that

$\displaystyle|G_{1}^{\mathcal{W}}(a,b)|=|\sum_{x\in
F_{2^{n}}}(-1)^{Tr(ax+bG_{1}(x))}|\leq 10\cdot 2^{\frac{n}{2}}+8,$

for any $(a,b)\in F_{2^{n}}\times F_{2^{n}}^{*}$. In fact, we have

$\displaystyle|\sum_{x\in F_{2^{n}}}(-1)^{Tr(ax+bG_{1}(x))}|$ $\displaystyle=$
$\displaystyle|\sum_{x\in
F_{2^{n}}}(-1)^{Tr(ax\\!+\\!b(x^{-1}\\!+\\!1\\!+\\!Tr(x\\!+\\!(x+1)^{-1})\\!+\\!Tr(x)Tr(x^{-1})Tr((x\\!+\\!1)^{-1})))}|$
$\displaystyle=$ $\displaystyle|\sum_{x\in
F_{2^{n}}}(-1)^{Tr(ax\\!+\\!bx^{-1})\\!+\\!Tr(b)(1\\!+\\!Tr(x\\!+\\!(x\\!+\\!1)^{-1})\\!+\\!Tr(x)Tr(x^{-1})Tr((x\\!+\\!1)^{-1}))}|.$

If $Tr(b)=0,$ then $|F^{\mathcal{W}}(a,b)|=|\sum_{x\in
F_{2^{n}}}(-1)^{Tr(ax+bx^{-1})}|\leq 2^{\frac{n}{2}+1}$, by Lemma 2.1.

Else if $Tr(b)=1,$ we get

$\displaystyle|G_{1}^{\mathcal{W}}(a,b)|$ $\displaystyle=$
$\displaystyle|\sum_{x\in
F_{2^{n}}}(-1)^{Tr((a+1)x+bx^{-1}+(x+1)^{-1})+Tr(x)Tr(x^{-1})Tr((x+1)^{-1})}|$
$\displaystyle=$ $\displaystyle|\sum_{x\in
F_{2^{n}},Tr(x)=0}(-1)^{Tr((a+1)x+bx^{-1}+(x+1)^{-1})}+$
$\displaystyle\sum_{x\in
F_{2^{n}},Tr(x)=1}(-1)^{Tr((a+1)x+bx^{-1}+(x+1)^{-1})+Tr(x^{-1})Tr((x+1)^{-1})}|$
$\displaystyle\leq$ $\displaystyle(2^{n/2\\!+\\!2}\\!+\\!4)\\!+\\!(6\cdot
2^{n/2}\\!+\\!4)~{}({\rm by~{}Lemmas~{}4.7~{}and~{}4.8})$ $\displaystyle=$
$\displaystyle 10\cdot 2^{\frac{n}{2}}\\!+\\!8.$

This completes the proof.

When $V=V_{1}$, the function in our construction is

$\displaystyle
G_{2}(x)=x^{-1}\\!+\\!1\\!+\\!Tr\bigg{(}x\\!+\\!\frac{1}{x\\!+\\!1}\bigg{)}\\!+\\!Tr(x)(Tr\bigg{(}\frac{1}{x}\bigg{)}\\!+\\!1)Tr\bigg{(}\frac{1}{x\\!+\\!1}\bigg{)}.$

And similar to the case $V=V_{0}$, we can get the following lower bound for
$NL(G_{2})$.

Theorem 4.10. For every even integer $n\geq 6,$ it holds

$\displaystyle NL(G_{2})\geq 2^{n-1}-5\cdot 2^{\frac{n}{2}}-4.$

When $V=\emptyset$, the function in our construction is

$\displaystyle
G_{3}(x)=x^{-1}\\!+\\!1\\!+\\!Tr\bigg{(}x\\!+\\!\frac{1}{x\\!+\\!1}\bigg{)}\\!+\\!Tr(x)Tr\bigg{(}\frac{1}{x\\!+\\!1}\bigg{)}.$

And we have

Theorem 4.11. For every even integer $n\geq 6,$ it holds

$\displaystyle NL(G_{3})\geq 2^{n-1}-3\cdot 2^{\frac{n}{2}}-2.$

Proof. It suffices to show that

$\displaystyle|G_{3}^{\mathcal{W}}(a,b)|=|\sum_{x\in
F_{2^{n}}}(-1)^{Tr(ax+bG_{3}(x))}|\leq 6\cdot 2^{\frac{n}{2}}+4,$

for any $(a,b)\in F_{2^{n}}\times F_{2^{n}}^{*}$. In fact, we have

$\displaystyle|\sum_{x\in F_{2^{n}}}(-1)^{Tr(ax+bG_{3}(x))}|$ $\displaystyle=$
$\displaystyle|\sum_{x\in
F_{2^{n}}}(-1)^{Tr(ax+b(x^{-1}+1+Tr(x+(x+1)^{-1})+Tr(x)Tr((x+1)^{-1})))}|$
$\displaystyle=$ $\displaystyle|\sum_{x\in
F_{2^{n}}}(-1)^{Tr(ax+bx^{-1})+Tr(b)(1+Tr(x+(x+1)^{-1})+Tr(x)Tr((x+1)^{-1}))}|.$

If $Tr(b)=0,$ then $|F^{\mathcal{W}}(a,b)|=|\sum_{x\in
F_{2^{n}}}(-1)^{Tr(ax+bx^{-1})}|\leq 2^{\frac{n}{2}+1}$, by Lemma 2.1.

Else if $Tr(b)=1,$ we get

$\displaystyle|G_{3}^{\mathcal{W}}(a,b)|$ $\displaystyle=$
$\displaystyle|\sum_{x\in
F_{2^{n}}}(-1)^{Tr((a+1)x+bx^{-1}+(x+1)^{-1})+Tr(x)Tr((x+1)^{-1})}|$
$\displaystyle=$ $\displaystyle|\sum_{x\in
F_{2^{n}},Tr(x)=0}(-1)^{Tr((a+1)x+bx^{-1}+(x+1)^{-1})}+$
$\displaystyle\sum_{x\in F_{2^{n}},Tr(x)=1}(-1)^{Tr((a+1)x+bx^{-1})}|$
$\displaystyle\leq$
$\displaystyle(2^{n/2\\!+\\!2}\\!+\\!4)\\!+\\!2^{n/2\\!+\\!1}~{}({\rm
by~{}Lemmas~{}4.7~{}and~{}2.1~{}resp.})$ $\displaystyle=$ $\displaystyle
6\cdot 2^{\frac{n}{2}}\\!+\\!4.$

This completes the proof.

###  4.4 CCZ-inequivalence and computational results

Generally, it is very hard to prove that two classes of functions are CCZ-
inequivalent. People often turn to check whether their CCZ-invariant
parameters, such as differential spectrum and extended Walsh spectrum, are the
same. By a magma programme, we computed the nonlinearity and the differential
spectrum of the newly discovered functions for $n=6$, and found that there are
at least 13 CCZ-inequivalent classes, which are listed in Table 2 (excluding
the 1st class function $G_{M}$ of [17]), where we let $\xi$ be the default
primitive element of $F_{2^{6}}$ in Magma version 2.19-10, $NL$ be the
nonlinearity of a function, and $[a,b,c]$ be the differential spectrum of a
function, which means that $0$ appears $a$ times, $2$ appears $b$ times and
$4$ appears $c$ times respectively. Comparing with Table 3 of [19], one can
find that among these 13 classes of functions in Table 2, the nonlinearity and
differential spectrum of 6 classes of them (with *) are different from those
in [19], which indicates that they are CCZ-inequivalent to the functions
constructed by [19].

Table 2: CCZ-inequivalent differentially 4-uniform permutations for $n=6$ $V$ | $NL$ | Differential spectrum |
---|---|---|---
$\emptyset$ | $20$ | $[2235,1578,219]$ |
$\\{\xi^{i}~{}|~{}i\in\\{21,42\\}\\}$ | $20$ | $[2247,1554,231]$ |
$\\{\xi^{i}~{}|~{}i\in\\{3,53\\}\\}$ | $18$ | $[2253,1542,237]$ |
$\\{\xi^{i}~{}|~{}i\in\\{3,6,43,53\\}\\}$ | $18$ | $[2265,1518,249]$ |
$\\{\xi^{i}~{}|~{}i\in\\{3,12,23,53\\}\\}$ | $18$ | $[2259,1530,243]$ |
$\\{\xi^{i}~{}|~{}i\in\\{3,21,42,53\\}\\}$ | $18$ | $[2271,1506,255]$ |
$\\{\xi^{i}~{}|~{}i\in\\{3,12,23,29,48,53\\}\\}$ | $20$ | $[2253,1542,237]$ |
$\\{\xi^{i}~{}|~{}i\in\\{3,21,24,42,46,53\\}\\}$ | $20$ | $[2277,1494,261]$ | *
$\\{\xi^{i}~{}|~{}i\in\\{3,21,29,42,48,53\\}\\}$ | $18$ | $[2283,1482,267]$ | *
$\\{\xi^{i}~{}|~{}i\in\\{3,21,33,42,53,58\\}\\}$ | $18$ | $[2289,1470,273]$ | *
$\\{\xi^{i}~{}|~{}i\in\\{3,12,21,23,29,42,48,53\\}\\}$ | $20$ | $[2283,1482,267]$ | *
$\\{\xi^{i}~{}|~{}i\in\\{3,21,29,33,42,48,53,58\\}\\}$ | $18$ | $[2295,1458,279]$ | *
$\\{\xi^{i}~{}|~{}i\in\\{3,6,21,29,42,43,48,53\\}\\}$ | $20$ | $[2295,1458,279]$ | *

In [19], three special classes of differentially 4-uniform permutations
$F_{1},F_{2}$ and $F_{3}$ were identified and proved to be CCZ-inequivalent to
known differentially 4-uniform power functions and to quadratic functions,
where

$\displaystyle
F_{1}(x)=\bigg{(}x+Tr\bigg{(}\frac{1}{x}\bigg{)}Tr\bigg{(}\frac{1}{x+1}\bigg{)}\bigg{)}^{-1},$
$\displaystyle
F_{2}(x)=\bigg{(}x+(1+Tr(x))Tr\bigg{(}\frac{1}{x}\bigg{)}Tr\bigg{(}\frac{1}{x+1}\bigg{)}\bigg{)}^{-1},$
$\displaystyle
F_{3}(x)=\bigg{(}x+Tr(x)Tr\bigg{(}\frac{1}{x}\bigg{)}Tr\bigg{(}\frac{1}{x+1}\bigg{)}\bigg{)}^{-1}.$

For our three special subclasses $G_{1},G_{2}$ and $G_{3}$, we have also
computed their differential spectrum for small $n=6,8,10$ and compared with
that of $G_{M}$ constructed by [17] (see Remark 3.2), and functions
$F_{1},F_{2},F_{3}$. Although they are constructed by permuting the
multiplicative inverse functions, the differential spectrum is different. The
computational results are listed in Table 3. We also list the lower bounds on
nonlinearity of these functions in Table 4, where the last row is the known
maximum values of the nonlinearity.

Table 3: The differentially spectrum of $G_{M}$, $G_{i}$ and $F_{i}$ for $n=6,8,10$ | $n=6$ | $n=8$ | $n=10$
---|---|---|---
$G_{1}$ | $[2253,1542,237]$ | $[36735,24450,4095]$ | $[586269,398790,62493]$
$G_{2}$ | $[2247,1554,231]$ | $[36495,24930,3855]$ | $[589089,393150,65313]$
$G_{3}$ | $[2235,1578,219]$ | $[36159,25602,3519]$ | $[581289,408750,57513]$
$G_{M}$ | $[2301,1446,285]$ | $[36735,24450,4095]$ | $[589389,392550,65613]$
$F_{1}$ | $[2289,1470,273]$ | $[36207,25506,3567]$ | $[580779,409770,57003]$
$F_{2}$ | $[2277,1494,261]$ | $[35199,27522,2559]$ | $[566259,438810,42483]$
$F_{3}$ | $[2127,1794,111]$ | $[36159,25602,3519]$ | $[565839,439650,42063]$
Table 4: Lower bounds for nonlinearity and exact values for small $n$ (the last row is the known maximum nonlinearity)  Functions | Lower bounds | $n=6$ | $n=8$ | $n=10$ | $n=12$
---|---|---|---|---|---
$G_{1}$ | $2^{n-1}-5\cdot 2^{n/2}-4$ | 20 | 96 | 450 | 1888
$G_{2}$ | $2^{n-1}-5\cdot 2^{n/2}-4$ | 20 | 100 | 442 | 1910
$G_{3}$ | $2^{n-1}-3\cdot 2^{n/2}-2$ | 20 | 100 | 446 | 1912
$G_{M}$ | $2^{n-1}-2^{n/2+1}-2$ | 20 | 102 | 454 | 1928
$F_{1}$ | $2^{n-1}-3\cdot 2^{n/2}-2$ | 20 | 100 | 442 | 1902
$F_{2}$ | $2^{n-1}-2^{n/2+2}-2$ | 22 | 102 | 450 | 1924
$F_{3}$ | $2^{n-1}-2^{n/2+2}-2$ | 22 | 102 | 444 | 1892
MAX | $2^{n-1}-2^{n/2}$ | 24 | 112 | 480 | 1984

##  5 Conclusion

In this paper we presented a new construction of differentially 4-uniform
permutations for any even $n\geq 6$, which gives many new CCZ-inequivalent
functions. We also deduced a lower bound on the nonlinearity of our functions,
and three improved lower bounds for three infinite subclasses.

## References

  * [1] E. Biham and A. Shamir, _Differential cryptanalysis of DES-like cryptosystems_ , J. Cryptol. 4(1), 3-72, 1991.
  * [2] C. Bracken, E. Byrne, N.Markin and G. McGuire, _A few more quadratic APN functions_ , Cryptography and Communications, 3(1), 43-53, 2011.
  * [3] C. Bracken and G. Leander, _A highly nonlinearity differentially 4-uniform power mapping that permutates fields of even degree_ , Finite Fields and Their Applications, 16(4), 231-242, 2010.
  * [4] C. Bracken, C.H. Tan and Y. Tan, _Binomial differentially 4-uniform permutations with high nonlinearity_ , Finite Fields and Their Applications, 18(3), 537-546, 2012.
  * [5] L. Budaghyan and C. Carlet, _Constructing new APN functions from known ones_ , Finite Fields and Their Applications, 15(2), 150-159, 2009.
  * [6] J.F Dillon, _APN polynomials and related codes_ , slides in Banhff Conference, 2006.
  * [7] J.F Dillon, _APN polynomials: an update_ , In Conference Finite Fields and Their Applications Fq9, Dublin, Ireland, 2009.
  * [8] Y. Edel and A. Pott, _A new almost perfect nonlinear function which is not quadratic_ , Advances in Mathematical Communications, 3(1), 59-81, 2009.
  * [9] R. Gold, _Maximal recursive sequences with 3-valued recursive cross-correlation functions (corresp.)_ , IEEE Trans. on Information Theory, 14(1), 154-156, 1968.
  * [10] T. Kasami, _The weight enumerators for several classes of subcodes of the 2nd order binary reed-muller codes_ , Information and Control, 18(4), 369-394, 1971.
  * [11] L. Knudsen, _Truncated and higher order differentials_ , Lecture Notes in Computer Sciences, volume 1008, FSE 1994, 196-211, 1995.
  * [12] G. Lachaud and J. Wolfmann, _The weights of the orthogonals of the extended quadratic binary Goppa codes_ , IEEE Trans. on Information Theory, 36(3), 686-692, 1990.
  * [13] Y.Q. Li, M.S. Wang and Y.Y. Yu, _Constructing differentially 4-uniform permutations over $F_{2^{2k}}$ from the inverse function revisted_, eprint.iacr/2013/731
  * [14] F.J. MacWilliams and N.J. Sloane, _The theory of error-correocting codes_ , Amsterdam, North Holland. 1977.
  * [15] L. Matsui, _Linear cryptanalysis method for DES cipher_ , Advances in Cryptology EUROCRYPT 93. Springer Berlin Heidelberg, 386-397, 1994.
  * [16] K. Nyberg, _Differentially uniform mappings for cryptography_ , In Adances in Cryptography, EUROCRYPT 93 (Lofthus, 1993), LNCS, volume 765, 55-64, 1994.
  * [17] L.J. Qu, Y. Tan, C.H. Tan and C. Li, _Constructing differentially 4-uniform permutations over $F_{2^{2k}}$ via the switching method_, IEEE Trans. on Information Theory, 59(7), 4675-4686, 2013.
  * [18] L.J. Qu, Y. Tan, C. Li and G. Gong, _More constructions of differentially 4-uniform permutations on $F_{2^{2k}}$_, arXiv:1309.7423v1[cs.IT], 2013.
  * [19] D. Tang, C. Carlet and X. Tang, _Differentially 4-uniform bijections by permuting the inverse function_ , eprint.iacr/2013/639
  * [20] Y. Tan, L.J. Qu, C.H. Tan and C. Li, _New Families of Differentially 4-Uniform Permutations over $F_{2^{2k}}$_, Sequences and Their Applications CSETA 2012, LNCS, 7338: 13-28, 2012.
  * [21] Z.B. Zha, L. Hu and S.W. Sun, _Constructing new differentially 4-uniform permutations from the inverse function_ , Finite Fields and Their Applications, 25, 64-78, 2014.