A new construction for involutions over finite fields

Abstract

In 2020, Niu et al. [Cryptogr. Commun., 2020, 12(2): 165−185] studied the fixed points of involutions over the finite field with q-elements. This paper further discusses the relationship between the fixed points set and the non-fixed points set of two involutions f_1\left(x \right) and f_2\left(x \right) over the finite field {\mathbb{F}}_q, and then obtains a necessary and sufficient condition for that the composite function f_1\circ f_2\left(x \right) is also an involution over {\mathbb{F}}_q. In particular, a special class of involutions over some finite fields is determined completely.

Keywords

Permutation polynomial / involution / fixed point / non-fixed point

1 Introduction and main results

Let q be a prime power, {\mathbb{F}}_q be the finite field with q elements, and {\mathbb{F}}_q^{\ast } denote its multiplicative group. A polynomial f(x) \in {\mathbb{F}}_q [x] is called a permutation polynomial when the mapping defined by f:a\to f (a) is a one-by-one mapping from {\mathbb{F}}_q to itself. Moreover, f(x) is called an involution over {\mathbb{F}}_q if the compositional inverse of f(x) is also f(x)(i.e., for any x\in {\mathbb{F}}_q, f\circ f(x)=x). From the definition of the permutation polynomial, it's easy to see that for any given permutation polynomial f(x)\in {\mathbb{F}}_q[x], f(x) corresponds to an element f in the group Sym( {\mathbb{F}}_q). In particular, if f(x)\in {\mathbb{F}}_q[x] is an involution, then ord(f )=2. It's well-known that permutation polynomials are widely used in cryptography, coding theory and combinatorial designs, thus they are particularly important for constructing permutation polynomials with special properties. In many situations, both permutation polynomials and their compositional inverses are required (it’s well-known that a polynomial can be regarded as a function). Therefore, if both the permutation and its compositional inverse are efficient in terms of implementation, it is extremely convenient for practical applications. Especially, the involution with itself the composition inverse are widely used, such as in \mathrm{A}\mathrm{E}\mathrm{S}, \mathrm{P}\mathrm{R}\mathrm{I}\mathrm{N}\mathrm{C}\mathrm{E} [2], \mathrm{M}\mathrm{i}\mathrm{d}\mathrm{o}\mathrm{r}\mathrm{i} [1]. In \mathrm{A}\mathrm{E}\mathrm{S}, the permutation polynomial on {\mathbb{F}}_{2^8} used by S-box is an involution. In \mathrm{P}\mathrm{R}\mathrm{I}\mathrm{N}\mathrm{C}\mathrm{E}, a linear involution was used to construct the core cipher. More typically, in \mathrm{M}\mathrm{i}\mathrm{d}\mathrm{o}\mathrm{r}\mathrm{i}, the encryption and the decryption can be performed basing on non-linear involutions over linear spaces with minimal tweaks in the circuit. Recently, Canteaut and Roué [3] have shown that involutions are the best candidates against several cryptanalytic attacks by analyzing the behaviors of the permutation of an affine equivalent class with respect to these attacks. The involution over finite fields can also be used to design codes and construct Bent functions [7, 10]. For instance, Gallager [9] used an involution to update check nodes to obtain the low-complexity hardware implementation of the sum product algorithm which was used for decoding.

To the best of our knowledge, the known involutions over finite fields are a few. In 2016, Charpin et al. [5, 6] firstly studied the explicit expression of the involution, and gave a method to construct new involutions from known involutions by using the combination method and skills for discussing Dickson polynomials in the even characteristic field. In 2017, Castro et al. [4] gave a necessary and sufficient condition for a monomial with a specific number of fixed points to be an involution over finite fields. In 2018, Fu and Feng [8] investigated all of differentially 4-uniform permutations that are known in the literature and determined whether they can be involutory. In 2019, Zheng et al. [12] used the idea of cyclotomic polynomials to give several necessary and sufficient conditions for a special form of polynomials to be an involution. In 2020, Niu et al. [11] gave several necessary and sufficient conditions for another special form of polynomials to be an involution basing on the AGW criterion.

In this paper, basing on the work of Niu et al. and the relationship between the set of fixed points and the set of non-fixed points, we obtain a necessary and sufficient condition for that the composition of two involutions is also an involution. According to the property of an involution's truth table over {\mathbb{F}}_q, we can obtain involutions by using Lagrange Interpolation Formula. Regretly, basing on Lagrange Interpolation Formula, we only obtain an involution once a time and the calculation is complex. Using the necessary and sufficient condition in this paper, two new involutions can be obtained from a known involution by using Lagrangian Interpolation Formula only once.

For convenience, let A_f denote the set of fixed points of a polynomial f(x)\in {\mathbb{F}}_q[x].

Lemma 1.1 [11]　 Let f(x) be an involution over {\mathbb{F}}_q, | A_f|=n(n\in \mathbb{N}). Then q-n is even. In particularly, when q is odd, | A_f|\ge 1.

According to Lemma 1.1, if f(x) is an involution, then |{\mathbb{F}}_q-A_f| is even. Let

| {\mathbb{F}}_q-A_f|=2 h(h\in {\mathbb{Z}}^{+}) ,{\mathbb{F}}_q-A_f=\{{\alpha }_1,{\alpha }_2,\dots ,{\alpha }_h,{\beta }_1,{\beta }_2,\dots , {\beta }_h\}.

Because f(x) is an involution over {\mathbb{F}}_q, {\mathbb{F}}_q-A_f is the set of non-fixed points of f(x) over {\mathbb{F}}_q, we can set {\beta }_i=f({\alpha }_i)(i=1,2,\dots ,h) and ( {\alpha }_i: {\beta }_i)(i=1,2,\dots ,h ) be the 2-cycle (i.e., the transposition).

• Denote B_f=\{( {\alpha }_1: {\beta }_1),\dots ,({\alpha }_h:{\beta }_h)\}.

Based on the above results, and the relationship between the fixed points set and the non-fixed points set of two involutions over {\mathbb{F}}_q, we obtain a necessary and sufficient condition for that the composition of two involutions is also an involution, and then a special class of involutions is constructed, namely, we prove the following main results.

Theorem 1.1　 Let f_1(x), f_2(x)\in {\mathbb{F}}_q[ x] be involutions over {\mathbb{F}}_q. Then f_1\circ f_2(x) is an involution over {\mathbb{F}}_q if and only if for any x\in A_{f_1}, f_2(x)\in A_{f_1}, and for any (x:f_1( x))\in B_{f_1}, one of the following holds:

(1) x,f_1(x) \in A_{f_2};

(2) (x:f_1(x))\in B_{f_2};

(3) there exists some ( x_1:x_2) \in B_{f_1} such that (x:x_1 ),(f_1(x) :x_2)\in B_{f_2} and (x:x_1 )\ne (f_1(x) :x_2).

By the definition, we have A_{f_2}\subseteq A_{f_1} when B_{f_1}\subseteq B_{f_2}. And for any x\in A_{f_1}, if x\in A_{f_1}\cap A_{f_2}, then f_2(x)=x\in A_{f_2}\subseteq A_{f_1}; if x\in A_{f_1}-A_{f_2}, then (x:f_2 (x))\in B_{f_2}, note that x\in A_{f_1}, and so (x:f_2 (x))\notin B_{f_1}(i.e., x,f_2( x)\in A_{f_1}). Now we can get the following corollary by Theorem 1.1.

Corollary 1.1　 Let f_1(x), f_2(x)\in {\mathbb{F}}_q[ x] be involutions over {\mathbb{F}}_q and B_{f_1}\subseteq B_{f_2}. Then f_1\circ f_2(x) is an involution over {\mathbb{F}}_q.

On the other hand, if A_{f_1}=A_{f_2} and B_{f_1}=B_{f_2}, then f_1(x)= f_2(x), thus we have

Corollary 1.2　 Let f_1(x), f_2(x)\in {\mathbb{F}}_q[ x] be involutions over {\mathbb{F}}_q, and A_{f_1}=A_{f_2}, B_{f_1}=B_{f_2}. Then f_1\circ f_2(x) is an involution over {\mathbb{F}}_q, and for any x\in {\mathbb{F}}_q, f_1\circ f_2(x)= x.

Remark 1.1　From the group’s point of view, for f_1,f_2 \in Sym({\mathbb{F}}_q ), if ord(f_1)=or d(f_2)= 2. Then ord(f_1{f}_2)=2 if and only if f_1{f}_2=f_2{f}_1.

Theorem 1.1 can be used to judge whether f_1\circ f_2(x) is an involution according to the set of fixed points and the set of non-fixed points of two involutions f_1(x),f_2(x); Remark 1.1 can be used to judge whether f_1\circ f_2(x) is an involution according to f_1\circ f_2(x)= f_2\circ f_1(x) or not. When the fixed points set and the non-fixed points set of two involutions are determined, it's more convenient to judge whether f_1\circ f_2(x) is an involution by Theorem 1.1; when the explicit formulas of two involutions are determined, it's more convenient to judge whether f_1\circ f_2(x) is an involution by Remark 1.1.

For f_3(x)=f_1\circ f_2(x), if f_1(x)=x or f_2(x)=x, then f_3(x)=f_2(x) or f_3(x)=f_1(x) correspondingly; if f_1(x)\ne x and f_2(x)\ne x, then f_3(x)\ne f_1(x) and f_3(x)\ne f_2(x). According to Theorem 1.1, f_3(x) is a new involution over {\mathbb{F}}_q.

Corollary 1.3

A_{f_3}=A_{f_1} \cap A_{f_2}\cup \{\alpha | \mathrm{\exists }\beta \in {\mathbb{F}}_q ,(\alpha :\beta )\in B_{f_1}\cap B_{f_2}\},

B_{f_3}=\{( \alpha :f_3(\alpha ))| \alpha \in {\mathbb{F}}_q-A_{f_3}\}.

For some special q and special involutions f_1(x),f_2(x)\in {\mathbb{F}}_q, the number of the involution f_1\circ f_2(x) over {\mathbb{F}}_q can be accurately calculated. Let's consider the involutions of the following form

f_i(x)= f_{r,a_i,b_i}(x) =\frac{a_i-b_i}{2}{x}^{\frac{q-1}{2}+r}+\frac{a_i+b_i}{2}{x}^r\in {\mathbb{F}}_q[x] (f_i(x)\ne x, i=1,2 ),

where \frac{1}{2} is viewed as the inverse of 2 modulo q-1 if q is even.

Corollary 1.4　(1) There are exactly 26 involutions in the formf_1\circ f_2(x)over{\mathbb{F}}_7listed inTab.1.

(2) There are exactly 158 involutions in the form f_1\circ f_2(x) over {\mathbb{F}}_{13} listed in Tab.2.

2 Proofs for main results

Proof for Theorem 1.1　We prove the necessity first. For any x\in {\mathbb{F}}_q, there are two cases because of {\mathbb{F}}_q=A_{f_1}\dot{\cup }({\mathbb{F}}_q -A_{f_1})=A_{f_2}\dot{\cup }({\mathbb{F}}_q -A_{f_2}).

Case 1　For any x\in A_{f_1}, since f_1\circ f_2(x) is an involution over {\mathbb{F}}_q, we have

f_1\circ f_2\circ f_1\circ f_2(x)= x.

Note that A_{f_1} is the set of fixed points of f_1(x), so we have f_2\circ f_1\circ f_2(x)=x. Note that f_2(x) is also an involution over {\mathbb{F}}_q, so we have f_1\circ f_2(x)=f_2(x) and

f_2(x)\in A_{f_1}.

Case 2　For x\in {\mathbb{F}}_q-A_{f_1}, it's easy to show that f_1(x)\in {\mathbb{F}}_q-A_{f_1} and (x:f_1 (x))\in B_{f_1}.

(1) For the case

x,f_1 (x)\in A_{f_2},

the conclusion is immediately.

(2) For the case x\in A_{f_2} and f_1(x)\notin A_{f_2}, there exists some x {}^{\prime }\in {\mathbb{F}}_q-A_{f_2} such that x{}^{\prime }\ne f_1(x) and ( f_1(x): x{}^{\prime }) \in B_{f_2}. So

f_1\circ f_2\circ f_1\circ f_2(x)= f_1\circ f_2\circ f_1(x)= f_1(x{}^{\prime }).

Since f_1\circ f_2(x) is an involution over {\mathbb{F}}_q, f_1\circ f_2\circ f_1\circ f_2(x)=x, which means f_1(x{}^{\prime })=x. Note that f_1(x) is an involution over {\mathbb{F}}_q, so x{}^{\prime }=f_1(x), which contradicts to the fact x{}^{\prime }\ne f_1(x). Similarly, x\notin A_{f_2} and f_1(x)\in A_{f_2} are both not true.

(3) For the case x,f_1(x)\notin A_{f_2}, it's easy to see that x,f_1( x)\in {\mathbb{F}}_q-A_{f_2}.

(i) If

(x:f_1(x)) \in B_{f_2},

then the conclusion is true.

(ii) If there exist some x_1,x_2\in {\mathbb{F}}_q-A_{f_2} such that (x:x_1 ),(f_1(x) :x_2)\in B_{f_2} and (x:x_1) \ne (f_1(x ):x_2), then we can conclude (x_1 :x_2)\in B_{f_1}.

In fact, since f_1\circ f_2(x) is an involution over {\mathbb{F}}_q, if x_1\in A_{f_1}, then we can get

x=f_1\circ f_2\circ f_1\circ f_2(x)=f_1\circ f_2\circ f_1(x_1)= f_1\circ f_2(x_1)=f_1(x),

which means x\in A_{f_1}. This contradicts to the fact x\in {\mathbb{F}}_q-A_{f_1}. Similarly, x_2\notin A_{f_1}. Thus we have x_1,x_2 \in {\mathbb{F}}_q -A_{f_1}.

Noting that any two elements in {\mathbb{F}}_q-A_{f_1} can form a transposition, there exist some x_3,x_4\in {\mathbb{F}}_q-A_{f_1} such that ( x_1:x_3) , (x_2:x_4 )\in B_{f_1}. On the one hand, since f_1\circ f_2(x) is an involution over {\mathbb{F}}_q, we have

x=f_1\circ f_2\circ f_1\circ f_2(x)=f_1\circ f_2\circ f_1(x_1)= f_1\circ f_2(x_3).

Since f_1(x),f_2(x) are both involutions over {\mathbb{F}}_q, we can use f_1 to act on both sides of the formula above to get f_2(x_3) =f_1(x) first, and then use f_2 to act on both sides to get f_2\circ f_1(x)= x_3. On the other hand, since (f_1(x):x_2) is a transposition and (f_1(x):x_2)\in B_{f_2}, we can get f_2\circ f_1(x)=x_2 and x_3=x_2. Similarly, we have x_4=x_1. And so

(x_1:x_2 )\in B_{f_1}.

Next, we prove the sufficiency. Noting that {\mathbb{F}}_q=A_{f_1}\dot{\cup }({\mathbb{F}}_q -A_{f_1}), for any x\in {\mathbb{F}}_q, there are two cases.

Case 1　For the case x\in A_{f_1}, noting that f_2(x)\in A_{f_1} and f_2(x)\in {\mathbb{F}}_q is an involution over {\mathbb{F}}_q, we can get

(2.1)\begin{array}{l}{f}_1\circ f_2\circ f_1\circ f_2(x)=f_1\circ f_2\circ f_2(x)=f_1(x)=x.\end{array}

Case 2　For the case x\in {\mathbb{F}}_q-A_{f_1}, we have f_1(x)\in {\mathbb{F}}_q-A_{f_1} and (x:f_1 (x))\in B_{f_1}.

(1) For x,f_1(x)\in A_{f_2}, noting that f_1(x)\in {\mathbb{F}}_q is an involution over {\mathbb{F}}_q and A_{f_2} is the set of fixed points of f_2(x) over {\mathbb{F}}_q, we can get

(2.2)\begin{array}{l}{f}_1\circ f_2\circ f_1\circ f_2(x)=f_1\circ f_2\circ f_1(x)=f_1\circ f_1(x)=x.\end{array}

(2) For (x:f_1( x))\in B_{f_2}, noting that f_1(x),f_2(x)\in {\mathbb{F}}_q[x] are both involutions over {\mathbb{F}}_q and f_2(x)=f_1(x), we can get

(2.3)\begin{array}{l}{f}_1\circ f_2\circ f_1\circ f_2(x)=f_1\circ f_2\circ f_1\circ f_1(x)=f_1\circ f_2(x)=f_1\circ f_1(x)=x.\end{array}

(3) If there exists some (x_1:x_2 )\in B_{f_1} such that (x:x_1 ),(f_1(x) :x_2)\in B_{f_2} and (x:x_1) \ne (f_1(x ):x_2), then

(2.4)\begin{array}{l}{f}_1\circ f_2\circ f_1\circ f_2(x)=f_1\circ f_2\circ f_1(x_1)=f_1\circ f_2(x_2)=f_1\circ f_1(x)=x.\end{array}

Now from (2.1)-(2.4), for any x\in {\mathbb{F}}_q, f_1\circ f_2\circ f_1\circ f_2(x)= x. And then f_1\circ f_2(x) is an involution over {\mathbb{F}}_q by the definition.

3 Examples

In this section, we give some examples to further check Theorem 1.1. Example 3.1 is for the case q=7; Examples 3.2−3.4 are for the case q=13; Example 3.5 is for the case q=2^3.

For convenience, we first give the following

Lemma 3.1 [12]　 Let a,b\in {\mathbb{F}}_q ,r\in {\mathbb{Z}}^{+} ,f_{r,a,b}(x) =\frac{a-b}{2}{x}^{\frac{q-1}{2}+r}+\frac{a+b}{2}{x}^r\in {\mathbb{F}}_q[x]. Then f_{r,a,b}(x) is an involution over {\mathbb{F}}_q if and only if the following conditions are true simultaneously.

(1) r^2\equiv 1 (\mathrm{mod} \frac{q-1}{2});

(2) \frac{a-b}{2}{a}^{\frac{q-1}{2}+r}+ \frac{a+b}{2}{a}^r =1;

(3) (-1{)}^r\frac{a-b}{2}{b}^{\frac{q-1}{2}+r}+\frac{a+b}{2}{b}^r= (-1 {)}^{\frac{2(r^2-1)}{q-1}}.

From Lemma 3.1, we have the following two corollaries.

Corollary 3.1　 For q=13, f_{r,a,b}( x) is an involution over {\mathbb{F}}_{13} if and only if r, a, b are given as follows:

And the corresponding truth table is asTable 3.

Corollary 3.2　 For q=7, f_{r,a,b}( x) is an involution over {\mathbb{F}}_7 if and only if r, a, b are given as follows:

And the corresponding truth table is listed in Tab.6.

Example 3.1　Let f_1(x)=4x^5+3x^4+4 x^2+4 x. Then the truth table of f_1(x) is as follows.

From the truth table, we can show that f_1(x) is an involution over {\mathbb{F}}_7 and

A_{f_1}=\{0, 1,3,- 2,-1,\}, B_{f_1}=\{(2: -3)\}.

Let f_2(x)=x^5. Then the truth table of f_2(x) is as follows.

From the truth table, we know that f_2(x) is an involution over {\mathbb{F}}_7 and

A_{f_2}=\{0, 1,-1\},B_{f_2}=\{(2: -3),(3: -2)\}.

On the one hand, from f_1\circ f_2(x)= x^5(4x^5 +3x^3+4x^2+4) and the following truth table, we know that f_1\circ f_2(x) is an involution over {\mathbb{F}}_7.

On the other hand, \mathrm{f}\mathrm{r}\mathrm{o}\mathrm{m}

A_{f_1}=\{0, 1,3,- 2,-1,\}, B_{f_1}=\{(2: -3)\},

A_{f_2}=\{0, 1,-1\},B_{f_2}=\{(2: -3),(3: -2)\},

we can get

B_{f_1}\subseteq B_{f_2}.

Now by Corollary 1.1, f_1\circ f_2(x) is an involution over {\mathbb{F}}_7.

Example 3.2　Let f_1(x)=5x^{11}+10x^{10}+ 4x^9+ 2x^8+ 4x^7+ 7x^5+ 2x^4+ 8x^3+ 7x^2+ 7x. Then the truth table of f_1(x) is as follows.

From the truth table, we can show that f_1(x) is an involution over {\mathbb{F}}_{13} and

A_{f_1}=\{0, 5,-5,6,-4 ,-2,-1\},B_{f_1}=\{(1 :4), (2:- 6),(3:- 3)\}.

Let f_2(x)=x^5(\frac{5}{2}{x}^6+\frac{3}{2})=9 x^{11}+8x^5. Then the truth table of f_2(x) is as follows.

From the truth table, we know that f_2(x) is an involution over {\mathbb{F}}_{13} and

A_{f_2}=\{0\}, B_{f_2}=\{( 1:4) ,(2: -6),(3: 3),(5:- 5),(6:- 2),(-4: -1)\}.

On the one hand, from f_1\circ f_2(x)= x^5(11x^{11}+ 5x^{10}+6x^9+7 x^8+4 x^6+3 x^5+9 x^4+11 x^3+9 x^2+1 ) and the following truth table, we know that f_1\circ f_2(x) is an involution over {\mathbb{F}}_{13}.

On the other hand, \mathrm{f}\mathrm{r}\mathrm{o}\mathrm{m}

A_{f_1}=\{0, 5,-5,6,-4 ,-2,-1\},B_{f_1}=\{(1 :4), (2:- 6),(3:- 3)\},

A_{f_2}=\{0\}, B_{f_2}=\{( 1:4) ,(2: -6),(3: 3),(5:- 5),(6:- 2),(-4: -1)\},

we can get

B_{f_1}\subseteq B_{f_2}.

Now by Corollary 1.1, f_1\circ f_2(x) is an involution over {\mathbb{F}}_{13}

Example 3.3　Let f_1(x)=9x^7+11x. Then the truth table of f_1(x) is as follows.

From the truth table, we can show that f_1(x) is an involution over {\mathbb{F}}_{13} and

A_1=\{0\}, B_{f_1}=\{( 1:-6),( 2:4) ,(3: -5),(5: -3),(6: -1),(-4:-2)\} .

Let f_2(x)=x^7. Then the truth table of f_2(x) is as follows.

From the truth table, we know that f_2(x) is an involution over {\mathbb{F}}_{13} and

A_{f_2}=\{0, 1,3,4 ,-4,-3,-1\}, B_{f_2}=\{(2: -2),(5: -5),(6: -6)\}.

On the one hand, from f_1\circ f_2(x)= x^7(9x^6 +11) and the following truth table, we know that f_1\circ f_2(x) is a permutation polynomial over {\mathbb{F}}_{13}, but not an involution over {\mathbb{F}}_{13}.

On the other hand, \mathrm{f}\mathrm{r}\mathrm{o}\mathrm{m}

A_{f_1}=\{0\}, B_{f_1}=\{( 1:-6),( 2:4) ,(3: -5),(5: -3),(6: -1),(-4:-2)\} ,

A_{f_2}=\{0, 1,3,4 ,-4,-3,-1\}, B_{f_2}=\{(2: -2),(5: -5),(6: -6)\},

we know that f_1\circ f_2(x) is not an involution over {\mathbb{F}}_{13} by Theorem 1.1.

Example 3.4　Let f_1(x)=4x^7-2x. Then the truth table of f_1(x) is as follows.

From the truth table, we can show that f_1(x) is an involution over {\mathbb{F}}_{13} and

A_{f_1}=\{0\}, B_{f_1}=\{( 1:2) ,(3: 6),(4:- 5),(5:- 4),(-6: -3),(-1:-2)\} .

Let f_2(x)=5 x^{11}. Then the truth table of f_2(x) is as follows.

From the truth table, we know that f_2(x) is an involution over {\mathbb{F}}_{13} and

A_{f_2}=\{0\}, B_{f_2}=\{( 1:5) ,(2: -4),(3: 6),(4:- 2),(-6: -3),(-5:-1)\} .

On the one hand, from f_1\circ f_2(x)= 3x^{11}+6x^5 and the following truth table, we know that f_1\circ f_2(x) is an involution over {\mathbb{F}}_{13}.

On the other hand, \mathrm{f}\mathrm{r}\mathrm{o}\mathrm{m}

A_{f_1}=\{0\}, B_{f_1}=\{( 1:2) ,(3: 6),(4:- 5),(5:- 4),(-6: -3),(-1:-2)\} ,

A_{f_2}=\{0\}, B_{f_2}=\{( 1:5) ,(2: -4),(3: 6),(4:- 2),(-6: -3),(-5:-1)\} ,

we know that f_1\circ f_2(x) is an involution over {\mathbb{F}}_{13} by Theorem 1.1.

Example 3.5　Let \gamma \in {\mathbb{F}}_{2^3} be a primitive element of {\mathbb{F}}_{2^3}. Then the minimum polynomial of \gamma over {\mathbb{F}}_2 is x^3+x+1, and {\gamma }^3=\gamma +1.

Let f_1(x)={\gamma }^6{x}^6+{\gamma }^4{x}^5+{\gamma }^2{x}^3+{\gamma }^4. Then the truth table of f_1(x) is as follows.

From the truth table, we can show that f_1(x) is an involution over {\mathbb{F}}_{2^3} and

A_{f_1}=\{1, \gamma \},B_{f_1}=\{(0 :{\gamma }^4),( {\gamma }^2: {\gamma }^3),({\gamma }^5:{\gamma }^6) \}.

Let f_2(x)=\gamma x^6. Then the truth table of f_2(x) is as follows.

From the truth table, we know that f_2(x) is an involution over {\mathbb{F}}_{2^3} and

A_{f_2}=\{0, {\gamma }^4\}, B_{f_2}=\{( 1:\gamma ),({\gamma }^2:{\gamma }^6) ,({\gamma }^3:{\gamma }^5)\}.

On the one hand, from f_1\circ f_2(x)= {\gamma }^5{x}^4+{\gamma }^2{x}^2+{\gamma }^{5}x+{\gamma }^4 and the following truth table, we know that f_1\circ f_2(x) is an involution over {\mathbb{F}}_{2^3}.

On the other hand, \mathrm{f}\mathrm{r}\mathrm{o}\mathrm{m}

A_{f_1}=\{1, \gamma \},B_{f_1}=\{(0 :{\gamma }^4),( {\gamma }^2: {\gamma }^3),({\gamma }^5:{\gamma }^6) \},

A_{f_2}=\{0, {\gamma }^4\}, B_{f_2}=\{( 1:\gamma ),({\gamma }^2:{\gamma }^6) ,({\gamma }^3:{\gamma }^5)\},

we know that f_1\circ f_2(x) is an involution over {\mathbb{F}}_{2^3} by Theorem 1.1.

References

[1] BanikSBogdanov AIsobeT, . Midori: A block cipher for low energy. In: Advances in Cryptology—ASIACRYPT 2015, Part II, Lecture Notes in Comput Sci, Vol 9453. Heidelberg: Springer, 2015, 411–436

[2] BorghoffJCanteaut AGüneysuT, . PRINCE—a low-latency block cipher for pervasive computing applications. In: Advances in Cryptology—ASIACRYPT 2012, Lecture Notes in Comput Sci, Vol 7658. Heidelberg: Springer, 2012, 208–225

[3] CanteautARoué J. On the behaviors of affine equivalent S-boxes regarding differential and linear attacks. In: Advances in Cryptology—EUROCRYPT 2015, Part I, Lecture Notes in Comput Sci, Vol 9056. Heidelberg: Springer, 45–74

[4] Castro F N, Corrada-Bravo C, Pacheco-Tallaj N. . Explicit formulas for monomial involutions over finite fields. Adv Math Commun 2017; 11(2): 301–306

[5] CharpinPMesnager SSarkarS. Dickson polynomials that are involutions. In: Contemporary Developments in Finite Fields and Applications. Hackensack, NJ: World Sci Publ, 2016, 22: 22–47

[6] Charpin P, Mesnager S, Sarkar S. Involutions over the Galois field F2n. IEEE Trans Inform Theory 2016; 62(4): 2266–2276

[7] Coulter R S, Mesnager S. Bent functions from involutions over F2n. IEEE Trans Inform Theory 2018; 64(4): part 2, 2979–2986

[8] Fu S H, Feng X T. Involutory differentially 4-uniform permutations from known constructions. Des Codes Cryptogr 2019; 87(1): 31–56

[9] Gallager R G. Low-density parity-check codes. IRE Trans Inform Theory 1962; 8(1): 21–28

[10] MesnagerS. On constructions of bent functions from involutions. In: 2016 IEEE International Symposium on Information Theory, IEEE, 2016: 110–114.

[11] Niu TL, Li K Q, Qu L J. . New constructions of involutions over finite fields. Cryptogr Commun 2020; 12(2): 165–185

[12] Zheng D B, Yuan M, Li N. . Constructions of involutions over finite fields. IEEE Trans Inform Theory 2019; 65(12): 7876–7883

RIGHTS & PERMISSIONS

Higher Education Press 2022