1 Introduction
It is well known that an APN function, i.e., a differentially 2-uniform function, must have non-trivial nonlinearity (see, e.g., [3, Prop. 13]). For functions with slightly worse differential properties, this does not necessarily need to hold. In particular, there exist differentially 4-uniform permutations with trivial nonlinearity of 0. Although this is not a new result of ours, we think that it is worth highlighting and studying such functions in more detail. For example, one possible application would be to construct other 4-uniform permutations, but with higher nonlinearity. In particular, one can reduce any permutation with trivial nonlinearity to a 2-1 function of the same uniformity and extend it back to a permutation in many possible ways.
Having a function with differential uniformity d, replacing one component by a linear function trivially yields a function with differential uniformity at most 2d and null nonlinearity. However, the crucial part is that the function constructed in that way is again a permutation. We were therefore interested in the following question: Can we find APN permutations for which one component can be replaced by a linear function such that it still remains a permutation?
Anzeige
In the first part of this work, we show that the inverses of Gold functions (see [7, 9]), i.e., the inverses of power permutations \(x \mapsto x^{2^{i}+1}\) in \({\mathbb {F}}_{2^{n}}\) with \(\gcd (i,n)=1\), have such a property. Thus, they yield a construction of 4-uniform permutations with null nonlinearity. We remark that this observation directly leads to the construction of the APN function CCZ-equivalent to \(x\mapsto x^{2^{i}+1}\) and EA-inequivalent to any power function constructed in [2]. Since the Gold functions are permutations only in odd dimension, we further observe that the differentially 4-uniform 2-1 function constructed in [1], which is defined in even and odd dimension (except for n = 4), can also be extended by a linear coordinate in order to obtain a 4-uniform permutation. By showing that such a 2-1 function exists for all n = 3 and n ≥ 5, we therefore conclude that 4-uniform permutations with trivial nonlinearity exist for all n = 3 and n ≥ 5.
In the second part of the paper we focus on 2-1 subfunctions of permutations, that are obtained by discarding one coordinate function. In [8], Idrisova has shown a necessary property on the subfunctions of APN permutations. In particular, for a subfunction \(S \colon {{\mathbb {F}}_{2}^{n}} \rightarrow {\mathbb {F}}_{2}^{n-1}\) of an APN permutation, she showed that, for all non-zero \(\alpha \in {{\mathbb {F}}_{2}^{n}}\), the following two conditions hold:
1.
If {S(x),S(x + α)} = {S(y),S(y + α)}, then either x = y or x = y + α.
2.
If S(x) = S(x + α) and S(y) = S(y + α), then either x = y or x = y + α.
We show that the above mentioned 4-uniform 2-1 function family constructed in [1], which is defined for n = 3 and n ≥ 5, always fulfills this necessary property. Therefore, and interestingly, 4-uniform 2-1 functions from \({\mathbb {F}}_{2^{n}}\) to \({\mathbb {F}}_{2^{n-1}}\) fulfilling this property do not exist only for those n for which we know (at the time of writing) that no APN permutation exists. In her work, Idrisova conjectured that all 4-uniform 2-1 functions from \({\mathbb {F}}_{2^{n}}\) to \({\mathbb {F}}_{2^{n-1}}\) fulfill this property. By using the 4-uniform permutations with null nonlinearity constructed in the first part, we provide counterexamples to that conjecture in the final part of the paper.
1.1 Notation and preliminaries
Let \({\mathbb {F}}_{2} = \{0,1\}\) denote the field with two elements and let \({\mathbb {F}}_{2^{n}}\) denote its extension field of dimension n. By Tr, we denote the trace function over \({\mathbb {F}}_{2^{n}}\) relative to \({\mathbb {F}}_{2}\), i.e., \(\text {Tr} \colon {\mathbb {F}}_{2^{n}} \mapsto {\mathbb {F}}_{2}, x \mapsto x + x^{2} + x^{2^{2}} +{\dots } + x^{2^{n-1}}\). Note that the trace function is \({\mathbb {F}}_{2}\)-linear.
Anzeige
A function \(F \colon {\mathbb {F}}_{2^{n}} \rightarrow {\mathbb {F}}_{2^{m}}\) is called differentially d-uniform if d is the smallest number such that, for every \(a \in {\mathbb {F}}_{2^{n}} \setminus \{0\}\) and every \(b \in {\mathbb {F}}_{2^{m}}\), the equation F(x) + F(x + a) = b has at most d solutions for \(x \in {\mathbb {F}}_{2^{n}}\). A differentially 2-uniform function is called Almost Perfect Nonlinear (APN). The nonlinearity of F, denoted nl(F), is defined as the minimum Hamming distance of any non-trivial component function to all affine Boolean functions.
There are several well-known equivalence relations on vectorial Boolean functions. The function \(G \colon {\mathbb {F}}_{2^{n}} \rightarrow {\mathbb {F}}_{2^{m}}\) is called affine equivalent to F if there exist affine permutations \(A \colon {\mathbb {F}}_{2^{n}} \rightarrow {\mathbb {F}}_{2^{n}}\) and \(B\colon {\mathbb {F}}_{2^{m}} \rightarrow {\mathbb {F}}_{2^{m}}\) such that F ∘ A = B ∘ G. The function G is called extended affine equivalent (EA-equivalent) to F if there exist affine permutations \(A \colon {\mathbb {F}}_{2^{n}} \rightarrow {\mathbb {F}}_{2^{n}}\) and \(B\colon {\mathbb {F}}_{2^{m}} \rightarrow {\mathbb {F}}_{2^{m}}\) and an affine function \(C \colon {\mathbb {F}}_{2^{n}} \rightarrow {\mathbb {F}}_{2^{m}}\) such that F ∘ A = B ∘ (G + C). We finally recall the notion of CCZ-eqivalence. Let \({\Gamma }_{F} := \{ (x,F(x)) \mid x \in {\mathbb {F}}_{2^{n}}\}\) be the function graph of F. The functions F and G are called CCZ-equivalent (see [2, 4]), if there exist an affine permutation \({\mathcal{L}} \colon {\mathbb {F}}_{2^{n}} \times {\mathbb {F}}_{2^{m}} \mapsto {\mathbb {F}}_{2^{n}} \times {\mathbb {F}}_{2^{m}}\) such that \({\Gamma }_{G} = {\mathcal{L}}({\Gamma }_{F})\). The differential uniformity and the nonlinearity are invariant under all of the above equivalence relations.
2 Some 4-uniform permutations
In this section, we give two example families of differentially 4-uniform permutations with trivial nonlinearity.
2.1 Inverses of gold functions: the case of n odd
An interesting construction can be obtained by the inverses of quadratic APN power permutations. For those, it is possible to replace a component function by a linear function and still obtain a permutation.
Proposition 1
Let n ≥ 3 be odd, let \(\alpha \in {\mathbb {F}}_{2^{n}}\) with Tr(α) = 1, and let d = (2i + 1)− 1 mod 2n − 1 with \(\gcd (i,n) = 1\). Then, the mapping
is a differentially 4-uniform permutation with null nonlinearity. The inverse can be given as
$$ G_{\alpha,d}\colon {\mathbb{F}}_{2^{n}} \rightarrow {\mathbb{F}}_{2^{n}}, \quad x \mapsto x^{d} + \text{Tr}(\alpha x^{d}+x) $$
$$ G^{-1}_{\alpha,d}\colon x \mapsto x^{2^{i}+1}+(x^{2^{i}}+x+1)\text{Tr}(\alpha x + x^{2^{i}+1}). $$
Proof
To show that Gα,d is a permutation, we show that the mapping
is an involution. Indeed, we can write \(G^{\prime }_{\alpha ,d}(G^{\prime }_{\alpha ,d}(x))\) as
where the last equality follows from the fact that Tr(1) = Tr(α) = 1 for odd n. The expression for the inverse of Gα,d follows because it can be given as \(G^{-1}_{\alpha ,d}(x) = G^{\prime }_{\alpha ,d}(x)^{2^{i}+1}\).
$$ G^{\prime}_{\alpha,d}(x) := G_{\alpha,d}(x^{2^{i}+1}) = x+\text{Tr}(\alpha x+x^{2^{i}+1}) $$
$$ \begin{array}{@{}rcl@{}} &&x + \text{Tr}(x^{2^{i}+1}) + \text{Tr}(\alpha)\text{Tr}(\alpha x + x^{2^{i}+1}) + \text{Tr}\left( \left( x+\text{Tr}(\alpha x + x^{2^{i}+1})\right)^{2^{i}+1}\right) \\ &=&x + \text{Tr}(x^{2^{i}+1}) + \text{Tr}(\alpha)\text{Tr}(\alpha x + x^{2^{i}+1}) + \text{Tr}(x^{2^{i}+1}) + \text{Tr}\left( \text{Tr}(\alpha x + x^{2^{i}+1})\right) \\ &=&x + \text{Tr}(\alpha)\text{Tr}(\alpha x + x^{2^{i}+1}) + \text{Tr}(1)\text{Tr}(\alpha x + x^{2^{i}+1}) = x, \end{array} $$
The 4-uniformity follows because x↦xd is APN as the inverse of the APN permutation \(x \mapsto x^{2^{i}+1}\) (see [9]). To see that nl(Gα,d) = 0, we observe that Tr(x) = Tr(α ⋅ Gα,d(x)). □
Remark 1
If we define Fd(x) := x + Tr(xd + x), the function \(H_{d}(x) := F_{d}(G_{1,d}^{-1}(x))\) is CCZ-equivalent to x↦xd by construction via the involution
operating on the function graph of x↦y = xd. By using the fact that \(H_{d}(x) = F_{d}(G^{\prime }_{1,d}(x)^{2^{i}+1})\), one can easily see that \(H_{d}(x) = x^{2^{i}+1}+(x^{2^{i}}+x)\text {Tr}(x + x^{2^{i}+1})\), which is equal to the function CCZ-equivalent to \(x\mapsto x^{2^{i}+1}\) and EA- inequivalent to any power function, constructed in [2].
$$ \mathcal{L}\colon {\mathbb{F}}_{2^{n}} \times {\mathbb{F}}_{2^{n}} \rightarrow {\mathbb{F}}_{2^{n}} \times {\mathbb{F}}_{2^{n}}, \quad (x,y) \mapsto \left( y + \text{Tr}(y) + \text{Tr}(x), x+\text{Tr}(x)+\text{Tr}(y)\right) $$
Remark 2
The existence of differentially 4-uniform permutations with trivial nonlinearity is not a new result. In particular, it was shown in [6] that the mapping
is a permutation in \({\mathbb {F}}_{2^{n}}\) for odd n ≥ 3. It was shown in [10] that this permutation is differentially 4-uniform. Although that, to the best of our knowledge, the null nonlinearity of Pn was not mentioned in previous work, it is trivial to observe. It simply holds because Pn is of the form x↦x + xd− 1 + (xd− 1)d for \(d = 2^{\frac {n+1}{2}}\) and thus, Tr(Pn(x)) = Tr(x). Note that \(2^{\frac {n+1}{2}-1}\) is the multiplicative inverse of \(2^{\frac {n+1}{2}+1}\) modulo 2n − 1, so this construction is also related to Gold functions.
$$ P_{n} \colon x \mapsto x + x^{2^{\frac{n+1}{2}}-1} + x^{2^{n}-2^{\frac{n+1}{2}}+1} $$
2.2 A construction covering the case of n even
In [1] Alsalami presented the following family of 4-uniform 2-1 functions, constructed by the finite field inversion.
Proposition 2 (Alsalami 1)
Let n ≥ 3 and let \(\gamma \in {\mathbb {F}}_{2^{n-1}}, \gamma \notin \{0,1\}\) with Tr(γ) = Tr(γ− 1) = 1. The function
is a differentially 4-uniform 2-1 function.
$$ S_{\gamma}\colon {\mathbb{F}}_{2^{n-1}} \times {\mathbb{F}}_{2} \rightarrow {\mathbb{F}}_{2^{n-1}}, \quad (x,x_{n}) \mapsto \gamma^{x_{n}} x^{2^{n-1}-2}, $$
Note that such a function Sγ does not exist for n = 4, because there is no element \(\gamma \in {\mathbb {F}}_{2^{3}}\setminus \{0,1\}\) with Tr(γ) = Tr(γ− 1). More generally, Idrisova remarked in [8] that no 4-uniform 2-1 function from \({\mathbb {F}}_{2^{4}}\) to \({\mathbb {F}}_{2^{3}}\) exists. However, Sγ exists for all other dimensions n = 3 and n ≥ 5 as shown in the following lemma.
Lemma 1
For m = 2 and m ≥ 4, there exist an element \(\gamma \in {\mathbb {F}}_{2^{m}} \setminus \{0,1\}\) with Tr(γ) = Tr(γ− 1) = 1.
Proof
We first consider the case of even m. Since no element in \({\mathbb {F}}_{2^{m}} \setminus \{0,1\}\) is self-inverse, \({\mathbb {F}}_{2^{m}} \setminus \{0,1\}\) can be partitioned into 2m− 1 − 1 sets of the form {γ,γ− 1}. Since exactly half of the elements in \({\mathbb {F}}_{2^{m}}\) have trace 1 and since Tr(0) = Tr(1) = 0, there are 2m− 1 elements in \({\mathbb {F}}_{2^{m}} \setminus \{0,1\}\) with trace 1. From the pigeonhole principle, there is at least one such set {γ,γ− 1} with Tr(γ) = Tr(γ− 1) = 1.
Let now m be odd. Let us define the Boolean functions
$$ \iota \colon {\mathbb{F}}_{2^{m}} \rightarrow {\mathbb{F}}_{2}, x \mapsto \text{Tr}(x^{2^{m}-2}) \quad \kappa \colon {\mathbb{F}}_{2^{m}} \rightarrow {\mathbb{F}}_{2}, x \mapsto \left\{\begin{array}{ll}x &\text{if } x \in {\mathbb{F}}_{2} \\ \text{Tr}(x)+1 &\text{if } x \notin {\mathbb{F}}_{2} \end{array}\right.. $$
Suppose there do not exist \(\gamma \in {\mathbb {F}}_{2^{m}} \setminus \{0,1\}\) with Tr(γ) = Tr(γ− 1), then, \(\forall \gamma \in {\mathbb {F}}_{2^{m}} \setminus \{0,1\}\), it is Tr(γ) = Tr(γ− 1) + 1 and therefore ι = κ because of the definitions of the above functions. However, it is nl(κ) ≤ 2, since κ has Hamming distance 2 from the affine function x↦Tr(x) + 1. Further, it is well known that \(\text {nl}(\iota ) \geq 2^{m-1}-2^{\frac {m}{2}}-2\) (see [3, p. 50], [5]). This is a contradiction if m ≥ 5 and thus, there exists \(\gamma \in {\mathbb {F}}_{2^{m}} \setminus \{0,1\}\) with Tr(γ) = Tr(γ− 1).
Suppose that Tr(γ) = Tr(γ− 1) = 0. Similarly as in the case of even m, we can partition \({\mathbb {F}}_{2^{m}} \setminus \{0,1,\gamma ,\gamma ^{-1}\}\) into 2m− 1 − 2 sets of the form \(\{\tilde {\gamma },\tilde {\gamma }^{-1}\}\). Since exactly half of the elements in \({\mathbb {F}}_{2^{m}}\) have trace 1 and since Tr(0)≠Tr(1), there are 2m− 1 − 1 elements in \({\mathbb {F}}_{2^{m}} \setminus \{0,1,\gamma ,\gamma ^{-1}\}\) with trace 1. From the pigeonhole principle, there is at least one such set \(\{\tilde {\gamma },\tilde {\gamma }^{-1}\}\) with \(\text {Tr}(\tilde {\gamma }) = \text {Tr}(\tilde {\gamma }^{-1}) = 1\). □
The 2-1 functions Sγ as given in Proposition 2 can trivially be extended to permutation on \({\mathbb {F}}_{2^{n}}\). Let \(f \colon {\mathbb {F}}_{2^{n}} \rightarrow {\mathbb {F}}_{2}\) be a Boolean function with |supp(f)| = 2n− 1 and \(S_{\gamma }(\text {supp}(f))={\mathbb {F}}_{2^{n-1}}\), the function
is a permutation on \({\mathbb {F}}_{2^{n}}\). By choosing f(x) = xn, we obtain a 4-uniform permutation with a linear component, i.e., nl(Rγ,f) = 0.
$$ R_{\gamma,f} \colon {{\mathbb{F}}_{2}^{n}} \rightarrow {{\mathbb{F}}_{2}^{n}}, \quad x \mapsto (S_{\gamma}(x),f(x)) $$
3 APN admissible functions
Let \(S = (S_{1},\dots ,S_{n})\) be a vectorial Boolean function defined by its coordinates \(S_{i} \colon {{\mathbb {F}}_{2}^{n}} \rightarrow {\mathbb {F}}_{2}\). For \(j \in \{1,\dots ,n\}\), we define \(S_{(j)} = (S_{1},\dots ,S_{j-1},S_{j+1},\dots ,S_{n})\) as the subfunction from \({{\mathbb {F}}_{2}^{n}}\) to \({\mathbb {F}}_{2}^{n-1}\) of S obtained by omitting the j-th coordinate. In [8], necessary properties on the subfunctions of APN permutations were given in terms of so-called admissible sequences. We slightly reformulate this definition by directly considering the properties of functions and not sequences.
Definition 1 (see 8)
A 4-uniform 2-1 function \(S\colon {{\mathbb {F}}_{2}^{n}} \rightarrow {\mathbb {F}}_{2}^{n-1}\) is called APN admissible, if, for all non-zero \(\alpha \in {{\mathbb {F}}_{2}^{n}}\), the following two conditions hold:
1.
If {S(x),S(x + α)} = {S(y),S(y + α)}, then either x = y or x = y + α.
2.
If S(x) = S(x + α) and S(y) = S(y + α), then either x = y or x = y + α.
The following fact for APN permutation was shown by Idrisova.
Proposition 3 (Prop. 5 of 8)
Let S be a subfunction of an APN permutation, i.e., S = T(j) for an APN permutation \(T \colon {{\mathbb {F}}_{2}^{n}} \rightarrow {{\mathbb {F}}_{2}^{n}}\). Then S is APN admissible.
3.1 The existence of APN admissible functions
If we have an APN permutation in n bit, one directly obtains an APN admissible function according to Proposition 3 by removing one coordinate. One can ask whether APN admissible functions exist in dimensions for which we don’t know APN permutations. For n = 4, APN admissible functions do not exist. In the following, we show that APN admissible functions exist for all n = 3 and n ≥ 5 by showing that Sγ is APN admissible.
Proposition 4
The function Sγ for \(\gamma \in {\mathbb {F}}_{2^{n-1}} \setminus \{0,1\}\) with Tr(γ) = Tr(γ− 1) = 1 is APN admissible.
Proof
Since Sγ is 2-1 and 4-uniform, we only need to show that the two conditions of Definition 1 are met. We first show Condition 1. Let \(x,y,\alpha \in {\mathbb {F}}_{2^{n-1}}\) and \(x_{n},y_{n},\alpha _{n} \in {\mathbb {F}}_{2}\) with (α,αn)≠(0,0) such that
If x = 0, then Sγ(x,xn) = 0. Since the only preimages of 0 are (0,0) and (0,1), Eq. (1) implies y = 0 or y + α = 0. It can easily be derived that (y,yn) = (0,xn) or (y,yn) = (α,xn + αn) from the fact that Sγ(z,zn) = Sγ(z,zn + 1) only holds if z = 0. Thus, Condition 1 is met for x = 0. A similar argument holds for y = 0,x + α = 0, and y + α = 0. Let us therefore assume that x∉{0,α} and y∉{0,α}. Equation (1) is equivalent to
which simplifies to
This holds if either
or
$$ \{ S_{\gamma}(x,x_{n}),S_{\gamma}(x+\alpha,x_{n}+\alpha_{n})\} = \{S_{\gamma}(y,y_{n}),S_{\gamma}(y+\alpha,y_{n}+\alpha_{n})\}. $$
(1)
$$ \begin{array}{@{}rcl@{}} &&\{ x (x+\alpha) y (y+\alpha) S_{\gamma}(x,x_{n}), x (x+\alpha) y (y+\alpha)S_{\gamma}(x+\alpha,x_{n}+\alpha_{n})\} \\ &=&\{ x (x+\alpha) y (y+\alpha)S_{\gamma}(y,y_{n}), x (x+\alpha) y (y+\alpha)S_{\gamma}(y+\alpha,y_{n}+\alpha_{n})\}, \end{array} $$
$$ \{ \gamma^{x_{n}} (x+\alpha) y (y+\alpha), \gamma^{x_{n} \oplus \alpha_{n}}x y (y+\alpha)\} = \{ \gamma^{y_{n}}x (x+\alpha) (y+\alpha), \gamma^{y_{n} \oplus \alpha_{n}}x (x+\alpha) y \}. $$
$$ \gamma^{x_{n}}y = \gamma^{y_{n}}x \quad \text{and} \quad \gamma^{x_{n}\oplus \alpha_{n}}(y + \alpha) = \gamma^{y_{n}\oplus \alpha_{n}}(x+\alpha), $$
$$ \gamma^{x_{n}}(y + \alpha) = \gamma^{y_{n}\oplus \alpha_{n}}x \quad \text{and} \quad \gamma^{x_{n}\oplus \alpha_{n}}y = \gamma^{y_{n}}(x + \alpha) . $$
In both of the above cases, by distinguishing all eight cases of (αn,xn,yn), one can derive that either (x,xn) = (y,yn) or (x,xn) = (y + α,yn + αn).
To show Condition 2, let \(x,y,\alpha \in {\mathbb {F}}_{2^{n-1}}\) and \(x_{n},y_{n},\alpha _{n} \in {\mathbb {F}}_{2}\) with (α,αn)≠(0,0) such that
Condition 2 is trivially met when x ∈{0,α} or y ∈{0,α}. Let therefore, again, x,y∉{0,α}. Equation (2) is equivalent to
For αn = 0, it follows that α = 0, which is a contratiction to (α,αn)≠(0,0). For αn = 1, one can easily derive that (x,xn) = (y,yn) or (x,xn) = (y + α,yn + αn) by checking all four cases for (xn,yn). □
$$ S_{\gamma}(x,x_{n}) = S_{\gamma}(x+\alpha,x_{n}+\alpha_{n}) \quad \text{and} \quad S_{\gamma}(y,y_{n}) = S_{\gamma}(y+\alpha,y_{n}+\alpha_{n}). $$
(2)
$$ \gamma^{x_{n}}(x+\alpha) = \gamma^{x_{n} \oplus \alpha_{n}}x \quad \text{and} \quad \gamma^{y_{n}}(y+\alpha) = \gamma^{y_{n} \oplus \alpha_{n}}y. $$
3.2 Idrisova’s conjecture
Idrisova conjectured that every 4-uniform 2-1 function from \({{\mathbb {F}}_{2}^{n}}\) to \({\mathbb {F}}_{2}^{n-1}\) is APN admissible [8, Conjecture 2]. That conjecture was experimentally verified for the case n ≤ 4. We now use the 4-uniform permutations with null nonlinearity defined above to construct counterexamples to that conjecture. The constructions are based on the following observation.
By ei we denote the i-th unit vector in \({{\mathbb {F}}_{2}^{n}}\), i.e., \(e_{i} = (0,\dots ,0,1,0,\dots ,0)\), where the 1 is set at position i.
Proposition 5
Let S be an n-bit permutation with a linear or affine component 〈γ,S〉, \(\gamma \in {{\mathbb {F}}_{2}^{n}}\). Then, for \(j \in \{1,\dots ,n\}\), if the vectors
are linearly independent, the subfunction S(j) is 2-1 and the differential uniformity of S(j) is equal to the differential uniformity of S.
$$ e_{1},e_{2},\dots,e_{j-1},e_{j+1},e_{j+2},\dots,e_{n},\gamma $$
Proof
W.l.o.g., let j = n. It is obvious that S(n) is 2-1. Let \(T := {\sum }_{i=1}^{n} \gamma _{i} S_{i}\), which is linear or affine, i.e., there exists an 𝜖 ∈{0,1} such that, for all \(x,y \in {{\mathbb {F}}_{2}^{n}}\), T(x) + T(y) = T(x + y) + 𝜖. Now, let \(x,\alpha \in {{\mathbb {F}}_{2}^{n}}\) and \(\upbeta \in {\mathbb {F}}_{2}^{n-1}\) be such that
This holds if and only if
$$ \begin{array}{@{}rcl@{}} &&S_{(n)}(x) + S_{(n)}(x+\alpha)\\ &=&\left( S_{1}(x),\dots,S_{n-1}(x)\right) + \left( S_{1}(x+\alpha),\dots,S_{n-1}(x+\alpha)\right) = \upbeta. \end{array} $$
$$ \begin{array}{@{}rcl@{}} &&\left( S_{1}(x),\dots,S_{n-1}(x),T(x)\right) + \left( S_{1}(x+\alpha),\dots,S_{n-1}(x+\alpha),T(x+\alpha)\right)\\ &=&\left( \upbeta,T(\alpha)+\epsilon\right). \end{array} $$
If \(e_{1},\dots ,e_{n-1},\gamma \) are linearly independent, the function \((S_{1},\dots ,S_{n-1},T)\) is linear equivalent to S. It follows that the uniformity of S(n) must be equal to the uniformity of S. □
Example 1
Let n = 5 and consider the function \(G_{1,3}\colon {\mathbb {F}}_{2^{5}} \mapsto {\mathbb {F}}_{2^{5}}\). By representing \({\mathbb {F}}_{2^{5}}\) as \({\mathbb {F}}_{2}[X]/_{(X^{5}+X^{2}+1)}\), a representation of G1,3 can be given by the look-up table
In this example, 〈(0,1,0,0,1),G〉 is linear, therefore
is a differentially 4-uniform 2-1 function according to Proposition 5. However, it is {G(2)(02),G(2)(02 + 01)} = {G(2)(0E),G(2)(0E + 01)} = {02,09}, so it is not APN admissible. This is a counterexample to Conjecture 2 of [8].
$$ \begin{array}{@{}rcl@{}} G&=&[\texttt{00},\texttt{01},\texttt{19},\texttt{0A},\texttt{06},\texttt{0E},\texttt{0B},\texttt{1C},\texttt{03},\texttt{0D},\texttt{05},\texttt{1B},\texttt{13},\texttt{1D},\texttt{11},\texttt{02},\\ &&\texttt{14},\texttt{1E},\texttt{10},\texttt{1A},\texttt{0F},\texttt{17},\texttt{12},\texttt{07},\texttt{15},\texttt{09},\texttt{08},\texttt{16},\texttt{18},\texttt{1F},\texttt{0C},\texttt{04}]. \end{array} $$
$$ \begin{array}{@{}rcl@{}} G_{(2)}&=& [\texttt{0}, \texttt{1}, \texttt{9}, \texttt{2}, \texttt{6}, \texttt{6}, \texttt{3}, \texttt{C}, \texttt{3}, \texttt{5}, \texttt{5}, \texttt{B}, \texttt{B}, \texttt{D}, \texttt{9}, \texttt{2},\\ &&\texttt{C}, \texttt{E}, \texttt{8}, \texttt{A}, \texttt{7}, \texttt{F}, \texttt{A}, \texttt{7}, \texttt{D}, \texttt{1}, \texttt{0}, \texttt{E}, \texttt{8}, \texttt{F}, \texttt{4}, \texttt{4}] \end{array} $$
Example 2
Let n = 6 and let \({\mathbb {F}}_{2^{5}}\) be represented as \({\mathbb {F}}_{2}[X]/_{(X^{5}+X^{2}+1)}\). Let \(\gamma = \alpha +1 \in {\mathbb {F}}_{2^{5}}\), where α is a root of X5 + X2 + 1. By choosing f(x) = xn, the function Rγ,f has a linear component by construction. It is linear equivalent to
which has the linear component 〈(1,1,1,1,1,1),R〉. Considering the linear equivalent permutation R allows us to remove an arbitrary coordinate function in order to obtain a 4-uniform 2-1 function by Proposition 5. In particular,
is differentially 4-uniform and 2-1, but
so it is not APN admissible. This is another counterexample to the Conjecture.
$$ \begin{array}{@{}rcl@{}} R &=& [ \texttt{00}, \texttt{23}, \texttt{13}, \texttt{3C}, \texttt{3B}, \texttt{17}, \texttt{2E}, \texttt{34}, \texttt{1F}, \texttt{24}, \texttt{39}, \texttt{15}, \texttt{27}, \texttt{31}, \texttt{2A}, \texttt{2D},\\ &&\texttt{3D}, \texttt{18}, \texttt{22}, \texttt{02}, \texttt{1E}, \texttt{0B}, \texttt{38}, \texttt{05}, \texttt{11}, \texttt{3E}, \texttt{1A}, \texttt{3F}, \texttt{25}, \texttt{33}, \texttt{14}, \texttt{08},\\ &&\texttt{20}, \texttt{21}, \texttt{12}, \texttt{01}, \texttt{09}, \texttt{1C}, \texttt{32}, \texttt{0C}, \texttt{36}, \texttt{2C}, \texttt{0E}, \texttt{30}, \texttt{29}, \texttt{0F}, \texttt{06}, \texttt{37},\\ &&\texttt{2B}, \texttt{0D}, \texttt{26}, \texttt{1D}, \texttt{07}, \texttt{3A}, \texttt{28}, \texttt{2F}, \texttt{16}, \texttt{0A}, \texttt{35}, \texttt{04}, \texttt{03}, \texttt{10}, \texttt{19}, \texttt{1B} ], \end{array} $$
$$ \begin{array}{@{}rcl@{}} R_{(6)} &=& [ \texttt{00}, \texttt{11}, \texttt{09}, \texttt{1E}, \texttt{1D}, \texttt{0B}, \texttt{17}, \texttt{1A}, \texttt{0F}, \texttt{12}, \texttt{1C}, \texttt{0A}, \texttt{13}, \texttt{18}, \texttt{15}, \texttt{16},\\ &&\texttt{1E}, \texttt{0C}, \texttt{11}, \texttt{01}, \texttt{0F}, \texttt{05}, \texttt{1C}, \texttt{02}, \texttt{08}, \texttt{1F}, \texttt{0D}, \texttt{1F}, \texttt{12}, \texttt{19}, \texttt{0A}, \texttt{04},\\ &&\texttt{10}, \texttt{10}, \texttt{09}, \texttt{00}, \texttt{04}, \texttt{0E}, \texttt{19}, \texttt{06}, \texttt{1B}, \texttt{16}, \texttt{07}, \texttt{18}, \texttt{14}, \texttt{07}, \texttt{03}, \texttt{1B},\\ &&\texttt{15}, \texttt{06}, \texttt{13}, \texttt{0E}, \texttt{03}, \texttt{1D}, \texttt{14}, \texttt{17}, \texttt{0B}, \texttt{05}, \texttt{1A}, \texttt{02}, \texttt{01}, \texttt{08}, \texttt{0C}, \texttt{0D} ] \end{array} $$
$$ \{R_{(6)}(\texttt{01}),R_{(6)}(\texttt{01}+\texttt{02})\} = \{R_{(6)}(\texttt{10}),R_{(6)}(\texttt{10}+\texttt{02})\} = \{ \texttt{11},\texttt{1E}\}, $$
We expect that similar counterexamples can be constructed for all n ≥ 5.
4 Conclusion
We have seen that 4-uniform permutations with null nonlinearity exist for all n = 3 and n ≥ 5, where an interesting construction can be given by the inverses of Gold functions. Moreover, 4-uniform 2-1 functions obtained from admissible sequences, as defined by Idrisova, exist for all n = 3 and n ≥ 5. It is interesting to observe that n = 4 defines a special case for which none of the above exist.
For future work it would be interesting to find more constructions of 4-uniform permutations with null nonlinearity and use them to construct 4-uniform permutations (or even APN permutations) with high nonlinearity. Such a construction can be achieved by the following procedure: Let F be a 4-uniform permutation in n bit with trivial nonlinearity.
1.
Choose a permutation G affine equivalent to F.
2.
Discard a coordinate of G to obtain a 4-uniform 2-1 function \(G^{\prime }\) from \({{\mathbb {F}}_{2}^{n}}\) to \({\mathbb {F}}_{2}^{n-1}\) by Proposition 5.
3.
Choose an n-bit Boolean function f with |supp(f)| = 2n− 1 for which \(G^{\prime }(\text {supp}(f))={\mathbb {F}}_{2}^{n-1}\) and construct the permutation \(H \colon x \mapsto (G^{\prime }(x),f(x))\).
Note that Step 2 and 3 of the above procedure were already suggested in [8]. However, starting from a 4-uniform permutation with trivial nonlinearity allows more freedom to obtain a 4-uniform 2-1 function. For n ∈{6,7,8} we checked all the constructions of Proposition 2 whether they can be extended to an APN permutation by Step 3 of the above algorithm. The answer is negative in all cases. We used an exhaustive tree search for constructing the last coordinate function.
Acknowledgements
Open Access funding provided by Projekt DEAL. This work was funded by Deutsche Forschungsgemeinschaft (DFG); project number 411879806, and by DFG under Germany’s Excellence Strategy - EXC 2092 CASA - 390781972.
Compliance with Ethical Standards
Conflict of interests
The authors declare that they have no conflict of interest.
Open AccessThis article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
Publisher’s note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.