Published in:
Open Access 16-10-2024
Revisiting products of the form X times a linearized polynomial L(X)
Published in: Designs, Codes and Cryptography | Issue 1/2025
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by (Link opens in a new window)
Abstract
1 Introduction and Preliminaries
Let \(q = p^m\) for a prime p and a positive integer m and let \(\mathbb {F}_{q^n}\) denote the field with \(q^n\) elements. A polynomial \(L \in \mathbb {F}_{q^n}[X]\) is called a q-polynomial if it is of the formThere is a one-to-one correspondence of q-polynomials in \(\mathbb {F}_{q^n}[X]\) and \(\mathbb {F}_q\)-linear mappings over \(\mathbb {F}_{q^n}\) by means of their evaluation maps.
$$\begin{aligned} L(X) = \sum _{i=0}^{n-1} a_i X^{q^i}, \quad a_i \in \mathbb {F}_{q^n}. \end{aligned}$$
(1)
For a q-polynomial \(L \in \mathbb {F}_{q^n}[X]\), we denote \(f_L :\mathbb {F}_{q^n} \rightarrow \mathbb {F}_{q^n}, x \mapsto x \cdot L(x)\). Such \(f_L\) are exactly the functions of the formGiven a function \(f :\mathbb {F}_{q^n} \rightarrow \mathbb {F}_{q^n}\) and \(a,b \in \mathbb {F}_{q^n}\), we defineThe differential spectrum of f, denoted by \(\mathcal {D}_f\), counts the occurrences of \(D_f(a,b)\) over all pairs \((a,b) \in \mathbb {F}_{q^n}^* \times \mathbb {F}_{q^n}\), formally,where \(\eta _i = |\{(a,b) \in \mathbb {F}_{q^n}^* \times \mathbb {F}_{q^n} \mid D_f(a,b) = i \} |\). The differential uniformity [23], denoted \(\delta _f\), is defined asThe differential uniformity, and more generally the differential spectrum of a function can be understood as a measure on the robustness against differential cryptanalysis [8] and its variants when using f as a substitution box in a symmetric cryptographic primitive (see e.g., [9] for a discussion). For p odd, functions reaching the lowest possible differential uniformity \(\delta _f = 1\) are called planar. For \(p=2\), the lowest possible differential uniformity is 2, and functions reaching this value with equality are called almost perfect nonlinear (APN). Besides the interest in functions with low differential uniformity for cryptographic applications, planar functions and APN functions have strong connections to objects in finite geometry and combinatorics (see [25] for a survey).
$$\begin{aligned} x \mapsto \sum _{i=0}^{n-1} a_i x^{q^i+1}, \quad a_i \in \mathbb {F}_{q^n}. \end{aligned}$$
(2)
$$\begin{aligned} D_f(a,b) :=\left| \left\{ x \in \mathbb {F}_{q^n} \Big | f(x+a) - f(x) = b\right\} \right| . \end{aligned}$$
$$\begin{aligned} \mathcal {D}_f :=(\eta _i)_{i=0,\dots ,q^n}, \end{aligned}$$
$$\begin{aligned} \delta _f :=\max _{a,b \in \mathbb {F}_{q^n}, a \ne 0}D_f(a,b). \end{aligned}$$
Advertisement
The differential uniformity of functions \(f_L\) has already been studied in the literature: In [7], Berger et al. showed that a function of the form (2) over a field of characteristic 2 can be APN (i.e., differentially 2-uniform) only if L is a monomial, hence the only APN functions \(f_L\) are the Gold APN functions (as defined in [18, 23]).
In the case of odd characteristic p, the planarity of functions \(f_L\) was first studied by Kyureghyan and Özbudak in [20]. They showed some sufficient conditions on L for \(f_L\) being planar as well as some non-existence results for special types of planar functions \(f_L\). However, all of the constructed planar functions were (CCZ-)equivalent to monomials. This study was continued in [14] and [29] by proving some open conjectures on the non-existence raised in [20].
For L being a trinomial of the form \(X^{q^2} + aX^q + bX\), Bartoli and Bonini characterized in [1] all planar functions \(f_L\) over \(\mathbb {F}_{q^3}\) with the restriction \(a,b \in \mathbb {F}_q\). Later, Chen and Mesnager [13] completed the characterization for general \(a,b \in \mathbb {F}_{q^3}\).
In [11], Budaghyan et al. introduced the notion of an isotopic shift of a function. Given \(g :\mathbb {F}_{q^n} \rightarrow \mathbb {F}_{q^n}\) and a q-polynomial \(L \in \mathbb {F}_{q^n}[X]\), the isotopic shift of g by L is defined as the function mapping \(x \in \mathbb {F}_{q^n}\) to \(g(x+L(x)) - g(x) - g(L(x))\). Hence, the isotopic shifts of \(g(x) = x^2\) are exactly the functions of the form \(2 \cdot f_L\). In [10], the authors studied isotopic shifts for constructing planar functions and showed that it is possible to have planar functions \(f_L\) inequivalent to monomials, more precisely, they obtained functions corresponding (up to equivalence) to commutative Dickson semifields.
Advertisement
For a q-polynomial \(L \in \mathbb {F}_{q^n}[X]\), letandThe set \(\mathcal {I}(L)\) denotes the image set of the rational function \(r_L :\mathbb {F}_{q^n}^* \rightarrow \mathbb {F}_{q^n}, x \mapsto \frac{L(x)}{x}\) and we have \(\mathcal {I}(L) = \mathbb {F}_{q^n} {\setminus } \mathcal {V}(L)\). Those sets played a central role in the study of planarity of \(f_L\) and were also studied in previous papers in the context of finite geometry and coding theory, see, e.g., [17, 20, 22] and the references therein. We would like to point out the geometric interpretation in more detail (see, e.g., [16]): Let W be a 2-dimensional \(\mathbb {F}_{q^n}\)-vector space and let \(\Lambda = \textrm{PG}(W,\mathbb {F}_{q^n}) = \textrm{PG}(1,q^n)\) be the projective line over \(\mathbb {F}_{q^n}\). An \(\mathbb {F}_q\)-linear set \(\mathcal {L}_U\) of \(\Lambda \) of rank n is defined as the point set of the non-zero points of an n-dimensional \(\mathbb {F}_q\)-subspace U of W, i.e.,If \(L \in \mathbb {F}_{q^n}[X]\) is a q-polynomial, we can take \(U = U_L :=\{(x,L(x)) \mid x \in \mathbb {F}_{q^n}\}\) and denote the corresponding linear set \(\mathcal {L}_{U_L}\) by \(\mathcal {L}_L\). We then haveThe study of linear sets has also been successfully applied to the study of APN functions. For instance, in [2] the authors analyze certain classes of \(\mathbb {F}_2\)-linear sets to prove the existence of APN functions of a specific form. It is known that the planarity property of a function \(f_L\) is completely determined by a property (independent of L) of the set \(\mathcal {I}(L)\). Indeed, \(f_L\) being planar is equivalent to \(x \mapsto a L(x) + x L(a)\) having trivial kernel for all \(a \in \mathbb {F}_{q^n}^*\), i.e., \(-\frac{L(a)}{a} \notin \mathcal {I}(L)\) for all \(a \ne 0\), i.e., \(0 \notin \mathcal {I}(L)\) and for all \(b \in \mathbb {F}_{q^n}^*\), at most one of \(-b,b\) is contained in \(\mathcal {I}(L)\) (see [20, Theorem 1]). So, if \(f_L\) is planar and M a q-polynomial for which \(\mathcal {I}(L) = \mathcal {I}(M)\), also \(f_M\) is planar. Clearly, for any planar function over \(\mathbb {F}_{q^n}\), there is only one possibility of its differential spectrum, i.e., \(\eta _1 = q^n(q^n-1)\) and \(\eta _i = 0\) for \(i \ne 1\).
$$\begin{aligned} \mathcal {V}(L) :=\{a \in \mathbb {F}_{q^n} \mid x \mapsto L(x) - ax \text { permutes } \mathbb {F}_{q^n}\} \end{aligned}$$
$$\begin{aligned} \mathcal {I}(L) :=\left\{ \frac{L(x)}{x} \Big | x \in \mathbb {F}_{q^n}^* \right\} . \end{aligned}$$
$$\begin{aligned}\mathcal {L}_U :=\{ \langle u \rangle _{\mathbb {F}_{q^n}} \mid u \in U \setminus \{0\}\}.\end{aligned}$$
$$\begin{aligned} \mathcal {L}_L = \{ \langle (1,L(x)/x) \rangle _{\mathbb {F}_{q^n}} \mid x \in \mathbb {F}_{q^n}^\star \} = \{ \langle (1,y) \rangle _{\mathbb {F}_{q^n}} \mid y \in \mathcal {I}(L)\}. \end{aligned}$$
One might ask more generally whether the differential uniformity, or even the differential spectrum, of \(f_L\) (not necessarily planar) is completely determined by the set \(\mathcal {I}(L)\):
Question 1
If \(\mathcal {I}(L) = \mathcal {I}(M)\) for q-polynomials L, M, do \(f_L\) and \(f_M\) have identical differential spectra?
The question for which pairs of q-polynomials \(L,M \in \mathbb {F}_{q^n}[X]\) the identity \(\mathcal {I}(L) = \mathcal {I}(M)\) holds was studied in [17] and a classification was obtained for the case of \(n \le 5\). To recall this result, we need the notion of \(\Gamma \textrm{L}(2,q^n)\)-equivalence of two q-polynomials, given below. For a function \(f :\mathbb {F}_{q^n} \rightarrow \mathbb {F}_{q^n}\), we denote by \(\mathcal {G}_f\) the graph of f, defined as \(\{(x,f(x)) \mid x \in \mathbb {F}_{q^n} \}\). The functions f and g are called CCZ-equivalent [12], if there is an affine bijection A over \(\mathbb {F}_{q^n} \times \mathbb {F}_{q^n}\) such that \(A(\mathcal {G}_f) = \mathcal {G}_g\). An important fact is that the differential spectrum of a function is invariant under CCZ-equivalence.
Definition 1
(see, e.g., [17]) Let \(s \in \mathbb {F}_{q^n}\), \(0 \le i \le n-1\). We denote by \(\mu _{s,i}\) the \(\mathbb {F}_q\)-linear mapping \(\mathbb {F}_{q^n} \rightarrow \mathbb {F}_{q^n}, x \mapsto s x^{q^i}\). Letfor some elements \(a,b,c,d \in \mathbb {F}_{q^n}\) and \(0 \le i \le n-1\). We say that \(\varphi \) is admissible for a q-polynomial \(L \in \mathbb {F}_{q^n}[X]\) if and only if \(ad - bc \ne 0\) (i.e., \(\varphi \) is invertible) and either \(b=0\) or \(-(a/b)^{q^{n-i}} \notin \mathcal {I}(L)\). We say that the q-polynomials \(L,M \in \mathbb {F}_{q^n}[X]\) are \(\Gamma \textrm{L}(2,q^n)\)-equivalent, if there exists an admissible mapping \(\varphi \) for L as in (3) such that L and M (as linear mappings) are CCZ-equivalent viaIn that case, the linear mappings M and L are related via \(M = H_L^{\varphi } \circ ({K_L^{\varphi }})^{-1}\), where \(K_L^{\varphi }(x) = ax^{q^i} + b L(x)^{q^i}\) and \(H_L^{\varphi }(x) = c x^{q^i} + d L(x)^{q^i}\). We also write \(M = \varphi (L)\).
$$\begin{aligned} \varphi :=\left( \begin{array}{cc} \mu _{a,i} & \mu _{b,i} \\ \mu _{c,i} & \mu _{d,i} \end{array}\right) \end{aligned}$$
(3)
$$\begin{aligned} \varphi (\mathcal {G}_L) = \mathcal {G}_M. \end{aligned}$$
Clearly (see also [17]), if M and L are \(\Gamma \textrm{L}(2,q)\)-equivalent via \(M = \varphi (L)\), then \(|\mathcal {I}(L) |= |\mathcal {I}(\varphi (L)) |\). Further, given L and M with \(\mathcal {I}(L) = \mathcal {I}(M)\) and admissible \(\varphi \) as in (3), then \(\mathcal {I}(\varphi (L)) = \mathcal {I}(\varphi (M))\).
Given a q-polynomial L in the form of (1), we denote by \(L^*\) its adjoint, i.e., the q-polynomialThe induced \(\mathbb {F}_q\)-linear mappings \(x \mapsto L(x)\) and \(x \mapsto L^*(x)\) over \(\mathbb {F}_{q^n}\) are adjoint relative to the bilinear form \((x,y) \mapsto \textrm{tr}(xy)\), where \(\textrm{tr}:x \mapsto \sum _{i=0}^{n-1} x^{q^i}\) denotes the trace function from \(\mathbb {F}_{q^n}\) to \(\mathbb {F}_q\). That is, \(\textrm{tr}(xL(y)) = \textrm{tr}(L^*(x)y)\) holds for all \(x,y \in \mathbb {F}_{q^n}\) (see, e.g., [22]).
$$\begin{aligned}L^* :=a_0 X + \sum _{i=1}^{n-1} a_i^{q^{n-i}}X^{q^{n-i}}.\end{aligned}$$
We have now established the necessary terminology to recall the classification result by Csajbók et al.
Theorem 1
[17] Let q be a prime power, \(n \le 5\) a positive integer and let \(L,M \in \mathbb {F}_{q^n}[X]\) be q-polynomials with maximum field of linearity \(\mathbb {F}_q\) (i.e., L or M is not a \(q^t\)-polynomial for \(t >1\)) such that \(\mathcal {I}(L) = \mathcal {I}(M)\).
-
\(\bullet \) If \(n \le 4\), there exists \(\lambda \in \mathbb {F}_{q^n}^*\) such that \(M(X) = L(\lambda X)/\lambda \) or \(M(X) = L^*(\lambda X)/\lambda \).
-
\(\bullet \) If \(n=5\), then either
-
(i) there exists \(\lambda \in \mathbb {F}_{q^n}^*\) such that \(M(X) = L(\lambda X)/\lambda \) or \(M(X) = L^*(\lambda X)/\lambda \), or
-
(ii) there exists an admissible mapping \(\varphi \) for L and M and \(a,b \in \mathbb {F}_{q^n}\) such that \(\varphi (L)(X) = a X^{q^i}\) and \(\varphi (M)(X) = b X^{q^j}\) with \(a^{\frac{q^n-1}{q-1}} = b^{\frac{q^n-1}{q-1}}\) and \(i,j \in \{1,\dots ,4\}\).
-
Since a q-polynomial \(L \in \mathbb {F}_{q^n}[X]\) with maximum field of linearity \(\mathbb {F}_{q^t}\) is also a \(q^t\)-polynomial in \(\mathbb {F}_{{q^t}^{n/t}}[X]\) and for \(L,M \in \mathbb {F}_{q^n}[X]\) with \(\mathcal {I}(L) = \mathcal {I}(M)\), the fields of linearity of L and M coincide [17, Propostion 2.1], this yields the following corollary.
Corollary 1
Let q be a prime power, \(n \le 5\) a positive integer and let \(L,M \in \mathbb {F}_{q^n}[X]\) be q-polynomials such that \(\mathcal {I}(L) = \mathcal {I}(M)\). Then,
(i)
there exists \(\lambda \in \mathbb {F}_{q^n}^*\) such that \(M(X) = L(\lambda X)/\lambda \) or \(M(X) = L^*(\lambda X)/\lambda \), or
(ii)
there exists an admissible mapping \(\varphi \) for L and M, some integers \(i,j \in \{1,\dots ,n-1\}\), and \(a,b \in \mathbb {F}_{q^n}\) such that \(\varphi (L)(X) = a X^{q^i}\) and \(\varphi (M)(X) = b X^{q^j}\).
1.1 Our Results
In the first part (Sect. 2), we characterize the differential spectrum of a function \(f_L\) for a q-polynomial L (Propostion 1). This characterization yields a sufficient condition on a pair (L, M) of q-polynomials such that \(f_L\) and \(f_M\) have the same differential spectrum, namely that, for all \(a \in \mathbb {F}_{q^n}\), the dimension of the kernel of \(x \mapsto L(x) - ax\) is the same as the dimension of the kernel of \(x \mapsto M(x) - ax\). While this condition is trivially fulfilled if \(M(X) = L(\lambda X)/\lambda \) for \(\lambda \ne 0\), we outline that it also holds for the pairs of q-polynomials \((L,L^*)\), \((aX^{q^i},bX^{q^j})\) with \(\mathcal {I}(aX^{q^i}) = \mathcal {I}(bX^{q^j})\), and \((\varphi (L),\varphi (M))\) for L, M fulfilling the condition above (see Lemmas 1, 2, and 3, respectively).1 This yields the following result.
Theorem 2
Let q be a prime power, \(n \le 5\) a positive integer and let \(L,M \in \mathbb {F}_{q^n}[X]\) be q-polynomials such that \(\mathcal {I}(L) = \mathcal {I}(M)\). Then, \(\mathcal {D}_{f_L} = \mathcal {D}_{f_M}\).
The case of \(n > 5\) is left as an open problem. To settle it, we pose the following interesting open question: If \(L,M \in \mathbb {F}_{q^n}[X]\) are q-polynomials with \(\mathcal {I}(L) = \mathcal {I}(M)\) and \(a \in \mathbb {F}_{q^n}\), does this imply the equality of the dimension of the kernel of \(x \mapsto L(x) - ax\) and the dimension of the kernel of \(x \mapsto M(x) - ax\) (Question 2)?
In Sect. 3, we show how to construct CCZ-inequivalent functions \(f_M\) with bounded differential uniformity from a given function \(f_L\) using \(\Gamma \textrm{L}(2,q^n)\)-equivalence (Corollary 3) and we further give a link between functions \(f_L\) of differential uniformity bounded above by q and scattered q-polynomials (Corollary 4).
2 On the Differential Spectrum of \(f_L\)
Given a q-polynomial \(L \in \mathbb {F}_{q^n}[X]\), we denote by \(\ker (L)\) the kernel of the \(\mathbb {F}_q\)-linear map \(x \mapsto L(x)\) over \(\mathbb {F}_{q^n}\), i.e., the subspace of all elements \(y \in \mathbb {F}_{q^n}\) with \(L(y) = 0\). For \(0 \le k \le n\), let us defineClearly, \(\mathcal {V}_0(L) = \mathcal {V}(L)\) and \(\cup _{k=1}^n \mathcal {V}_k(L) = \mathcal {I}(L)\). Further, note that, for \(1 \le k \le n\), we haveThe sets \(\mathcal {V}_k(L)\) for \(0 \le k \le n\) have the following interpretation in terms of linear sets: For a point \(P = \langle (x,y) \rangle _{\mathbb {F}_{q^n}} \in \textrm{PG}(1,q^n)\) with \(x,y \in \mathbb {F}_{q^n}\), the weight of P with respect to the \(\mathbb {F}_q\)-linear set \(\mathcal {L}_L\), denoted by \(w_{\mathcal {L}_L}(P)\), is defined as the dimension of the intersection \(U_L \cap \langle (x,y) \rangle _{\mathbb {F}_{q^n}}\) as an \(\mathbb {F}_q\)-vector space. The set \(\mathcal {V}_k(L)\) consists precisely of those \(y \in \mathbb {F}_{q^n}\) for which \(w_{\mathcal {L}_L}(\langle (1,y) \rangle _{\mathbb {F}_{q^n}}) = k\).
$$\begin{aligned} \mathcal {V}_k(L) :=\{a \in \mathbb {F}_{q^n} \mid \dim \ker (L(X)-aX)=k\}. \end{aligned}$$
$$\begin{aligned} \mathcal {V}_k(L) = \left\{ b \in \mathcal {I}(L) \Big | b = \frac{L(x)}{x} \text { for exactly } q^k-1 \text { distinct } x \in \mathbb {F}_{q^n}^* \right\} . \end{aligned}$$
(4)
The crucial point for the following discussion is the fact that the differential spectrum of \(f_L\) is completely determined by \((\mathcal {V}_k(L))_{k=1,\dots ,n}\), which we show in the following characterization. For a set S, we denote by \(-S\) the set \(\{-a \mid a \in S\}\).
Proposition 1
Let \(L \in \mathbb {F}_{q^n}[X]\) be a q-polynomial and \(f_L :\mathbb {F}_{q^n} \rightarrow \mathbb {F}_{q^n}, x \mapsto x L(x)\). For the differential spectrum \(\mathcal {D}_{f_L} = (\eta _0,\eta _1,\dots ,\eta _{q^n})\), we haveIn particular, if \(L,M \in \mathbb {F}_{q^n}[X]\) are q-polynomials such that \(\mathcal {V}_k(L) = \mathcal {V}_k(M)\) holds for all \(1 \le k \le n\), we have \(\mathcal {D}_{f_L} = \mathcal {D}_{f_M}\).
$$\begin{aligned} \eta _i = {\left\{ \begin{array}{ll} q^{n-k} \cdot \sum _{\ell = 1}^n (q^\ell -1) \cdot |\mathcal {V}_\ell (L) \cap - \mathcal {V}_k(L)|& \text {if } i = q^k \\ \sum _{k=1}^n (q^n- q^{n-k}) \cdot \sum _{\ell =1}^n (q^\ell -1) \cdot |\mathcal {V}_\ell (L) \cap -\mathcal {V}_k(L)|& \text {if } i = 0 \\ 0 & \text {else} \end{array}\right. }. \end{aligned}$$
(5)
Proof
For any \(a \in \mathbb {F}_{q^n}\), the differential mapping \(x \mapsto f_L(x+a)-f_L(x) = aL(x) + L(a)x + aL(a)\) is affine, hence the solutions \(x \in \mathbb {F}_{q^n}\) of \(f_L(x+a) - f_L(x) = d\) (if they exist) form a coset of \(S_a\), where \(S_a\) is the vector space of solutions \(x \in \mathbb {F}_{q^n}\) of \(aL(x) + L(a)x = 0\), i.e., \(S_a = \ker (aL(X) +L(a)X)\). The solutions exist if and only if \((d-aL(a)) \in \textrm{Im}(x \mapsto aL(x) + L(a)x)\). From this, we immediately get \(\eta _i = 0\) for \(i \ne 0\) not being a power of q, andwhere the second to last equality holds because \({\dot{\cup }}_{\ell =1}^n\mathcal {V}_\ell (L) = \mathcal {I}(L)\) and each element in \(\mathcal {V}_\ell (L)\) has \(q^\ell -1\) preimages under \(r_L\). The identity for \(\eta _0\) follows from the fact2 that \(\sum _{i=0}^{q^n} \eta _i = \sum _{i=1}^{q^n} i \cdot \eta _i = q^n(q^n-1)\). Indeed, since \(\eta _i = 0\) for positive i not being a power of q, we get \(\eta _0 = \sum _{k=1}^n (q^k-1) \cdot \eta _{q^k}\). \(\square \)
$$\begin{aligned} \eta _{q^k}&= q^{n-k} \cdot \left|\left\{ a \in \mathbb {F}_{q^n}^* \big | \dim \ker (L(X) +\frac{L(a)}{a}X) = k \right\} \right|\\&= q^{n-k} \cdot \left|\left\{ a \in \mathbb {F}_{q^n}^* \big | -\frac{L(a)}{a} \in \mathcal {V}_k(L)\right\} \right|\\&= q^{n-k} \cdot \sum _{\ell =1}^n (q^\ell -1) \cdot \left|\left\{ \frac{L(a)}{a} \in \mathcal {V}_\ell (L) \big | -\frac{L(a)}{a} \in \mathcal {V}_k(L) \right\} \right|\\&= q^{n-k} \cdot \sum _{\ell =1}^n (q^\ell -1) \cdot |\mathcal {V}_\ell (L) \cap -\mathcal {V}_k(L)|, \end{aligned}$$
Corollary 2
Let \(L \in \mathbb {F}_{q^n}[X]\) be a q-polynomial and \(f_L :\mathbb {F}_{q^n} \rightarrow \mathbb {F}_{q^n}, x \mapsto x L(x)\). Then, \(\delta _{f_L} = q^k\), where \(k \in \{0,\dots ,n\}\) is the largest integer such that \(|\mathcal {I}(L) \cap -\mathcal {V}_k(L)|\ne \emptyset \), i.e., such that there exists \(a \in \mathbb {F}_{q^n}\) for which \(L(X) - aX\) is not permutation polynomial and \(\dim \ker (L(X) + aX) = k\).
Proof
Clearly, the differential uniformity of \(f_L\) can only be a power of q. From Propostion 1, the value \(\eta _{q^k}\) is nonzero if and only if \(\bigcup _{\ell =1}^n \left( \mathcal {V}_\ell (L) \cap -\mathcal {V}_k(L)\right) \) is not empty. The statement follows from the fact that \(\mathcal {I}(L) = \cup _{\ell = 1}^n \mathcal {V}_\ell (L)\). \(\square \)
Remark 1
Proposition 1 and Corollary 2 generalize [20, Theorem 1 (c)]. Indeed \(f_L\) is planar if and only if \(\eta _{q^k} = 0\) holds for all \(1 \le k \le n\). By Corollary 2, this condition is equivalent to \(\mathcal {I}(L) \cap -\mathcal {I}(L) = \emptyset \), i.e., \(0 \notin \mathcal {I}(L)\) and for all \(b \in \mathbb {F}_{q^n}^*\), at most one of b or \(-b\) is contained in \(\mathcal {I}(L)\).
It was first proven in [3, Lemma 2.6] that \(\mathcal {V}(L) = \mathcal {V}(L^*)\) and \(\mathcal {I}(L) = \mathcal {I}(L^*)\). There are various other proofs given in the literature, e.g., in [22], which uses the characterization of permutations by their Walsh transforms. A particularly elegant proof was given in [16, Rem. 3.3], proving the (a priori) more general question of equality of \(\mathcal {V}_k(L)\) and \(\mathcal {V}_k(L^*), 0 \le k \le n\). For completeness, we repeat this proof in the following.
Lemma 1
(see [16]) Let \(L \in \mathbb {F}_{q^n}[X]\) be a q-polynomial. For all \(0 \le k \le n\), we have \(\mathcal {V}_k(L) = \mathcal {V}_k(L^*)\).
Proof
For a q-polynomial \(L = \sum _{i=0}^{n-1}a_iX^{q^i} \in \mathbb {F}_{q^n}[X]\), letdenote the corresponding \(n \times n\) Dickson matrix over \(\mathbb {F}_{q^n}\), so that \(\ker (D_L) = \ker (L)\) and \((D_L)^\top = D_{L^*}\) (see [28]). The statement follows since, for any \(a \in \mathbb {F}_{q^n}\), we have\(\square \)
$$\begin{aligned} D_L :=\left( \begin{array}{cccc} a_0 & a_1 & \dots & a_{n-1} \\ a_{n-1}^q & a_0^q & \dots & a_{n-2}^q \\ \vdots & \vdots & \vdots & \vdots \\ a_1^{q^{n-1}} & a_2^{q^{n-1}} & \dots & a_0^{q^{n-1}} \end{array}\right) \end{aligned}$$
$$\begin{aligned} \dim \ker (L(X) - aX)&= \dim \ker (D_L - D_{aX}) = \dim \ker ((D_L - D_{aX})^\top ) \\ &= \dim \ker (D_{L^*} - D_{aX}) = \dim \ker (L^*(X) -aX).\end{aligned}$$
Remark 2
Let \(\zeta \in \mathbb {C}\) be a primitive p-th root of unity. The Walsh transform of \(f :\mathbb {F}_{q^n} \rightarrow \mathbb {F}_{q^n}\) at point (a, b), \(a,b \in \mathbb {F}_{q^n}\), is defined aswhere \(\textrm{tr}_p(x) :=\sum _{i=0}^{mn-1}x^{p^i}\) denotes the absolute trace function from \(\mathbb {F}_{q^n}\) to \(\mathbb {F}_p\). Let \(a \in \mathbb {F}_{q^n}, b \in \mathbb {F}_{q^n}^*\). For the Walsh transform of \(f_L\) and \(f_{L^*}\), we getSince a function f over \(\mathbb {F}_{q^n}\) is a permutation if and only if \(\mathcal {W}_{f}(0,b) = 0\) holds for all \(b \in \mathbb {F}_{q^n}^*\) (see, e.g., [19, Theorem 1.1]), we immediately get that \(f_L\) is a permutation if and only if \(f_{L^*}\) is. \(\square \)
$$\begin{aligned} \mathcal {W}_f(a,b):=\sum _{x \in \mathbb {F}_{q^n}} \zeta ^{\textrm{tr}_p(a x) + \textrm{tr}_p(bf(x))} \in \mathbb {C}, \end{aligned}$$
$$\begin{aligned} \mathcal {W}_{f_L}(a,b)&= \sum _{x \in \mathbb {F}_{q^n}} \zeta ^{\textrm{tr}_p(a x) + \textrm{tr}_p(bxL(x))} = \sum _{x \in \mathbb {F}_{q^n}} \zeta ^{\textrm{tr}_p(a x) + \textrm{tr}_p(xL^*(bx))} \\&= \sum _{x \in \mathbb {F}_{q^n}} \zeta ^{\textrm{tr}_p(a b^{-1}x) + \textrm{tr}_p(b^{-1}xL^*(x))} = \mathcal {W}_{f_{L^*}}(ab^{-1},b^{-1}). \end{aligned}$$
By a folklore argument, we get the following for q-monomials.
Lemma 2
Let \(L = a X^{q^i}\) and \(M = b X^{q^j}\), \(a,b \in \mathbb {F}_{q^n}\), be q-polynomials in \(\mathbb {F}_{q^n}[X]\) such that \(\mathcal {V}(L) = \mathcal {V}(M)\). Then, for all \(0 \le k \le n\), we have \(\mathcal {V}_k(L) = \mathcal {V}_k(M)\). More precisely, if \(a,b \in \mathbb {F}_{q^n}^*\), we have \(\mathcal {V}(L)_{\gcd (i,n)} = \mathcal {I}(L)\), and \(\mathcal {V}_k(L) = \emptyset \) for \(k \notin \{0,\gcd (i,n)\}\).
Proof
If \(a = 0\), then also \(b= 0\), so that \(L = M\). Let us therefore assume \(a,b \in \mathbb {F}_{q^n}^*\). It is well known that a monomial function \(x \mapsto x^d\) over \(\mathbb {F}_{q^n}^*\) is \(\gcd (d, q^n-1)\)-to-1. By assumption, we havehence the mappings \(x \mapsto x^{q^i-1}\) and \(x \mapsto x^{q^j-1}\) over \(\mathbb {F}_{q^n}^*\) have the same image size and are thus \(\gcd (q^i-1, q^n-1)\)-to-one. By using (4) and the fact that \(\gcd (q^i-1,q^n-1) = q^{\gcd (i,n)}-1\), the result follows. \(\square \)
$$\begin{aligned} \mathcal {I}(L) = \left\{ a x^{p^i-1} \mid x \in \mathbb {F}_{q^n}^* \right\} = \left\{ b x^{p^j-1} \mid x \in \mathbb {F}_{q^n}^* \right\} = \mathcal {I}(M), \end{aligned}$$
To settle Theorem 2, we finally show that the property of equality of sets \(\mathcal {V}_k(L)\), \(\mathcal {V}_k(M)\) is not affected when changing L, M under \(\Gamma \textrm{L}(2,q^n)\)-equivalence using the same \(\varphi \). We can show more generally how the sets \(\mathcal {V}_k(L), k = 1,\dots ,n\) are affected under \(\Gamma \textrm{L}(2,q^n)\)-equivalence of L.
Lemma 3
Let \(L \in \mathbb {F}_{q^n}[X]\) be a q-polynomial and let \(\varphi \) be an admissible mapping for L. Let \(1 \le k \le n\). The sets \(\mathcal {V}_k(L)\) and \(\mathcal {V}_k(\varphi (L))\) are related via a bijection \(\nu _\varphi :\mathcal {I}(\varphi (L)) \rightarrow \mathcal {I}(L)\) byIn particular, we have \(|\mathcal {V}_k(L)|= |\mathcal {V}_k(\varphi (L))|\), and, for a q-polynomial \(M \in \mathbb {F}_{q^n}[X]\) with \(\mathcal {I}(M) = \mathcal {I}(L)\) and \(\mathcal {V}_k(M) = \mathcal {V}_k(L)\), we have \(\mathcal {V}_k(\varphi (M)) = \mathcal {V}_k(\varphi (L))\).
$$\begin{aligned} \nu _\varphi ^{-1}(\mathcal {V}_k(L)) = \mathcal {V}_k(\varphi (L)). \end{aligned}$$
Proof
Letbe admissible for L and let us fix \(k \ge 1\) and let \(\gamma \in \mathcal {V}_k(\varphi (L))\). We havewhich is equal toif \(d-\gamma b \ne 0\). Since \(k \ne 0\), necessarily \(d-\gamma b \ne 0\), as otherwise \((d-\gamma b)^{q^{n-i}}L(x) - (\gamma a - c)^{q^{n-i}} x = 0\) would only have one solution \(x = 0\) (note that both \(d-\gamma b\) and \(\gamma a - c\) cannot be simultaneously zero because of the invertibility of \(\varphi \)). Since \(ad - bc \ne 0\), the mappingis injective with domain \(\mathbb {F}_{q^n} {\setminus } \{ x \in \mathbb {F}_{q^n} \mid d - x b = 0\}\), hence it induces a bijection from \(\mathcal {I}(\varphi (L))\) to \(\mathcal {I}(L)\). The first part of the assertion follows, as we have shown \(\nu _\varphi (\gamma ) \in \mathcal {V}_k(L)\). The second part is a trivial corollary. Note that we need \(\mathcal {I}(M) = \mathcal {I}(L)\) to ensure that \(\varphi \) is admissible for M. \(\square \)
$$\begin{aligned} \varphi = \left( \begin{array}{cc} \mu _{a,i} & \mu _{b,i} \\ \mu _{c,i} & \mu _{d,i} \end{array}\right) \end{aligned}$$
$$\begin{aligned}&\left|\{ x \in \mathbb {F}_{q^n} \mid \varphi (L)(x) - \gamma x = 0\} \right|= \left|\{ x \in \mathbb {F}_{q^n} \mid H^\varphi _L(x) - \gamma K^\varphi _L(x) = 0\} \right|\\&= \left|\{ x \in \mathbb {F}_{q^n} \mid (d-\gamma b)^{q^{n-i}}L(x) - (\gamma a - c)^{q^{n-i}} x = 0\} \right|, \end{aligned}$$
$$\begin{aligned} \left|\left\{ x \in \mathbb {F}_{q^n} \Big | L(x) - \left( \frac{\gamma a - c}{d-\gamma b}\right) ^{q^{n-i}} x = 0 \right\} \right|\end{aligned}$$
$$\begin{aligned} \nu _\varphi :x \mapsto \left( \frac{x a - c}{d - x b}\right) ^{q^{n-i}} \end{aligned}$$
The above Lemmas 1, 2, and 3, together with Theorem 1 imply Theorem 2 and thus completely settle Question 1 for the case of \(n \le 5\).
An interesting open question is whether the sets \(\mathcal {V}_k(L)\), \(k=1,\dots ,n\) are completely determined from \(\mathcal {I}(L)\) (equivalently from \(\mathcal {V}(L)\)) in general.
Question 2
Let \(L,M \in \mathbb {F}_{q^n}[X]\) be q-polynomials with \(\mathcal {V}(L) = \mathcal {V}(M)\). Does this imply \(\mathcal {V}_k(L) = \mathcal {V}_k(M)\) for all \(k \in \{1,\dots ,n\}\)?
In terms of linear sets, the question is equivalent to asking whether the weights of \(\langle (1,y) \rangle _{\mathbb {F}_{q^n}}\) with respect to the linear set \(\mathcal {L}_L\) are completely determined by the points \(\langle (1,y) \rangle _{\mathbb {F}_{q^n}}\) of weight \(w_{\mathcal {L}_L}(\langle (1,y) \rangle _{\mathbb {F}_{q^n}}) = 0\). Answering this question affirmatively immediately gives a positive answer to Question 1.
Remark 3
Besides the pairs of q-polynomials \((L,L^*)\), \((aX^{q^i},bX^{q^j})\) fulfilling \(\mathcal {I}(aX^{q^i}) = \mathcal {I}(bX^{q^j})\), and \((\varphi (L),\varphi (M))\) with \(\mathcal {I}(L)=\mathcal {I}(M)\), Question 2 also has an affirmative answer when one of L or M corresponds to the trace function \(x \mapsto \textrm{tr}(x)\). This follows immediately from the fact that for a q-polynomial M with \(\mathcal {I}(M) = \mathcal {I}(\textrm{tr}(X))\), we have \(M = \textrm{tr}(\lambda X)/\lambda \) for \(\lambda \ne 0\), as proven in [16, Theorem 3.7] (see also [17, Theorem 1.3]).
3 Bounded Differential Uniformity and Scattered q-Polynomials
Using Corollary 2, a simple upper bound on the differential uniformity of \(f_L\) can be given based on the emptiness of sets \(\mathcal {V}_k(L)\). That is, if \(k \in \{1,\dots ,n\}\) is the largest integer such that \(\mathcal {V}_k(L) \ne \emptyset \), the differential uniformity of \(f_L\) is bounded above by \(q^k\). Moreover, for the case of \(p=2\), we have \(-\mathcal {V}_k(L) = \mathcal {V}_k(L) \subseteq \mathcal {I}(L)\). Hence, for \(p=2\), the differential uniformity is equal to \(q^k\).
Then, from Lemma 3, it follows that we obtain functions of bounded differential uniformity from \(f_L\) if we stay in the same \(\Gamma \textrm{L}(2,q^n)\)-equivalence class.
Corollary 3
Let \(L \in \mathbb {F}_{q^n}[X]\) be a q-polynomial and let \(k \in \{1,\dots ,n\}\) be the largest integer such that \(\mathcal {V}_k(L) \ne \emptyset \). For any mapping \(\varphi \) admissible for L, the differential uniformity of \(f_{\varphi (L)}\) is bounded above by \(q^k\).
For odd values of p, this allows us to obtain functions \(f_M\) with different differential spectra (hence CCZ-inequivalent to each other), but \(\delta _{f_M} \le q^k\), from M within the \(\Gamma \textrm{L}(2,q^n)\)-equivalence class of L (an example is given in Example 1 below). However, in even characteristic, we do not leave the extended-affine equivalence class of \(f_L\) (and hence cannot obtain distinct differential spectra), as the following lemma states. Note that two functions \(f,g :\mathbb {F}_{q^n} \rightarrow \mathbb {F}_{q^n}\) are extended-affine equivalent (EA-equivalent) if there exist affine bijections \(A,B :\mathbb {F}_{q^n} \rightarrow \mathbb {F}_{q^n}\) and an affine function \(C :\mathbb {F}_{q^n} \rightarrow \mathbb {F}_{q^n}\) such that \(g = B \circ f \circ A + C\). In case that A and B are also linear and \(C= 0\), the functions f and g are called linear-equivalent. Since EA-equivalence is a special case of CCZ-equivalence, two EA-equivalent functions have the same differential spectrum.
Lemma 4
Let \(p=2\) and \(L \in \mathbb {F}_{q^n}[X]\) be a q-polynomial. Let \(\varphi \) be an admissible mapping for L as in (3). Then, \(f_L\) and \(f_{\varphi (L)}\) are EA-equivalent.
Proof
\(f_{\varphi {(L)}}\) corresponds to the mapping \(x \mapsto x \cdot H_L^\varphi ({K_L^{\varphi }}^{-1}(x))\), which is linear-equivalent to \(x \mapsto K_L^\varphi (x) \cdot H_L^\varphi (x)\). Now, we havewhich is linear-equivalent toNote that, since \(p=2\), we have \(ad + bc = ad - bc \ne 0\) because \(\varphi \) is admissible for L. Moreover, since \(p=2\), the mapping \(x \mapsto (ad+bc)^{-q^{-i}}((ac)^{q^{-i}} \cdot x^{2} + (bd)^{q^{-i}} \cdot L(x)^{2})\) is linear, hence \(f_{\varphi (L)}\) is EA-equivalent to \(f_L\). \(\square \)
$$\begin{aligned} K_L^\varphi (x) \cdot H_L^\varphi (x) = (ad + bc) \cdot (x L(x))^{q^i} + ac \cdot x^{2q^i} + bd \cdot L(x)^{2q^i}, \end{aligned}$$
$$\begin{aligned} xL(x) + (ad+bc)^{-q^{-i}}((ac)^{q^{-i}} \cdot x^{2} + (bd)^{q^{-i}} \cdot L(x)^{2}). \end{aligned}$$
Remark 4
Let \(\gamma \in \mathbb {F}_{q^n}\) and \(1 \le k \le n\). Then, \(\gamma \in \mathcal {I}(\varphi (L))\) and \(-\gamma \in \mathcal {V}_k(\varphi (L))\) if and only if \(\nu _\varphi (\gamma ) \in \mathcal {I}(L)\) and \(\nu _\varphi (-\gamma ) \in \mathcal {V}_k(L)\). Hence, by Corollary 2, the functions \(f_L\) and \(f_{\varphi (L)}\) have the same differential uniformity if \(\nu _\varphi (-\gamma ) = - \nu _\varphi (\gamma )\) holds for all \(\gamma \in \mathbb {F}_{q^n}\) with \(\gamma \in \mathcal {I}(\varphi (L))\). This condition is equivalent to \(ab \gamma ^2 - cd = 0\) for all \(\gamma \in \mathcal {I}(\varphi (L))\). Hence, a generic choice of \(\varphi \) preserving differential uniformity is such that \(a=d = 0\) or \(b = c = 0\). But then, \(f_L\) and \(f_{\varphi (L)}\) are linear-equivalent.
The q-polynomials L such that \(\mathcal {V}_k(L) = \emptyset \) for all \(k > 1\) are called scattered q-polynomials [26]. They are widely studied as they have applications in finite geometry (in terms of maximum scattered linear sets) and coding theory (in terms of rank distance codes [26]), see [21] and the references therein. It is well known that a q-polynomial \(L \in \mathbb {F}_{q^n}[X]\) is scattered if and only if \(\mathcal {I}(L)\) is of maximal size, i.e., \(\vert \mathcal {I}(L) |= \frac{q^n-1}{q-1}\). Indeed, \(\mathcal {I}(L)\) is of maximal size if and only if each element \(\frac{L(y)}{y} \in \mathcal {I}(L)\) has \(q-1\) preimages \(x = cy\) with \(c \in \mathbb {F}_{q}^*\). This yields an affirmative answer to Question 1 and Question 2 for those L, M for which \(\mathcal {V}(L)\) and \(\mathcal {V}(M)\) have size \(q^n-\frac{q^n-1}{q-1}\). There are only a few known instances and families of scattered q-polynomials, see e.g., the list in [4, Section 1]. The best known family of scattered q-polynomials are the monomials \(X^{q^s}\) with \(\gcd (s,n) = 1\). Bartoli and Zhou [5] showed that those monomials are the only exceptional scattered (of index 0) monic q-polynomials, i.e., the only monic q-polynomials that are scattered over infinitely many extensions of \(\mathbb {F}_q\).
For scattered q-polynomials, we get the following immediate corollaries from Propostion 1 and Corollary 3, respectively.
Corollary 4
Let \(L \in \mathbb {F}_{q^n}[X]\) be a q-polynomial. If L is scattered, the differential uniformity of \(f_L\) is bounded above by q and, for \(\mathcal {D}_{f_L} = (\eta _i)_{i=0,\dots ,q^n}\), we have \(\eta _i = 0\) for \(i \notin \{0,1,q\}\) andIf \(p = 2\), the differential uniformity of \(f_L\) is equal to q if and only if L is scattered.
$$\begin{aligned} \eta _q&= q^{n-1}(q-1) \cdot |\mathcal {I}(L) \cap - \mathcal {I}(L)|\\ \eta _1&= q^{n} \cdot (q-1) \cdot |\mathcal {I}(L) \cap - \mathcal {V}(L)|\\ \eta _0&= q^{n-1}(q-1)^2 \cdot |\mathcal {I}(L) \cap - \mathcal {I}(L)|. \end{aligned}$$
Corollary 5
Let \(L \in \mathbb {F}_{q^n}[X]\) be a scattered q-polynomial and let \(\varphi \) be an admissible mapping for L as in (3). Then, \(\delta _{f_{\varphi (L)}} \le q\).
This corollary is a consequence of the fact that the property of a q-polynomial in \(\mathbb {F}_{q^n}[X]\) being scattered is invariant under \(\Gamma \textrm{L}(2,q^n)\)-equivalence.
Example 1
Consider \(q = p\) for an odd prime p and let \(L = X^{p^s} \in \mathbb {F}_{p^n}[X]\) for s with \(\gcd (s,n) = 1\). Then, \(f_L :\mathbb {F}_{p^n} \rightarrow \mathbb {F}_{p^n}, x \mapsto x^{p^s+1}\) is planar if and only if n is odd [15]. Since L is scattered, \(f_L\) has differential uniformity of p if n is even. Let \(a \in \mathbb {F}_{q^n}^*\). The mappingis admissible for L. Then, \(\varphi (L)(x) = H_L^\varphi ((K_L^\varphi )^{-1}(x))\) with \(H_L^\varphi (x) = ax^{p^s} + a^{p^s}x\) and \(K_L^\varphi (x) = x\), so \(\varphi (L) = aX^{p^s} + a^{p^s}X = f_L(X+a) - f_L(X) - f_L(a)\) (which is also scattered). Hence, the differential uniformity of \(f_{\varphi (L)} :\mathbb {F}_{p^n} \rightarrow \mathbb {F}_{p^n}, x \mapsto ax^{p^s+1} + a^{p^s}x^2\) is bounded above by p. Note that, for each \(a \in \mathbb {F}_{q^n}^*\), the function \(f_{\varphi (L)}\) is linear-equivalent to \(x \mapsto x^{p^s+1} + x^2\). We experimentally checked that, for \(p \in \{3,5,7\}\), \(n \in \{2,3,4,5\}\) and \(\gcd (s,n) = 1\), the differential uniformity of \(x \mapsto x^{p^s+1} + x^2\) is indeed equal to p.
$$\begin{aligned} \varphi :=\begin{pmatrix} \mu _{1,0} & 0 \\ \mu _{L(a),0}& \mu _{a,0} \end{pmatrix}\end{aligned}$$
In the following example, we illustrate that it is possible to get a variety of distinct differential spectra for \(f_{\varphi (L)}\) when L is a scattered q-polynomial and \(\varphi \) and admissible mapping for L (in the case where q is odd).
Example 2
Again, we consider the scattered polynomial \(L = X^{p^s} \in \mathbb {F}_{p^n}[X]\), but for \(p=n=3\) and \(s=1\) fixed. Hence, \(f_L\) is planar, so the differential spectrum is \(\mathcal {D}_{f_L} = (0,702,0,0,0)\). Generating several admissible mappings \(\varphi \) for L, we obtain the following six additional differential spectra for \(f_{\varphi (L)}\): (252,324,126,0,0), (144,486,72,0,0), (288,270,144,0,0), (180,432,90,0,0), (216,378,108,0,0), and (468,0,234,0,0).
In general, it would be interesting to classify all possible differential spectra of \(f_{\varphi (L)}\) for admissible mappings \(\varphi \) for L, for a given scattered q-polynomial L and to understand whether a scattered q-polynomial L can yield CCZ-inequivalent planar functions \(f_{\varphi (L)}\).
Remark 5
It was proven in [7, Theorem 6] that an APN function \(f_L\) for \(L = \sum _{i=1}^{n-1}a_iX^{2^i} \in \mathbb {F}_{2^n}[X]\) is APN (i.e., \(\delta _{f_L} = 2\)) if and only if L is a monomial \(aX^{2^k}\) with \(\gcd (k,n) =1\), \(a \in \mathbb {F}_{2^n}^*\). To obtain this result, the authors of [7] proved that \(f_L\) is APN if and only if \(r_L\) is a permutation of \(\mathbb {F}_{2^n}^*\), i.e., if and only if \(|\mathcal {I}(L) |= 2^n-1\), i.e., if and only if L is scattered. This is a special case of Corollary 4. They then used the fact that \(r_L\) can only be a permutation if L is a monomial, as already proven by Payne [24] and by the authors in [6] using Hermite’s criterion.
This means that any scattered 2-polynomial is is necessarily a monomial. Note that there exist more instances of scattered q-polynomials for q being a larger power of 2, see, e.g., [4].
Acknowledgements
The author thanks the anonymous reviewers for their helpful comments and Daniele Bartoli for a discussion on the problem stated in Question 2.
Declarations
Competing interests
The authors declare no competing interests.
Open Access This 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.
