Differentially 4-uniform bijections by permuting the inverse function

Abstract

Block ciphers use substitution boxes (S-boxes) whose aim is to create confusion into the cryptosystems. Functions used as S-boxes should have low differential uniformity, high nonlinearity and algebraic degree larger than 3 (preferably strictly larger). They should be fastly computable; from this viewpoint, it is better when they are in even number of variables. In addition, the functions should be bijections in a substitution-permutation network. Almost perfect nonlinear (APN) functions have the lowest differential uniformity 2 and the existence of APN bijections over $\mathbb {F}_{2^n}$ for even $n\ge 8$ is a big open problem. In the present paper, we focus on constructing differentially 4-uniform bijections suitable for designing S-boxes for block ciphers. Based on the idea of permuting the inverse function, we design a construction providing a large number of differentially 4-uniform bijections with maximum algebraic degree and high nonlinearity. For every even $n\ge 12$, we mathematically prove that the functions in a subclass of the constructed class are CCZ-inequivalent to known differentially 4-uniform power functions and to quadratic functions. This is the first mathematical proof that the functions in an infinite class of differentially 4-uniform bijections are CCZ-inequivalent to known differentially 4-uniform power functions and to quadratic functions. We also get a naive lower bound on the nonlinearity of our functions, which can be very high in some cases, and obtain improved lower bounds on the nonlinearity for three special subcases of functions which are extremely large.

1 Introduction

The generally accepted design principles for block ciphers and stream ciphers are confusion and diffusion; they were introduced by Shannon in [13]. Confusion means making the relation between the ciphertext and the plaintext as complex as possible for the attacker and diffusion is the spreading out of the influence of one or several arbitrary bits of the plaintext or/and of the key over the output bits. In block ciphers, the confusion property is provided by substitution boxes (S-boxes) with good cryptographic properties and the diffusion is created by (generally) linear transformations with large branch number (related to codes of large minimum distance). In addition, S-boxes must be bijective in substitution-permutation networks (like the advanced encryption standard, AES). In the present paper, we concentrate on the design of bijective S-boxes.

An S-box with $n$ input bits and $n$ output bits is a multiple-output Boolean function which is often called an $(n,n)$-function or (if the value $n$ is omitted) a vectorial Boolean function. The S-boxes used in cryptosystems should satisfy all relevant design criteria simultaneously in order to be resistant against the known attacks and, hopefully, against some attacks which may exist but are not yet efficient and might be improved in the future. Linear cryptanalysis is a known-plaintext attack based on the existence of linear relations satisfied with a probability significantly different from 1/2, relating the plaintext bits, the ciphertext bits and the key bits. To contribute to resisting linear cryptanalysis [11], S-boxes used in cryptosystems should have high nonlinearity. The differential attack, developed by Biham and Shamir [1], is a chosen-plaintext attack that exploits the correlation between the input and output differences of a pair of plaintext blocks through the network of transformations with same key. The differential attack has a substantial impact on the design of block encryption algorithms. After this attack was invented, Nyberg [12] proposed the concept of differential $\delta$-uniformity (see Definition 1 below), for measuring the ability of a given function to contribute to resisting this attack. For a given $(n,n)$-function $G$, the value of $\delta$ should be as small as possible. It is well-known that the smallest possible value of $\delta$ of $(n,n)$-functions is 2; the functions achieving this value are called almost perfect nonlinear (APN). Furthermore, functions used as S-boxes should have algebraic degree as high as possible, or at least not low, to resist the higher order differential attack [9] introduced by Knudsen. The algebraic degree of 2 is very weak but a degree of 3 seems not enough and a degree at least $4$ is safer. In addition, functions would better have high graph algebraic immunity to resist the algebraic attacks (this attack is not yet efficient but we must consider the possibility it becomes efficient in the future). Moreover, we need the S-boxes to be efficiently computable, which in software is easier if the number $n$ of input bits is even; in fact, the best is to take $n$ equal to a power of $2$, since this allows decomposing optimally the computation of the output in $\mathbb {F}_{2^n}$ into computations in subfields. In hardware, $n$ does not need to be a power of 2, but we like in general the cryptosystems to be efficiently implementable in both hardware and software (which is also more convenient for the design of the whole cipher); for instance the number of input and output bits of the S-boxes of the AES is $8$.

Up to now, there is only one sporadic example of APN bijection for $n=6$, found in [4] and it is a big open problem to know whether there exist APN bijections over $\mathbb {F}_{2^n}$ for even $n\ge 8$. So, for resisting differential attacks in even dimensions, we need to choose differentially 4-uniform bijections as S-boxes when $n$ is even. Differential 4-uniformity is not optimal but it can withstand differential attacks in an efficient way. For example, the AES uses a differentially 4-uniform bijection with 8 input bits. By now, only a few classes of differentially 4-uniform bijections in even dimensions have been found, some of them are listed in [6, 16]. We list all known APN bijections and differentially 4-uniform bijections in even dimensions below for the convenience of the reader. Clearly, the functions $x^{d}$ and $x^{2^i d}$ are affine equivalent for every $i$, so we only list one value of $d$ for each cyclotomic coset of 2 mod $2^n-1$. Besides, any bijection is CCZ-equivalent (see definition in Sect. 2) to its compositional inverse, so we also omit $d^{-1}$ when $d$ is co-prime with $2^n-1$.

• There is only one example of APN bijection on 6 variables, given by Dillon [4] (the problem of finding an example of APN bijections in even number of variables had been open for 10 years). But it is CCZ-equivalent to a quadratic function, which may be vulnerable by the higher order differential attack, and its expression is complex, which leads to inefficient implementation in both hardware and software.

• The inverse function $x^{2^n-2}$ is bijective and is differentially 4-uniform when $n$ is even [12]; it is used as the S-box of the AES with $n=8$. This class of functions has best known nonlinearity $2^{n-1}-2^{n/2}$ and has maximum algebraic degree $n-1$. But it is the worst possible with respect to algebraic attacks since if we denote $y=x^{-1}$ then we have the bilinear relation $x^2y=x$. As mentioned above, though the algebraic attacks are not yet efficient, they represent a threat. A possible way to repair this weakness will be to compose the inverse function with a simple permutation, see below.

• The gold functions $x^{2^i+1}$ such that $\gcd (i,n)=2$ are differentially 4-uniform. Sometimes, functions in this class are bijective since $\gcd (2^i+1,2^n-1)$ divides $\gcd (2^{2i}-1,2^n-1)=2^{\gcd (2i,n)}-1$; hence if $n\equiv 2$ [mod 4], the function is bijective, but $n$ is not a power of 2 and more problematically this class of functions is quadratic and can not be used as S-box.

• The Kasami functions $x^{2^{2i}-2^i+1}$ such that $n\equiv 2$ [mod 4] and $\gcd (i,n)=2$ are differentially 4-uniform. Sometimes, functions in this class are bijective as well. This class of functions never reaches the maximum algebraic degree $n-1$ (but this may not be a problem). More problematically, it is related to quadratic functions when it is bijective, since $2^{2i}-2^i+1=\frac{2^{3i}+1}{2^i+1}$, $2^i+1$ is co-prime with $2^n-1$ when $n\equiv 2$ [mod 4] and $\gcd (i,n)=2$; this implies that it has the form $F(x)=R_1(R_2^{-1}(x))$ where $R_1$ and $R_2$ are quadratic permutations. Maybe this could be used in an extended higher order differential attack. So this function, which is clearly the most interesting power function to be used as S-box, would represent some risk.

• The function $x^{2^{n/2+n/4+1}}$ is differentially 4-uniform [2] and has best known nonlinearity $2^{n-1}-2^{n/2}$ as well. It is bijective if $n$ is divisible by 4 but not by 8; in this case, $n$ is not a power of 2; more problematically the function has algebraic degree 3 which is too low.

• A class of binomial differentially 4-uniform bijections with high nonlinearity has been proposed in [3]. Let $n=3k$ and $t$ be a divisor of $k$ where $3\not \mid k$ and $\frac{k}{t}$ is odd. Let $s$ be an integer such that $\gcd (3k,s)=t$ and $3|(k+s)$. Then the functions $\alpha x^{2^s+1}+\alpha ^{2^k}x^{2^{-k}+2^{k+s}}$, where $\alpha$ is a primitive element of $\mathbb {F}_{2^n}$, are differentially $2^t$-uniform and bijective. This class of functions has nonlinearity $2^{n-1}-2^{(n+t-2)/2}$ if $n+t$ is even and $2^{n-1}-2^{(n+t-3)/2}$ if $n+t$ is odd. This implies that such functions are differentially 4-uniform bijections and have best known nonlinearity $2^{n-1}-2^{n/2}$, when $t=2$. The authors also pointed out that a generalized functions $\alpha x^{2^s+1}+\alpha ^{2^k}x^{2^{ik}+2^{tk+s}}$, where $3\not \mid k$, $k/2$ is odd, $\gcd (3k,s)=2$, $i\equiv ks\mod 3$ and $t\equiv -i\mod 3$ are also differentially 4-uniform and bijective, and the Walsh spectrum is a subset of $\{0,\pm 2^{3k/2},\pm 2^{(3k+2)/2}\}$. Both of them have algebraic degree 2 which is too low.

• In [15], the authors modified the method introduced in [6], initially designed for constructing differentially 4-uniform bijections in odd dimensions, to construct differentially 4-uniform bijections in even dimensions. They obtained three classes of differentially 4-uniform bijections with best known nonlinearity $2^{n-1}-2^{n/2}$ and algebraic degree $(n+2)/2$. Those functions are interesting but the authors did not discuss whether they are CCZ-equivalent to power functions and quadratic functions.

• Later, Qu et al. [16] proposed two classes of differentially 4-uniform bijections in even dimensions by adding some special Boolean functions to the inverse function. The first class of functions is of the form $x^{2^n-2}+tr_1^n(x^2(x+1)^{2^n-2})$, which has optimal algebraic degree $n-1$ and a nonlinearity greater than $2^{n-1}-2^{n/2+1}-2$. The second one is of the form $x^{2^n-2}+tr_1^n\left( x^{(2^n-2)d}+(x^{2^n-2}+1)^d\right)$, where $d=3(2^t+1)$, $2\le t\le n/2-1$. It has algebraic degree $n-1$ as well and a nonlinearity at least $2^{n-2}-2^{n/2-1}-1$. The authors did not mathematically prove whether their functions are CCZ-inequivalent to the inverse function, but we can easily check, with the help of computer, that those two classes of functions are CCZ-inequivalent to the inverse function for even $n=6,8,10,12$. These two classes of functions are then interesting; they have high nonlinearity, maximum algebraic degree and no obvious weakness. A generalized method for constructing differentially 4-uniform bijections in even dimensions is also presented in [16], which includes the former two classes of functions. This generalized method can produce many CCZ-inequivalent differentially 4-uniform bijections in even dimensions, according to their computational results in small numbers of dimensions.

• Very recently, Zha et al. [17] presented two classes of differentially 4-uniform bijections by applying affine transformations on the elements of some subfields of the inverse function. Their functions have maximum algebraic degree $n-1$. The lower bounds on nonlinearity are naive but their constructions are interesting.

• In [8], Carlet et al. built a family of differentially 4-uniform bijections in even dimensions $n$ no less than 6 by concatenating two $(n-1,n)$-functions. This family includes at least $\left( 2^{n-3}-\lfloor 2^{(n-1)/2-1}\rfloor -1\right) \cdot 2^{2^{n-1}}$ bijections, all of algebraic degree $n-1$. The authors also mathematically proved that, for any even $n$ no less than 8, bijections in this family are CCZ-inequivalent to the gold functions, to the Kasami functions, to the functions discussed in [2] and to quadratic functions. Further, they showed a subclass of the family which has nonlinearity at least $2^{n-1}-2\lfloor 2^{(n+1)/2}\rfloor -4$ and is CCZ-inequivalent to all known differentially 4-uniform power bijections and to quadratic functions.

Except for the inverse function (which has however a potential weakness), the Kasami functions (which may have some potential weaknesses), the functions constructed in [15–17] (which have not been proven CCZ-inequivalent to known differentially 4-uniform power functions) and the functions in the subclass in [8] there is no low differentially uniform bijection which can be used as S-box. Therefore, the research of more functions having all the desired features is useful and this is our motivation in the present paper.

Since the inverse function is a differentially 4-uniform bijection when $n$ is even and has best known nonlinearity and maximum algebraic degree, we can try, as Qu et al., to construct new differentially 4-uniform bijections by modifying the inverse function. A natural method for doing this is, contrary to Qu et al., to compose the inverse function with a well-chosen permutation, simple enough to allow handling the behavior of the parameters above. In the present paper, we give a construction of differentially 4-uniform bijections in even dimensions by “permuting” this way the inverse function. More precisely, for any even $n\ge 6$, we find a class of subsets, denoted by $U$, of $\mathbb {F}_{2^n}$, such that, taking as output $(x+1)^{2^n-2}$ if $x\in U$ and $x^{2^n-2}$ otherwise gives a differentially 4-uniform permutation. For every even $n$, we can get at least $2^{2^{n-3}-2^{n/2-2}}$ different such sets $U$. For example, for $n=6$ we can obtain $2^7$ differentially 4-uniform bijections; for $n=8$ we can obtain $2^{36}$ ones. We list the numbers of constructed differentially 4-uniform bijections in Table 2 for even $n$ ranging from $6$ to $20$. Furthermore, for every even $n\ge 12$, we mathematically prove that if the size of $U$ is such that $0<|U|<(2^{n-1}-2^{n/2})/3-2$ then our functions are CCZ-inequivalent to known differentially 4-uniform power functions and to quadratic functions. This is the first time that can be mathematically proven that an infinite class of differentially 4-uniform bijections contains elements CCZ-inequivalent to known differentially 4-uniform power functions and to quadratic functions. By computer investigation, we checked that when $n=6$ all the obtained bijections are CCZ-inequivalent to known differentially 4-uniform bijections listed above. We also prove that, for any even $n\ge 6$, our functions have maximum algebraic degree $n-1$. We also have a lower bound on the nonlinearity for all our functions, that is $2^{n-1}-2^{n/2}-|U|$, which can be quite high in some cases since the size of $U$ can take any even integer ranging from $2$ to $U_{max}$ (see the definition of $U_{max}$ in Sect. 4.2). For special sets $U=U_{max}$, $U=U_{m_0}$ and $U=U_{m_1}$ (see Sect. 4.2 for their definitions) we obtain improved lower bounds on the nonlinearity and the actual nonlinearities are very high. We summarize in Table 1 the cryptographic properties of known differentially 4-uniform bijections on even variables. It is seen from Table 1 that all known differentially 4-uniform power bijections on even variables have exact or potential weakness, so we only compare our functions with known non-power differentially 4-uniform bijections proposed in [16]. We can see from Table 1 that compared with the bijections constructed in [16], our lower bound on nonlinearity with $0<|U|<(2^{n-1}-2^{n/2})/3-2$ is better than that of the functions in [16] when we restrict the size of $U$ to at most $2^{n/2}$. We also can see from Table 1 that the lower bounds on the nonlinearity of our functions with $U=U_{max}$, $U=U_{m_0}$ and $U=U_{m_1}$ are a little less than that of the first class of functions in [16] but much better than that of the second one in [16] . Actually, for small numbers of variables $n$, the exact nonlinearities of these three classes of functions are very close to that of the first class in [16] (see Table 4 in Sect. 5) and, the most important point, our functions with $U=U_{m_0}$ and $U=U_{m_1}$ are CCZ-inequivalent to known differentially 4-uniform power functions.

Table 1 Known differentially 4-uniform bijections on even variables $n$

The remainder of this paper is organized as follows. In Sect. 2, the notation and the necessary preliminaries required for the subsequent sections are reviewed. We propose in Sect. 3 a new construction of differentially 4-uniform bijections over $\mathbb {F}_{2^n}$ ($n$ even). In Sect. 4, the algebraic degree is determined and several lower bounds on the nonlinearity of the constructed functions are presented. The CCZ-inequivalence between constructed functions and known differentially 4-uniform power bijections are proved as well. In Sect. 5, we compare the nonlinearity of our functions to the nonlinearity of all known differentially 4-uniform bijections. Finally, Sect. 6 concludes the paper.

2 Preliminaries

Let $n$ be a positive integer; mappings $G$ from the finite field $\mathbb {F}_{2^n}$ to itself are often called $(n,n)$ -functions or (if the value $n$ is omitted) vectorial Boolean functions. A Boolean function of $n$ variables is a function from $\mathbb {F}_2^n$ into $\mathbb {F}_2$. We denote by $\mathcal {B}_n$ the set of Boolean functions in $n$ variables. The basic representation of a Boolean function $f(x_1, \ldots , x_n)$ is by its truth table, i.e.,

$$\begin{aligned} f=\left[ f(0, 0, \ldots , 0), f(1, 0,\ldots , 0), f(0, 1,\ldots , 0), f(1, 1, \ldots , 0), \cdots , f(1, 1, \ldots , 1)\right] . \end{aligned}$$

We say that a Boolean function $f$ is balanced if its truth table contains an equal number of ones and zeros, that is, if its Hamming weight equals $2^{n-1}$. The Hamming weight of $f$, denoted by $\mathrm {wt}(f)$, is the size of the support of $f$, where the support of $f$ is defined as $\mathrm{Supp}(f)=\{x \in \mathbb {F}^n_2\,|\, f(x) = 1\}$. Given two Boolean functions $f$ and $g$ in $n$ variables, the Hamming distance between $f$ and $g$ is defined as $d_H(f,g)=|\{ x\in \mathbb {F}_2^n \,|\, f(x)\ne g(x) \}|$. Let $G$ be an $(n,n)$-function, the Boolean functions $g_1(x),\cdots ,g_n(x)$ such that $G(x) =(g_1(x),\ldots , g_n(x))$, are called the coordinate functions of $G$. The linear combinations, with non all-zero coefficients, of the coordinate functions of $G$ are called the component functions of $G$. The component functions of $G$ can be expressed as $tr_1^n(aG)$, where $a\in \mathbb {F}_{2^n}^*$ and $tr_1^n(x)=\sum \nolimits _{i=0}^{n-1}x^{2^i}$ is the trace function from $\mathbb {F}_{2^n}$ to $\mathbb {F}_2$. Design criteria on S-boxes can be expressed as properties of the component functions or of the vectorial function itself.

For measuring the quality of a given function to resist the differential attack [1], Nyberg [12] introduced the concept of differential $\delta$ -uniformity:

Definition 1

An $(n,n)$-function $G$ is called differentially $\delta$-uniform if, for every nonzero $a\in \mathbb {F}_{2^n}$ and every $b\in \mathbb {F}_{2^n}$, the equation $G(x)+G(x+a)=b$ has at most $\delta$ solutions.

The smaller $\delta$ is, the better is the contribution of $G$ to resist the differential attack. The values of $\delta$ are always even since if $x$ is a solution of equation $G(x)+G(x+a)=b$ then $x+a$ is also a solution. The smallest possible value of $\delta$ of $(n,n)$-functions is 2 and the functions achieving this value are called almost perfect nonlinear (APN) functions. For every $a\in \mathbb {F}_{2^n}^*$ and every $b\in \mathbb {F}_{2^n}$, we denote by $\delta _G(a,b)$ the size of the set $\{x\in \mathbb {F}_{2^n}\,|\, G(x)+G(x+a)=b\}$ and therefore $\delta$ equals the maximum value of $\delta _G(a,b)$. The multi-set $[\delta _G(a,b)\,|\, a\in \mathbb {F}_{2^n}^*,b\in \mathbb {F}_{2^n}]$ is called the differential spectrum of $G$.

S-boxes used in cryptosystems should have high nonlinearity in order to prevent linear cryptanalysis [11]. The nonlinearity of a Boolean function $f$ of $n$ variables is the minimum Hamming distance between $f$ and all the affine functions $A_n$:

$$\begin{aligned} N_f&= \min _{g\in A_n}(d_H(f,g))\\&= 2^{n-1}-\frac{1}{2}\max _{\alpha \in \mathbb {F}_{2^n}}|W_f(\alpha )|, \end{aligned}$$

where $W_f(\alpha )=\sum _{x\in \mathbb {F}_{2^n}}(-1)^{f(x)+tr_1^n(\alpha x)}$ is the Walsh transform of $f$ at $\alpha$. The nonlinearity $NL(G)$ of an $(n,n)$-function $G$ is the minimum Hamming distance between all the component functions $tr_1^n(aG)$ of $G$, where $a\in \mathbb {F}_{2^n}^*$, and all affine functions on $n$ variables. We have:

$$\begin{aligned} NL(G)=2^{n-1}-\frac{1}{2}\max _{(a,b)\in \mathbb {F}_{2^n}^*\times \mathbb {F}_{2^n}}|W_G(a,b)|, \end{aligned}$$

where $W_G(a,b)=\sum _{x\in \mathbb {F}_{2^n}}(-1)^{tr_1^n(aG(x)+bx)}$ is the value of the Walsh transform of $G$ at $(a,b)$; the multi-set of these values is called the Walsh spectrum of $G$. We call extended Walsh spectrum of $G$ the multi-set of their absolute values. It is well known that the nonlinearity $NL(G)$ is upper-bounded by $2^{n-1}-2^{\frac{n-1}{2}}$ (nonlinearity achievable for every $n$ odd) and the best known value of $NL(G)$ is $2^{n-1}-2^{\frac{n}{2}}$ for even $n$.

The algebraic degree is also an important parameter of the S-boxes used in cryptosystems. Every $(n,n)$-function $G$ can be uniquely represented by an univariate polynomial:

$$\begin{aligned} G(x)=\sum _{i=0}^{2^n-1}a_ix^i,a_i\in \mathbb {F}_{2^n}. \end{aligned}$$

The algebraic degree, denoted by $\mathrm{deg}(G)$, is defined as the maximal 2-weight of the exponents $i$ such that $a_i\not =0$, where the 2-weight of a given integer $i$ is the number of ones in its binary expansion. S-boxes used in cryptosystems should have high algebraic degree, or at least not a low one, to resist the higher order differential attack; it is known that the algebraic degree of bijective functions on $n$ variables is upper-bounded by $n-1$.

Two functions are considered as equivalent if one can be obtained from the other by some simple transformation (and a function equivalent to a weak function under some transformation preserving the attack on this function will be weak as well). There are mainly three such equivalence notions, called affine equivalence, extended affine equivalence (in brief, EA equivalence) and Carlet–Charpin–Zinoviev equivalence (CCZ-equivalence), respectively. Given two $(n,n)$-functions $G$ and $H$, we say that they are affine equivalent if $G(x)=A_1(H(A_2(x)))$, where $A_1$ and $A_2$ are affine permutations on $\mathbb {F}_{2^n}$; we say that they are EA-equivalent if $G(x)=A_1(H(A_2(x)))+A_3(x)$, where $A_1$ and $A_2$ are affine permutations on $\mathbb {F}_{2^n}$ and $A_3$ is an affine function on $F_{2^n}$; we say that they are CCZ-equivalent [5, 7] if their graphs $\{(x,y)\in \mathbb {F}_{2^n}\times \mathbb {F}_{2^n}\,|\, y=G(x)\}$ and $\{(x,y)\in \mathbb {F}_{2^n}\times \mathbb {F}_{2^n}\,|\, y=H(x)\}$ are affine equivalent, that is, if there exists an affine automorphism $L=(L_1,L_2)$ of $\mathbb {F}_{2^n}\times \mathbb {F}_{2^n}$, where $L_1$ and $L_2$ are two affine functions from $\mathbb {F}_{2^n}\times \mathbb {F}_{2^n}$ to $\mathbb {F}_{2^n}$, such that $y=G(x)\Leftrightarrow L_2(x,y)=H(L_1(x,y))$. It is well-known that EA equivalence implies CCZ-equivalence, but the converse is false. The differential spectrum and extended Walsh spectrum are invariant under EA and CCZ-equivalence; the algebraic degree is not invariant under CCZ-equivalence but it is invariant under EA equivalence, for functions of degrees at least 2.

3 New differentially 4-uniform bijections

Let $n$ be a positive even integer. In this section, we obtain a class of differentially 4-uniform bijections of the form $x\in \mathbb {F}_{2^n}\rightarrow (T(x))^{-1}\in \mathbb {F}_{2^n}$ (we shall call such composition with $T$ “permuting the inverse function”), where $T$ is a bijective mapping from $\mathbb {F}_{2^n}$ to $\mathbb {F}_{2^n}$ and $x\rightarrow x^{-1}$ is the inverse function, with the convention $0^{-1}=0$ (we shall always use this kind of convention in the sequel). It is well-known that the inverse function is a differentially 4-uniform bijection [12].

Construction 1

Let $n\ge 6$ be an even number and $U$ be a subset of $\mathbb {F}_{2^n}$ satisfying:

• a) for any $x\in U$, $x+1\in U$ and

• b) for any $x\in U$, $tr_1^n(x^{-1})=1$.

We define an $(n,n)$-function $F$ on $\mathbb {F}_{2^n}$ as follows:

$$\begin{aligned} F(x)&= \left\{ \begin{array}{ll} (x+1)^{-1},&{} \quad x\in U\\ x^{-1},&{} \quad x\in \mathbb {F}_{2^n}\setminus U\\ \end{array} \right. . \end{aligned}$$

In fact, the function $F$ can be rewritten as

$$\begin{aligned} F(x)=(x+\delta _U(x))^{-1} \end{aligned}$$

(1)

where $\delta _U$ is the indicator function of $U$, i.e. $\delta _U(x)=1$ if $x\in U$ and $\delta _U(x)=0$ otherwise. Since $U$ is stable under the addition by 1, i.e.,

$$\begin{aligned} \delta _U(x)+\delta _U(x+1)=0,\, \quad \mathrm {for\, all}\, x\in \mathbb {F}_{2^n}, \end{aligned}$$

(2)

we can easily see that $x\rightarrow x+\delta _U(x)$ is its own inverse, and therefore is a bijection on $\mathbb {F}_{2^n}$. Hence, function $F$ is bijective on $\mathbb {F}_{2^n}$.

3.1 Differential 4-uniformity

In what follows, we shall prove that any function $F$, defined above, is differentially 4-uniform. For doing this, we first need several preliminary results.

Lemma 1

([10]) Let $n$ be a positive integer. For any $(a,b)\in \mathbb {F}_{2^n}^*\times \mathbb {F}_{2^n}$ let us define the polynomial $\mu (x)=ax^2+bx+c\in \mathbb {F}_{2^n}[x]$. Then $\mu (x)=0$ has 2 solutions if and only if $tr_1^n(b^{-2}ac)=0$.

Lemma 2

Let $n$ be a positive integer. For any $b\in \mathbb {F}_{2^n}^*$, let us define the polynomial $\mu (x)=bx^2+(1+b)x+b^{-1}\in \mathbb {F}_{2^n}[x]$. If $\mu (x)=0$ has 2 solutions $\lambda ,\nu$ then we have $tr_1^n(\lambda ^{-1})=tr_1^n(\nu ^{-1})=0$ if $n$ is even and $tr_1^n(\lambda ^{-1})=tr_1^n(\nu ^{-1})=1$ if $n$ is odd.

Proof

The two roots $\lambda$ and $\nu$ of the equation $bx^2+(1+b)x+b^{-1}=0$ are nonzero since $b\ne 0$. It is sufficient to show that $tr_1^n(\lambda ^{-1}+1)=tr_1^n(\nu ^{-1}+1)=0$. Note that $\lambda ^{-1}$ and $\nu ^{-1}$ are the roots of the reciprocal equation $b+(1+b)x+b^{-1}x^2=0$. Multiplying by $b$, we have $x^2+(b+b^2)x+b^2=0$. Given an equation $x^2+Sx+P=0$, adding 1 to each root corresponds to keeping the same sum $S$ and to replacing the product $P$ by $P+S+1$. We obtain here the equation $x^2+(b+b^2)x+b+1=0$ having roots $\lambda ^{-1}+1$ and $\nu ^{-1}+1$. What we need is to prove that the roots of this equation have null trace, that is, have the form $u+u^2$. Given an equation $x^2+sx+p=0$ whose roots are $u$ and $v$, the equation whose roots are $u+u^2$ and $v+v^2$ is $x^2+Sx+P=0$ with $S=s+s^2$ and $P=p(1+s+p)$. Applying this observation to the equation $x^2+(b+b^2)x+b+1=0$ with $s=b$ and $S=b+b^2$, the roots have null trace only if there exists $p$ in $\mathbb {F}_{2^n}$ such that $p^2+(b+1)p=b+1$. The existence of $p$ is guaranteed by Lemma 1, due to the fact that $tr_1^n((b+1)^{-1})=tr_1^n((b+1)^{-2})=0$, where the latter follows from applying Lemma 1 to the original equation $bx^2+(1+b)x+b^{-1}=0$ with two solutions. $\square$

The proof of the differential 4-uniformity of our functions will be based on the following lemma:

Lemma 3

Let $U$ be the set defined in Construction 1. For any $(a,b)\in \mathbb {F}_{2^n}^*\times \mathbb {F}_{2^n}$, let us consider the four following equations on $\mathbb {F}_{2^n}$:

$$\begin{aligned} x^{-1}+(x+a)^{-1}&=b, \quad x,x+a\in \mathbb {F}_{2^n}\setminus U\end{aligned}$$

(3)

$$\begin{aligned} (x+1)^{-1}+(x+1+a)^{-1}&=b, \quad x,x+a\in U\end{aligned}$$

(4)

$$\begin{aligned} (x+1)^{-1}+(x+a)^{-1}&=b, \quad x\in U,x+a\in \mathbb {F}_{2^n}\setminus U\end{aligned}$$

(5)

$$\begin{aligned} x^{-1}+(x+1+a)^{-1}&=b, \quad x\in \mathbb {F}_{2^n}\setminus U,x+a\in U. \end{aligned}$$

(6)

If $(a,b)\in \mathbb {F}_{2^n}\setminus \{0,1\}\times \mathbb {F}_{2^n}^*$, then the following statements hold:

• (1) The sum of the numbers of solutions of (3) and (4) is at most 4. Moreover:

  • (1.1) If $ab\not =1$, then the sum of the numbers of solutions of (3) and (4) is at most 2.

  • (1.2) If $a\in U$ and $b(a+1)=1$, then Eqs. 3 and refsolu2 have no solution.

• (2) The sum of the numbers of solutions of (5) and (6) is at most 4. Moreover:

  • (2.1) If $b(a+1)\not =1$ or $a\not \in U$, then the sum of the numbers of solutions of (5) and (6) is at most 2.

  • (2.2) If $ab=1$, then Eqs. 5 and 6 have no solution.

Lemma 3 will be proved in Appendix. Now we are ready to prove our main result.

Theorem 1

The bijection $F$ defined in Construction 1 is differentially 4-uniform.

Proof

Let us check that

$$\begin{aligned} F(x)+F(x+a)=b \end{aligned}$$

(7)

has at most 4 solutions for every fixed $(a,b)\in \mathbb {F}_{2^n}^*\times \mathbb {F}_{2^n}$. By the definition of $F$, (7) is equivalent to Eqs. 3–6. Recall that $F$ is a bijection. Then (7) has no solution for $(a,b)\in \mathbb {F}_{2^n}^*\times \{0\}$. So we only need to consider $(a,b)\in \mathbb {F}_{2^n}^*\times \mathbb {F}_{2^n}^*$.

Firstly, we can see that (7) has at most 4 solutions if $(a,b)\in \{1\}\times \mathbb {F}_{2^n}^*$. In this case, (3) and (4) become the same equation $x^{-1}+(x+a)^{-1}=b$ with $x,x+a$ in $U$ and $\mathbb {F}_{2^n}\setminus U$ respectively. Since the function $x\rightarrow x^{-1}$ is 4 uniform, we can see that the sum of the numbers of solutions of (3) and (4) is at most 4; and (5), (6) have no solution for $a=1$ since we assume $b\not =0$.

Secondly, we prove that (7) has at most 4 solutions for every $(a,b)\in \mathbb {F}_{2^n}\setminus \{0,1\}\times \mathbb {F}_{2^n}^*$.

Case A $ab=1$.

It follows from (1) in Lemma 3 that the sum of the numbers of solutions of (3) and (4) is at most 4 and from (2.2) of Lemma 3 that Eqs. 5 and 6 have no solution. Therefore, (7) has at most 4 solutions.

Case B $ab\not =1$

• Case B-1 $b(a+1)=1$ and $a\in U$

According to (1.2) in Lemma 3, Eqs. 3 and 4 have no solution in this case, and according to (2) in Lemma 3, the sum of the numbers of solutions of (5) and (6) is at most 4. This implies that (7) has at most 4 solutions in this case.

• Case B-2 $b(a+1)\not =1$ or $a\not \in U$

According to (1.1–2.1 resp.) in Lemma 3 respectively, the sum of the numbers of solutions of (3) and (4) (5 and 6 resp.) is at most 2. So (7) has at most 4 solutions.

Hence, function $F$ is differentially 4-uniform. $\square$

Remark 1

We should mention that the condition (a) in Construction 1 is a necessary and sufficient condition such that $F$ is bijective. And the condition (b) in Construction 1 is a sufficient but not necessary condition such that $F$ is differentially 4-uniform. Some examples of differentially 4-uniform bijections which satisfy condition (a) but do not satisfy condition (b) can be found in [16] according to Remark 2.

4 Other cryptographic properties of $F$

In this section, we focus on the cryptographic properties of $F$. We first prove that $F$ has maximum algebraic degree $n-1$. In addition, we obtain several lower bounds on the nonlinearity for $F$. Finally, we show that our functions, in some cases, are CCZ-inequivalent to known differentially 4-uniform power functions, including the inverse function, and to quadratic functions.

4.1 Algebraic degree

Theorem 2

For every even $n\ge 6$, $F$ has algebraic degree $n-1$.

Proof

Recall that $F$ has algebraic degree at most $n-1$ since $F$ is bijective. So we only need to prove that $F$ has algebraic degree at least $n-1$. Recall the following two facts:

• 1. $F$ has algebraic degree at most $k$ if and only if, for every $a\in \mathbb {F}_{2^n}^*$, the Boolean function $tr_1^n(aF)$ defined on $\mathbb {F}_{2^n}$ has algebraic degree at most $k$;

• 2. An $n$-variable Boolean function $f$ has algebraic degree $n$ if and only if $\mathrm {wt}(f)\equiv 1\pmod 2$.

If $F$ has algebraic degree at most $k$, we have that, for every $n$-variable Boolean function $h$ with $\mathrm {deg}(h)\le n-k-1$, the expression $tr_1^n(\sum _{x\in \mathbb {F}_{2^n}}aF(x)h(x))=\sum _{x\in \mathbb {F}_{2^n}}$ $tr_1^n(aF(x))h(x)$ is null for all $a\in \mathbb {F}_{2^n}^*$ and hence $\sum _{x\in \mathbb {F}_{2^n}}F(x)h(x)=0$.

Therefore, for proving that $F$ has algebraic degree at least $n-1$, it is sufficient to show that there exists a Boolean function $h$ with algebraic degree at most 1 such that $\sum _{x\in \mathbb {F}_{2^n}}F(x)h(x)\ne 0$. Taking $h(x)=tr_1^n(x)$ which has algebraic degree $1$, we have

$$\begin{aligned} \sum _{x\in \mathbb {F}_{2^n}}F(x)h(x)&= \sum _{x\in \mathbb {F}_{2^n}}tr_1^n(x)(x+\delta _U(x))^{-1}\\&= \sum _{x\in \mathbb {F}_{2^n}}tr_1^n(x+\delta _U(x))x^{-1}\\&= \sum _{x\in U}tr_1^n(x+1)x^{-1}+\sum _{x\in \mathbb {F}_{2^n}\setminus U}tr_1^n(x)x^{-1}\\&= \sum _{x\in \mathbb {F}_{2^n}}tr_1^n(x)x^{-1}\\&= \sum _{x\in \mathbb {F}_{2^n}^*}\sum _{i=0}^{n-1}x^{2^i-1}\\&= 1 \end{aligned}$$

where we use that $x\rightarrow x+\delta _U(x)$ is its own inverse in the second identity, that $tr_1^n(1)=0$ for even $n$ in the fourth identity, and that $\sum _{x\in \mathbb {F}_{2^n}^*}x^{2^i-1}=\sum _{x\in \mathbb {F}_{2^n}^*}1=1(\mod \,2)$ for $i=0$ and $\sum _{x\in \mathbb {F}_{2^n}^*}x^{2^i-1}=0$ for $0<i<n$ in the last identity. $\square$

Remark 2

It is well-known that any $(n,n)$-function and its compositional inverse function are CCZ-equivalent. In fact, we can easily verify that the compositional inverse function of any bijection of the form $\left( x+g(x)\right) ^{-1}$ is $x^{-1}+g(x^{-1})$. Therefore, by Eqs. 1 and 2, we have that the compositional inverse function of $F$ is $F^{-1}(x)=x^{-1}+\delta _U(x^{-1})$. We should point that there possibly exist some sets $U$ such that our functions are CCZ-equivalent to some functions generated in [16], but it is difficult to find such sets $U$ and we did not find any example. Using a similar argument as the proof of Theorem 2, we can easily see that $F^{-1}$ has algebraic degree $n-1$ as well.

4.2 Nonlinearity

In this subsection, we will give several lower bounds on the nonlinearity of $F$. Let us first give a lower bound on the nonlinearity of $F$, which only relies on the nonlinearity of the inverse function and on the size of $U$.

Let us denote by $I$ the inverse function. We recall what we know on the Walsh spectrum of the component functions of $I$.

Lemma 4

([14]) For any positive integer $n$ and arbitrary $a\in \mathbb {F}_{2^n}^*$, the Walsh spectrum of $tr_1^n(ax^{-1})$ defined on $\mathbb {F}_{2^n}$ can take any value divisible by $4$ in the range $[-2^{{n/2}+1}+1,2^{{n/2}+1}+1]$.

By Lemma 4, the following naive bound on the nonlinearity of $F$ is straightforward.

Theorem 3

For every even $n\ge 6$, we have $NL(F)\ge 2^{n-1}-2^{n/2}-|U|$.

Proof

For any $(a,b)\in \mathbb {F}_{2^n}^*\times \mathbb {F}_{2^n}$, we have

$$\begin{aligned} |W_F(a,b)|&= \Bigg |\sum _{x\in \mathbb {F}_{2^n}\setminus U}(-1)^{tr_1^n(ax^{-1}+bx)}+\sum _{x\in U}(-1)^{tr_1^n(a(x+1)^{-1}+bx)}\Bigg |\\&= \Bigg |\sum _{x\in \mathbb {F}_{2^n}}(-1)^{tr_1^n(ax^{-1}+bx)}+\sum _{x\in U}(-1)^{tr_1^n(a(x+1)^{-1}+bx)}-\sum _{x\in U}(-1)^{tr_1^n(ax^{-1}+bx)}\Bigg |\\&\le |W_I(a,b)|+2|U|. \end{aligned}$$

By Lemma 4 we have $|W_F(a,b)|\le 2^{n/2+1}+2|U|$ and therefore $NL(F)\ge 2^{n-1}-2^{n/2}-|U|$. $\square$

This bound indicates that if the size of $U$ is very small, then the nonlinearity of $F$ is close to that of $I$, which is very high. However, if the size of $U$ is too small, then $F$ is very close to the inverse function. Then if there exists an attack on the inverse function, this attack can represent a threat for function $F$ too. Thus, the size of $U$ should not be too small.

For even $n\ge 6$, we can see that the union of all the sets $U$ satisfying the conditions of Construction 1, that is the set $\{x\in \mathbb {F}_{2^n}\, |\, tr_1^n(x^{-1})=tr_1^n((x+1)^{-1})=1\}$, that we shall denote by $U_{\max }$ from now on, is the largest one. Let us define $U_{m_0}=\{x\in U_{\max }\,|\, tr_1^n(x)=0\}$ and $U_{m_1}=\{x\in U_{\max }\,|\, tr_1^n(x)=1\}$ from now on. We can see that $U_{\max }=U_{m_0}\cup U_{m_1}$, and both $U_{m_0}$ and $U_{m_1}$ satisfy the two conditions for $U$ in Construction 1. It is easily checked that

$$\begin{aligned} \delta _{U_{\max }}(x)&= tr_1^n\big (x^{-1}\big )tr_1^n\big ((x+1)^{-1}\big )\end{aligned}$$

(8)

$$\begin{aligned} \delta _{U_{m_0}}(x)&= \big (1+tr_1^n(x)\big )tr_1^n\big (x^{-1}\big )tr_1^n\big ((x+1)^{-1}\big ) \end{aligned}$$

(9)

and

$$\begin{aligned} \delta _{U_{m_1}}(x)&= tr_1^n\big (x\big )tr_1^n\big (x^{-1}\big )tr_1^n\big ((x+1)^{-1}\big ) \end{aligned}$$

(10)

In what follows, we will give three lower bounds on the nonlinearity of $F$ with $U=U_{\max }, U_{m_0},U_{m_1}$ respectively.

We need some lemmas and corollaries, which will be useful for establishing our lower bounds.

Lemma 5

Let $n$ be a positive integer and $h$ be a Boolean function defined on $\mathbb {F}_{2^n}$. Then for any $b\in \mathbb {F}_{2^n}$, the following statements hold:

• (1) $\sum \limits _{x\in \mathbb {F}_{2^n}, tr_1^n(x)=0}(-1)^{h(x)+tr_1^n(bx)}=\frac{1}{2}\left( W_h(b)+W_h(b+1)\right)$;

• (2) $\sum \limits _{x\in \mathbb {F}_{2^n}, tr_1^n(x)=1}(-1)^{h(x)+tr_1^n(bx)}=\frac{1}{2}\left( W_h(b)-W_h(b+1)\right)$;

• (3) $|\sum \limits _{x\in \mathbb {F}_{2^n}, tr_1^n(x)=c}(-1)^{h(x)+tr_1^n(bx)}|\le \max \limits _{a\in \mathbb {F}_{2^n}}|W_h(a)|$, where $c\in \mathbb {F}_2$.

We omit the proof of Lemma 5, which follows easily from the fact that $\sum _{x\in \mathbb {F}_{2^n}}(-1)^{tr_1^n(x)}=0$.

Lemma 6

([16]) Let $n$ be a positive integer, then $|\sum _{x\in \mathbb {F}_{2^n}}(-1)^{tr_1^n(ax+bx^{-1}+x^2(x+1)^{-1})}|\le 2\lfloor 2^{n/2+1}\rfloor +4$ for any $(a,b)\in \mathbb {F}_{2^n}\times \mathbb {F}_{2^n}$.

Note that $x^2(x+1)^{-1}=x+1+(x+1)^{-1}$. Then Lemma 6 is equivalent to:

Corollary 1

For any positive integer $n$, we have $|\sum _{x\in \mathbb {F}_{2^n}}(-1)^{tr_1^n(ax+bx^{-1}+(x+1)^{-1})}|\le 2\lfloor 2^{n/2+1}\rfloor +4$ for any $(a,b)\in \mathbb {F}_{2^n}\times \mathbb {F}_{2^n}$.

Lemma 7

For any even integer $n$, we have

$$\begin{aligned} \max _{(a,b)\in \mathbb {F}_{2^n}^*\times \mathbb {F}_{2^n}^*}|\sum _{x\in \mathbb {F}_{2^n},tr_1^n(x)=c}(-1)^{tr_1^n(ax^{-1}+bx)+tr_1^n(x^{-1})tr_1^n((x+1)^{-1})}|\le 6\cdot 2^{n/2}+4, \end{aligned}$$

where $c\in \mathbb {F}_2$.

Proof

For any $(a,b)\in \mathbb {F}_{2^n}^*\times \mathbb {F}_{2^n}^*$, we have

$$\begin{aligned}&\sum _{x\in \mathbb {F}_{2^n}}(-1)^{tr_1^n(ax^{-1}+bx)+tr_1^n(x^{-1})tr_1^n((x+1)^{-1})}\\&= \sum _{x\in \mathbb {F}_{2^n}\setminus \mathbb {F}_2}(-1)^{tr_1^n(ax+bx^{-1})+tr_1^n(x)tr_1^n(x(x+1)^{-1})}+\sum _{x\in \mathbb {F}_2}(-1)^{tr_1^n(ax+bx^{-1})+tr_1^n(x)tr_1^n((x+1)^{-1})}\\&\text{(by } \text{ changing } x \text{ into } x^{-1} \text{ and } \text{ checking } \text{ for } x=0,1 )\\&= \sum _{x\in \mathbb {F}_{2^n}}(-1)^{tr_1^n(ax+bx^{-1})+tr_1^n(x)tr_1^n((x+1)^{-1})} \text{(since } tr_1^n(1)=0 \text{ for } \text{ even } n)\\&= \sum _{x\in \mathbb {F}_{2^n},tr_1^n(x)=0}(-1)^{tr_1^n(ax+bx^{-1})} +\sum _{x\in \mathbb {F}_{2^n},tr_1^n(x)=1}(-1)^{tr_1^n(ax+bx^{-1}+(x+1)^{-1})} \end{aligned}$$

It follows from Lemmas 4 and 5 that

$$\begin{aligned} \Bigg |\sum _{x\in \mathbb {F}_{2^n},tr_1^n(x)=c}(-1)^{tr_1^n(ax+bx^{-1})}\Bigg |\le 2^{n/2+1}. \end{aligned}$$

By Corollary 1 and Lemma 5, we get

$$\begin{aligned} \Bigg |\sum _{x\in \mathbb {F}_{2^n},tr_1^n(x)=c}(-1)^{tr_1^n(ax+bx^{-1}+(x+1)^{-1})}\Bigg |\le 2^{n/2+2}+4 \end{aligned}$$

Therefore, we have $\max _{(a,b)\in \mathbb {F}_{2^n}^*\times \mathbb {F}_{2^n}^*}|\sum _{x\in \mathbb {F}_{2^n},tr_1^n(x)=c}(-1)^{tr_1^n(ax^{-1}+bx)+tr_1^n(x^{-1})tr_1^n((x+1)^{-1})}| \le 6\cdot 2^{n/2}+4$. $\square$

Lemma 8

Let $n$ be an integer and $f$ be a Boolean function defined on $\mathbb {F}_{2^n}$ such that $f(x)+f(x+1)=0$. Then for any $(a,b)\in F_{2^n}^*\times \mathbb {F}_{2^n}$, we have $\sum _{x\in \mathbb {F}_{2^n}}(-1)^{tr_1^n(a(x+f(x))^{-1}+bx)}=\sum _{x\in \mathbb {F}_{2^n}}(-1)^{tr_1^n(ax^{-1}+b(x+f(x)))}$.

Proof

Indeed, $x\rightarrow x+f(x)$ is a bijection on $\mathbb {F}_{2^n}$. The equality is then obtained by the change of variable $x:=x+f(x)$. $\square$

We are now ready to give the lower bounds on the nonlinearity of $F$ with $U=U_{\max }, U_{m_0}$ and $U_{m_1}$ respectively.

Theorem 4

For every even $n\ge 6$, taking $U=U_{\max }$, we have $NL(F)\ge 2^{n-1}-3\cdot 2^{n/2}-2$.

Proof

If $b=0$, then we have $W_F(a,b)=0$ for all $a\in \mathbb {F}_{2^n}^*$ since $F$ is bijective. We assume now that $b\ne 0$. Then, by Lemma 8 and Eq. 8, we have

$$\begin{aligned} W_F(a,b)&= \sum _{x\in \mathbb {F}_{2^n}}(-1)^{tr_1^n(a(x+\delta _{U_{\max }}(x))^{-1}+bx)}\\&= \sum _{x\in \mathbb {F}_{2^n}}(-1)^{tr_1^n(ax^{-1}+b(x+\delta _{U_{\max }}(x)))}\\&= \sum _{x\in \mathbb {F}_{2^n}}(-1)^{tr_1^n(ax^{-1}+bx)+\delta _{U_{\max }}(x)tr_1^n(b)}. \end{aligned}$$

If $tr_1^n(b)=0$, then $W_F(a,b)=\sum _{x\in \mathbb {F}_{2^n}}(-1)^{tr_1^n(ax^{-1}+bx)}$ and hence $|W_F(a,b)|\le 2^{n/2+1}$ according to Lemma 4. If $tr_1^n(b)=1$, we have

$$\begin{aligned} \big |W_F(a,b)\big |&= \Bigg |\sum _{x\in \mathbb {F}_{2^n}}(-1)^{tr_1^n(ax^{-1}+bx)+\delta _{U_{\max }}(x)}\Bigg |\\&= \Bigg |\sum _{x\in \mathbb {F}_{2^n}}(-1)^{tr_1^n(ax^{-1}+bx)+tr_1^n(x^{-1})tr_1^n\left( (x+1)^{-1}\right) }\Bigg |, \end{aligned}$$

which is less or equal to $6\cdot 2^{n/2}+4$ by Lemma 7.

We deduce that $|W_F(a,b)|\le 6\cdot 2^{\frac{n}{2}+1}+4$ for all $(a,b)\in F_{2^n}^*\times \mathbb {F}_{2^n}^*$. Recall that $W_F(a,b)=0$ if $b=0$. Then we can see that $NL(F)\ge 2^{n-1}-3\cdot 2^{n/2}-2$. $\square$

Theorem 5

For every even $n\ge 6$, taking $U=U_{m_0}$, we have $NL(F)\ge 2^{n-1}-2^{n/2+2}-2$.

Proof

Since $F$ is bijective, we have $W_F(a,b)=0$ for all $a\in \mathbb {F}_{2^n}^*,b=0$. We assume now that $b\ne 0$. Applying Lemma 8 to Eq. 9, we have

$$\begin{aligned} W_F(a,b)&= \sum _{x\in \mathbb {F}_{2^n}}(-1)^{tr_1^n(a(x+\delta _{U_{m_0}}(x))^{-1}+bx)}\\&= \sum _{x\in \mathbb {F}_{2^n}}(-1)^{tr_1^n(ax^{-1}+b(x+\delta _{U_{m_0}}(x)))}\\&= \sum _{x\in \mathbb {F}_{2^n}}(-1)^{tr_1^n(ax^{-1}+bx)+\delta _{U_{m_0}}(x)tr_1^n(b)}. \end{aligned}$$

If $tr_1^n(b)=0$, then $W_F(a,b)=\sum _{x\in \mathbb {F}_{2^n}}(-1)^{tr_1^n(ax^{-1}+bx)}$ and therefore $|W_F(a,b)|\le 2^{n/2+1}$, by Lemma 4.

Consider the case $tr_1^n(b)=1$, we get

$$\begin{aligned} W_F(a,b)&= \sum _{x\in \mathbb {F}_{2^n}}(-1)^{tr_1^n(ax^{-1}+bx)+\delta _{U_{m_0}}(x)}\\&= \sum _{x\in \mathbb {F}_{2^n}}(-1)^{tr_1^n(ax^{-1}+bx)+(1+tr_1^n(x))tr_1^n(x^{-1})tr_1^n((x+1)^{-1})}\\&= \sum _{x\in \mathbb {F}_{2^n},tr_1^n(x)=1}(-1)^{tr_1^n(ax^{-1}+bx)}\\&+\sum _{x\in \mathbb {F}_{2^n},tr_1^n(x)=0}(-1)^{tr_1^n(ax^{-1}+bx)+tr_1^n(x^{-1})tr_1^n((x+1)^{-1})} \end{aligned}$$

By Lemmas 4 and 5, we have

$$\begin{aligned} \Bigg |\sum _{x\in \mathbb {F}_{2^n},tr_1^n(x)=1}(-1)^{tr_1^n(ax^{-1}+bx)}\Bigg |\le 2^{n/2+1}. \end{aligned}$$

According to Lemma 7, we have

$$\begin{aligned} \Big |\sum _{x\in \mathbb {F}_{2^n},tr_1^n(x)=0}(-1)^{tr_1^n(ax^{-1}+bx)+tr_1^n(x^{-1})tr_1^n((x+1)^{-1})}\Big |\le 6\cdot 2^{n/2}+4. \end{aligned}$$

Hence, $|W_F(a,b)|\le 8\cdot 2^{n/2}+4$ for $tr_1^n(b)=1$.

Combining above cases, we can see that $|W_F(a,b)|\le 8\cdot 2^{n/2}+4$ for all $(a,b)\in F_{2^n}^*\times \mathbb {F}_{2^n}^*$. Recall that $W_F(a,b)=0$ if $b=0$. Therefore, we have $NL(F)\ge 2^{n-1}-2^{n/2+2}-2$. $\square$

Similar to the case $U=U_{m_0}$, we can easily get a lower bound on the nonlinearity of $F$ with $U=U_{m_1}$.

Theorem 6

For every even $n\ge 6$, taking $U=U_{m_1}$, we have $NL(F)\ge 2^{n-1}-2^{n/2+2}-2$.

4.3 CCZ-inequivalence

Since our functions are derived from the inverse function, we need to investigate whether they are CCZ-inequivalent to the inverse function. We will prove that, for any even $n\ge 6$, our functions are CCZ-inequivalent to the inverse function when the size of $U$ is such that $0<|U|<(2^{n-1}-2^{n/2})/3-2$. Besides, we also prove that our functions are CCZ-inequivalent to the gold functions, the Kasami functions, the functions discussed in [2] and quadratic functions. Thus, our functions are CCZ-inequivalent to known differentially 4-uniform power functions and to quadratic functions for any even $n\ge 6$ when the size of $U$ is such that $0<|U|<(2^{n-1}-2^{n/2})/3-2$.

Proving the CCZ-inequivalence between two functions by directly using the definition of CCZ-equivalence is very difficult, but some CCZ-invariant parameters can be proved to be different for the two functions. Our results on the CCZ-inequivalence rely on the following lemma.

Lemma 9

([5, 7]) The differential and extended Walsh spectra are CCZ-invariant parameters.

As we know, for even $n$, the number of pairs $(a,b)\in \mathbb {F}_{2^n}^*\times \mathbb {F}_{2^n}$ such that $\delta _I(a,b)=4$ is $2^n-1$. According to Lemma 9, for proving that $F$ is CCZ-inequivalent to the inverse function, we only need to prove that the number of pairs $(a,b)$ such that $\delta _F(a,b)=4$ is not $2^n-1$; similarly, for proving that $F$ is not CCZ-equivalent to the gold functions, the Kasami functions, the functions discussed in [2] and quadratic functions, we only need to show that $F$ has extended Walsh spectrum distinct from those of these functions.

We first need the following corollaries which can be deduced from Lemma 4.

Corollary 2

For even $n\ge 6$, we have $2^{n-2}-2^{n/2-1}\le |U_{\max }|\le 2^{n-2}+2^{n/2-1}$

Proof

Let $R=\sum _{x\in \mathbb {F}_{2^n}}(-1)^{tr_1^n(x^{-1}+(1+x)^{-1})}$. On one hand, since the Hamming weights of the functions $tr_1^n(x^{-1})$ and $tr_1^n((1+x)^{-1})$ equal $2^{n-1}$, then $R=2^n-2\mathrm {wt}(tr_1^n(x^{-1})+tr_1^n((1+x)^{-1}))=2^n-2\mathrm {wt}(tr_1^n(x^{-1}))-2\mathrm {wt}(tr_1^n((1+x)^{-1}))+4|U_{\max }|=-2^n+4|U_{\max }|$ and $|U_{\max }|=2^{n-2}+R/4$. On the other hand, $R=\sum _{x\in \mathbb {F}_{2^n}}(-1)^{tr_1^n(x^{-1}+(1+x)^{-1})}=\sum _{x\in \mathbb {F}_{2^n}}(-1)^{tr_1^n(x+(1+x^{-1})^{-1})}=\sum _{x\in \mathbb {F}_{2^n}}(-1)^{tr_1^n(x+1+(x+1)^{-1})}=\sum _{x\in \mathbb {F}_{2^n}}(-1)^{tr_1^n(x+x^{-1})}$, which can be checked separately for $x\not \in \mathbb {F}_2$ and $x\in \mathbb {F}_2$ by using that $tr_1^n(1)=0$. Then by Lemma 4 we have $|R|\le 2^{n/2+1}$ and hence $2^{n-2}-2^{n/2-1}\le |U_{\max }|\le 2^{n-2}+2^{n/2-1}$. $\square$

Remark 3

Obviously, the size of $U$ can be any even integer ranging from $2$ to $U_{\max }$. By Corollary 2, we can see that there are at least $2^{2^{n-3}-2^{n/2-2}}$ different sets $U$. We list in Table 2 the exact numbers of sets $U$ for even $n$ ranging from $6$ to $20$.

Table 2 The exact numbers of the sets $U$

Corollary 3

Let $n\ge 3$ be an integer and $h\in \mathcal {B}_n$ be defined as $h(x)=tr_1^n(x^{-1})$. Define $C_{{\mu ,\nu }}(\tau )=\sum _{x\in \mathbb {F}_{2^n}}(-1)^{tr_1^n(\mu x^{-1})+tr_1^n(\nu (x+\tau )^{-1})}$, where $\mu ,\nu ,\tau \in \mathbb {F}_{2^n}^*$. Then the value of $C_{{\mu ,\nu }}(\tau )$ belongs to $[-2^{{n/2}+1}-3, 2^{{n/2}+1}+1]$ and is divisible by $4$.

Proof

For any $\mu ,\nu ,\tau \in \mathbb {F}_{2^n}^*$, we have (still using the convention $\frac{1}{0}=0$)

$$\begin{aligned} C_{{\mu ,\nu }}(\tau )&=\sum _{x\in \mathbb {F}_{2^n}}(-1)^{tr_1^n(\frac{\mu }{x}+\frac{\nu }{x+\tau })}\\&=\sum _{x\in \mathbb {F}_{2^n}\setminus \{0,\tau \}}(-1)^{tr_1^n(\frac{\mu }{x}+\frac{\nu }{x+\tau })}+(-1)^{tr_1^n(\frac{\mu }{\tau })}+(-1)^{tr_1^n(\frac{\nu }{\tau })}\\&=\sum _{x\in \mathbb {F}_{2^n}\setminus \{0,\tau ^{-1}\}}(-1)^{tr_1^n(\mu x+\frac{\nu x}{1+\tau x})}+(-1)^{tr_1^n(\frac{\mu }{\tau })}+(-1)^{tr_1^n(\frac{\nu }{\tau })}\\&=\sum _{x\in \mathbb {F}_{2^n}\setminus \{0,\tau ^{-1}\}}(-1)^{tr_1^n(\mu x+\frac{1}{1+\tau x}\cdot \frac{\nu }{\tau }+\frac{\nu }{\tau })}+(-1)^{tr_1^n(\frac{\mu }{\tau })}+(-1)^{tr_1^n(\frac{\nu }{\tau })}\\&=\sum _{x\in \mathbb {F}_{2^n}\setminus \{0,1\}}(-1)^{tr_1^n(\frac{\mu x}{\tau }+\frac{\nu }{\tau x}+\frac{\mu }{\tau }+\frac{\nu }{\tau })}+(-1)^{tr_1^n(\frac{\mu }{\tau })}+(-1)^{tr_1^n(\frac{\nu }{\tau })}\\&=\sum _{x\in \mathbb {F}_{2^n}\setminus \{0,\frac{\tau }{\nu }\}}(-1)^{tr_1^n(\frac{1}{x}+\frac{\mu \nu }{\tau ^2}x)+tr_1^n(\frac{\mu }{\tau }+\frac{\nu }{\tau })}+(-1)^{tr_1^n(\frac{\mu }{\tau })}+(-1)^{tr_1^n(\frac{\nu }{\tau })}\\&=\sum _{x\in \mathbb {F}_{2^n}}(-1)^{tr_1^n(\frac{1}{x}+\frac{\mu \nu }{\tau ^2}x)+tr_1^n(\frac{\mu }{\tau }+\frac{\nu }{\tau })}- (-1)^{tr_1^n(\frac{\mu }{\tau }+\frac{\nu }{\tau })}-(-1)^{tr_1^n(0)}\\&\qquad +(-1)^{tr_1^n(\frac{\mu }{\tau })}+(-1)^{tr_1^n(\frac{\nu }{\tau })} \end{aligned}$$

where the third, fifth, and sixth identities hold by changing $x$ to ${1\over x}$, ${x+1\over \tau }$, and ${\nu x\over \tau }$ respectively. Note that $-(-1)^{tr_1^n(\frac{\mu }{\tau }+\frac{\nu }{\tau })}-(-1)^{tr_1^n(0)}+(-1)^{tr_1^n(\frac{\mu }{\tau })}+(-1)^{tr_1^n(\frac{\nu }{\tau })}$ equals $0$ or $-4$. According to Lemma 4, we can see that $C_{{\mu ,\nu }}(\tau )$ belongs to $[-2^{{n/2}+1}-3, 2^{{n/2}+1}+1]$ and is divisible by $4$. This finishes the proof. $\square$

In addition, we need the following lemmas.

Lemma 10

Let $n$ be an even number and $U$ be a set defined in Construction 1. Then for any $\beta \in U$, there is no $a\in \mathbb {F}_{2^n}$ such that

$$\begin{aligned} a(\beta +1)^{-1}+a(\beta +a)^{-1}+1=0, \end{aligned}$$

(11)

Proof

In (11), note that $a\ne \beta$ and $\beta \ne 1$ because of $1\not \in U$. Multiplied by $(\beta +1)(\beta +a)$, it gives $a^2+\beta a+(\beta ^2+\beta )=0$. Further, $\beta \not =0$ because of $0\not \in U$. We then have $tr_1^n((\beta ^2+\beta )\beta ^{-2})=tr_1^n(1+\beta ^{-1})=tr_1^n(1)+tr_1^n(\beta ^{-1})=0+1=1$ for $n$ even and $\beta \in U$. Hence, it follows from Lemma 1 that $a^2+\beta a+(\beta ^2+\beta )=0$ has no solution in $\mathbb {F}_{2^n}$. That is to say, there is no element $a\in \mathbb {F}_{2^n}$ satisfying Eq. 11. $\square$

Lemma 11

Let $n$ be an even number and $U$ be the set defined in Construction 1. Then for any $\beta \in U$ and $\xi \in \mathbb {F}_{2^n}$, there are at most two elements $a\in \mathbb {F}_{2^n}\setminus \{0,\beta \}$ such that $\left( (\beta +1)^{-1}+(\beta +a)^{-1}\right) {\xi }^2+\left( a(\beta +1)^{-1}+a(\beta +a)^{-1}\right) {\xi }+a=0$.

Proof

If $\xi =0$, then there is no such element $a\in \mathbb {F}_{2^n}\setminus \{0,\beta \}$. So we assume that $\xi \ne 0$. Since $a(\beta +a)^{-1}=1+\beta (\beta +a)^{-1}$, the equality

$$\begin{aligned} \left( (\beta +1)^{-1}+(\beta +a)^{-1}\right) {\xi }^2+\left( a(\beta +1)^{-1}+a(\beta +a)^{-1}\right) {\xi }+a=0 \end{aligned}$$

is equivalent to

$$\begin{aligned} ({\xi }^2+\beta \xi )(\beta +a)^{-1}+(\xi (\beta +1)^{-1}+1)a+(\xi +{\xi }^2(\beta +1)^{-1})=0. \end{aligned}$$

(12)

Since $\beta \not =a$, multiplied by $\beta +a$, (12) becomes

$$\begin{aligned} ({\xi }^2+\beta \xi )+(\xi (\beta +1)^{-1}+1)(\beta a+a^2)+(\xi +{\xi }^2(\beta +1)^{-1})(\beta +a)=0, \end{aligned}$$

or equivalently

$$\begin{aligned} \left( \xi (\beta +1)^{-1}+1\right) a^2+ (\xi (\beta +1)^{-1}+1)(\beta +\xi )a+{\xi }^2(\beta +1)^{-1}=0, \end{aligned}$$

(13)

which is a quadratic equation in $a$. Note that $\xi \not =0$. Then we have ${\xi }^2(\beta +1)^{-1}\not =0$ and hence the coefficients of Eq. 13 do not vanish simultaneously, implying that for any $\beta \in U$ and $\xi \in \mathbb {F}_{2^n}^*$, there are at most two elements $a\in \mathbb {F}_{2^n}\setminus \{0,\beta \}$ satisfying Eq. 12. $\square$

We now show the CCZ-inequivalence of our functions.

Theorem 7

For every even $n\ge 6$, the functions generated by Construction 1 are CCZ-inequivalent to the inverse function when the set $U$ is such that $0<|U|< \frac{2^{n-1}-2^{n/2}}{3}-2$.

Proof

As mentioned before, it suffices to show that the number of pairs $(a,b)\in \mathbb {F}_{2^n}^*\times \mathbb {F}_{2^n}$ such that $\delta _F(a,b)=4$ is strictly greater than $2^n-1$ when $0<|U|\le \lceil \frac{2^{n-1}-2^{n/2}}{3}\rceil -3$. Recall that (7) is equivalent to Eqs. 3–6. For obtaining such a lower bound, we consider the following two cases:

• Case 1 $ab=1$

For every $a\not \in U$, we can see that $x=0,x=a$ are two solutions of Eq. 3. Let us bound from below the number of cases that Eq. 3 has two more solutions. It follows from $ab=1$ that $tr_1^n((ab)^{-1})=tr_1^n(1)=0$ and hence the equation $bx^2+abx+a=0$ has two solutions, that is, $\left( \frac{x}{a}\right) ^2+\frac{x}{a}=\frac{1}{ab}$ has two solutions. More precisely, it is easy to see that, denoting by $d$ the integer $(2^n-1)/3$ and by $\alpha$ a primitive element of $\mathbb {F}_{2^n}$, the two solutions are $a\alpha ^{d}$ and $a\alpha ^{d}+a$ since $\alpha ^{2d}+\alpha ^{d}=1$. Hence, if $a\alpha ^{d}\not \in U$ and $a\alpha ^{d}+a\not \in U$ then we can check that $a\alpha ^{d}$ and $a\alpha ^{d}+a$ are two more solutions of Eq. 3. Note that $a\alpha ^{d}$ and $a\alpha ^{d}+a$ range over $\mathbb {F}_{2^n}^*$ when $a$ ranges over $\mathbb {F}_{2^n}^*$. So there are at most $2|U|$ elements $a\in \mathbb {F}_{2^n}^*$ such that $a\alpha ^{d}\in U$ or $a\alpha ^{d}+a\in U$. Further by excluding the case where $a\in U$, there are at least $2^n-1-3|U|$ pairs $(a,a^{-1})$ with $\delta _F(a,a^{-1})=4$.

• Case 2 $ab\not =1$, $b\ne 0$

Note that we need to exclude $b=0$ because, $F$ being bijective, we have $\delta _F(1,0)=0$. For simplicity, we restrict our discussion to the case that there exists $\beta \in U$ such that $b=(\beta +1)^{-1}+(\beta +a)^{-1}$, which satisfies $ab\not =1$ by Lemma 10. In this case, $\beta$ and $\beta +a$ are respectively the solutions of Eqs. 5 and 6 only if $\beta \in U$ and $\beta +a\in \mathbb {F}_{2^n}\setminus U$. Additionally, we require $tr_1^n((ab)^{-1})=0$ so that $bx^2+abx+a=0$ has two solutions and then (3) may have two solutions. We shall bound from below the number of such pairs $(a,b)$.

Firstly we bound the cardinality of $T_{\beta }=\{a\in \mathbb {F}_{2^n}\setminus \{0,1,\beta \}\,|\, tr_1^n((ab)^{-1})=0, b=(\beta +1)^{-1}+(\beta +a)^{-1}\}$ for given $\beta \in U$, where we exclude $a=1$ for avoiding $b=0$ and $a=\beta$ for simplifying our proof. Since

$$\begin{aligned} (ab)^{-1}&= (a(\beta +1)^{-1}+a(\beta +a)^{-1})^{-1}\\&= (\beta ^2+\beta +a\beta +a)(a+a^2)^{-1}\\&= (\beta ^2+\beta +a\beta +a)(a^{-1}+(a+1)^{-1})\\&= (\beta ^2+\beta )a^{-1}+\beta +1+(\beta ^2+\beta +a\beta +a)(a+1)^{-1}\\&= (\beta ^2+\beta )a^{-1}+(\beta ^2+1)(a+1)^{-1}, \end{aligned}$$

applying Corollary 3 in place of $x=a$, $\mu =\beta ^2+\beta$, $\nu =\beta ^2+1$ and $\tau =1$, we deduce that $C_{{\mu ,\nu }}(\tau )=2N-2^n\ge -2^{{n/2}+1}-3$ where $N$ is the number of $a\in \mathbb {F}_{2^n}$ with $tr_1^n((ab)^{-1})=0$. That is, $2N-2^n\ge -2^{{n/2}+1}$ because $C_{{\mu ,\nu }}(\tau )$ is divisible by 4 and $n$ is even. Therefore, $|T_{\beta }|\ge 2^{n-1}-2^{n/2}-3$.

For any $a\in T_{\beta }$, assume that the two distinct solutions of equation $bx^2+abx+a=0$, or equivalently

$$\begin{aligned} \left( (\beta +1)^{-1}+(\beta +a)^{-1}\right) x^2+\left( a(\beta +1)^{-1}+a(\beta +a)^{-1}\right) x+a=0 \end{aligned}$$

(14)

are $x_a'$ and $x_a''$. There are 3 cases: 1) $x_a',x_a''\in U$, 2) $x_a',x_a''\not \in U$ and 3) $x_a'\in U,x_a''\not \in U$ or $x_a''\in U,x_a'\not \in U$. Suppose that cases 1), 2) and 3) occur $t_1$, $t_2$ and $t_3$ times respectively with $a$ ranging through $T_{\beta }$. Straightforwardly, $t_1+t_2+t_3=|T_{\beta }|$. It further follows from Lemma 11 that, if we let $x=x_a'$ or $x=x_a''$ in (14), there are at most two $a\in T_{\beta }$ such that Eq. 14 holds. This means that every element of $U$ as the solutions of (14) appears at most two times when $a$ runs through $T_{\beta }$. So we have $2t_1+t_3\le 2|U|$ and hence $t_2=|T_{\beta }|-(t_1+t_3)\ge |T_{\beta }|-(2t_1+t_3)\ge |T_{\beta }|-2|U|$.

Denote by $S_\beta$ the subset of $T_{\beta }$ such that Eq. 3 has two distinct solutions. We then have $|S_\beta |=t_2\ge 2^{n-1}-2^{n/2}-2|U|-3$. Define $S'_\beta =\{a\in S_\beta \,|\, \beta +a\not \in U\}$ whose size is at least $2^{n-1}-2^{n/2}-3|U|-3$. By the definition of $S_{\beta }'$ and $\beta \in U$, $\beta$ and $\beta +a$ are respectively solutions of (5) and (6) for any $a\in S'_\beta$. Note that $\beta \not =\beta +a$ for every $a\in T_{\beta }$ due to $a\not =1$. Note also that neither $\beta$ nor $\beta +a$ are solutions of (3) due to $\beta \in U$. In other words, for any $a\in S_\beta '$, the four elements $\beta$, $\beta +a$, $x_a'$ and $x_a''$ are distinct. Therefore, given an element $\beta \in U$, for all $a\in S_\beta '$ and $b=(\beta +1)^{-1}+(\beta +a)^{-1}\not =0$ we have $\delta _F(a,b)=4$ in this case.

Next we bound from below the total number of pairs $(a,b)=(a,(\beta +1)^{-1}+(\beta +a)^{-1})$ such that $\delta _F(a,b)=4$ when $\beta$ runs through $U$. For any two distinct elements $\beta _1,\beta _2\in U$, we define $B_i=\{(a,b)\,|\, a\in S'_{\beta _i}, b=(\beta _i+1)^{-1}+(\beta _i+a)^{-1}\}$ for $i=1,2$. We now prove that the intersection of $B_1$ and $B_2$ is empty. Assume that $B_1$ and $B_2$ have a common element $(a,b)$. According to the definitions of $S'_{\beta _1}$ and $S'_{\beta _2}$, $\beta _1,\beta _2$ (resp. $\beta _1+a,\beta _2+a$) are two distinct solutions of (5) and (6), $\beta _1\ne \beta _2+a$ and $\beta _2\ne \beta _1+a$ because of $\beta _1,\beta _2\in U$. Moreover, $\beta _1\ne \beta _1+a$ and $\beta _2\ne \beta _2+a$ because of $a\ne 0$. Hence, $\beta _1, \beta _2, \beta _1+a+1$ and $\beta _2+a+1$ are four distinct solutions of Eq. 7. Since $\beta _1,\beta _2\in U$ and $\beta _1+a,\beta _2+a\not \in U$, none of them is a solutions of (3). By the definitions of $S'_{\beta _1}$ and $S'_{\beta _2}$, Eq. 3 has two distinct solutions $x_a'$ and $x_a''$. That is to say, the six elements $\beta _1, \beta _2, \beta _1+a,\beta _2+a,x_a',x_a''$ are distinct, a contradiction to the fact that $F$ is differentially 4-uniform. Then, for any two distinct elements $\beta _1,\beta _2\in U$, sets $B_1$ and $B_2$ have no common element. Thus, there are at least $\sum _{\beta \in U}|S'_\beta |\ge (2^{n-1}-2^{n/2}-3|U|-3)|U|$ pairs $(a,b)$ with $ab\ne 1$ such that $\delta _F(a,b)=4$ when $\beta$ runs through $U$ in this case.

From above discussion, there are at least $\left( 2^n-1-3|U|\right)$ pairs $(a,b)$ with $ab=1$ such that $\delta _F(a,b)=4$ by Case 1 and there are at least $(2^{n-1}-2^{n/2}-3|U|-3)|U|$ pairs $(a,b)$ with $ab\ne 1$ such that $\delta _F(a,b)=4$ by Cases 2. We then have $\left( 2^n-1-3|U|\right) +\left( 2^{n-1}-2^{n/2}-3|U|-3\right) |U|>2^n-1$, i.e., $\left( 2^{n-1}-2^{n/2}-3|U|-6\right) |U|>0$ if and only if $0<|U|< \frac{2^{n-1}-2^{n/2}}{3}-2$. This completes the proof. $\square$

Theorem 8

For every even $n\ge 6$, the functions $F$ are CCZ-inequivalent to the gold functions, the Kasami functions, the functions discussed in [2] and quadratic functions.

Proof

By Lemma 9, the extended Walsh spectrum is a CCZ-invariant parameter. It is well known that, for even $n$, the elements of the extended Walsh spectra of the gold functions, the Kasami functions and the functions discussed in [2] belong to the set $\{0, \pm 2^{n/2}, \pm 2^{n/2+1}\}$ and that the elements of the extended Walsh spectrum of quadratic functions can be divisible by $2^{n/2}$ (indeed, the component functions of any quadratic function have algebraic degree at most 2. We know that the nonlinearity of any affine function is equal to 0 and the Walsh spectrum of any quadratic Boolean function is $\pm 2^{n/2}$ or $0,\pm 2^{n/2+l}$, where $l\ge 1$). Hence, for proving that $F$ is CCZ-inequivalent to those functions, it is sufficient to prove that $F$ has different extended Walsh spectrum compared to theirs. Note that, for any $(a,b)\in F_{2^n}^*\times \mathbb {F}_{2^n}$, we get

$$\begin{aligned}&W_F(a,b)\\&\quad =\sum _{x\in \mathbb {F}_{2^n}\setminus U}(-1)^{tr_1^n(ax^{-1}+bx)}+\sum _{x\in U}(-1)^{tr_1^n(a(x+1)^{-1}+bx)}\\&\quad =\sum _{x\in \mathbb {F}_{2^n}\setminus U}(-1)^{tr_1^n(ax^{-1}+bx)}+\sum _{x\in U}(-1)^{tr_1^n(a x^{-1}+b(x+1))} \end{aligned}$$

where in the last identity we make use of the fact that $U$ is stable with respect to the addition by 1. Then, $W_F(a,b)=W_I(a,b)$ when $tr_1^n(b)=0$. Let $b_0$ be a nonzero element of $\mathbb {F}_{2^n}^*$ with $tr_1^n(b_0)=0$. Thus, we have $W_F(a,b_0)=W_I(a,b_0)=\sum _{x\in \mathbb {F}_{2^n}}(-1)^{tr_1^n(ax^{-1}+b_0x)}=\sum _{x\in \mathbb {F}_{2^n}}(-1)^{tr_1^n(x^{-1}+ab_0x)}=W_I(1,ab_0)$ for any $a\in \mathbb {F}_{2^n}^*$. Note that $ab_0$ can run through $\mathbb {F}_{2^n}^*$ when $a$ runs through $\mathbb {F}_{2^n}^*$ and $W_I(1,0)=\sum _{x\in \mathbb {F}_{2^n}}(-1)^{tr_1^n(x^{-1})}=0$. Therefore, it follows from Lemma 4 that the extended Walsh spectrum of $F$ includes any value divisible by $4$ in the range $[-2^{{n/2}+1}+1,2^{{n/2}+1}+1]$. That is, the extended Walsh spectrum of $F$ is different from that of the gold functions, the Kasami functions, the functions discussed in [2] and quadratic functions, and then functions $F$ are CCZ-inequivalent to them. This completes the proof. $\square$

By Theorems 7 and 8, we directly get the following corollary.

Corollary 4

For every even $n\ge 6$, $F$ is CCZ-inequivalent to all known differentially 4-uniform power functions and to quadratic functions when the set $U$ is such that $0<|U|< \frac{2^{n-1}-2^{n/2}}{3}-2$.

Remark 4

This is the first time that is mathematically proven that an infinite class of differentially 4-uniform functions is CCZ-inequivalent to all known differentially 4-uniform power functions and to quadratic functions.

For $n=6$, by a Magma program, we checked that there are $14$ elements of $\mathbb {F}_{2^6}$ such that $tr_1^n(x^{-1})=tr_1^n((x+1)^{-1})=1$. So there are $2^7=128$ different sets $U$. With the help of computer, we can obtain all differentially 4-uniform bijections generated by Construction 1. We list them in Table 3, in which $D_t=|\{(a,b)\,|\,\delta _F(a,b)=t\}|$, and $\alpha$ is the default primitive element of $\mathbb {F}_{2^6}$ in Magma version 2.12-16. There are at least 22 classes of CCZ-inequivalent differentially 4-uniform bijections, since there are 22 functions having distinct nonlinearities or differential spectra and these parameters are CCZ-invariant, whereas the number is 7 in [16] and is 3 in [17]. This means that some of our functions are CCZ-inequivalent to those of [16, 17]. We also checked that these 22 classes of differentially 4-uniform bijections are CCZ-inequivalent to the two classes of functions $x^{-1}+tr_1^n(x^2(x+1)^{-1})$ and $x^{-1}+tr\left( x^{-d}+(x^{-1}+1)^d\right)$ where $d=3(2^t+1)$ and $2\le t\le n/2-1$ presented in [16]. We leave open the problem of determining whether our functions and the functions in [8, 16, 17] are pairwise CCZ-inequivalent in general (or EA-inequivalent) and will study it as a subsequent work if possible. We also checked that all of our functions have graph algebraic immunity 2 for $n=6$, which achieve the upper bound on graph algebraic immunity of $(n,n)$-functions for $n=6$. But this is not enough to show that our functions have high graph algebraic immunity. It is interesting to determine the graph algebraic immunity of our functions for $n\ge 8$.

Table 3 The classes of differentially 4-uniform bijections for $n=6$

We shall now prove that $F$ with $U=U_{m_0}$ and $U=U_{m_1}$ are CCZ-inequivalent to known differentially 4-uniform power functions and to quadratic functions. For doing this, we first need two upper bounds on the sizes of $U_{m_0}$ and $U_{m_1}$ respectively.

Lemma 12

For every even $n\ge 6$, we have $2^{n-3}-7\cdot 2^{n/2-2}\le |U_{m_0}|\le 2^{n-3}+7\cdot 2^{n/2-2}$ and $2^{n-3}-5\cdot 2^{n/2-2}\le |U_{m_1}|\le 2^{n-3}+5\cdot 2^{n/2-2}$.

This lemma will be proved in Appendix.

We can easily deduce that $2^{n-3}+7\cdot 2^{n/2-2}<(2^{n-1}-2^{n/2})/3-2$ when $n\ge 12$. Hence, By Lemma 12 and Theorem 7, we directly obtain the following theorem.

Theorem 9

For even $n\ge 12$. $F$ with $U=U_{m_0}$ and $U=U_{m_1}$ are CCZ-inequivalent to known differential 4-uniformity power functions and to quadratic functions.

Remark 5

It seems that it is difficult to mathematically prove whether the functions generated by Construction 1 are pairwise CCZ-inequivalent or to prove a lower bound on the number of CCZ-inequivalent differentially 4-uniform constructed bijections. We leave it as an open problem.

5 Comparison of the nonlinearity with that of all known differentially 4-uniform bijections

In this section, we compare our lower bounds and the actual values on the nonlinearity of $F$ to that of all known differentially 4-uniform bijections.

We first compare our lower bounds and the actual values on the nonlinearity of $F$ to that of known differentially 4-uniform non-power bijections. In [16], two infinite classes of differentially 4-uniform bijections were proposed. They are of the form $x^{-1}+tr_1^n(x^2(x+1)^{-1})$ and $x^{-1}+tr_1^n\left( x^{-d}+(x^{-1}+1)^d\right)$ where $d=3(2^t+1)$ and $2\le t\le n/2-1$. For convenience, we denote these two classes of functions by $Q_1$ and $Q_2$ respectively. For a given infinite class of functions, let us denote by $\mathcal {NL}$ the best known lower bound on their nonlinearity and by $NL$ the actual value of their nonlinearity. We list in Table 4 below, for even numbers of variables ranging from 6 to 12, the concrete values of $\mathcal {NL}$ and $NL$ of our functions and of the functions $Q_1$ and $Q_2$ (we list the values of $NL$ corresponding to the parameter $t$ from $2$ to $n/2-1$ in one cell). We can see from Tables 1 and 4 that although the lower bounds on the nonlinearity of $F$ with $U=U_{\max }$, $U=U_{m_0}$ and $U=U_{m_1}$ are a little less than that of the function $Q_1$, the actual value of the nonlinearity is very close to that of function $Q_1$, and that our three lower bounds are much better than those for function $Q_2$. Particularly, the lower bound on the nonlinearity of $F$ given in Theorem 3 is better than the actual nonlinearities of $Q_1$ and $Q_2$ when we take $|U|<10$ for $n=8$, $|U|<26$ for $n=10$ and $|U|<56$ for $n=12$.

Table 4 Comparison of the lower bound and actual values on nonlinearity

Very recently, Zha et al. [17] presented two classes of differentially 4-uniform bijections, based on modifying the inverse function on the subfield $\mathbb {F}_{2^s}$, where $s$ is an even divisor of $n$. The functions in both of them have maximum algebraic degree $n-1$ and a naive lower bound on their nonlinearity could be proved, which is $2^{n-1}-2^{n/2}-2^s$. As in our Theorem 3, their classes can contain some functions with high nonlinearity when the value of $s$ is small. We should mention that our functions are different from Zha et al.’s functions, because all of our functions satisfy $F(0)=0$ and $F(1)=1$ simultaneously, but their functions do not.

We now compare our lower bounds and the actual values on the nonlinearity of $F$ to those of known differentially 4-uniform power bijections. Recall that all known differentially 4-uniform power bijections have exact nonlinearity $2^{n-1}-2^{n/2}$ which is equal to the best known nonlinearity. We can see from Table 1 that all our lower bounds on nonlinearity of $F$ are strictly less than those for the differentially 4-uniform power bijections. But by Theorem 3, the nonlinearity of our functions can be very close to $2^{n-1}-2^{n/2}$ when we restrict the size of $U$ to a very small value (e.g. $|U|=2$). More interestingly, we can see from Table 1 that the lower bounds on the nonlinearity of $F$ with $U=U_{\max }$, $U=U_{m_0}$ and $U=U_{m_1}$ are not much less than $2^{n-1}-2^{n/2}$ and we can see from Table 4 that the actual values on the nonlinearity of $F$ with those sets are better than their lower bounds.

Obviously, the lower bound given in Theorem 3 is not tight, we give some examples for $n=8$ below to show that Construction 1 can generate bijections with actual nonlinearity larger than those of $Q_1$ and $Q_2$ and very close to $2^{n-1}-2^{n/2}=112$ when the size of $U$ is greater than 10.

Example 1

For $n=8$, let $\alpha$ be the default primitive element of $\mathbb {F}_{2^8}$ in Magma version 2.12-16.

• If $U=\{\alpha ^i\,|\,i\in \{11,22,44,88,95,97,125,133,175,176,190,194,215,235,245,$ $250\}\}$, we have the size of $U$ is $16$ and $NL(F)=106$.

• If $U=\{\alpha ^i\,|\,i\in \{5,10,11,20,21,22,40,42,44,65,69,80,81,84,88,95,97,111,$ $123,125, 130,133,138,160,162,168,175,176,183,189,190,194,215,219,222,$ $235,237,245,246,250\}\}$, we have the size of $U$ is $40$ and $NL(F)=104$.

6 Conclusion

For any even $n\ge 6$, a construction of differentially 4-uniform bijections on $\mathbb {F}_{2^n}$ is proposed in this paper. We deduced a lower bound on the nonlinearity for our functions which is very high in some cases and three improved lower bounds on the nonlinearity for three special subcases. Compared to all known differentially 4-uniform functions, the lower bounds on the nonlinearity of our functions are sometimes very close to the best known ones. The constructed functions have maximum algebraic degree and are CCZ-inequivalent to known differentially 4-uniform power functions and to quadratic functions in some cases. This is the first time that is mathematically proved that an infinite class of differentially 4-uniform bijections contains functions CCZ-inequivalent to known differentially 4-uniform power functions and to quadratic functions.

Appendix

Proof of Lemma 3

For every $a\in \mathbb {F}_{2^n}$, if $x\not =0$ and $x\not =a$, Eq. 3 is equivalent to the equation:

$$\begin{aligned} bx^2+abx+a=0,&x,x+a\in \mathbb {F}_{2^n}\setminus U, \end{aligned}$$

(15)

if $x\not =1$ and $x\not =a+1$, Eq. 4 is equivalent to the equation:

$$\begin{aligned} bx^2+abx+ab+a+b=0,&x,x+a\in U, \end{aligned}$$

(16)

if $x\not =1$ and $x\not =a$, Eq. 5 is equivalent to the equation:

$$\begin{aligned} bx^2+b(a+1)x+ab+a+1=0,&x\in U,x+a\in \mathbb {F}_{2^n}\setminus U, \end{aligned}$$

(17)

and if $x\not =0$ and $x\not =a+1$, Eq. 6 is equivalent to the equation:

$$\begin{aligned} bx^2+b(a+1)x+a+1=0,&x\in \mathbb {F}_{2^n}\setminus U,x+a\in U. \end{aligned}$$

(18)

Note that the root $\lambda$ of the equation $bx^2+abx+a=0$, if exist, is one-to-one corresponding to the root $\lambda +1$ of the equation $bx^2+abx+ab+a+b=0$ plus 1. Since $U$ is stable under the addition by 1, Eqs. 15 and 16 cannot have solutions simultaneously. Therefore, the sum of the numbers of solutions of (15) and (16) is at most 2.

Similarly, the sums of the roots in the equations $bx^2+b(a+1)x+ab+a+1=0$ and $bx^2+b(a+1)x+a+1=0$ both equal $a+1$. If $\gamma$ is a solution of (17), then $\gamma +a +1$ is not a solution of (17) because of $\gamma +a\in \mathbb {F}_{2^n}\setminus U$; and so does for the solution $\gamma$ of (18). That is, each equation has at most one solution. Then, the sum of the numbers of solutions of (17) and (18) is at most 2.

• (1) Note that $0,1\not \in U$ since $tr_1^n(1)=0$. Clearly, $x=1,a+1$ do not satisfy $x,x+a\in U$, which indicate that Eq. 4 has the same solutions as Eq. 16. Recall that the sum of the numbers of solutions of (15) and (16) is at most 2. Then, the sum of the numbers of solutions of (3) and (4) is at most 4 since in contrast to Eqs. 15, 3 may have two more solutions $x=0,a$.

  • (1.1) If $ab\not =1$, obviously $0,a$ are not solutions of (3). Thus, the sum of the numbers of solutions of (3) and (4) is at most 2.

  • (1.1) If $a\in U$ and $b(a+1)=1$, we have again $ab\not =1$ since $b\not =0$. Thus, Eqs. 3 and 4 are equivalent to (15) and (16), respectively. By dividing $ab$ in $b(a+1)=1$, we have $1+a^{-1}=(ab)^{-1}$ and hence $tr_1^n((ab)^{-1})=tr_1^n(1+a^{-1})=tr_1^n(a^{-1})=1$, which implies that (15) has no solution by Lemma 1. Moreover, by $b(a+1)=1$, the equality (16) becomes $bx^2+abx+a+1=0$, which has no solution by Lemma 1 due to $tr_1^n(b(a+1)(ab)^{-2})=tr_1^n((ab)^{-2})=1$. Therefore, (3) and (4) have no solution.

• (2) Since $1\not \in U$, we have that $1$ and $a+1$ are not solutions of (5) and (6) respectively. Hence, the sum of the numbers of solutions of (5) and (6) is at most 4, which is at most 2 more than that of (17) and (18).

  • (2.1) If $b(a+1)\not =1$ or $a\not \in U$, clearly $1,a$ are not solutions of (5) and $0,a+1$ are not solutions of (6). Then Eqs. 5 and 6 have the same solutions as Eqs. 17 and 18. Hence, the sum of the numbers of solutions of (5) and (6) is at most 2, according to the observation above.

  • (2.2) If $ab=1$, then we have $b(a+1)\not =1$ since $b\not =0$. It follows from above that Eqs. 5 and 6 have the same solutions as Eqs. 17 and 18. Assume that $\lambda$ is a solution of (17), then $\lambda \in U$ and hence $tr_1^n(\lambda ^{-1})=1$. Therefore, (17) has no solution, according to Lemma 2. Assume that $\gamma$ is a solution of (18), then we have that $\gamma \not \in U$ and $\gamma +a\in U$. It is easy to verify that $\gamma +a$ is a solution of (17), a contradiction. That is, (18) has no solution. Therefore, we deduce that both (17) and (18) have no solution.

Proof of Lemma 12

Define $A_0=\{x\in \mathbb {F}_{2^n}\,|\, (tr_1^n(x), tr_1^n(x^{-1}),tr_1^n((1+x)^{-1}))=(1,0,0)\}$, $A_1=\{x\in \mathbb {F}_{2^n}\,|\, (tr_1^n(x), tr_1^n(x^{-1}),tr_1^n((1+x)^{-1}))=(1,0,1)\}$, $A_2=\{x\in \mathbb {F}_{2^n}\,|\, (tr_1^n(x), tr_1^n(x^{-1}),tr_1^n((1+x)^{-1}))=(1,1,0)\}$ and $A_3=\{x\in \mathbb {F}_{2^n}\,|\, (tr_1^n(x), tr_1^n(x^{-1}), tr_1^n((1+x)^{-1}))=(1,1,1)\}$. Obviously, $|U_{m_1}|=|A_3|$ according to (10), and $\sum _{i=0}^4|A_i|=2^{n-1}$ due to $\mathrm {wt}(tr_1^n(x))=2^{n-1}$.

Note that $\sum _{x\in \mathbb {F}_{2^n}}(-1)^{tr_1^n(x+x^{-1}+(x+1)^{-1})}=2^n-2\mathrm {wt}(tr_1^n(x+x^{-1}+(x+1)^{-1})) =2^n-2\big (\mathrm {wt}(tr_1^n(x))+\mathrm {wt}(tr_1^n(x^{-1}+(x+1)^{-1}))-2|\{x\in \mathbb {F}_{2^n}\,|\,tr_1^n(x)=tr_1^n(x^{-1}+(x+1)^{-1}) =1\}|\big ) =-2\mathrm {wt}(tr_1^n(x^{-1}+(x+1)^{-1}))+4(|A_1|+|A_2|)$. Then, $4(|A_1|+|A_2|)=\sum _{x\in \mathbb {F}_{2^n}}(-1)^{tr_1^n(x+x^{-1}+(x+1)^{-1})}+2\mathrm {wt}(tr_1^n(x^{-1}+(x+1)^{-1}))$. Recall that in the proof of Corollary 2, we have already proven $|\sum _{x\in \mathbb {F}_{2^n}}(-1)^{tr_1^n(x^{-1}+(1+x)^{-1})}|\le 2^{n/2+1}$. Hence, we have then $2^n-2^{n/2+1}\le 2\mathrm {wt}(tr_1^n(x^{-1}+(x+1)^{-1}))\le 2^n+2^{n/2+1}$. Besides, by Corollary 1, $-2^{n/2+2}-4\le \sum _{x\in \mathbb {F}_{2^n}}(-1)^{tr_1^n(x+x^{-1}+(x+1)^{-1})}\le 2^{n/2+2}+4$. Therefore,

$$\begin{aligned} 2^{n-2}-3\cdot 2^{n/2-1}-1\le |A_1|+|A_2|\le 2^{n-2}+3\cdot 2^{n/2-1}+1 \end{aligned}$$

by $\sum _{i=0}^4|A_i|=2^{n-1}$ which gives

$$\begin{aligned} 2^{n-2}-3\cdot 2^{n/2-1}-1\le |A_0|+|A_3|\le 2^{n-2}+3\cdot 2^{n/2-1}+1 \end{aligned}$$

(19)

Note that

$$\begin{aligned} \sum _{x\in \mathbb {F}_{2^n}, tr_1^n(x)=1}(-1)^{tr_1^n(x^{-1})}&= \frac{1}{2}\left( \sum _{x\in \mathbb {F}_{2^n}}(-1)^{tr_1^n(x^{-1})}-\sum _{x\in \mathbb {F}_{2^n}}(-1)^{tr_1^n(x^{-1}+x)}\right) \\&= -\frac{1}{2}\sum _{x\in \mathbb {F}_{2^n}}(-1)^{tr_1^n(x^{-1}+x)} \end{aligned}$$

and

$$\begin{aligned} \sum _{x\in \mathbb {F}_{2^n}, tr_1^n(x)=1}(-1)^{tr_1^n(x^{-1})}=|A_0|+|A_1|-|A_2|-|A_3|. \end{aligned}$$

Then, by Lemma 4, we have

$$\begin{aligned} -2^{n/2}\le |A_0|+|A_1|-|A_2|-|A_3|\le 2^{n/2} \end{aligned}$$

(20)

Similarly, we have $\sum _{x\in \mathbb {F}_{2^n}, tr_1^n(x)=1}(-1)^{tr_1^n((x+1)^{-1})}=-\frac{1}{2}\sum _{x\in \mathbb {F}_{2^n}}(-1)^{tr_1^n((x+1)^{-1}+x)}$ and then

$$\begin{aligned} -2^{n/2}\le |A_0|+|A_2|-|A_1|-|A_3|\le 2^{n/2}. \end{aligned}$$

(21)

Combining (19)–(21), we get $2^{n-3}-5\cdot 2^{n/2-2}\le |A_3|\le 2^{n-3}+5\cdot 2^{n/2-2}$, which implies $2^{n-3}-5\cdot 2^{n/2-2}\le |U_{m_1}|\le 2^{n-3}+5\cdot 2^{n/2-2}$. By $U_{\max }=U_{m_0}\cup U_{m_1}$ and $2^{n-2}-2^{n/2-1}\le |U_{\max }|\le 2^{n-2}+2^{n/2-1}$, we have $2^{n-3}-7\cdot 2^{n/2-2}\le |U_{m_0}|\le 2^{n-3}+7\cdot 2^{n/2-2}$, which completes the proof.