1. Introduction
A mapping \(f : \mathbb{F}_{2}^n\rightarrow\mathbb{F}_{2}^m\) is called a vectorial Boolean function, also known as an \((n, m)\)-function. When \(n=1\), \(f\) reduces to a Boolean function. In this letter, we limit our study to the \((n,m)\)-functions where \(n=m\). Let \(\mathbb{F}_{2^n}\) be the finite field with \(2^n\) elements, and \(\mathbb{F}_{2^n}^\ast=\mathbb{F}_{2^n}\backslash\{0\}\) be the multiplicative group of \(\mathbb{F}_{2^n}\). By identifying the vector space \(\mathbb{F}_{2}^n\) with the additive structure of \(\mathbb{F}_{2^n}\), \(f\) can be viewed as a mapping from \(\mathbb{F}_{2^n}\) to itself. If the mapping \(f: c\mapsto f(c)\) is a bijection on \(\mathbb{F}_{2^n}\), then \(f(x)\) is called a permutation polynomial over \(\mathbb{F}_{2^n}\). Due to its important applications in cryptography, coding theory and combinatorial designs (see [8], [13], [14] for instance), permutation polynomials have been intensively studied in the past. The study can be generalized from the case of univariate to bivariate. Let \(f_1(x,y), f_2(x,y)\in\mathbb{F}_{2^n}[x,y]\), then \(F(x, y)=(f_1(x,y), f_2(x,y))\) is called a permutation polynomial over \(\mathbb{F}_{2^n}\times\mathbb{F}_{2^n}\) if the corresponding mapping of \(F(x,y)\) is a bijection of \(\mathbb{F}_{2^n}\times\mathbb{F}_{2^n}\).
Though the number of papers on univariate permutation polynomials over \(\mathbb{F}_{2^n}\) is very large so far [7], the results on bivariate permutation polynomials are not so many. In recent years, to construct permutation polynomials with good cryptographic properties such as low differential uniformity, many researchers investigated permutation polynomials over \(\mathbb{F}_{2^n}\times\mathbb{F}_{2^n}\) with the form of butterfly structure
| \[\begin{eqnarray*} ((x+\alpha y)^{2^i+1}+\beta y^{2^i+1},(y+\alpha x)^{2^i+1}+\beta x^{2^i+1}) \tag{1} \end{eqnarray*}\] |
and obtained several constructions (see for instance [1], [3], [4], [6], [11]). Very recently, G\(\ddot{{\rm o}}\)lo\(\check{{\rm g}}\)lu [2] classified fractional projective permutations over finite fields, which generalized the results of permutations in the form of (1). In addition, it is worth noting that permutation polynomials can be also utilized for constructing bent functions, which are regarded as maximally nonlinear Boolean functions. For further details, we refer the reader to [5], [9], [10].
In this letter, our aim is to construct explicitly more new bivariate permutation polynomials over \(\mathbb{F}_{2^n}\times\mathbb{F}_{2^n}\) by using orthogonal system of equations. In our new method, we divide the set \(\mathbb{F}_{2^n}\times\mathbb{F}_{2^n}\) into two parts, and verify that the polynomial is injective on each part and the corresponding image sets are disjoint, then it is a permutation polynomial. Finally, we obtain four new classes of such permutation polynomials.
2. Preliminaries
In this section, we introduce some notations and auxiliary results which are useful in the sequel.
Let \(n\) be any positive integer and \(m~|~n\), we denote by
| \[\operatorname{Tr}_{m}^{n}(x)=x+x^{2^{m}}+x^{2^{2 m}}+\cdots+x^{2^{n-m}}\] |
the trace mapping from \(\mathbb{F}_{2^n}\) to \(\mathbb{F}_{2^m}\).
The following lemma is directly from Lemma 2.3 of [12].
Lemma 2.1 Let \(n, i\) be any positive integers and \(x\ne y\) be two elements of \(\mathbb{F}_{2^n}\). Then
| \[\frac{x^{2^{i}} y+x y^{2^{i}}}{(x+y)^{2^i+1}}= \sum_{t=0}^{i-1}\frac{(xy)^{2^t}}{(x+y)^{2^{t+1}}}.\] |
Throughout this letter, we denote the image set of a polynomial \(F(x,y)\) over \(A\times B\subseteq\mathbb{F}_{2^n}\times\mathbb{F}_{2^n}\) as Im(\(F(A,B)\)).
3. Constructions of Bivariate Permutation Polynomials
In this section, we propose four classes of permutation polynomials over \(\mathbb{F}_{2^n}\times\mathbb{F}_{2^n}\).
The first class of permutation polynomials is given as follows.
Theorem 3.1 Let \(n, d\) be positive integers such that gcd\((d, 2^n-1)=1\). Let \(a\ne b\in\mathbb{F}_{2^n}\), \(f(x,y)\in\mathbb{F}_{2^n}[x,y]\) be a homogeneous polynomial of degree \(d\) such that \(f(0,y)\ne 0\), \(f(y):=f(1,y)\) is a permutation polynomial over \(\mathbb{F}_{2^n}\). Then \(F(x,y)=(f(x,y)+ax^d, f(x,y)+bx^d)\) permutes \(\mathbb{F}_{2^n}^2\).
Proof. In order to prove that \(F\) is a permutation, one only needs to show that if the system of equations
| \[\begin{eqnarray*} \left\{\begin{array}{@{}l@{}} f(x,y)+ax^d=c_1,\\ f(x,y)+bx^d=c_2 \end{array}\right. \tag{2} \end{eqnarray*}\] |
has a solution \((x_0,y_0)\) in \(\mathbb{F}_{2^n}^2\) for all \(c_1,c_2\in\mathbb{F}_{2^n}\), then this solution is unique. Firstly, we consider the case that \((x_0,y_0)\in\mathbb{F}_{2^n}^\ast\times\mathbb{F}_{2^n}\). Let \(y_0=sx_0\) with some \(s\in\mathbb{F}_{2^n}\). Then System (2) can be rewritten as
| \[\begin{eqnarray*} \left\{\begin{array}{@{}l@{}} x_0^{d}(f(s)+a)=c_1, \\ x_0^{d}(f(s)+b)=c_2. \end{array}\right. \tag{3} \end{eqnarray*}\] |
Note that if \(c_1=0\), then \(f(s)=a\), and thus \(s\) is uniquely determined by \(a\), since \(f\) permutes \(\mathbb{F}_{2^n}\). Furthermore, \(x_0=(\frac{c_2}{a+b})^{\frac{1}{d}}\) as gcd\((d,2^n-1)=1\). The case that \(c_2=0\) is similar, so we omit it. Next we assume that \(c_1c_2\ne0\) and \(c=\frac{c_1}{c_2}\), then System (3) is equivalent to
| \[f(s)(c+1)+a+bc=0.\] |
If \(c=1\), then we have \(a=b\), which contradicts to the assumption that \(a\ne b\). Hence we can get
| \[f(s)=\frac{a+bc}{c+1},\] |
hence \(s\) is determined by the above equation. Therefore \((x_0,y_0)\) can be determined uniquely.
Secondly, we consider the case that \((x_0,y_0)\in\{0\}\times\mathbb{F}_{2^n}\). Then \(y_0\) is uniquely determined by \(f(0,y)=c_0\in\mathbb{F}_{2^n}\). At last, we prove that \(F(\mathbb{F}_{2^n}^\ast,\mathbb{F}_{2^n})\cap F(0,\mathbb{F}_{2^n})=\emptyset\). It is equivalent to showing that
| \[\left\{\begin{array}{@{}l@{}} x_0^{d}(f(s)+a)=f(0,y), \\ x_0^{d}(f(s)+b)=f(0,y) \end{array}\right.\] |
does not hold, which is obvious since \(a\ne b\). This completes the proof.
Corollary 3.2 Let gcd\((n,3)=1\) and \(a\ne b\in\mathbb{F}_{2^n}\), then \(F(x,y)=(y^4+x^2y^2+x^3y+ax^4,y^4+x^2y^2+x^3y+bx^4)\) permutes \(\mathbb{F}_{2^n}^2\).
Proof. Let \(d=4\) in Theorem 3.1, then we have \(f(y)=f(1,y)=y^4+y^2+y\). It is easily checked that \(f(y)=0\) has a unique solution \(y=0\) in \(\mathbb{F}_{2^n}\), since \(y^3+y+1\) is irreducible over \(\mathbb{F}_{2}\) and gcd\((n,3)=1\).
The second class of permutation polynomials is constructed from some bivariate pentanomials.
Theorem 3.3 Let \(n,i\) be any positive integers such that \(n\) is odd and gcd\((n,3i)=1\). Let
| \[\begin{aligned} &&\!\!\!\!\! f_1(x,y)\!=\!x^{2^{2i}\!+\!2^{i}+1}\!+\!x^{2^{2i}+1}y^{2^{i}}\!+\!x^{2^{2i}}y^{2^i+1}\!+\! x^{2^{i}+1}y^{2^{2i}}\!+\!xy^{2^{2i}+2^i},\\ &&\!\!\!\!\! f_2(x,y)\!=\!x^{2^{2i}\!+\!2^i}y\!+\!x^{2^{2i}}y^{2^i+1}\!+\!x^{2^{2i}-1}y^{2^{i}+2}\!+\! x^{2^i}y^{2^{2i}+1}\!+\!y^{2^{2i}+2^i+1}, \end{aligned}\] |
then \(F(x,y)=(f_1(x,y),f_2(x,y))\) permutes \(\mathbb{F}_{2^n}^2\).
Proof. To prove that \(F(x,y)=(f_1(x,y),f_2(x,y))\) permutes \(\mathbb{F}_{2^n}^2\), one only needs to show under the assumption that for all \(c_1,c_2\in\mathbb{F}_{2^n}\) the system
| \[\begin{eqnarray*} \left\{\begin{array}{@{}l@{}} x^{2^{2i}\!+\!2^{i}+1}+x^{2^{2i}+1}y^{2^{i}}\!+\!x^{2^{2i}}y^{2^i+1}\!+\!x^{2^{i}+1} y^{2^{2i}}\!+\!xy^{2^{2i}+2^i}\!=\!c_1,\\ x^{2^{2i}+2^i}y\!+\!x^{2^{2i}}y^{2^i+1}\!+\!x^{2^{2i}-1}y^{2^{i}+2}\!+\!x^{2^i} y^{2^{2i}+1}\!+\!y^{2^{2i}\!+\!2^i+1}\!=\!c_2 \end{array}\right. \tag{4} \end{eqnarray*}\] |
has a solution \((x_0,y_0)\) in \(\mathbb{F}_{2^n}^2\), then it must be unique. Firstly, we consider the case that \((x_0,y_0)\in\mathbb{F}_{2^n}^\ast\times\mathbb{F}_{2^n}\). Let \(y_0=sx_0\) with \(s\in\mathbb{F}_{2^n}\). Then System (4) can be rewritten as
| \[\begin{eqnarray*} \left\{\begin{array}{@{}l@{}} x_0^{2^{2i}+2^{i}+1}(s^{2^{2i}+2^i}+s^{2^{2i}}+s^{2^i+1}+s^{2^i}+1)=c_1, \\ x_0^{2^{2i}+2^i+1}(s^{2^{2i}+2^i+1}+s^{2^{2i}+1}+s^{2^{i}+2}+s^{2^i+1}+s)=c_2. \end{array}\right. \tag{5} \end{eqnarray*}\] |
Note that if \(c_2=0\), then \(s=0\) or \(s^{2^{2i}+2^i}+s^{2^{2i}}+s^{2^i+1}+s^{2^i}+1=0\). For the former, we have \(x_0=c_1^{\frac{1}{2^{2i}+2^i+1}}\) as gcd\((n,3i)=1\). Thus, \((c_1^{\frac{1}{2^{2i}+2^i+1}},0)\) is the unique solution of (4). For the latter, one has
| \[\begin{eqnarray*} 0=\operatorname{Tr}_1^n\bigg(s^{2^{2i}+2^i}+s^{2^{2i}}+s^{2^i+1}+s^{2^i}\bigg)=\operatorname{Tr}_1^n(1), \tag{6} \end{eqnarray*}\] |
which contradicts to \(n\) being odd. Therefore, if \(c_2\ne0\) and let \(c=\frac{c_1}{c_2}\), then System (5) is equivalent to
| \[\begin{eqnarray*} \nonumber (s^{2^{2i}+2^i}+s^{2^{2i}}+s^{2^i+1}+s^{2^i}+1)(s+c)=0, \end{eqnarray*}\] |
which implies that \(s=c\). Therefore we has the unique solution \((x_0,y_0)=((\frac{c_1}{c^{2^{2i}+2^i}+c^{2^{2i}}+c^{2^i+1}+c^{2^i}+1})^{\frac{1}{2^{2i}+2^i+1}}, c\cdot(\frac{c_1}{c^{2^{2i}+2^i}+c^{2^{2i}}+c^{2^i+1}+c^{2^i}+1})^{\frac{1}{2^{2i}+2^i+1}})\) for (4).
Secondly, for the case \((x_0,y_0)\in \{0\}\times\mathbb{F}_{2^n}\), we get \(y_0=c_2^{\frac{1}{2^{2i}+2^i+1}}\). This completes the proof.
Example 3.4 Let \(n=5\) and \(i=1\), then \(F(x,y)=(x^7+x^5y^2+x^4y^3+x^3y^4+xy^6,x^6y+x^4y^3+x^3y^4+x^2y^5+y^7)\) is a permutation polynomial over \(\mathbb{F}_{2^5}^2\).
The third class of permutation polynomials is constructed from linear bivariate binomials and quadrinomials of algebraic degree 2.
Theorem 3.5 Let \(i<n, j\) be positive integers, \(k=\)gcd\((n,i)\) and \(f_1(x,y)=(x+ay)^{2^j}, f_2(x,y)=x^{2^i+1}+b x^{2^i}y+c xy^{2^i}+d y^{2^i+1}\in\mathbb{F}_{2^n}[x]\). Let
| \[\left\{\begin{array}{@{}l@{}} \theta_1= a+b,\\ \theta_2= a^{2^i}+c, \\ \theta_3= a^{2^i+1}+d+a^{2^i}b+ac, \\ \theta_4= a^{2^i+1}+d,\\ \theta_5= a^{2^i}d+a^{2^i+1}c,\\ \theta_6= a^{2^i+1}b+ad \end{array}\right.\] |
such that \(\theta_3\not=0\), \(\theta_2^{2^i}=\theta_1{\theta_3^{2^i-1}}\), \(\theta_6^{2^i}=\theta_5{\theta_3^{2^i-1}}\) and \(\operatorname{Tr}_k^n(\frac{\theta_4}{\theta_3})\ne0\). Then \(F(x,y)=(f_1(x,y),f_2(x,y))\) permutes \(\mathbb{F}_{2^n}^2\).
Proof. One only needs to show that if \(F(x_1,y_1)=F(x_2,y_2)\), i.e,
| \[\begin{eqnarray*} \left\{\begin{array}{@{}l@{}} (x_1+ay_1)^{2^j}= (x_2+ay_2)^{2^j}, \\ x_1^{2^i+1}+b x_1^{2^i}y_1+c x_1y_1^{2^i}+d y_1^{2^i+1} \\ = x_2^{2^i+1}+b x_2^{2^i}y_2+c x_2y_2^{2^i}+d y_2^{2^i+1}, \end{array}\right. \tag{7} \end{eqnarray*}\] |
then \(x_1=x_2\) and \(y_1=y_2\), say \(F\) is injective. Firstly, we prove that \(F(x,y)\) is injective on \(\mathbb{F}_{2^n}^\ast\times\mathbb{F}_{2^n}\). Suppose that (7) holds for some \((x_1,y_1)\) and \((x_2,y_2)\in\mathbb{F}_{2^n}^\ast\times\mathbb{F}_{2^n}\). There exist some \(s, r\in\mathbb{F}_{2^n}\) such that \(y_1=sx_1\) and \(y_2=rx_2\). Thus, System (7) can be rewritten as
| \[\begin{equation*} \left\{\begin{array}{l} x_1^{2^j}(a s+1)^{2^j}=x_2^{2^j}(a r+1)^{2^j}, \hskip20mm (8a)\\ x_1^{2^i+1}\left(d s^{2^i+1}+c s^{2^i}+b s+1\right) \\ =x_2^{2^i+1}\left(d r^{2^i+1}+c r^{2^i}+b r+1\right). \hskip14mm (8b) \end{array}\right. \end{equation*}\] |
Raising (8a) and (8b) to \(({2^i+1})\)-th power and \({2^j}\)-th power, respectively, and eliminating \(x_1\) and \(x_2\), one has
| \[\begin{eqnarray*} \nonumber (as+1)^{2^j(2^i+1)}(d r^{2^i+1}+c r^{2^i}+b r+1)^{2^j}\\=(ar+1)^{2^j(2^i+1)}(ds^{2^i+1}+c s^{2^i}+b s+1)^{2^j},\nonumber \end{eqnarray*}\] |
which is equivalent to
| \[\begin{eqnarray*} (ds^{2^i+1}\!+\!cs^{2^i}\!+\!bs\!+\!1)((ar)^{2^i+1}\!+\!(ar)^{2^i}\!+\!ar\!+\!1)\nonumber\\ =\!(dr^{2^i+1}\!+\!cr^{2^i}\!+\!br\!+\!1)((as)^{2^i+1}\!+\!(as)^{2^i}\!+\!as\!+\!1) \tag{9} \end{eqnarray*}\] |
since gcd\((2^j,2^n-1)=1\). By expanding (9), we have then
| \[\begin{eqnarray*} \nonumber &&\!\!\!\!\! \theta_{1}(s+r)+\theta_{2}(s+r)^{2^{i}}+\theta_{5}(s+r)(s r)^{2^{i}}\\ &&\!\!\!\!\! +\theta_{6}(s+r)^{2^{i}}(s r)+\theta_{4}(s+r)^{2^{i}+1}+\theta_{3}(s^{2^{i}} r+s r^{2^{i}})=0. \nonumber \end{eqnarray*}\] |
If \(s\not=r\), then by the assumptions that \(\theta_3\not=0\), \(\theta_2^{2^i}=\theta_1{\theta_3^{2^i-1}}\) and \(\theta_6^{2^i}=\theta_5{\theta_3^{2^i-1}}\), the above equation is equivalent to
| \[\left( \frac{\theta_{2}+\theta_{6}sr}{\theta_{3}(s+r)}\right)^{2^{i}}+ \frac{\theta_{2}+\theta_{6}sr}{\theta_{3}(s+r)} +\frac{\theta_{4}}{\theta_{3}}+\frac{s^{2^{i}} r+s r^{2^{i}}}{(s+r)^{2^i+1}}=0.\] |
Note that \(\frac{s^{2^{i}} r+s r^{2^{i}}}{(s+r)^{2^i+1}}= \sum_{t=0}^{i-1}\frac{(sr)^{2^t}}{(s+r)^{2^{t+1}}}\) by Lemma 2.1 and \(\frac{sr}{(s+r)^2}=\frac{s}{s+r}+(\frac{s}{s+r})^2\). Applying \(\operatorname{Tr}_k^{n}(\cdot)\) on both sides of the above equation, then we can get
| \[\begin{eqnarray*} \nonumber \operatorname{Tr}_k^{n}(\frac{\theta_4}{\theta_3})&=&\operatorname{Tr}_k^{n}\left(\left( \frac{\theta_{2}+\theta_{6}sr}{\theta_{3}(s+r)}\right)^{2^{i}}+ \frac{\theta_{2}+\theta_{6}sr}{\theta_{3}(s+r)}\right)\\ &&+\operatorname{Tr}_k^{n}\left(\sum_{t=0}^{i-1}\left(\frac{s}{s+r}+(\frac{s}{s+r})^2\right)^{2^t}\right)=0, \tag{10} \end{eqnarray*}\] |
which contradict to the condition that \(\operatorname{Tr}_k^n(\frac{\theta_4}{\theta_3})=1\). Therefore, we must have \(s=r\), which implies from (7) that \(x_1=x_2\) or
| \[\begin{eqnarray*} \left\{\begin{array}{@{}l@{}} (as+1)^{2^i}=0,\\ d s^{2^i+1}+c s^{2^i}+b s+1=0. \end{array}\right. \tag{11} \end{eqnarray*}\] |
Hence if (11) does not hold, then \(x_1=x_2\) and thus \(y_1=y_2\), so that \(F(x,y)\) is indeed injective on \(\mathbb{F}_{2^n}^\ast\times\mathbb{F}_{2^n}\).
On the other hand, it is easy to see that \(F(0,y)=((ay)^{2^j}, dy^{2^i+1})\) is injective on \(\{0\}\times\mathbb{F}_{2^n}\).
Therefore, we only need to show that
| \[F(\mathbb{F}_{2^n}^\ast,\mathbb{F}_{2^n})\cap F(0,\mathbb{F}_{2^n})=\emptyset,\] |
and that (11) does not hold. Assume that \((x_1, y_1)\in\mathbb{F}_{2^n}^\ast\times\mathbb{F}_{2^n}\) and \((x_2,y_2)\in\{0\}\times\mathbb{F}_{2^n}\) such that \(F(x_1, y_1)=F(x_2, y_2)\). Let \(y_1=sx_1\), then (7) can be rewritten as
| \[\begin{equation*} \left\{\begin{array}{l} x_1^{2^j}(as+1)^{2^i}=(ay_2)^{2^j},\hskip35mm (12a) \\ x_1^{2^i+1}(d s^{2^i+1}+c s^{2^i}+bs+1)=d y_2^{2^i+1}.\hskip11mm (12b) \end{array} \right. \end{equation*}\] |
Raising (12a) and (12b) to \(({2^i+1})\)-th power and \({2^j}\)-th power, respectively, and then computing \(d^{2^j}\times(12a)+a^{2^{i+j}+2^j}\times(12b)\), one gets
| \[\theta_5s^{2^i}+\theta_6s+\theta_4=0.\] |
Dividing \(\theta_3\) and applying \(\operatorname{Tr}_k^{n}(\cdot)\) on both sides of the above equation, we obtain
| \[\operatorname{Tr}_k^{n}\bigg(\frac{\theta_4}{\theta_3}\bigg) =\operatorname{Tr}_k^{n}\bigg(\bigg(\frac{\theta_6s}{\theta_3}\bigg)^{2^i}+\frac{\theta_6s}{\theta_3}\bigg)=0,\] |
which contradicts to \(\operatorname{Tr}_k^n(\frac{\theta_4}{\theta_3})\ne0\). Thus, one gets \(F(\mathbb{F}_{2^n}^\ast,\mathbb{F}_{2^n})\cap F(0,\mathbb{F}_{2^n})=\emptyset\). Moreover, it is also easy to check that (11) does not hold by the above discussion.
Thus, \(F(x,y)\) permutes \(\mathbb{F}_{2^n}^2\). This completes the proof.
Example 3.6 Let \(n=3\) and \(w\) be a primitive element of \(\mathbb{F}_{2^3}\). Then it can be checked by Magma that \(a=b=c=1\), \(d=w\), \(i=1\) and \(j=2\) satisfy all the conditions of Theorem 3.5. Therefore, \(F(x,y)=(x^4+y^4,x^3+x^2y+xy^2+wy^3)\) is a permutation polynomial over \(\mathbb{F}_{2^3}^2\).
Remark 3.7 For \(n\leq 5\) and \(F(x,y)\) on \(\mathbb{F}_{2^n}[x,y]\times\mathbb{F}_{2^n}[x,y]\) of the given form, we have checked by Magma software that the conditions of Theorem 3.5 are also necessary. For example, there are in total 31744 different triples \((a,b,c,d)\in (\mathbb{F}_{2^5})^4\) which satisfy the conditions of Theorem 3.5 and the corresponding polynomials are exactly all those \(F(x,y)\in\mathbb{F}_{2^5}[x,y]\) permuting \(\mathbb{F}_{2^5}^2\).
The fourth class of permutation polynomials is constructed by some bivariate trinomials and quadrinomials of algebraic degree 3.
Theorem 3.8 Let \(n\) be odd, \(f_1(x,y)=x^4+x^2y^2+x^3y\) and \(f_2(x,y)=x^4+x^3y+xy^3+y^4\), then \(F(x,y)=(f_1(x,y),f_2(x,y))\) permutes \(\mathbb{F}_{2^n}^2\).
Proof. Let \((x_1, y_1), (x_2, y_2)\in\mathbb{F}_{2^n}^2\) such that \(F(x_1, y_1)=F(x_2, y_2)\), i.e,
| \[\begin{eqnarray*} \left\{\begin{array}{@{}l@{}} x_1^4+x_1^2y_1^2+x_1^3y_1= x_2^4+x_2^2y_2^2+x_2^3y_2, \\ x_1^4+x_1^3y_1+x_1y_1^3+y_1^4=x_2^4+x_2^3y_2+x_2y_2^3+y_2^4, \end{array}\right. \tag{13} \end{eqnarray*}\] |
one needs to show \((x_1, y_1)=(x_2, y_2)\).
Firstly, assume that \((x_1, y_1), (x_2, y_2)\in\mathbb{F}_{2^n}^\ast\times\mathbb{F}_{2^n}\). Write \(y_1=sx_1\) and \(y_2=rx_2\) for some \(s, r\in\mathbb{F}_{2^n}\). Then (13) can be rewritten as
| \[\begin{eqnarray*} \left\{\begin{array}{@{}l@{}} x_1^{4}(s^2+s+1)=x_2^{4}(r^2+r+1), \\ x_1^{4}(s^4+s^3+s+1)=x_2^{4}(r^4+r^3+r+1), \end{array}\right. \tag{14} \end{eqnarray*}\] |
which gives
| \[\begin{eqnarray*} (s^2\!+\!s\!+\!1)(r^4\!+\!r^3\!+\!r\!+\!1)\!=\!(r^2\!+\!r\!+\!1)(s^4\!+\!s^3\!+\!s\!+\!1). \tag{15} \end{eqnarray*}\] |
By expanding (15), we have then
| \[\begin{eqnarray*} &&\!\!\!\!\! s^2r^2(s+r)^2+sr(s+r)^3+sr(s+r)^2+(s+r)^4\nonumber\\ &&\!\!\!\!\! +(s+r)^3+(s+r)^2=0. \tag{16} \end{eqnarray*}\] |
Suppose that \(s\not=r\). Let \(v=sr\) and \(u=s+r\), the above equation is equivalent to
| \[\begin{eqnarray*} v^2+(u+1)v+u^2+u+1=0. \tag{17} \end{eqnarray*}\] |
Note that
| \[\operatorname{Tr}_1^n\bigg(\frac{u^2+u+1}{(u+1)^2}\bigg)=\operatorname{Tr}_1^n(1) +\operatorname{Tr}_1^n\bigg(\frac{u}{u+1}+\bigg(\frac{u}{u+1}\bigg)^2\bigg)=1,\] |
since \(n\) is odd. It means that (17) has no solution in \(\mathbb{F}_{2^n}\). Therefore, it must hold \(s=r\), which implies from (13) that \(x_1=x_2\) or
| \[\begin{eqnarray*} \left\{\begin{array}{@{}l@{}} s^2+s+1=0,\\ s^4+s^3+s+1=0. \end{array}\right. \tag{18} \end{eqnarray*}\] |
Note that (18) does not hold, since \(s^2+s+1=0\) has no solution in \(\mathbb{F}_{2^n}\). Then we get \(x_1=x_2\) and \(y_1=y_2\).
On the other hand, since \(F(0,y)=(0,y^{4})\), it is obvious that \(F(0,y_1)=F(0,y_2)\) indicates \(y_1=y_2\).
At last, we need to show that (13) cannot hold if \((x_1, y_1)\in\mathbb{F}_{2^n}^\ast\times\mathbb{F}_{2^n}, (x_2, y_2)\in\{0\}\times \mathbb{F}_{2^n}.\) Assume that there exist some \((x_1,y_1)\in\mathbb{F}_{2^n}^\ast\times\mathbb{F}_{2^n}\) and \((x_2,y_2)\in\{0\}\times\mathbb{F}_{2^n}\) satisfying (13). Then there is some \(s\in\mathbb{F}_{2^n}\) such that \(y_1=sx_1\), and (13) can be rewritten as
| \[\left\{ \begin{array}{@{}l@{}} x_1^{4}(s^2+s+1)=0, \\ x_1^{4}(s^4+s^3+s+1)=y_2^4. \end{array} \right.\] |
Since \(n\) is odd and \(s^2+s+1\) is irreducible over \(\mathbb{F}_2\), \(s^2+s+1=0\) has no solution in \(\mathbb{F}_{2^n}\), a contradiction.
Therefore, \(F(x,y)\) permutes \(\mathbb{F}_{2^n}^2\). This completes the proof.
Acknowledgments
This work was supported in part by the National Key Research and Development Program of China under Grant 2019YFB2101703; in part by the National Natural Science Foundation of China under Grants 61972258, 62272107 and U19A2066; in part by the Innovation Ac-tion Plan of Shanghai Science and Technology under Grants 20511102200 and 21511102200; in part by the Key Research and Development Program of Guangdong Province under Grant 2020B0101090001, and in part by Open Research Program of Shanghai Key Lab of Intelligent Information Processing under Grant IIPL201902.
References
[1] A. Canteaut, S. Duval, and L. Perrin, “A generalisation of Dillon’s APN permutation with the best known differential and nonlinear properties for all fields of size 24k+2,” IEEE Trans. Inf. Theory, vol.63, no.11, pp.7575-7591, March 2017.
CrossRef
[2] F. Göloǧlu, “Classification of fractional projective permutations over finite fields,” Finite Fields Their Appl., vol.81, p.102027, Aug. 2022.
CrossRef
[3] N. Li, Z. Hu, M. Xiong, and X. Zeng, “4-uniform BCT permutations from generalized butterfly structure,” arXiv:2001.00464, Jan. 2020.
CrossRef
[4] K. Li, C. Li, T. Helleseth, and L. Qu, “Cryptographically strong permutations from the butterfly structure,” Des. Codes Cryptogr., vol.89, pp.737-761, Feb. 2021.
CrossRef
[5] Y. Li, K. Li, S. Mesnager, and L. Qu, “More permutations and involutions for constructing bent functions,” Des. Codes Cryptogr., vol.13, pp.459-473, March 2021.
CrossRef
[6] Y. Li, S. Tian, Y. Yu, and M. Wang, “On the generalization of butterfly structure,” ToSC, vol.2018, no.1, pp.160-179, March 2018.
CrossRef
[7] N. Li and X. Zeng, “A survey on the applications of Niho exponents,” Cryptogr. Commun., vol.11, pp.509-548, May 2019.
CrossRef
[8] J. Peng, L. Zheng, C. Wu, and H. Kan, “Permutation polynomials x2k+1+3 + ax2k+2 + bx over 𝔽2k2 and their differential uniformity,” Sci. China Inf. Sci., vol.63, pp.1-3, 2020.
CrossRef
[9] E. Pasalic, S. Hodžić, F. Zhang, and Y. Wei, “Bent functions from nonlinear permutations and conversely,” Cryptogr. Commun., vol.11, pp.207-225, March 2019.
CrossRef
[10] S. Pang, M. Feng, X. Wang, and J. Wang, “Construction of permutations and bent functions,” IEICE Trans. Fundamentals, vol.E101-A, no.3, pp.604-607, March 2018.
CrossRef
[11] L. Perrin, A. Udovenko, and A. Biryukov, “Cryptanalysis of a theorem: Decomposing the only known solution to the big APN problem,” Advances in Cryptology - CRYPTO 2016, Lect. Notes Comput. Sci., vol.9815, pp.93-122, July 2016.
CrossRef
[12] L. Wang and B. Wu, “General constructions of permutation polynomials of the form (x2m + x + δ)i(2m-1)+1 + x over 𝔽2m2,” Finite Fields Their Appl., vol.52, pp.137-155, July 2018.
CrossRef
[13] L. Zheng, B. Liu, H. Kan, J. Peng, and D. Tang, “More classes of permutation quadrinomials from Niho exponents in characteristic two,” Finite Fields Their Appl., vol.78, p.101962, Feb. 2022.
CrossRef
[14] L. Zheng, J. Peng, H. Kan, Y. Li, and J. Luo, “On constructions and properties of (n, m)-functions with maximal number of bent components,” Des. Codes Cryptogr., vol.88, pp.2171-2186, June 2020.
CrossRef
