# Two-to-one mappings and involutions without fixed points over
${\mathbb{F}}_{2^{n}}$

Mu Yuan1, Dabin Zheng1111Corresponding author<EMAIL_ADDRESS>(M.
Yuan), dzheng@hubu.edu.cn(D. Zheng), ypwang@aliyun.com(Y. Wang). This work was
partially supported by the National Natural Science Foundation of China under
Grant Number 11971156.  and Yan-Ping Wang2

(1\. Hubei Key Laboratory of Applied Mathematics,
Faculty of Mathematics and Statistics, Hubei University, Wuhan 430062, China
2\. College of Mathematics and Statistics, Northwest Normal University,
Lanzhou 730070, China )

Abstract. In this paper, two-to-one mappings and involutions without any fixed
point on finite fields of even characteristic are investigated. First, we
characterize a closed relationship between them by implicit functions and
develop an AGW-like criterion for $2$-to-$1$ mappings. Using this criterion,
some new constructions of $2$-to-$1$ mappings are proposed and eight classes
of $2$-to-$1$ mappings of the form $(x^{2^{k}}+x+\delta)^{s}+cx$ are obtained.
Finally, a number of classes of involutions without any fixed point are
derived from the known $2$-to-$1$ mappings by the relation between them.

Keywords. Finite field, involution, two-to-one mapping, symbolic computation

##  1 Introduction

Let $q$ be a power of a prime $p$ and ${\mathbb{F}}_{q}$ be the finite field
with $q$ elements. A polynomial $f(x)\in{\mathbb{F}}_{q}[x]$ is called a
permutation polynomial if $f:c\mapsto f(c)$ from ${\mathbb{F}}_{q}$ to itself
is a bijection. In particular, $f$ is called an involution if the
compositional inverse of $f$ is itself. If involutions are used as part of a
block cipher, they are very suitable for use in devices with limited resources
since the implementation of the inverse does not require additional resources.
Involutions have been used in block ciphers such as AES [1], Khazad, Anubis
[4] and PRINCE [5]. Furthermore, to resist reflection cryptanalysis, the
involutions used in PRINCE-like ciphers should not have fixed points [6, 31].
The reference [9] first provided a systematic study of involutions over finite
field of even characteristic and recent results on involutions can be found in
[10, 9, 15, 28, 30, 43]. A polynomial $f(x)\in{\mathbb{F}}_{q}[x]$ is said to
be a two-to-one ($2$-to-$1$) mapping on ${\mathbb{F}}_{q}$ if the equation
$f(x)=a$ has either two or no solutions in ${\mathbb{F}}_{q}$ for any
$a\in{\mathbb{F}}_{q}$. Two-to-one mappings over finite fields are used in
design special important primitives in symmetric cryptography such as APN
functions [29, 34], bent functions [8], planar functions [11, 36] and good
linear codes [22] in coding theory. For example, Carlet and Mesnager
constructed new bent Boolean functions in bivariate representation with
$2$-to-$1$ mappings over finite fields of even characteristic [8]. In
addition, the hyperoval in finite geometry can be defined by o-polynomials,
which are closed related to 2-to-1 mappings. As far as we know, Charpin and
Kyureghyan in [7, 19] first obtained some $2$-to-$1$ mappings of the special
forms in their study of permutation polynomials by using linear translators.
Very recently, Mesnager and Qu in [27] first systematically studied $2$-to-$1$
mappings over finite fields as a specific goal, then Li et al. [23] further
constructed some $2$-to-$1$ trinomials and quadrinomials over finite fields of
even characteristic. Almost all $2$-to-$1$ mappings over
${\mathbb{F}}_{2^{n}}$ in [27, 23] exist only when $n$ is odd.

In this paper, we first characterize a relationship between $2$-to-$1$
mappings and involutions over finite fields and show that the involutions
derived from $2$-to-$1$ mappings have no fixed points. Then, along the line of
work in [27], we propose another AGW-like criterion for constructing
$2$-to-$1$ mappings over ${\mathbb{F}}_{2^{n}}$. By application of this
criterion, some general constructions of $2$-to-$1$ mappings over
${\mathbb{F}}_{2^{n}}$ are obtained. In particular, we investigate the
$2$-to-$1$ property of polynomials over ${\mathbb{F}}_{2^{2m}}$ with the
following form

$(x^{2^{k}}+x+\delta)^{s}+cx,$ (1)

and obtain many new $2$-to-$1$ mappings of the form (1) and corresponding
involutions derived from them over ${\mathbb{F}}_{2^{2m}}$ by using the
proposed relation and the multivariate method introduced by Dobbertin [14].
Moreover, some involutions over ${\mathbb{F}}_{2^{2m+1}}$ are also derived
from known $2$-to-$1$ mappings over this finite field.

The remainder of this paper is organized as follows. In Section 2, we
introduce some basic concepts and related results. In Section 3, we
characterize a relationship between $2$-to-$1$ mappings and involutions
without any fixed point. In Section 4, we provide another AGW-like criterion
for constructing $2$-to-$1$ mappings over finite fields. In Section 5, many
$2$-to-$1$ mappings with the form (1) over ${\mathbb{F}}_{2^{2m}}$ are
obtained and the corresponding involutions are derived from them. In Section
6, many involutions without any fixed point over ${\mathbb{F}}_{2^{2m+1}}$ are
derived from known $2$-to-$1$ mappings over this finite field. Finally,
Section 7 concludes this paper.

##  2 Preliminaries

Let $q$ be a power of $2$, ${\mathbb{F}}_{q}$ the finite field with $q$
elements and ${\mathbb{F}}_{q}^{*}$ its multiplicative group. Let
${\mathbb{N}}$ denote the set of all positive integers. For $d\in{\mathbb{N}}$
with $d\,|\,(q-1)$, let $\mu_{d}$ denote the subgroup of
${\mathbb{F}}_{q}^{*}$ with order $d$ and
$\mu_{d}^{*}=\mu_{d}\setminus\\{1\\}$. For $k,\ell\in{\mathbb{N}}$ with
$\ell\,|\,k$, the trace function ${\rm Tr}^{k}_{\ell}(\cdot)$ is defined as

${\rm Tr}^{k}_{\ell}(x)=\sum_{i=0}^{k/\ell-1}x^{2^{\ell\cdot i}}.$

In particular, ${\rm Tr}^{k}_{1}(x)$ is called the absolute trace function
defined on ${\mathbb{F}}_{2^{k}}$, and it is denoted by ${\rm Tr}_{k}(x)$ for
short. A positive integer $s$ is called a Niho exponent with respect to the
finite field ${\mathbb{F}}_{2^{2m}}$ if $s\equiv 2^{j}\,\,({\rm
mod}\,\,2^{m}-1)$ for some $j\in{\mathbb{N}}$. Now, we give the definition of
2-to-1 mappings over any finite set.

###### Definition 2.1

[27] Let $A$ and $B$ be two finite sets, and let $f$ be a mapping from $A$ to
$B$. Then $f$ is called a 2-to-1 mapping if one of the following two cases
holds:

  1. (1)

If $\sharp A$ is even, then for any $b\in B$, it has either $2$ or $0$
preimages of $f$;

  2. (2)

If $\sharp A$ is odd, then for all but one $b\in B$, it has either $2$ or $0$
preimages of $f$, and the exception element has exactly one preimage.

Next, we recall the resultant of two polynomials over fields. Let
$f(x)=\sum_{i=0}^{n}a_{n-i}x^{i}$ and $g(x)=\sum_{i=0}^{m}b_{n-i}x^{i}$ be two
polynomials of positive degree over ${\mathbb{F}}_{q}$, where $a_{0}\neq 0$
and $b_{0}\neq 0$. The Sylvester resultant of $f(x)$ and $g(x)$, denoted by
$Res(f,g,x)$, is the following determinant:

$\displaystyle
Res(f,g,x)=\begin{array}[]{|cccccccc|}a_{0}&a_{1}&\cdots&a_{n}&0&&\cdots&0\\\
0&a_{0}&a_{1}&\cdots&a_{n}&0&\cdots&0\\\ \vdots&&&&&&&\vdots\\\
0&\cdots&0&a_{0}&a_{1}&&\cdots&a_{n}\\\
b_{0}&b_{1}&\cdots&&b_{m}&0&\cdots&0\\\
0&b_{0}&b_{1}&\cdots&&b_{m}&\cdots&0\\\ \vdots&&&&&&&\vdots\\\
0&\cdots&0&b_{0}&b_{1}&&\cdots&b_{m}\\\ \end{array}$
$\displaystyle\begin{array}[]{l}\left.\rule{0.0pt}{28.45274pt}\right\\}$m$~{}\text{rows}\\\
\\\ \left.\rule{0.0pt}{28.45274pt}\right\\}$n$~{}\text{rows}\end{array}$

There are two polynomials $A,B\in{\mathbb{F}}_{q}[x]$ such that
$Af+Bg=Res(f,g,x)$, and so $Res(f,g,x)=0$ if and only if $f(x)$ and $g(x)$
have a common divisor of positive degree. For two polynomials
$F(x,y),\,G(x,y)\in\mathbb{F}_{q}[x,y]$ of positive degree in $y$, the
resultant $Res(F,G,y)$ with respect to $y$ is a polynomial in $x$, and is in
the elimination ideal $\langle F,G\rangle\cap{\mathbb{F}}_{q}[x]$. So,
$Res(F,G,y)$ vanishes at any common solution of $F=G=0$. For more information
on resultants, the reader can refer to [12].

For later usage we recall some results on the number of the solutions of
quadratic and cubic equations over ${\mathbb{F}}_{2^{n}}$.

###### Lemma 2.2

[26] Let $a,b\in{\mathbb{F}}_{2^{n}}$ and $a\neq 0$. Then the quadratic
equation $x^{2}+ax+b=0$ has solutions in ${\mathbb{F}}_{2^{n}}$ if and only if
${\rm Tr}_{n}(\frac{b}{a^{2}})=0$.

###### Lemma 2.3

[3] Let $a,b\in{\mathbb{F}}_{2^{n}}$ and $b\neq 0$. Then the cubic equation
$x^{3}+ax+b=0$ has a unique solution in ${\mathbb{F}}_{2^{n}}$ if and only if
${\rm Tr}_{n}(\frac{a^{3}}{b^{2}}+1)\neq 0$.

###### Lemma 2.4

[27] Let $f(x)=x^{4}+a_{3}x^{3}+a_{2}x^{2}+a_{1}x\in{\mathbb{F}}_{2^{n}}[x]$.
Then $f(x)$ is $2$-to-$1$ over ${\mathbb{F}}_{2^{n}}$ if and only if one of
the following holds:

  * •

$a_{3}=a_{1}=0$, $a_{2}\neq 0$;

  * •

$a_{3}=0$, $a_{1}\neq 0$ and ${\rm
Tr}_{n}\left(a_{2}^{3}/a_{1}^{2}+1\right)\neq 0$;

  * •

$n$ is odd, $a_{3}\neq 0$ and $a_{2}^{2}=a_{1}a_{3}$.

##  3 A relation between $2$-to-$1$ mappings and involutions

In this section, a closed relationship between $2$-to-$1$ mappings and
involutions over finite fields is investigated. This relation is useful for us
to obtain involutions without fixed points from 2-to-1 mappings over finite
fields. We also study the relation between two involutions derived from two
$2$-to-$1$ mappings which are differed by a bijection.

###### Theorem 3.1

Let $D$ be a subset of ${\mathbb{F}}_{q}$ with even cardinality and
$\mathcal{D}=\\{(x,y)\in D^{2}|\,\,\,\,x\neq y\\}$. Let $f$ be a $2$-to-$1$
mapping on $D$. Then the equation $G(x,y)=f(x)-f(y)=0$ on $\mathcal{D}$
determines an involution $y=\mathcal{I}_{f}(x)$ on $D$. Furthermore,
$y=\mathcal{I}_{f}(x)$ has no fixed point on $D$.

Proof. Since $f$ is a $2$-to-$1$ mapping on $D$, for any $x\in D$, there
exists a unique $y\in D$ with $y\neq x$ satisfying $G(x,y):=f(x)-f(y)=0$, that
is, the equation $G(x,y)=0$ on $\mathcal{D}$ defines a mapping
$\mathcal{I}_{f}:x\rightarrow y$ from $D$ to $D$. Since $D$ is a finite set,
by Lagrange’s interpolation formula the expression of this mapping can be
represented as follows, $\mathcal{I}_{f}(x)=\sum_{a\in
D}\mathcal{I}_{f}(a)(1+(x+a)^{q-1})$. Moreover, for any $a\in D$, there exists
$b\in D$ with $b\neq a$ such that $G(b,a)=0$ and $G(a,b)=0$, simultaneously.
So $\mathcal{I}_{f}(a)=b$ and $\mathcal{I}_{f}(b)=a$. That is to say,
$y=\mathcal{I}_{f}(x)$ is an involution on $D$ without any fixed point. $\Box$

###### Remark 3.2

We call $\mathcal{I}_{f}(x)$ the involution derived from a $2$-to-$1$ mapping
$f$ on $D$. The following are two examples.

(1) Let $L(x)$ be a linearized $2$-to-$1$ mapping on ${\mathbb{F}}_{2^{n}}$
and $\alpha\in{\mathbb{F}}_{2^{n}}^{*}$ be a root of $L(x)$. For any
$x\in{\mathbb{F}}_{2^{n}}$, the equation $G(x,y)=L(x)+L(y)=L(x+y)=0$ has two
solutions $y=x$ and $y=x+\alpha$, and so the involution derived from $L(x)$ is
$\mathcal{I}_{L}(x)=x+\alpha$.

(2) For any APN function $F(x)$ on ${\mathbb{F}}_{2^{n}}$, the derivative
$D_{a}F(x)=F(x)+F(x+a)$ is a $2$-to-$1$ mapping on ${\mathbb{F}}_{2^{n}}$ for
any $a\in{\mathbb{F}}_{2^{n}}^{*}$. Analysis similar to that in (1) shows that
the involution derived from $D_{a}F(x)$ is $\mathcal{I}_{D_{a}F}(x)=x+a$.

Let $D$ and $S$ be two finite sets with the same even cardinality, and let $f$
be a $2$-to-$1$ mapping on $D$ and $p$ be a bijection from $S$ to $D$. It is
easy to see that $y=\mathcal{I}_{f}(x)$ is the unique solution of the equation
$f(x)-f(y)=0$ in $\\{(x,y)\in D^{2}|\,\,x\neq y\\}$ if and only if
$y=p^{-1}\circ\mathcal{I}_{f}\circ p(x)$ is the unique solution of the
equation $f\circ p(x)-f\circ p(y)=0$ in $\\{(x,y)\in S^{2}|\,\,x\neq y\\}$.
So, we have the following proposition.

###### Proposition 3.3

Let $D$ and $S$ be two subsets of ${\mathbb{F}}_{q}$ with the same even
cardinality. Let $f$ be a $2$-to-$1$ mapping on $D$ and $p$ be a bijection
from $S$ to $D$. Then the involution derived from $f$ on $D$ is
$\mathcal{I}_{f}$ if and only if the involution derived from $f\circ p$ on $S$
is $\mathcal{I}_{f\circ p}=p^{-1}\circ\mathcal{I}_{f}\circ p$.

Let $f$ be a $2$-to-$1$ mapping, and $p$ be a injection over ${\rm Im}(f)$. We
have the following proposition about the $2$-to-$1$ mappings $p\circ f$ and
$f$.

###### Proposition 3.4

Let $A,B,C$ be three finite sets with $\sharp A=2\sharp B=2\sharp C$, $f$ be a
$2$-to-$1$ mappings from $A$ to $B$, and $\bar{f}$ be a $2$-to-$1$ mapping
from $A$ to $C$. Then the involutions derived from $f$ and $\bar{f}$
respectively both are $\mathcal{I}$ if and only if there exists a bijection
$p$ from $B$ to $C$ such that $\bar{f}=p\circ f$.

Proof. The sufficiency holds since the equations $f(x)-f(y)=0$ and $p\circ
f(x)-p\circ f(y)=0$ have the same roots in $\\{(x,y)\in A^{2}|x\neq y\\}$.

Next, we prove the necessity. Assume that the involutions derived from $f$ and
$\bar{f}$ respectively both are $\mathcal{I}$. Since $f$ is a $2$-to-$1$
mapping over $A$, we have $A=\cup_{b\in B}A_{b}$, where $A_{b}=\\{x\in
A|f(x)=b\\}$ and $\sharp A_{b}=2$. Pick one element from each $A_{b}$ for
$b\in B$ to form a set $\bar{A}$. Let $f_{\bar{A}}$ and $\bar{f}_{\bar{A}}$
denote the mappings of $f$ and $\bar{f}$ restricted on $\bar{A}$,
respectively. By the definition of $\bar{A}$, one can verify that
$f_{\bar{A}}$ and $\bar{f}_{\bar{A}}$ are bijective from $\bar{A}$ to $B$ and
$C$, respectively, and $\mathcal{I}(\bar{A})=A\setminus\bar{A}$. Similarly,
$f$ and $\bar{f}$ are also bijective from $A\setminus\bar{A}$ to $B$ and $C$,
respectively. Hence, $f$ and $\bar{f}$ can be rewritten as

$f(x)=\left\\{\begin{aligned} &f_{\bar{A}}(x),&&x\in\bar{A};\\\
&f_{\bar{A}}(\mathcal{I}(x)),&&x\in
A\setminus\bar{A}\end{aligned}\right.{\,\,\text{a}nd\,\,}\bar{f}(x)=\left\\{\begin{aligned}
&\bar{f}_{\bar{A}}(x),&&x\in\bar{A};\\\
&\bar{f}_{\bar{A}}(\mathcal{I}(x)),&&x\in
A\setminus\bar{A}.\end{aligned}\right.$

Thus, there exists a bijection $p=\bar{f}_{\bar{A}}\circ f_{\bar{A}}^{-1}$
from $B$ to $C$ such that $\bar{f}=p\circ f$. $\Box$

For a given involution $\mathcal{I}$ without fixed points over
${\mathbb{F}}_{2^{n}}$, we have
${\mathbb{F}}_{2^{n}}=\bigcup_{a\in{\mathbb{F}}_{2^{n}}}S_{a}$, where
$S_{a}=\\{a,\mathcal{I}(a)\\}$. Pick one element from each $S_{a}$ for
$a\in{\mathbb{F}}_{2^{n}}$ to form a new set $S$. It is easy to see that

$f(x)=\left\\{\begin{aligned} &x,&&x\in S;\\\
&\mathcal{I}(x),&&x\in{\mathbb{F}}_{2^{n}}\setminus S\end{aligned}\right.$

is a $2$-to-$1$ mapping over ${\mathbb{F}}_{2^{n}}$ and the involution derived
from it is $\mathcal{I}$. By Proposition 3.4, all $2$-to-$1$ mappings which
derive the involution $\mathcal{I}$ can be obtained by composing $f$ with a
bijection on Im$(f)$. Note that there are $\binom{2^{n}}{2^{n-1}}$ subsets in
${\mathbb{F}}_{2^{n}}$ with cardinality $2^{n-1}$. For each such subset $T$,
there are $2^{n-1}!$ bijections from $S$ to $T$. So, we have the following
result.

###### Corollary 3.5

Let $n\in{\mathbb{N}}$, for a given involution $\mathcal{I}$ without fixed
points on ${\mathbb{F}}_{2^{n}}$, there are $\frac{2^{n}!}{2^{n-1}!}$ distinct
$2$-to-$1$ mappings from which $\mathcal{I}$ can be derived.

##  4 AGW-like criterion for $2$-to-$1$ mappings

The AGW criterion [2] transforms the problem of proving the permutation
property of a polynomial on a finite set $A$ into showing that another
polynomial is a permutation on a subset of $A$. This technique facilitates the
proof and computer experiments of finding new permutation polynomials.
Recently, this method has been generalized to construct $2$-to-$1$ mappings
over ${\mathbb{F}}_{2^{n}}$ by Mesnager and Qu as follows.

###### Lemma 4.1

[27] Let $A$, $S$ and $\bar{S}$ be finite sets with $\sharp S=\sharp\bar{S}$.
Let $f,\bar{f},\lambda,\bar{\lambda}$ be four mappings defined as the
following diagram such that $\bar{\lambda}\circ f=\bar{f}\circ\lambda$. If
$\bar{f}$ is a bijection from $S$ to $\bar{S}$, $f|_{\lambda^{-1}(s)}$ is
$2$-to-$1$ for any $s\in S$, and there is at most one $s\in S$ such that
$\sharp\lambda^{-1}(s)$ is odd, then $f$ is a $2$-to-$1$ mapping over $A$.

$\begin{CD}A@>{f}>{}>A\\\ @V{}V{\lambda}V@V{}V{\bar{\lambda}}V\\\
S@>{\bar{f}}>{}>\bar{S}\end{CD}$

In Remark 7 of [27], authors also wanted to derive $2$-to-$1$ mappings $f$ on
$A$ by the assumption that $\bar{f}$ was a $2$-to-$1$ mapping on $S$ and
$f|_{\lambda^{-1}(s)}$ was injective. But they found that it seems not easy to
add a condition such that $f$ was a $2$-to-$1$ mapping on $A$. Here, we find a
restriction on $f$ and then propose another AGW-like criterion for
constructions of new $2$-to-$1$ mappings.

###### Proposition 4.2

Let $A,\bar{A},S,\bar{S}$ be four finite sets and
$f,\bar{f},\lambda,\bar{\lambda}$ be four surjective mappings defined as the
following diagram such that $\bar{\lambda}\circ f=\bar{f}\circ\lambda$. Then
$f$ is a $2$-to-$1$ mapping on $A$ if the following two conditions hold:

  1. (1)

$\bar{f}$ is a $2$-to-$1$ mapping from $S$ to $\bar{S}$;

  2. (2)

$\sharp S$ is even, and $f$ is bijective from $\lambda^{-1}(s)=\\{x\in
A|\lambda(x)=s\\}$ to
$\bar{\lambda}^{-1}(\bar{f}(s))=\\{x\in\bar{A}|\bar{\lambda}(x)=\bar{f}(s)\\}$
for any $s\in S$.

$\begin{CD}A@>{f}>{}>\bar{A}\\\ @V{}V{\lambda}V@V{}V{\bar{\lambda}}V\\\
S@>{\bar{f}}>{}>\bar{S}\end{CD}$

Proof. For any $b\in\bar{A}$, let $\bar{s}=\bar{\lambda}(b)$. Since $f$ is
surjective, there exist some $a\in A$ such that $f(a)=b$. From above diagram
we have $\bar{\lambda}\circ f(a)=\bar{f}\circ\lambda(a)=\bar{s}$. Since
$\bar{f}$ is a $2$-to-$1$ mapping from $S$ to $\bar{S}$, there exist exactly
two elements $s_{1},s_{2}$ in $S$ such that
$\bar{f}(s_{1})=\bar{f}(s_{2})=\bar{s}$. Hence, we must have
$a\in\lambda^{-1}(s_{1})$ or $\lambda^{-1}(s_{2})$. Note that $f$ is bijective
from $\lambda^{-1}(s_{i})$ to $\bar{\lambda}^{-1}(\bar{s})$, where $i=1,2$.
Thus, $b$ has exactly two preimages $a_{1}\in\lambda^{-1}(s_{1})$ and
$a_{2}\in\lambda^{-1}(s_{2})$. $\Box$

By applying Proposition 4.2, we can propose some general constructions of
$2$-to-$1$ mappings as follows.

###### Theorem 4.3

Let $q=2^{k}$ and $k,n\in{\mathbb{N}}$. Let
$g,\phi,\psi,\bar{\psi},h\in{\mathbb{F}}_{q^{n}}[x]$ be such that $\phi$ and
$\psi$ are $2$-linearized, $\bar{\psi}$ is $q$-linearized,
$\phi\circ\psi=\bar{\psi}\circ\phi$, and
$h(\psi({\mathbb{F}}_{q^{n}}))\subset{\mathbb{F}}_{q}^{*}$. Set
$f=h(\psi(x))\phi(x)+g(\psi(x))$. Then $f$ is a $2$-to-$1$ mapping over
${\mathbb{F}}_{q^{n}}$, if the following two conditions hold:

  1. (1)

$\bar{f}=h(x)\phi(x)+\bar{\psi}\circ g(x)$ is a $2$-to-$1$ mapping over
$\psi({\mathbb{F}}_{q^{n}})$;

  2. (2)

$ker(\phi)\cap ker(\psi)=\\{0\\}$ and ${\rm dim\,\,}ker(\psi)={\rm
dim\,\,}ker(\bar{\psi})$.

Proof. For $x\in{\mathbb{F}}_{q^{n}}$, we have

$\displaystyle\bar{\psi}\circ f(x)$
$\displaystyle=\bar{\psi}(h(\psi(x))\phi(x))+\bar{\psi}(g(\psi(x)))$
$\displaystyle=h(\psi(x))\phi(\psi(x))+\bar{\psi}(g(\psi(x)))$
$\displaystyle=\bar{f}\circ\psi(x).$

The second equality holds since
$h(\psi({\mathbb{F}}_{q^{n}}))\subseteq{\mathbb{F}}_{q}^{*}$, $\bar{\psi}$ is
$q$-linearized and $\phi\circ\psi=\bar{\psi}\circ\phi$. So, the following
diagram is commutative.

$\begin{CD}{\mathbb{F}}_{q^{n}}@>{f}>{}>{\mathbb{F}}_{q^{n}}\\\
@V{}V{\psi}V@V{}V{\bar{\psi}}V\\\
\psi({\mathbb{F}}_{q^{n}})@>{\bar{f}}>{}>\bar{\psi}({\mathbb{F}}_{q^{n}})\end{CD}$

This shows that $f(\psi^{-1}(s))\subseteq\bar{\psi}^{-1}(\bar{f}(s))$ for any
$s\in\psi({\mathbb{F}}_{q^{n}})$.

By Proposition 4.2, in the following we only need to show that $f$ is
bijective from $\psi^{-1}(s)$ to $\bar{\psi}^{-1}(\bar{f}(s))$ for any
$s\in\psi({\mathbb{F}}_{q^{n}})$. For some $a\neq b\in\psi^{-1}(s)$, assume
that $f(a)=f(b)$, then $h(s)\phi(a-b)=0$. Note that
$h(\psi({\mathbb{F}}_{q^{n}}))\subset{\mathbb{F}}_{q}^{*}$. We have $a-b\in
ker(\phi)\cap ker(\bar{\psi})$, and so $a=b$. This is a contradiction. Since
${\rm dim\,\,}ker(\psi)={\rm dim\,\,}ker(\bar{\psi})$, $f$ is surjective from
$\psi^{-1}(s)$ to $\bar{\psi}^{-1}(\bar{f}(s))$. This completes the proof.
$\Box$

Let $\psi(x)=\bar{\psi}(x)={\rm Tr}_{m}^{n}(x)$ and $\phi(x)=x^{2}+x$. An
explicit construction of $2$-to-$1$ mapping is given as follows.

###### Corollary 4.4

Let $m,n\in{\mathbb{N}}$ with $n/m$ odd. Let $g(x)\in{\mathbb{F}}_{2^{n}}[x]$
and $h(x)=x^{2}+x+a\in{\mathbb{F}}_{2^{m}}[x]$ with ${\rm Tr}_{m}(a)\neq 0$.
Then $f(x)=(x^{2}+x)h({\rm Tr}^{n}_{m}(x))+g({\rm
Tr}_{m}^{n}(x))^{2^{m}}+g({\rm Tr}_{m}^{n}(x))$ is a $2$-to-$1$ mapping over
${\mathbb{F}}_{2^{n}}$.

Proof. Let $\psi(x)=\bar{\psi}(x)={\rm Tr}_{m}^{n}(x)$, $\phi(x)=x^{2}+x$ and
$\bar{f}(x)=h(x)\phi(x)$. Since ${\rm Tr}_{m}(a)\neq 0$, $h(x)$ has no root in
${\mathbb{F}}_{2^{m}}$ by Lemma 2.2. Since $n/m$ is odd and ${\rm
Tr}^{n}_{m}(1)\neq 0$, we see that $ker(x^{2}+x)\cap ker({\rm
Tr}_{m}^{n}(x))=\\{0\\}$. Since ${\rm Tr}_{m}(a)\neq 0$ , by Lemma 2.4,
$\bar{f}$ is $2$-to-$1$ over ${\mathbb{F}}_{2^{m}}$. By Theorem 4.3,
$f(x)=(x^{2}+x)h({\rm Tr}^{n}_{m}(x))+g({\rm Tr}_{m}^{n}(x))^{2^{m}}+g({\rm
Tr}_{m}^{n}(x))$ is a $2$-to-$1$ mapping over ${\mathbb{F}}_{2^{n}}$. $\Box$

###### Theorem 4.5

Let $k,n\in{\mathbb{N}}$ and $q=2^{k}$. Let
$L_{1}(x),L_{2}(x),L_{3}(x)\in{\mathbb{F}}_{q}[x]$ be $q$-linearized, and
$g(x)\in{\mathbb{F}}_{q^{n}}[x]$ be such that
$g(L_{3}({\mathbb{F}}_{q^{n}}))\subseteq{\mathbb{F}}_{q}$. Then
$f=L_{1}(x)+L_{2}(x)g(L_{3}(x))$ is a $2$-to-$1$ mapping over
${\mathbb{F}}_{q^{n}}$ if the following two conditions hold:

  1. (1)

$\bar{f}(x)=L_{1}(x)+L_{3}(x)g(x)$ is a $2$-to-$1$ mapping over
$\psi({\mathbb{F}}_{q^{n}})$;

  2. (2)

$ker(F_{y})\cap ker(L_{3})=\\{0\\}$ for any $y\in
L_{3}({\mathbb{F}}_{q^{n}})$, where $F_{y}(x)=L_{1}(x)+L_{2}(x)g(y)$.

Proof. It is easy to verify that $L_{3}\circ f=\bar{f}\circ L_{3}$, i.e., the
following diagram is commutative,

$\begin{CD}{\mathbb{F}}_{q^{n}}@>{f}>{}>{\mathbb{F}}_{q^{n}}\\\
@V{}V{L_{3}}V@V{}V{L_{3}}V\\\
L_{3}({{\mathbb{F}}_{q^{n}}})@>{\bar{f}}>{}>L_{3}({\mathbb{F}}_{q^{n}})\end{CD}$

Then we see that $f(L_{3}^{-1}(y))\subseteq L_{3}^{-1}(\bar{f}(y))$ for any
$y\in L_{3}^{-1}(y)$.

We claim that $\bar{f}$ is bijective from $L_{3}^{-1}(y)$ to
$L_{3}^{-1}(\bar{f}(y))$ for any $y\in L_{3}({\mathbb{F}}_{q^{n}})$, if
$ker(F_{y})\cap ker(L_{3})=\\{0\\}$ for all $y\in
L_{3}({\mathbb{F}}_{q^{n}})$. Otherwise, for some $a,b\in L_{3}^{-1}(y)$ with
$a\neq b$, we have $f(a)=f(b)$, i.e., $F_{y}(a)=F_{y}(b)$. So $a-b\in
ker(F_{y})\cap ker(L_{3})$, that is, $a=b$, which is a contradiction. The
proof is completed by Proposition 4.2. $\Box$

Let $L(x)=x^{2}$, $L_{2}(x)=x$ and $L_{3}(x)={\rm Tr}^{kn}_{k}(x)$. An more
explicit construction of $2$-to-$1$ mappings is provided as follows.

###### Proposition 4.6

Let $q=2^{k}$, $k\in{\mathbb{N}}$ and $n$ be odd. Let
$g(x)=x^{3}+bx+a\in{\mathbb{F}}_{q}[x]$ with ${\rm
Tr}_{k}(\frac{(b+1)^{3}}{a^{2}}+1)\neq 0$. Then $f=x^{2}+xg({\rm
Tr}^{kn}_{k}(x))$ is a $2$-to-$1$ mapping over ${\mathbb{F}}_{q^{n}}$.

Proof. It is easy to verify that $\bar{f}(x)=x^{2}+xg(x)=x^{4}+(b+1)x^{2}+ax$
is $2$-to-$1$ over ${\mathbb{F}}_{2^{k}}$ by Lemma 2.4. For any
$y\in{\mathbb{F}}_{2^{k}}$, if there exists $z\in{\mathbb{F}}_{q^{n}}^{*}$
such that $F_{y}(z)=z^{2}+zg(y)=0$ and ${\rm Tr}^{kn}_{k}(z)=0$, then we have
$z=g(y)$, and ${\rm Tr}^{kn}_{k}(g(y))=ng(y)=0$, which is contradictory to
that $n$ is odd, that is to say, $ker(F_{y})\cap ker({\rm
Tr}^{kn}_{k}(x))=\\{0\\}$. This completes the proof. $\Box$

By a similar analysis in Theorems 4.3 and 4.5, we have the following theorem.

###### Theorem 4.7

Let $n,k,\ell$ be positive integers with $k<n$, $\ell=\gcd(n,k)$ and
$\delta\in{\mathbb{F}}_{2^{n}}$. Let $S=\\{x^{2^{k}}+x+\delta\mid
x\in{\mathbb{F}}_{2^{n}}\\}$, $g(x)\in{\mathbb{F}}_{2^{n}}[x]$,
$L(x)\in{\mathbb{F}}_{2^{\ell}}[x]$ be $q$-linearized and
$h(x)=g(x)^{2^{k}}+g(x)+L(x)$. Then $f(x)=g(x^{2^{k}}+x+\delta)+L(x)$ is a
$2$-to-$1$ mapping on ${\mathbb{F}}_{2^{n}}$ if the following two conditions
hold:

  1. (1)

$h$ is a $2$-to-$1$ mapping on $S$;

  2. (2)

$ker(L)$ $\cap\,\,ker$$(x^{2^{k}}+x)=\\{0\\}$.

##  5 Two-to-one mappings of the form $(x^{2^{k}}+x+\delta)^{s}+cx$ and the
involutions derived from them

In this section, we study the $2$-to-$1$ property of the polynomials
introduced in Theorem 4.7 with a more specific shape of (1), and investigate
their derived involutions over ${\mathbb{F}}_{2^{2m}}$. In fact, the
permutation property of the polynomials of the form (1) was firstly studied by
Helleseth and Zinoviev [17] to derive new Kloosterman sums identities over
${\mathbb{F}}_{2^{n}}$, then the permutation of this type of polynomials is
specially studied by Ding and Yuan [37]. Subsequently, many permutation
polynomials of the form (1) or its generalization have been obtained in the
past two decades. The reader is referred to [38, 39, 42, 40, 33] and the
references therein for information. The following is a necessary and
sufficient condition for the polynomials of the form (1) being $2$-to-$1$
mappings.

###### Theorem 5.1

Let $n,k,\ell$ be positive integers with $k<n$, $\ell=\gcd(n,k)$ and
$\delta\in{\mathbb{F}}_{2^{n}}$. Let $S=\\{x^{2^{k}}+x+\delta\mid
x\in{\mathbb{F}}_{2^{n}}\\}$ and
$h(x)=x^{2^{k}s}+x^{s}+cx\in{\mathbb{F}}_{2^{\ell}}[x]$. Then
$f(x)=(x^{2^{k}}+x+\delta)^{s}+cx$ is a $2$-to-$1$ mapping on
${\mathbb{F}}_{2^{n}}$ if and only if $h(x)$ is a $2$-to-$1$ mapping on $S$.

Proof. The sufficiency is derived directly from Theorem 4.7. Next, we show the
necessity. Let $\lambda(x)=x^{2^{k}}+x+\delta$ and
$\bar{\lambda}(x)=x^{2^{k}}+x+\delta$. It is easy to show that the following
diagram is commutative.

$\begin{CD}{\mathbb{F}}_{2^{n}}@>{f}>{}>{\mathbb{F}}_{2^{n}}\\\
@V{}V{\lambda}V@V{}V{\bar{\lambda}}V\\\ S@>{h}>{}>h(S)\end{CD}$

Let $\alpha\in h(S)$, $h^{-1}(\alpha)$ and $\bar{\lambda}^{-1}(\alpha)$ denote
the set of preimages of $\alpha$ under the mappings $h$ and $\bar{\lambda}$,
respectively. Let $\beta\in h^{-1}(\alpha)$ and $\lambda^{-1}(\beta)$ denote
the set of preimages of $\beta$ under the mapping $\lambda$. The mapping $f$
is linear when it is restricted to $\lambda^{-1}(\beta)$, i.e.,
$f|_{\lambda^{-1}(\beta)}(x)=\beta^{s}+cx$. So, $f$ is a bijection from
$\lambda^{-1}(\beta)$ to $\bar{\lambda}^{-1}(\alpha)$ since above diagram is
commutative. Since $f$ is a 2-to-1 mapping, for any $\alpha\in h(S)$ it has
exactly two preimages under the mapping $h$. $\Box$

###### Proposition 5.2

Follow the notation introduced in Theorem 5.1. Let $g(x)=x^{s}$. If the
involution derived from $h$ on $S$ is $\mathcal{I}_{h}$, then the involution
derived from $f$ on ${\mathbb{F}}_{2^{n}}$ is
$\mathcal{I}_{f}(x)=c^{-1}(g\circ\mathcal{I}_{h}\circ\lambda(x)+g\circ\lambda(x))+x$.

Proof. Since $f$ is a $2$-to-$1$ mapping on ${\mathbb{F}}_{2^{n}}$, for
$x\in{\mathbb{F}}_{2^{n}}$, there exists a unique $y\in{\mathbb{F}}_{2^{n}}$
with $y\neq x$ such that

$f(x)+f(y)=g(x^{2^{k}}+x+\delta)+cx+g(y^{2^{k}}+y+\delta)+cy=0.$ (3)

Let $\lambda(x)=x^{2^{k}}+x+\delta$. Taking the both sides of ${\rm
Eq.}(\ref{eq:roots})$ to the power of $2^{m}$, then adding it to ${\rm
Eq.}(\ref{eq:roots})$, we have

$h(\lambda(x))+h(\lambda(y))=0.$

Since the involution derived from $h$ on $S$ is $\mathcal{I}_{h}$, we must
have $\lambda(y)=\mathcal{I}_{h}\circ\lambda(x)$ or $\lambda(x)=\lambda(y)$.
If $\lambda(x)=\lambda(y)$, together with Eq.(3), we then have $y=x$, which is
a contradiction. Substituting $\lambda(y)=\mathcal{I}_{h}\circ\lambda(x)$ into
Eq.(3), we obtain
$y=c^{-1}(g\circ\mathcal{I}_{h}\circ\lambda(x)+g\circ\lambda(x))+x$. $\Box$

###  5.1 Several classes of $2$-to-$1$ mappings and corresponding involutions
over ${\mathbb{F}}_{2^{2m}}$

In this subsection, by application of Theorem 5.1 and Proposition 5.2 we
construct several classes of $2$-to-$1$ mappings of the form
$f(x)=(x^{2^{k}}+x+\delta)^{s}+cx$ and obtain their corresponding involutions
over ${\mathbb{F}}_{2^{2m}}$.

###### Theorem 5.3

Let $m\in{\mathbb{N}}$ be even and $\delta\in{\mathbb{F}}_{2^{2m}}$ with ${\rm
Tr}_{2m}(\delta)=1$. Then $f(x)=(x^{2}+x+\delta)^{2^{2m-2}+2^{m-2}}+x$ is a
$2$-to-$1$ mapping on ${\mathbb{F}}_{2^{2m}}$.

Proof. It is easy to see that $p(x)=x^{4}$ is a permutation on
$S=\\{x^{2}+x+\delta\mid x\in{\mathbb{F}}_{2^{2m}}\\}$. To show that $f(x)$ is
2-to-1 on ${\mathbb{F}}_{2^{2m}}$, by Theorem 5.1, it is sufficient to show
that $\bar{h}(x)=h(x^{4})=x^{2^{m+1}+2}+x^{2^{m}+1}+x^{4}$ is a $2$-to-$1$
mapping on $S$, which can be rewritten as
$\\{x\in{\mathbb{F}}_{2^{2m}}\mid{\rm Tr}_{2m}(x)=1\\}$. To this end, we only
need to show that for any $x\in S$, the equation

$H(y):=\bar{h}(y+x)+\bar{h}(x)=0$ (4)

has exactly two distinct solutions in
$S_{0}=\\{z\in{\mathbb{F}}_{2^{2m}}\mid{\rm Tr}_{2m}(z)=0\\}$. Let
$Y=y^{2^{m}}$ and $X=x^{2^{m}}$. Then Eq.(4) is reduced to

$H(y)={x}^{2}{Y}^{2}+{X}^{2}{y}^{2}+{Y}^{4}+{y}^{2}{Y}^{2}+xY+Xy+Yy=0.$ (5)

Raising both sides of ${\rm Eq.}(\ref{eq:thm2:2})$ to the power of $2^{m}$ and
combining $y=Y^{2^{m}}$ and $x=X^{2^{m}}$, we have

${X}^{2}{y}^{2}+{x}^{2}{Y}^{2}+{y}^{4}+{Y}^{2}{y}^{2}+Xy+xY+yY=0.$ (6)

Adding Eq.(5) to Eq.(6), we obtain

$(y+Y)^{4}=0.$

So, $Y=y$, i.e., $y\in{\mathbb{F}}_{2^{m}}$. Substituting it into Eq.(5), we
get

$(x^{2}+X^{2}+1)y^{2}+(x+X)y=0.$ (7)

We claim that $x+X\neq 0$ and $x+X+1\neq 0$. Otherwise, ${\rm Tr}_{2m}(x)={\rm
Tr}_{m}(x+X)={\rm Tr}_{m}(x+X+1)=0$ since $m$ is even. This contradicts to
that ${\rm Tr}_{2m}(x)=1$ since $x\in S$. Thus, Eq.(7) has exactly two
solutions. Moreover,
$y=\frac{x+X}{x^{2}+X^{2}+1}\in{\mathbb{F}}_{2^{m}}^{*}\subseteq S_{0}$. This
completes the proof. $\Box$

###### Corollary 5.4

Let $m\in{\mathbb{N}}$ be even and $\delta\in{\mathbb{F}}_{2^{2m}}$ with ${\rm
Tr}_{2m}(\delta)=1$. Then
$\mathcal{I}(x)=x+1+\frac{1}{x^{2^{m+1}}+x^{2^{m}}+x^{2}+x+\delta+\delta^{2^{m}}+1}$
is an involution without any fixed point on ${\mathbb{F}}_{2^{2m}}$.

Proof. From the proof of Theorem 5.3, we see that the involution derived from
$\bar{h}$ on $S$ is
$\mathcal{I}_{\bar{h}}(x)=x+\frac{x+x^{2^{m}}}{x^{2^{m+1}}+x^{2}+1}$. Since
$\bar{h}=h\circ p$ and $p(x)=x^{4}$ is linear over ${\mathbb{F}}_{2^{2m}}$, by
Proposition 3.3, the involution derived from $h$ on $S$ is

$\mathcal{I}_{h}(x)=\mathcal{I}_{\bar{h}\circ
p^{-1}}(x)=p\circ\mathcal{I}_{\bar{h}}\circ
p^{-1}(x)=\mathcal{I}_{\bar{h}}\circ p\circ
p^{-1}(x)=\mathcal{I}_{\bar{h}}(x).$

Let $g(x)=x^{2^{2m-2}+2^{m-2}}$, $\lambda(x)=x^{2}+x+\delta$ and $c=1$. By
Proposition 5.2, the involution derived from $f$ in Theorem 5.3 is

$\begin{split}\mathcal{I}_{f}(x)&=g\circ\mathcal{I}_{h}\circ\lambda(x)+g\circ\lambda(x)+x\\\
&=x+1+\frac{1}{x^{2^{m+1}}+x^{2^{m}}+x^{2}+x+\delta+\delta^{2^{m}}+1}.\end{split}$

This completes proof. $\Box$

###### Theorem 5.5

Let $m\in{\mathbb{N}}$ be even and $\delta\in{\mathbb{F}}_{2^{2m}}$ with ${\rm
Tr}_{2m}(\delta)=1$. Then $f(x)=(x^{2}+x+\delta)^{2^{m}+1}+x$ is a $2$-to-$1$
mapping on ${\mathbb{F}}_{2^{2m}}$.

Proof. To show that $f(x)$ is a $2$-to-$1$ mapping on ${\mathbb{F}}_{2^{2m}}$,
by Theorem 5.1, it is sufficient to prove $h(x)=x^{2^{m+1}+2}+x^{2^{m}+1}+x$
is a $2$-to-$1$ mapping on $S=\\{x\in{\mathbb{F}}_{2^{2m}}\mid{\rm
Tr}_{2m}(x)=1\\}$. To this end, we only need to show that for any $x\in S$,
the equation

$\begin{split}H(y):=&h(y+x)+h(x)=0\\\ \end{split}$ (8)

has exactly two distinct solutions in
$S_{0}=\\{x\in{\mathbb{F}}_{2^{2m}}\mid{\rm Tr}_{2m}(x)=0\\}$. Let
$Y=y^{2^{m}}$ and $X=x^{2^{m}}$. Then Eq.(8) becomes

$y^{2}Y^{2}+x^{2}Y^{2}+X^{2}y^{2}+xY+Xy+yY+y=0.$ (9)

Raising both sides of Eq.(9) to the power of $2^{m}$ and combining
$y=Y^{2^{m}}$ and $x=X^{2^{m}}$, we have

$y^{2}Y^{2}+x^{2}Y^{2}+X^{2}y^{2}+xY+Xy+yY+Y=0.$ (10)

Then adding Eq.(9) to Eq.(10) we get $Y=y$, i.e., $y\in{\mathbb{F}}_{2^{m}}$.
Substituting it into Eq.(9), we obtain

$y^{4}+(x^{2}+X^{2}+1)y^{2}+(x+X+1)y=0.$ (11)

It is clear that $y=0$ is a solution of Eq.(11). Next, we show that

$y^{3}+(x^{2}+X^{2}+1)y+(x+X+1)=0$ (12)

has a unique root in ${\mathbb{F}}_{2^{m}}^{*}$, which is a subset of $S_{0}$.

We claim that $x+X+1\neq 0$. Otherwise, ${\rm Tr}_{2m}(x)={\rm
Tr}_{m}(x+X+1)=0$ since $m$ is even, which contradicts to that ${\rm
Tr}_{2m}(x)=1$ since $x\in S$. According to Lemma 2.3, Eq.(11) has exactly one
root in ${\mathbb{F}}_{2^{m}}^{*}$ since ${\rm
Tr}_{m}((x^{2}+X^{2}+1)^{2}+1)={\rm Tr}_{m}(x+X)={\rm Tr}_{2m}(x)=1$. $\Box$

By a similar argument as above, we have the following theorem.

###### Theorem 5.6

Let $m\in{\mathbb{N}}$ be even, and $\delta\in{\mathbb{F}}_{2^{2m}}$ with
${\rm Tr}_{2m}(\delta)=1$. Then $f(x)=(x^{2}+x+\delta)^{2^{2m-1}+2^{m-1}}+x$
is a $2$-to-$1$ mapping on ${\mathbb{F}}_{2^{2m}}$.

###### Remark 5.7

Since the explicit expression of the involution derived from $h$ on $S$ is not
clear, we can’t obtain the explicit expression of the involutions derived from
the $2$-to-$1$ mappings in Theorems 5.5 and 5.6.

###### Theorem 5.8

Let $m,i\in{\mathbb{N}}$ with ${\rm gcd}(m,i)=1$ and
$\delta\in{\mathbb{F}}_{2^{2m}}$, $c\in{\mathbb{F}}_{2^{m}}^{*}$ with ${\rm
Tr}_{m}^{2m}(\delta^{2}+c^{2^{m-i}}\delta)\neq 0$. Then
$f(x)=(x^{2^{m}}+x+\delta)^{2^{i}+1}+cx$ is a $2$-to-$1$ mapping on
${\mathbb{F}}_{2^{2m}}$.

Proof. To show that $f(x)$ is a $2$-to-$1$ mapping on ${\mathbb{F}}_{2^{2m}}$,
by Theorem 5.1, it is sufficient to show that $h(x)=x^{(2^{i}+1)\cdot
2^{m}}+x^{2^{i}+1}+cx$ is a $2$-to-$1$ mapping on
$S=\\{x\in{\mathbb{F}}_{2^{2m}}\mid{\rm Tr}^{2m}_{m}(x)={\rm
Tr}^{2m}_{m}(\delta)\\}$. To this end, we only need to show that for any $x\in
S$, the equation

$\begin{split}H(y):=&h(y+x)+h(x)=0\end{split}$ (13)

has exactly two distinct solutions in
$S_{0}=\\{z\in{\mathbb{F}}_{2^{2m}}\mid{\rm Tr}^{2m}_{m}(z)=0\\}$, which is
exactly ${\mathbb{F}}_{2^{m}}$. Let $X=x^{2^{m}}$. Since $y^{2^{m}}=y$ for
$y\in{\mathbb{F}}_{2^{m}}$, Eq.(13) is reduced to

$H(y)=(x+X)y^{2^{i}}+(x^{2^{i}}+X^{2^{i}}+c)y=0.$

Next, we show that

$(x+X)y^{2^{i}-1}+x^{2^{i}}+X^{2^{i}}+c=0$ (14)

has a unique root in ${\mathbb{F}}_{2^{m}}^{*}$.

Let $\gamma={\rm Tr}^{2m}_{m}(\delta)$. From $x\in S$ we see that
$x+X=\gamma$. Since ${\rm Tr}_{m}^{2m}(\delta^{2}+c^{2^{m-i}}\delta)\neq 0$,
i.e., $\gamma^{2}+c^{2^{m-i}}\gamma\neq 0$, we have $x+X\neq 0$ and
$x^{2^{i}}+X^{2^{i}}+c\neq 0$. Thus, Eq.(14) has a unique root
$y=(\gamma^{2^{i}-1}+\frac{c}{\gamma})^{\frac{1}{2^{i}-1}}$ in
${\mathbb{F}}_{2^{m}}^{*}$, where $\frac{1}{2^{i}-1}$ denotes the inverse of
$2^{i}-1$ modulo $2^{m}-1$ since ${\rm gcd}(m,i)=1$. $\Box$

###### Theorem 5.9

Let $m,i\in{\mathbb{N}}$, $\delta\in{\mathbb{F}}_{2^{2m}}$,
$c\in{\mathbb{F}}_{2^{m}}$ and ${\rm Tr}_{m}^{2m}(\delta)=\gamma$ with
$\gamma^{2^{i}+2}+c\gamma\neq 0$. Then
$f(x)=(x^{2^{m}}+x+\delta)^{2^{m}+2^{i}+1}+cx$ is a $2$-to-$1$ mapping on
${\mathbb{F}}_{2^{2m}}$.

Proof. To show that $f(x)$ is a $2$-to-$1$ mapping on ${\mathbb{F}}_{2^{2m}}$,
by Theorem 5.1, it is sufficient to show that
$h(x)=x^{2^{m}+2^{i}+1}+x^{1+(2^{i}+1)\cdot 2^{m}}+cx$ is a $2$-to-$1$ mapping
on $S=\\{x\in{\mathbb{F}}_{2^{2m}}\mid{\rm Tr}^{2m}_{m}(x)={\rm
Tr}^{2m}_{m}(\delta)\\}$. To this end, we only need to show that for any $x\in
S$, the equation

$\begin{split}H(y):=&h(y+x)+h(x)\end{split}$ (15)

has exactly two distinct solutions in
$S_{0}=\\{x\in{\mathbb{F}}_{2^{2m}}\mid{\rm Tr}^{2m}_{m}(x)=0\\}$, which is
exactly ${\mathbb{F}}_{2^{m}}$. Let $X=x^{2^{m}}$. Since $y^{2^{m}}=y$ for
$y\in{\mathbb{F}}_{2^{m}}$, Eq.(15) is reduced to

$({x}^{{2}^{i}}+{X}^{{2}^{i}})y^{2}+((x+X)^{2^{i}+1}+c)y=0.$ (16)

Next, we only need to show that

$({x}^{{2}^{i}}+{X}^{{2}^{i}})y+(x+X)^{2^{i}+1}+c=0$ (17)

has a unique root in ${\mathbb{F}}_{2^{m}}^{*}$.

Since $\gamma^{2^{i}+2}+c\gamma\neq 0$, we have $x^{2^{i}}+X^{2^{i}}\neq 0$
and $(x+X)^{2^{i}+1}+c\neq 0$. Thus, Eq.(17) has a unique root
$y=\gamma+\frac{c}{\gamma^{2^{i}}}$ in ${\mathbb{F}}_{2^{m}}^{*}$. $\Box$

###### Remark 5.10

By Proposition 3.3, if the involution derived from the $2$-to-$1$ mapping
$h(x)=x^{2^{k}s}+x^{s}+cx$ on $S$ is $\mathcal{I}_{h}(x)=x+\xi$, where
$\xi\in{\mathbb{F}}_{2^{m}}^{*}$ is a constant. Then the involution derived
from $f(x)=(x^{2^{k}}+x+\delta)^{s}+cx$ on ${\mathbb{F}}_{2^{2m}}$ is
$\mathcal{I}_{f}(x)=c^{-1}[(x^{2^{k}}+x+\delta+\xi)^{s}+(x^{2^{k}}+x+\delta)^{s}]+x$.
As a consequence, the involution derived from the $2$-to-$1$ mapping in
Theorem 5.8 is linear. The involution derived from $2$-to-$1$ mapping in
Theorem 5.9 is given in the following corollary.

###### Corollary 5.11

Let $m,i\in{\mathbb{N}}$, $\delta\in{\mathbb{F}}_{2^{2m}}$,
$c\in{\mathbb{F}}_{2^{m}}^{*}$ and $\gamma=\delta+\delta^{2^{m}}$ with
$\gamma^{2^{i}+2}+c\gamma\neq 0$. Then
$\mathcal{I}(x)=c^{-1}[(x^{2^{m}}+x+\delta+\gamma+\frac{1}{\gamma^{2^{i}}})^{2^{m}+2^{i}+1}+(x^{2^{m}}+x+\delta)^{2^{m}+2^{i}+1}]+x$
is an involution without any fixed point on ${\mathbb{F}}_{2^{2m}}$.

###### Theorem 5.12

Let $m\in{\mathbb{N}}$ be even and $\delta\in{\mathbb{F}}_{2^{2m}}$ with ${\rm
Tr}_{2m}(\delta)=1$. Then $f(x)=(x^{2}+x+\delta)^{\frac{2^{2m}+2^{m}+1}{3}}+x$
is a $2$-to-$1$ mapping on ${\mathbb{F}}_{2^{2m}}$.

Proof. To show that $f(x)$ is a $2$-to-$1$ mapping on ${\mathbb{F}}_{2^{2m}}$,
by Theorem 5.1, it is sufficient to show that
$h(x)=x^{\frac{2^{2m}+2^{m}+1}{3}}+x^{\frac{2(2^{2m}+2^{m}+1)}{3}}+x$ is a
$2$-to-$1$ mapping on $S=\\{x\in{\mathbb{F}}_{2^{2m}}\mid{\rm
Tr}_{2m}(x)=1\\}$. Note that $(2-2^{m})\cdot\frac{2^{2m}+2^{m}+1}{3}\equiv
1\pmod{2^{2m}-1}$. So, $p(x)=x^{2-2^{m}}$ is a permutation on
${\mathbb{F}}_{2^{2m}}^{*}$, and it is also a bijection from
$\bar{S}=\\{x\in{\mathbb{F}}_{2^{2m}}\mid{\rm Tr}_{2m}(x^{2-2^{m}})=1\\}$ to
$S$. Now, we only need to prove $h(x^{2-2^{m}})$ is a $2$-to-$1$ mapping on
$\bar{S}$. Next, we show the equation

$h(y^{2-2^{m}})-h(x^{2-2^{m}})=y^{2}+y+y^{2-2^{m}}-x^{2}+x+x^{2-2^{m}}=0$ (18)

has a unique solution $y\in\bar{S}$ with $y\neq x$, where $x\in\bar{S}$.

Let $X=x^{2^{m}}$, $Y=y^{2^{m}}$. Substituting these into Eq.(18) and then
raising both sides of Eq.(18) to the power of $2^{m}$, we have

$\left\\{\begin{gathered}x^{2}+x+\frac{x^{2}}{X}=y^{2}+y+\frac{y^{2}}{Y},\\\
X^{2}+X+\frac{X^{2}}{x}=Y^{2}+Y+\frac{Y^{2}}{y}.\end{gathered}\right.$ (19)

The system of Eq.(19) is equivalent to the following system,

$\left\\{\begin{aligned}
&P(x,X,y,Y):=\left({y}^{2}X+Xy+{x}^{2}+xX+{x}^{2}X\right)Y+{y}^{2}X=0,\\\
&Q(x,X,y,Y):=\left(xy+x\right){Y}^{2}+Yxy+{X}^{2}xy+yxX+y{X}^{2}=0.\end{aligned}\right.$

Since ${\rm Tr}_{2m}(x^{2}+x+\frac{x^{2}}{X})={\rm
Tr}_{2m}(\frac{x^{2}}{X})={\rm Tr}_{2m}(x^{2-2^{m}})=1$, by Lemma 2.2, there
is no $y\in{\mathbb{F}}_{2^{2m}}$ satisfying
${y}^{2}X+Xy+{x}^{2}+xX+{x}^{2}X=0$ for $x,X\in\bar{S}$, i.e.,
${y}^{2}X+Xy+{x}^{2}+xX+{x}^{2}X\neq 0$ for any $x,y\in\bar{S}$. Computing the
resultant of $P$ and $Q$ with respect to $Y$ gives

$Res(P,Q,Y)=xX(x+y)^{2}(xX+x+X)(Xy+xX+x+X)^{2}=0.$ (20)

We claim that $xX+x+X\neq 0$ for $x\in\bar{S}$. Otherwise,
$(xX+x+X)\frac{x}{X}=0$, and then ${\rm Tr}_{2m}((xX+x+X)\frac{x}{X})={\rm
Tr}_{2m}(x^{2}+x+\frac{x^{2}}{X})={\rm Tr}_{2m}(x^{2-2^{m}})=0$. This is a
contradiction. So, Eq.(20) has two solutions $y=x$ and $y=x+1+\frac{x}{X}$. It
remains to show that the second solution is in $\bar{S}$.

$\begin{split}{\rm Tr}_{2m}(y^{2-2^{m}})&={\rm
Tr}_{2m}\left(\left(\frac{xX+x+X}{X}\right)^{2-2^{m}}\right)\\\ &={\rm
Tr}_{2m}\left(\frac{x^{2}}{X}+\frac{x^{2}}{X^{2}}+\frac{x}{X}\right)={\rm
Tr}_{2m}(x^{2-2^{m}})=1.\end{split}$

Thus, $y=x+1+\frac{x}{X}\in\bar{S}$ is the unique solution of Eq.(18) with
$y\neq x$. $\Box$

###### Corollary 5.13

Let $m\in{\mathbb{N}}$ be even and $\delta\in{\mathbb{F}}_{2^{2m}}$ with ${\rm
Tr}_{2m}(\delta)=1$. Then
$\mathcal{I}(x)=(x^{2}+x+\delta)^{\frac{2^{2m+1}-2^{m}-1}{3}}+x+1$ is an
involution without any fixed point in ${\mathbb{F}}_{2^{2m}}$.

Proof. Let $g(x)=x^{\frac{2^{2m}+2^{m}+1}{3}}$, $c=1$. From Theorem 5.12, we
see that the involution derived from $h\circ g^{-1}$ on $\bar{S}$ is
$\mathcal{I}_{h\circ g^{-1}}(x)=x+1+{x^{1-2^{m}}}$. By Proposition 3.3, the
involution derived from $h$ on $S$ is
$\mathcal{I}_{h}=g^{-1}\circ\mathcal{I}_{h\circ g^{-1}}\circ g$. Let
$\lambda(x)=x^{2}+x+\delta$ and $c=1$, then by Proposition 5.2, the involution
derived from $f$ on ${\mathbb{F}}_{2^{2m}}$ is

$\begin{split}&\mathcal{I}_{f}(x)=g\circ\mathcal{I}_{h}\circ\lambda(x)+g\circ\lambda(x)+x=\mathcal{I}_{h\circ
g^{-1}}\circ g\circ\lambda(x)+g\circ\lambda(x)+x\\\
&=(x^{2}+x+\delta)^{\frac{2^{2m}+2^{m}+1}{3}(1-2^{m})}+x+1=(x^{2}+x+\delta)^{\frac{2^{2m+1}-2^{m}-1}{3}}+x+1.\end{split}$

$\Box$

In the following, we consider the $2$-to-$1$ mappings of the form (1) with $s$
being a Niho exponent. The $2$-to-$1$ mappings of this type are connected to
the polynomials of the form $h(x)=x^{r}\bar{h}(x^{s})$ over
${\mathbb{F}}_{2^{n}}$, where $s\,|\,(2^{n}-1)$ and
$\bar{h}[x]\in{\mathbb{F}}_{2^{n}}[x]$. It is known that the permutation
property of the polynomials of this form have been extensively studied in the
literature. See, for example, [2, 13, 16, 18, 20, 21, 24, 25, 32, 35, 41, 44,
45, 42]. To this end, we first give some preliminary lemmas.

###### Lemma 5.14

Let $m\in{\mathbb{N}}$,
$\delta\in{\mathbb{F}}_{2^{2m}}\setminus{\mathbb{F}}_{2^{m}}$ and
$\bar{h}(x)\in{\mathbb{F}}_{2^{2m}}[x]$. Then $h(x)=x^{r}\bar{h}(x^{2^{m}-1})$
is a $2$-to-$1$ mapping on $S=\\{z+\delta\mid z\in{\mathbb{F}}_{2^{m}}\\}$ if
and only if $\varphi(x)=x^{r}\bar{h}(x)^{2^{m}-1}$ is a $2$-to-$1$ mapping on
$\mu_{2^{m}+1}^{*}$.

Proof. Let $\phi(x)=x^{2^{m}-1}$. It is easy to verify that $\phi\circ
h=\varphi\circ\phi$. Moreover, we show that $\phi$ is a bijection from $S$ to
$\mu_{2^{m}+1}^{*}$. For any $z\in{\mathbb{F}}_{2^{m}}$, we have

$\left(\phi(z+\delta)\right)^{2^{m}+1}=\left((z+\delta)^{2^{m}-1}\right)^{2^{m}+1}=1.$

So, $\phi(z+\delta)\in\mu_{2^{m}+1}^{*}$. If there exist
$z_{1},z_{2}\in{\mathbb{F}}_{2^{m}}$ such that
$\phi(z_{1}+\delta)=\phi(z_{2}+\delta)$, i.e.,

$\frac{z_{1}+\delta^{2^{m}}}{z_{1}+\delta}=\frac{z_{2}+\delta^{2^{m}}}{z_{2}+\delta}.$

This implies that $z_{1}=z_{2}$ since
$\delta\in{\mathbb{F}}_{2^{2m}}\setminus{\mathbb{F}}_{2^{m}}$. Then the result
follows from the fact that $h=\phi^{-1}\circ\varphi\circ\phi$. $\Box$

###### Lemma 5.15

Let $m\in{\mathbb{N}}$ and $\theta\in\mu_{2^{m}+1}^{*}$. Then
$\psi(x)=\frac{1+\theta x}{\theta+x}$ is a bijection from
$\mu_{2^{m}+1}^{*}\setminus\\{\theta\\}$ to
${\mathbb{F}}_{2^{m}}\setminus\\{1\\}$.

Proof. Note that $\psi(x)^{2^{m}}=\frac{1+(\theta
x)^{-1}}{\theta^{-1}+x^{-1}}=\psi(x)$ if
$x\in\mu_{2^{m}+1}^{*}\setminus\\{\theta\\}$, and $\psi(x)=1$ if and only if
$x=1$. So, $\psi(x)\in{\mathbb{F}}_{2^{m}}\setminus\\{1\\}$ for
$x\in\mu_{2^{m}+1}^{*}\setminus\\{\theta\\}$. If there exist two elements
$z_{1},z_{2}\in\mu_{2^{m}+1}^{*}$ such that $\psi(z_{1})=\psi(z_{2})$, i.e.,
$\frac{1+\theta z_{1}}{\theta+z_{1}}=\frac{1+\theta z_{2}}{\theta+z_{2}}$.
Then we have $(\theta^{2}+1)(z_{1}+z_{2})=0$, and so $z_{1}=z_{2}$. This shows
that $\psi$ is a bijection from $\mu_{2^{m}+1}^{*}\setminus\\{\theta\\}$ to
${\mathbb{F}}_{2^{m}}\setminus\\{1\\}$ since these two sets have the same
cardinality. $\Box$

###### Theorem 5.16

Let $m\in{\mathbb{N}}$,
$\delta\in{\mathbb{F}}_{2^{2m}}\setminus{\mathbb{F}}_{2^{m}}$ and
$c\in{\mathbb{F}}_{2^{m}}^{*}$ with ${\rm Tr}_{m}(\frac{1}{c}+1)=1$. Then
$f(x)=(x^{2^{m}}+x+\delta)^{2^{2m-2}+2^{m}-2^{m-2}}+cx$ is a $2$-to-$1$
mapping on ${\mathbb{F}}_{2^{2m}}$.

Proof. To show that $f$ is a $2$-to-$1$ mapping on ${\mathbb{F}}_{2^{2m}}$, by
Theorem 5.1, it is sufficient to show that

$\displaystyle h(x)$
$\displaystyle=x^{2^{2m-2}+2^{m}-2^{m-2}}+x^{(2^{2m-2}+2^{m}-2^{m-2})2^{m}}+cx$
$\displaystyle=x^{(2^{m-2}+1)(2^{m}-1)+1}+x^{(2^{m}-2^{m-2}+1)(2^{m}-1)+1}+cx$

is a $2$-to-$1$ mapping on $S=\\{z+\delta\mid z\in{\mathbb{F}}_{2^{m}}\\}$. By
Lemma 5.14, we only need to show
$\varphi(x)=x(x^{2^{m-2}+1}+x^{2^{m}-2^{m-2}+1}+c)^{2^{m}-1}$ is a $2$-to-$1$
mapping on $\mu_{2^{m}+1}^{*}$. First, we show that there is no
$x\in\mu_{2^{m}+1}$ such that $x^{2^{m-2}+1}+x^{2^{m}-2^{m-2}+1}+c=0$.
Otherwise, suppose $x\in\mu_{2^{m}+1}^{*}$ satisfies

$x^{2^{m-2}+1}+x^{-2^{m-2}}+c=0.$ (21)

Multiplying the both sides of Eq.(21) by $x^{-1}$, then taking them to the
power of $2^{m}$ and combining the facts $x^{2^{2m}}=x$ and
$x^{2^{m}}=x^{-1}$, we have

$x^{-2^{m-2}}+x^{2^{m-2}+1}+cx=0.$ (22)

From Eq.(21) and Eq.(22) we have $x=1$. This is a contradiction to
$x\in\mu_{2^{m}+1}^{*}$.

To show that $\varphi(x)$ is a $2$-to-$1$ mapping on $\mu_{2^{m}+1}^{*}$, we
next prove that $\varphi(x^{4})$ is a $2$-to-$1$ mapping on
$\mu_{2^{m}+1}^{*}$ since ${\rm gcd}(4,2^{m}+1)=1$. Assume that there are two
distinct elements $x,y\in\mu_{2^{m}+1}^{*}$ such that
$\varphi(x^{4})=\varphi(y^{4})$, i.e.,

$\frac{cx^{4}+x^{3}+x}{x^{3}+x+c}=\frac{cy^{4}+y^{3}+y}{y^{3}+y+c}.$ (23)

Since $x\neq y$, Eq.(23) is reduced to

$x^{3}y^{3}+x^{2}y^{2}+xy+1+x^{2}+y^{2}+x^{3}y+xy^{3}+c(x+y)^{3}=0.$ (24)

Eq.(24) is further reduced to

$z^{3}+z+c=0,$ (25)

where $z=\frac{1+xy}{x+y}\in{\mathbb{F}}_{2^{m}}$. Since ${\rm
Tr}_{m}(\frac{1}{c}+1)=1$, by Lemma 2.3, we know that Eq.(25) has a unique
solution $z=\alpha\in{\mathbb{F}}_{2^{m}}\setminus\\{1\\}$. Thus, by Lemma
5.15, $y=\frac{\alpha x+1}{x+\alpha}$ is the unique element in
$\mu_{2^{m}+1}^{*}\setminus\\{x\\}$ satisfying
$\varphi(x^{4})=\varphi(y^{4})$. This completes the proof. $\Box$

###### Corollary 5.17

Let $m\in{\mathbb{N}}$,
$\delta\in{\mathbb{F}}_{2^{2m}}\setminus{\mathbb{F}}_{2^{m}}$ and
$c\in{\mathbb{F}}_{2^{m}}^{*}$ with ${\rm Tr}_{m}(\frac{1}{c}+1)=1$. Let
$\alpha\in{\mathbb{F}}_{2^{m}}$ be the root of $x^{3}+x+c=0$. Then

$\begin{split}\mathcal{I}_{f}(x)=c^{-1}[(x^{2^{m}}+x+\delta+&\frac{(\delta+\delta^{2^{m}})}{\alpha^{4}+1})^{2^{2m-2}+2^{m}-2^{m-2}}\\\
&+(x^{2^{m}}+x+\delta)^{2^{2m-2}+2^{m}-2^{m-2}}]+x\end{split}$

is an involution without any fixed point in ${\mathbb{F}}_{2^{2m}}$.

Proof. Follow the notation introduced in Theorem 5.16 and let
$\phi(x)=x^{2^{m}-1}$, $p(x)=x^{4}$. By Theorem 5.16, the involution derived
from $\varphi\circ p$ on $\mu_{2^{m}+1}^{*}$ is $\mathcal{I}_{\varphi\circ
p}(x)=\frac{\alpha x+1}{x+\alpha}$. Then, by Theorem 3.3, the involution
derived from $\varphi$ is
$\mathcal{I}_{\varphi}(x)=p\circ\mathcal{I}_{\varphi\circ p}\circ
p^{-1}(x)=\frac{\alpha^{4}x+1}{x+\alpha^{4}}$. For any $x\in S$, there exists
$z\in{\mathbb{F}}_{2^{m}}$ such that $x=z+\delta$. Then
$\phi(x)=x^{2^{m}-1}=\frac{z+\delta^{2^{m}}}{z+\delta}=1+\frac{\delta+\delta^{2^{m}}}{x}$
and $\phi^{-1}(x)=\frac{\delta+\delta^{2^{m}}}{1+x}$. By Theorem 3.3 again,
the involution derived from $h$ on $S$ is
$\mathcal{I}_{h}(x)=\phi^{-1}\circ\mathcal{I}_{\varphi}\circ\phi(x)=x+\frac{\delta+\delta^{2^{m}}}{\alpha^{4}+1}$
since $h(x)=\phi^{-1}\circ\varphi\circ\phi(x)$. Thus, by Remark 5.10, the
involution derived from $f$ on ${\mathbb{F}}_{2^{2m}}$ is
$\mathcal{I}_{f}(x)=c^{-1}[(x^{2^{m}}+x+\delta+\frac{(\delta+\delta^{2^{m}})}{\alpha^{4}+1})^{2^{2m-2}+2^{m}-2^{m-2}}+(x^{2^{m}}+x+\delta)^{2^{2m-2}+2^{m}-2^{m-2}}]+x$.
$\Box$

###### Theorem 5.18

Let $m\in{\mathbb{N}}$,
$\delta\in{\mathbb{F}}_{2^{4m}}\setminus{\mathbb{F}}_{2^{2m}}$ and
$c\in{\mathbb{F}}_{2^{2m}}\setminus{\mathbb{F}}_{2^{m}}$. Then
$f(x)=(x^{2^{2m}}+x+\delta)^{(2^{2m-1}-2^{m-1}+1)(2^{2m}-1)+1}+cx$ is a
$2$-to-$1$ mapping on ${\mathbb{F}}_{2^{4m}}$.

Proof. To show that $f$ is a $2$-to-$1$ mapping on ${\mathbb{F}}_{2^{4m}}$, by
Theorem 5.1, it is sufficient to show that

$h(x)=x^{(2^{2m-1}-2^{m-1}+1)(2^{2m}-1)+1}+x^{(2^{m-1}-2^{2m-1})(2^{2m}-1)+1}+cx$

is a $2$-to-$1$ mapping on $S=\\{z+\delta\mid z\in{\mathbb{F}}_{2^{2m}}\\}$.
By Lemma 5.14, we only need to show
$\varphi(x)=x(x^{2^{2m-1}-2^{m-1}+1}+x^{2^{m-1}-2^{2m-1}}+c)^{2^{2m}-1}$ is a
$2$-to-$1$ mapping on $\mu_{2^{2m}+1}^{*}$. First, we show that for any
$x\in\mu_{2^{2m}+1}^{*}$, $x^{2^{2m-1}-2^{m-1}+1}+x^{2^{m-1}-2^{2m-1}}+c\neq
0.$ Otherwise, assume that $x_{0}\in\mu_{2^{2m}+1}^{*}$ satisfies

$x_{0}^{2^{2m-1}-2^{m-1}+1}+x_{0}^{2^{m-1}-2^{2m-1}}+c=0.$ (26)

Multiplying the both sides of Eq.(26) by $x_{0}^{-1}$, then taking them to the
power of $2^{2m}$, we get

$x_{0}^{2^{m-1}-2^{2m-1}}+x_{0}^{2^{2m-1}-2^{m-1}+1}+cx_{0}=0.$ (27)

From Eq.(26) and Eq.(27) we have $c(x_{0}+1)=0$. This contradicts with that
$x_{0}\in\mu_{2^{2m}+1}^{*}$.

Next, we show that $\varphi(x^{2})$ is a $2$-to-$1$ mapping on
$\mu_{2^{2m}+1}^{*}$ since ${\rm gcd}(2,2^{2m}+1)=1$. Assume that there exist
$x,y\in\mu_{2^{2m}+1}^{*}$ with $x\neq y$ such that
$\varphi(x^{2})=\varphi(y^{2})$, i.e.,

$\frac{x^{2^{2m+1}-2^{m+1}+2}+cx^{2^{2m}-2^{m}+2}+1}{x^{2^{2m+1}-2^{m+1}+2}+cx^{2^{2m}-2^{m}}+1}=\frac{y^{2^{2m+1}-2^{m+1}+2}+cy^{2^{2m}-2^{m}+2}+1}{y^{2^{2m+1}-2^{m+1}+2}+cy^{2^{2m}-2^{m}}+1}.$
(28)

Let $X=x^{2^{m}}$ and $Y=y^{2^{m}}$. Note that $x^{2^{2m}+1}=y^{2^{2m}+1}=1$
and from Eq.(28) we have

$\begin{split}&P(x,X,y,Y):=\left(y{x}^{2}X+Xy\right){Y}^{2}\\\
&+\left({y}^{2}x{X}^{2}+{y}^{2}cX+c{x}^{2}X+{y}^{2}x+{X}^{2}x+x\right)Y+y{x}^{2}X+Xy=0.\end{split}$
(29)

Let $\bar{c}=c^{2^{m}}$. Note that $Y^{2^{m}}=y^{-1}$ and $X^{2^{m}}=x^{-1}$.
Taking the both sides of Eq.(29) to the power of $2^{m}$, then multiplying
them by $x^{2}y^{2}$, we have

$\begin{split}Q(x,X,y,Y)&:=x^{4}y^{4}P(x,X,y,Y)^{2^{m}}+\left({y}^{2}x{X}^{2}+{y}^{2}x+{X}^{2}x+x\right)Y\\\
&+\bar{c}{X}^{2}yx+y{x}^{2}X+Xy=0.\end{split}$ (30)

By calculating the resultant of $P$ and $Q$ with respect to $Y$, we have

$Res(P,Q,Y)=y^{2}X^{2}(y+x)^{2}(A(x,X)y^{2}+B(x,X))=0,$ (31)

where $A(x,X)=A_{1}(x,X)A_{2}(x,X)$, $B(x,X)=B_{1}(x,X)B_{2}(x,X)$ and

$\begin{gathered}A_{1}(x,X)={x}^{2}{X}^{2}\bar{c}+xXc\bar{c}+{x}^{2}\bar{c}+c{x}^{2}+c,\\\
A_{2}(x,X)={x}^{2}{X}^{2}\bar{c}+c{x}^{2}{X}^{2}+xXc\bar{c}+{x}^{2}\bar{c}+c{X}^{2},\\\
B_{1}(x,X)=x^{2}(xXc\bar{c}+\bar{c}{X}^{2}+c{x}^{2}+\bar{c}+c),\\\
B_{2}(x,X)=c{x}^{2}{X}^{2}+xXc\bar{c}+\bar{c}{X}^{2}+c{X}^{2}+\bar{c}.\end{gathered}$

In the following we show that $A_{1}(x,X)\neq 0$ for any
$x\in\mu_{2^{2m}+1}^{*}$. And $A_{2}(x,X)\neq 0$, $B_{1}(x,X)\neq 0$,
$B_{2}(x,X)\neq 0$, $A(x,X)+B(x,X)\neq 0$ and $A(x,X)+x^{2}B(x,X)\neq 0$ for
$x\in\mu_{2^{2m}+1}^{*}$ can be proved similarly. Assume that there exists
$\bar{x}\in\mu_{2^{2m}+1}^{*}$ such that $A_{1}(\bar{x},\bar{X})=0$, where
$\bar{X}=\bar{x}^{2^{m}}$. Then

$\bar{x}^{2}\bar{X}^{2}A_{1}(\bar{x},\bar{X})^{2^{m}}+A_{1}(\bar{x},\bar{X})=(\bar{c}+c)(\bar{x}+\bar{X})^{2}=0.$

This is a contradiction since
$c\in{\mathbb{F}}_{2^{2m}}\setminus{\mathbb{F}}_{2^{m}}$ and
$\bar{x}\in\mu_{2^{2m}+1}^{*}$. For $x\in\mu_{2^{2m}+1}^{*}$, it is easy to
show that

$\left(\frac{B(x,X)}{A(x,X)}\right)^{2^{2m}}=\frac{B(\frac{1}{x},\frac{1}{X})}{A(\frac{1}{x},\frac{1}{X})}=\frac{A(x,X)}{B(x,X)}.$

This shows that $\frac{B(x,X)}{A(x,X)}\in\mu_{2^{2m}+1}^{*}$. Thus, from
Eq.(31) we know that $y=\sqrt{\frac{B(x,X)}{A(x,X)}}$ is the unique solution
of Eq.(28) with $y\neq x$. $\Box$

###### Corollary 5.19

Let $m\in{\mathbb{N}}$,
$\delta\in{\mathbb{F}}_{2^{4m}}\setminus{\mathbb{F}}_{2^{2m}}$,
$c\in{\mathbb{F}}_{2^{2m}}\setminus{\mathbb{F}}_{2^{m}}$, and let
$A,B\in{\mathbb{F}}_{2^{4m}}[x,X]$ be defined in Eq.(31), and let
$g(x)=x^{(2^{2m-1}-2^{m-1}+1)(2^{2m}-1)+1}$, $\phi(x)=x^{2^{2m}-1}$,
$\lambda(x)=x^{2^{2m}}+x+\delta$ and
$\mathcal{I}_{h}(x)=\phi^{-1}\circ\frac{B(\sqrt{x},x^{2^{m-1}})}{A(\sqrt{x},x^{2^{m-1}})}\circ\phi(x)$.
Then
$\mathcal{I}(x)=c^{-1}(g\circ\mathcal{I}_{h}\circ\lambda(x)+g\circ\lambda(x))+x$
is an involution on ${\mathbb{F}}_{2^{4m}}$.

All results in this section are summarized in Table 1.

Table 1: $2$-to-$1$ mappings of the form
${(x^{2^{k}}+x+\delta)}^{s}+cx\in{\mathbb{F}}_{2^{2m}}[x]$

No | $k$ | $m$ | $s$ | Conditions | Ref. | Involution
---|---|---|---|---|---|---
1 | $1$ | even | $2^{m}+1$ | ${\rm Tr}_{2m}(\delta)=1,c=1$ | Thm. 5.5 |
2 | $1$ | even | $2^{2m-1}+2^{m-1}$ | ${\rm Tr}_{2m}(\delta)=1,c=1$ | Thm. 5.6 |
3 | $1$ | even | $2^{2m-2}+2^{m-2}$ | ${\rm Tr}_{2m}(\delta)=1,c=1$ | Thm. 5.3 | Cor. 5.4
4 | $1$ | even | $\frac{2^{2m}+2^{m}+1}{3}$ | ${\rm Tr}_{2m}(\delta)=1,c=1$ | Thm. 5.12 | Cor. 5.13
5 | $m$ | ${\rm gcd}(m,i)=1$ | $2^{i}+1$ | ${\rm Tr}^{2m}_{m}(\delta^{2}+c^{2^{m-i}}\delta)\neq 0$ | Thm. 5.8 | affine polynomial
6 | $m$ | $m\in{\mathbb{N}}$ | $2^{m}+2^{i}+1$ | ${\rm Tr}^{2m}_{m}(\delta)^{2^{i}+2}+c{\rm Tr}^{2m}_{m}(\delta)\neq 0$ | Thm. 5.9 | Cor. 5.11
7 | $m$ | $m\in{\mathbb{N}}$ | $2^{2m-2}+2^{m}-2^{m-2}$ | $\delta\in{\mathbb{F}}_{2^{2m}}\setminus{\mathbb{F}}_{2^{m}},{\rm Tr}(\frac{1}{c}+1)\neq 0,c\in{\mathbb{F}}_{2^{m}}^{*}$ | Thm. 5.16 | Cor. 5.17
8 | $m$ | even | $(2^{m-1}-2^{m/2-1}+1)(2^{m}-1)+1$ | $\delta\in{\mathbb{F}}_{2^{2m}}\setminus{\mathbb{F}}_{2^{m}},c\in{\mathbb{F}}_{2^{m}}\setminus{\mathbb{F}}_{2^{m/2}}$ | Thm. 5.18 | Cor. 5.19

##  6 The involutions derived from the known $2$-to-$1$ mappings over
${\mathbb{F}}_{2^{2m+1}}$

By using Theorem 3.1 and the multivariate technique introduced by Dobbertin
[14], we obtain five classes of new involutions on ${\mathbb{F}}_{2^{2m+1}}$
from known $2$-to-$1$ mappings proposed in [23]. To this end, we first recall
the known $2$-to-$1$ mappings over ${\mathbb{F}}_{2^{2m+1}}$ introduced in
[23].

###### Lemma 6.1

[23] For $m\in{\mathbb{N}}$, the polynomial $f(x)$ is a $2$-to-$1$ mapping
over ${\mathbb{F}}_{2^{2m+1}}$ in the following cases:

  1. (1)

$f(x)=x^{2^{m+1}+2}+x^{2^{m+1}}+x^{2}+x$;

  2. (2)

$f(x)=x^{2^{m+1}+2}+x^{2^{m+1}+2}+x^{2}+x$;

  3. (3)

$f(x)=x^{2^{m+2}+4}+x^{2^{m+1}+2}+x^{2}+x$;

  4. (4)

$f(x)=x^{2^{2m+1}-2^{m+1}+2}+x^{2^{m+1}}+x^{2}+x$;

  5. (5)

$f(x)=x^{2^{2m+1}-2}+x^{2^{2m+1}-2^{m+1}}+x^{2^{2m+1}-2^{m+1}-2}+x$.

###### Theorem 6.2

For $m\in{\mathbb{N}}$, the following polynomials are involutions over
${\mathbb{F}}_{2^{2m+1}}$:

  1. (1)

$\mathcal{I}(x)=x+\frac{1}{x^{2^{m+2}+2}+x^{2^{m+2}}+x^{2^{m+1}}+x^{2}+1}$;

  2. (2)

$\mathcal{I}(x)=x+\frac{1}{x^{2^{m+1}}+x^{2^{m+1}-1}+1}$;

  3. (3)

$\mathcal{I}(x)=x+\frac{1}{x^{2^{m+2}+2}+x^{2^{m+1}}+1}$;

  4. (4)

$\mathcal{I}(x)=x^{2^{2m+1}-2^{m+1}+1}+x^{2^{m+1}-1}+x+1$;

  5. (5)

$\mathcal{I}(x)=\left\\{\begin{aligned}
&x^{2^{2m+1}-2}+x^{2^{2m+1}-2^{m+1}}+x^{2^{2m+1}-2^{m+1}-2},&&x\not\in{\mathbb{F}}_{2};\\\
&x+1,&&x\in{\mathbb{F}}_{2}.\end{aligned}\right.$

Proof. We prove the conclusion only for Case (1). The conclusions in Cases
(2)-(5) can be similarly proved. Since
$f(x)=x^{2^{m+1}+2}+x^{2^{m+1}}+x^{2}+x$ in Lemma 6.1 is a $2$-to-$1$ mapping
over ${\mathbb{F}}_{2^{2m+1}}$, by Theorem 3.1 we only need to check that
$y=\mathcal{I}(x)$ in Case (1) satisfies that $f(x)+f(y)=0$ for
$x\in{\mathbb{F}}_{2^{2m+1}}$.

Let $X=x^{2^{m+1}}$, then $X^{2^{m+1}}=x^{2}$ and
$\mathcal{I}(x)=x+\frac{1}{X^{2}x^{2}+X^{2}+X+x^{2}+1}$. We claim that
$X^{2}x^{2}+X^{2}+X+x^{2}+1\neq 0$ for $x\in{\mathbb{F}}_{2^{2m+1}}$.
Otherwise, we have

$H(x):=X^{2}(x^{2}+1)+X+x^{2}+1=0$ (32)

for some $x\in{\mathbb{F}}_{2^{2m+1}}$. Raising the both sides of Eq.(32) to
the power of $2^{m+1}$ , we get

$G(x):=X^{2}(x^{4}+1)+x^{4}+x^{2}+1=0.$ (33)

Combining Eq.(32) and Eq.(33), we obtain

$(x^{4}+1)\cdot(H(x))^{2}+(G(x))^{2}+G(x)=(x+1)^{2}=0.$

This contradicts Eq.(32). Then the conclusion follows from direct verification
by substitution. $\Box$

##  7 Concluding remark

In this paper, we characterized a closed relationship between $2$-to-$1$
mappings and involutions without any fixed point over finite fields, and
proposed an AGW-like criterion for $2$-to-$1$ mappings over finite fields of
even characteristic. Using this criterion, eight classes of $2$-to-$1$
mappings of the form (1) were obtained, and ten classes of involutions without
any fixed point were produced by the proposed connection between the
$2$-to-$1$ mappings and the involutions. Theorem 3.1 shows that a $2$-to-$1$
mapping can derive an involution over finite fields, but it seems not easy to
obtain the explicit expression of derived involutions from $2$-to-$1$
mappings. This is a problem worthy of further investigation.

## References

  * [1] Advanced Encryption Standard, http://en.wikipedia.org/wiki/ Rijndael S-box.
  * [2] A. Akbary, D. Ghioca and Q. Wang, On constructing permutations of finite fields, Finite Fields Appl., 17, 51-67, 2011.
  * [3] E. R. Berlekamp, H. Rumsey and G. Solomon, On the solution of algebraic equations over finite fields, Inf. Control., 10, 553-564, 1967.
  * [4] A. Biryukov, Analysis of involutional ciphers: Khazad and Anubis, In: T. Johansson (eds), Fast Software Encryption, FSE 2003, LNCS 2887, 45-53, 2003, Springer, Berlin, Heidelberg.
  * [5] J. Borghoff, A. Canteaut, T. Güneysu, E.B. Kavun, M. Knezevic, L.R. Knudsen, G. Leander, V. Nikov, C. Paar C, C. Rechberger, P. Rombouts, S. Thomsen and T. Yalçin, PRINCE-A low-latency block cipher for pervasive computing applications, In X. Wang and K. Sako (Eds.) Advances in Cryptology-ASIACRYPT 2012, LNCS 7658, 208-225, 2012, Springer, Berlin, Heidelberg.
  * [6] C. Boura, A. Canteaut, L. R. Knudsen and G. Leander, Reflection ciphers, Des. Codes Cryptogr., 82, 3-25, 2017.
  * [7] P. Charpin, G.M. Kyureghyan: When does $G(x)+\gamma Tr(H(x))$ permute ${\mathbb{F}}_{p^{n}}$? Finite Fields Appl., 15 (5), 615-632, 2009.
  * [8] C. Carlet and S. Mesnager, On Dillon’s class $\mathcal{H}$ of bent functions, Niho bent functions and o-polynomials, J. Comb. Theory, Ser. A, 118, 2393-2410, 2011.
  * [9] P. Charpin, S. Mesnager and S. Sarkar, Involutions over the Galois field ${\mathbb{F}}_{2^{n}}$, IEEE Trans. Inf. Theory, 62(4), 2266-2276, 2016.
  * [10] P. Charpin, S. Mesnager and S. Sarkar, Dickson polynomials that are involutions, Journal, Contemporary Developments in Finite Fields and Their Appl., World Scientific Press, 22-45, 2016.
  * [11] Y. Chen and J. Polhill, Paley type group schemes and planar Dembowski-Ostrom polynomials, Discrete Math., 311(14), 1349-1364, 2011.
  * [12] D. Cox, J. Little and D. O’Shea, Ideals, Varieties, and Algorithms, Third Edition, Springer, 2007.
  * [13] C. Ding, L. Qu, Q. Wang, J. Yuan and P. Yuan, Permutation trinomials over finite fields with even characteristic, SIAM J. Discrete Math., 29, 79-92, 2015.
  * [14] H. Dobbertin, Uniformly representable permutation polynomials, Sequence and Their Applications, SETA 2001, Springer, 2(9), 1-22, 2002.
  * [15] S. Fu and X. Feng, Involutory differentially 4-uniform permutations from known constructions, Des. Codes Cryptogr., 87, 31-56, 2019.
  * [16] R. Gupta and R.K. Sharma, Some new classes of permutation trinomials over finite fields with even characteristic, Finite Fields Appl., 41, 89-96, 2016.
  * [17] T. Helleseth and V. Zinoviev, New Kloosterman sums identities over ${\mathbb{F}}_{2^{m}}$ for all $m$, Finite Fields Appl., 9(2), 187–193, 2003.
  * [18] X. Hou, Permutation polynomials of ${\mathbb{F}}_{q^{2}}$ of the form $aX+X^{r(q-1)+1}$, Contemporary developments in finite fields and applications, 74-101, World Sci. Publ., Hackensack, NJ, 2016.
  * [19] G.M. Kyureghyan, Constructing permutations of finite fields via linear translators, J. Comb. Theory, Ser. A, 118 (3), 1052-1061, 2011.
  * [20] G. Kyureghyan and M.E. Zieve, Permutation polynomials of the form $X+\gamma{\rm Tr}(X^{k})$, Contemporary Developments in Finite Fields and Appl., DOI:10.1142/9789814719261-0011, 2016.
  * [21] N. Li and T. Helleseth, Several classes of permutation trinomials from Niho exponents, Cryptogr. Commun., 9(6), 693-705, 2017.
  * [22] K. Li, C. Li, T. Helleseth and L. Qu, Binary linear codes with few weights from two-to-one functions, IEEE Trans. Inf. Theory, DOI: 10.1109/TIT.2021.3068743.
  * [23] K. Li, S. Mesnager and L. Qu, Further study of 2-to-1 mappings over ${\mathbb{F}}_{2^{n}}$, IEEE Trans. Inf. Theory, DOI:10.1109/TIT.2021.3057094.
  * [24] K. Li, L. Qu and X. Chen, New classes of permutation bionmials and permutation trinomials over finite fields, Finite Fields Appl., 43, 69-85, 2017.
  * [25] K. Li, L. Qu and Q. Wang, New constructions of permutation polynomials of the form $x^{r}h(x^{q-1})$ over ${\mathbb{F}}_{q^{2}}$, Des. Codes Cryptogr., 86, 2379-2405, 2018.
  * [26] R. Lidl and H. Niederreiter, Finite Fields, Encycl. Math. Appl., Cambridge University Press, 1997.
  * [27] S. Mesnager and L. Qu, On two-to-one mappings over finite fields, IEEE Trans. Inf. Theory, 65(12), 7884-7895, 2019.
  * [28] T. Niu, K. Li, L. Qu and Q. Wang, New constructions of involutions over finite fields, Cryptogr. Commun., 12, 165-185, 2020.
  * [29] A. Pott, Almost perfect and planar functions, Des. Codes Cryptogr., 78(1), 41-195, 2016.
  * [30] I. Rubio, N. Pacheco-Tallaj, C. Corrada-Bravo and FN. Castro, Explicit formulas for monomial involutions over finite fields, Adv. Math. Commun., 11(2), 301-306, 2017.
  * [31] H. Soleimany, C. Blondeau, X. Yu, W. Wu, K. Nyberg, H. Zhang, L. Zhang and Y. Wang, Reflection Cryptanalysis of PRINCE-Like Ciphers, J. Cryptogr., 28, 718-744, 2015.
  * [32] Z. Tu, X. Zeng and L. Hu, Several classes of complete permutation polynomials, Finite Fields Appl., 25, 182-193, 2014.
  * [33] Z. Tu, X. Zeng and X. Jiang, Two classes of permutation polynomials having the form ${(x^{2^{m}}+x+\delta)}^{s}+x$, Finite Fields Appl., 31, 12-24, 2015.
  * [34] I. Villa, On APN functions $L_{1}(x^{3})+L_{2}(x^{9})$ with linear $L_{1}$ and $L_{2}$, Cryptogr. Commun., 11, 3-20, 2019.
  * [35] Q. Wang, Cyclotomic mapping permutation polynomials over finite fields, Proceedings of the 2007 international conference on Sequences, subsequences, and consequences (SSC 2007), Pages 119-128, Los Angeles, CA, USA, 2007.
  * [36] G. Weng and X. Zeng, Further results on planar DO functions and commutative semifields, Des. Codes Cryptogr., 63(3), 413-423, 2012.
  * [37] J. Yuan and C. Ding, Four classes of permutation polynomials of ${\mathbb{F}}_{2^{m}}$, Finite Fields Appl., 13(4), 869–876, 2007.
  * [38] P. Yuan and C. Ding, Permutation polynomials over finite fields from a powerful lemma, Finite Fields Appl., 17, 560-574, 2011.
  * [39] P. Yuan and C. Ding, Further results on permutation polynomials over finite fields, Finite Fields Appl., 27, 88-103, 2014.
  * [40] X. Zeng, X. Zhu, L. Hu, Two new permutation polynomials with the form ${(x^{2^{k}}+x+\delta)}^{s}+x$ over ${\mathbb{F}}_{2^{n}}$, Appl. Algebra Eng. Commun. Comput., 21(2), 145-150, 2010.
  * [41] Z. Zha, L. Hu and S. Fan, Further results on permutation trinomials over finite fields with even characteristic, Finite Fields Appl., 45, 43-52, 2017.
  * [42] D. Zheng, M. Yuan and L. Yu, Two types of permutation polynomials with special forms, Finite Fields Appl., 56, 1-16, 2019.
  * [43] D. Zheng, M. Yuan, N. Li, L. Hu and X. Zeng, Constructions of involutions over finite fields, IEEE Trans. Inf. Theory, 65(12), 7876-7883, 2019.
  * [44] M.E. Zieve, On some permutation polynomials over ${\mathbb{F}}_{q}$ of the form $x^{r}h(x^{(q-1)/d})$, Proc. Amer. Math. Soc., 137, 209-216, 2009.
  * [45] M.E. Zieve, Permutation polynomials on ${\mathbb{F}}_{q}$ induced from R$\acute{e}$dei function bijections on subgroups of ${\mathbb{F}}_{q}^{*}$, arXiv:1310.0776v2 [cs.IT], 2013.