A note on “Cryptographically strong permutations from the butterfly structure”

Abstract

Very recently, a class of cryptographically strong permutations with boomerang uniformity 4 and the best known nonlinearity is constructed from the closed butterfly structure in Li et al. (Des Codes Cryptogr 89(4):737–761, 2021). In this note, we provide two additional results concerning these permutations. We first represent the conditions of these permutation obtained in Li et al. (Des Codes Cryptogr 89(4):737–761, 2021) in a much simpler form, and then show that they are linear equivalent to Gold functions. We also prove a criterion for solving a new type of equations over finite fields, which is useful and may be of independent interest.

1 Introduction

1.1 Background

As a generalization of Dillon’s APN permutation in dimension six, butterfly structure was initially proposed by Perrin et al. [14] to generate 2m-bit mappings by concatenating two bivariate functions over ${{\mathbb {F}}}_{2^m}$. Canteaut et al. [3] further studied this structure and generalized it as below. Let R(x, y) be a bivariate polynomial on ${{\mathbb {F}}}_{2^m}$ such that $R_{y}:x \mapsto R(x,y)$ is a permutation of ${{\mathbb {F}}}_{2^m}$ for any $y \in {{\mathbb {F}}}_{2^m}$. The closed butterfly is the function $V_R: {{\mathbb {F}}}_{2^m}\times {{\mathbb {F}}}_{2^m}\rightarrow {{\mathbb {F}}}_{2^m}\times {{\mathbb {F}}}_{2^m}$ defined by

$$\begin{aligned} V_{R}(x,y)=\left( R(x,y),R(y,x)\right) , \end{aligned}$$

(1.1)

and the open butterfly is the function $H_{R}: {{\mathbb {F}}}_{2^m}\times {{\mathbb {F}}}_{2^m}\rightarrow {{\mathbb {F}}}_{2^m}\times {{\mathbb {F}}}_{2^m}$ defined by

$$\begin{aligned} H_{R}(x,y)=\left( R\left( y,R_{y}^{-1}(x)\right) ,R_{y}^{-1}(x)\right) , \end{aligned}$$

where $R_{y}^{-1}$ is the compositional inverse of $R_{y}$. It is known that $H_{R}$ is always an involution (and hence a permutation) and the two functions $H_{R}$ and $V_{R}$ are CCZ-equivalent, so they share the same differential uniformity, nonlinearity and Walsh spectrum [3].

Let m, k be positive integers such that m is odd and $\gcd (k,m)=1$. Extending previous work [3, 5], Li et al. [11] considered a general bivariate polynomial R(x, y) of the form

$$\begin{aligned} R(x,y)=(x+\alpha y)^{2^k+1}+\beta y^{2^k+1} \end{aligned}$$

for any $\alpha ,\beta \in {{\mathbb {F}}}_{2^m}^*:={{\mathbb {F}}}_{2^m}\backslash \{0\}$ and proved that the corresponding butterflies $H_R$ and $V_R$ are differentially 4-uniform and have the best known nonlinearity when $\beta \ne (\alpha +1)^{2^k+1}$. Under this condition, however, the closed butterfly $V_R$ may not be a permutation.

Since $\gcd (2^k+1,2^m-1)=1$, any $\beta \in {{\mathbb {F}}}_{2^m}^*$ can be written as $\beta =\beta _1^{2^k+1}$ for some $\beta _1\in {{\mathbb {F}}}_{2^m}^*$. So equivalently, the general bivariate polynomial R(x, y) may be written as

$$\begin{aligned} R(x,y)=\left( x+\alpha y\right) ^{2^k+1}+\left( \beta y\right) ^{2^k+1}, \quad \alpha , \beta \in {{\mathbb {F}}}_{2^m}^*. \end{aligned}$$

(1.2)

In an interesting recent paper [8], the authors not only provided conditions under which the closed butterfly $V_R$ is a permutation, but also proved that under these conditions the boomerang uniformity of $V_R$ is 4, a new and important cryptographic property which was discovered to be useful in analyzing the boomerang attack. Interested readers may refer to [2, 4, 17] for more details. These functions $V_R$ may be considered as the sixth known family of permutations with boomerang uniformity 4 over the field $\mathbb {F}_{2^{2m}}$ in the literature. Observe that for R(x, y) given in (1.2), if k is even, letting $k':=m-k$, then $k'$ is odd and $\gcd (k',m)=1$. It is easy to see that for any $x,y, \alpha , \beta \in {{\mathbb {F}}}_{2^m}$ we have

$$\begin{aligned} R(x,y)^{2^{k'}}= \left( x+\alpha y\right) ^{2^{k'}+1}+\left( \beta y\right) ^{2^{k'}+1}. \end{aligned}$$

So the case of k being even is equivalent to that of $k'$ which is odd now. For this reason, using the new definition of R(x, y) in (1.2), we may state the main result of [8] as follows:

Theorem 1

[8, Theorem 1] Let m, k be odd with $\gcd (m,k)=1$ and $q=2^m$. The closed butterfly function $V_R(x,y)$ given by (1.1) where the function R(x, y) is given in (1.2) permutes ${{\mathbb {F}}}_{q}^2$ and has boomerang uniformity 4 if $(\alpha ,\beta )$ is taken from the following set

$$\begin{aligned} \Gamma =\left\{ (\alpha ,\beta ) \in {{\mathbb {F}}}_{q}^* \times {{\mathbb {F}}}_{q}^*: \varphi _2^{2^k}=\varphi _1 \varphi _3^{2^k-1} \text{ and } \varphi _3 \ne 0\right\} , \end{aligned}$$

(1.3)

where $\varphi _1,\varphi _2,\varphi _3$ are given by

$$\begin{aligned} \left\{ \begin{array}{l} \varphi _1=(\alpha +1)^{2^{k+1}+2}+\alpha ^{2^k+2}+\alpha ^{2^k}+\alpha \beta ^{2^k+1}+\beta ^{2^{k+1}+2}, \\ \varphi _2=(\alpha +1)^{2^{k+1}+2}+\alpha ^{2^{k+1}+1}+\alpha +\alpha ^{2^k} \beta ^{2^k+1}+\beta ^{2^{k+1}+2}, \\ \varphi _3=(\alpha +1)^{2^{k+1}+2}+\beta ^{2^{k+1}+2}. \end{array}\right. \end{aligned}$$

(1.4)

Two natural questions arise from Theorem 1. First, the set $\Gamma$ given in (1.3) looks quite complicated. Is there a simpler way to represent $\Gamma$? Second, two functions F and $F^\prime$ over ${{\mathbb {F}}}_{2^n}$ are called linear (resp. affine) equivalent if $F=A_1\circ F^\prime \circ A_2$ holds for some linear (resp. affine) permutations $A_{1}$ and $A_{2}$ over ${{\mathbb {F}}}_{2^n}$. It was observed in [8] by numerical computation that when $m=3,5$ and $(\alpha , \beta ) \in \Gamma$, the closed butterfly function $V_R(x,y)$ is affine equivalent to the Gold function. Is this true in general? In this note, we answer these two questions.

1.2 Statement of the main results

Theorem 2

Let m, k be odd integers with $\gcd (m,k)=1$.

• (1) $\left( \alpha ,\beta \right) \in \Gamma$ if and only if $\alpha , \beta \in {{\mathbb {F}}}_{2^m}^*$ satisfy $\alpha ^2+\beta ^2+\alpha \beta +1=0$.

• (2) If $(\alpha ,\beta ) \in \Gamma$, then the closed butterfly function $V_R(x,y)$ over ${{\mathbb {F}}}_{2^m}^2$ given in (1.1) is linear equivalent to the Gold function $x^{2^{k-m}+1}$ over $\mathbb {F}_{2^{2m}}$.

Remark 1

According to [8, Conjecture 19], the closed butterfly $V_R$ is a permutation with boomerang uniformity 4 if and only if $(\alpha , \beta ) \in \Gamma$. Hence if this conjecture is true, then Theorem 2 shows that all closed butterfly functions $V_R$ which are permutations with boomerang uniformity 4 are linear equivalent to the Gold function. We also remark that [8, Conjecture 19] is a consequence of a much more general conjecture concerning permutation properties of general quadrinomials of the form (3.2) in [10, Sect. VI]. This conjecture has been proved to be true for $k=1$ in [7] but remains open for $k>1$.

Remark 2

It seems fitting to summarize here what we have known about the open butterfly function $H_R$. The setting is the same as in Theorem 2.

• (1) $H_R$ is always an involution (and hence a permutation) and the two functions $H_R$ and $V_R$ are CCZ-equivalent, so they share the same differential uniformity, nonlinearity and Walsh spectrum. The open butterfly function $H_R$ is particularly interesting. Interested readers may refer to [3, 5, 11] for some of their cryptographic properties.

• (2) Theorem 2 shows that $H_R$ is CCZ-equivalent to the Gold function $x^{2^{k-m}+1}$ when $(\alpha , \beta ) \in \Gamma$. Experimental results show however that for $m=3$, $H_R$ is not EA-equivalent to general Gold functions when $(\alpha ,\beta ) \in \Gamma$.

• (3) When $(\alpha , \beta ) \notin \Gamma$, experimental results show that for $m=3,5$, $H_R$ (and also $V_R$) is CCZ-inequivalent to general Gold functions.

• (4) As for the boomerang uniformity of $H_R$, experimental results show that for $m=3$, the boomerang uniformity of $H_R$ is at least 12 for any $(\alpha ,\beta ) \in \mathbb {F}_{2^3}^2$, except when $H_R$ becomes APN, which are CCZ-equivalent to the only known APN permutation over $\mathbb {F}_{2^6}$. It was known that $H_R$ is not APN whenever $m >3$.

Next, in view of [8] and [10], there is no need to publish the arxiv paper [9], which proved essentially the same result as [8]. Instead we take this opportunity to present from [9] a criterion for solving a new type of equations over finite fields. We believe this criterion is useful and is of independent interest. In fact it played an essential role in the proofs of [10], which substantially extends the work [8, 15, 16]. A special case of this criterion for $k=1$ has appeared in [15]. Similar criteria were well-known in the literature for equations over finite fields such as $x^2+ax+b=0$ [12], $x^{2^k+1}+x+a=0$ [6] and $x^{q+1}+ax+b=0$ [1].

Theorem 3

Let m, k be odd integers with $\gcd (k,m)=1$ and $n=2m$. For any $\mu ,\nu \in {{\mathbb {F}}}_{2^n}$, define

$$\begin{aligned} L_{\mu ,\nu }(x)=x^{2^k}+\mu {\overline{x}}+(\mu +1)x+\nu . \end{aligned}$$

Here ${\overline{x}}=x^{2^m}$ for any $x \in {{\mathbb {F}}}_{2^n}$. Then the equation $L_{\mu ,\nu }(x)=0$ has either 0, 2 or 4 solutions in ${{\mathbb {F}}}_{2^n}$. More precisely, let $\xi , \Delta \in {{\mathbb {F}}}_{2^m}$ and $\lambda \in {{\mathbb {F}}}_{2^n}$ be defined by the equations

$$\begin{aligned} \xi ^{2^k-1}=1+\mu +{\overline{\mu }},\;\;\; \Delta =\frac{\nu +{\overline{\nu }}}{\xi ^{2^k}},\;\;\; \lambda ^{2^k}+\lambda =\mu \xi . \end{aligned}$$

(1.5)

Then

• (1) $L_{\mu ,\nu }(x)=0$ has two solutions in ${{\mathbb {F}}}_{2^n}$ if and only if one of the following conditions is satisfied:

  • (i) $1+\mu +{\overline{\mu }}=0$ and $\sum _{i=0}^{m-1}(\mu ^{2^k}(\nu +{\overline{\nu }})+\nu ^{2^k})^{2^{ki}}=\nu +{\overline{\nu }}$;

  • (ii) $1+\mu +{\overline{\mu }}\ne 0$, $\mathrm{{Tr}}_{1}^{m}(\Delta )=0$ and ${\overline{\lambda }}+\lambda =\xi +1$.

• (2) $L_{\mu ,\nu }(x)=0$ has four solutions in ${{\mathbb {F}}}_{2^n}$ if and only if

  $$\begin{aligned}1+\mu +{\overline{\mu }}\ne 0, \mathrm{{Tr}}_{1}^{m}(\Delta )=0, {\overline{\lambda }}+\lambda =\xi , \text{ and } \mathrm{{Tr}}_{1}^{n}(\frac{\lambda ^{2^k}{\overline{\nu }}}{\xi ^{2^k}})=0.\end{aligned}$$

• (3) If $\nu =0, 1+\mu +{\overline{\mu }} \ne 0$ and $\lambda +{\overline{\lambda }}=\xi$, then $L_{\mu ,\nu }(x)=0$ has four solutions in ${{\mathbb {F}}}_{2^n}$, and these four solutions are $0,1,\lambda , \lambda +1$.

We remark that Theorem 3 can be used to study the number of solutions of equations of the form $c_1 x^{2^k+1}+c_2 {\bar{x}}^{2^k+1}+c_3 x^{2^k} x^{2^m}+c_4 x x^{2^{m+k}}$ over $\mathbb {F}_{2^{2m}}$, where m, k are odd, $\gcd (m,k)=1$ and $c_1, c_2, c_3, c_4 \in \mathbb {F}_{2^{2m}}$.

This note is organized as follows: we prove (1) and (2) of Theorem 2 in Sects. 2 and 3 respectively; we prove Theorem 3 in Sect. 4. Finally we conclude this note in Sect. 5.

2 Proof of part (1) of Theorem 2

To simplify our computation a little bit, we use

$$\begin{aligned} \alpha \mapsto \alpha +1, \quad \sigma :=2^k. \end{aligned}$$

Under this new $\alpha$ and symbol $\sigma$, we can rewrite $\varphi _1,\varphi _2$ and $\varphi _3$ as

$$\begin{aligned} \left\{ \begin{array}{l} \varphi _1=\alpha ^2(1+\alpha +\alpha ^2)^{\sigma }+\beta ^{\sigma +1}\left( \beta ^{\sigma +1}+\alpha +1\right) , \\ \varphi _2=\alpha ^{2\sigma }(1+\alpha +\alpha ^2)+\beta ^{\sigma +1}\left( \beta ^{\sigma +1}+\alpha ^{\sigma }+1\right) , \\ \varphi _3=\left( \alpha ^{\sigma +1}+\beta ^{\sigma +1}\right) ^2. \end{array}\right. \end{aligned}$$

(2.1)

Now assume

$$\begin{aligned} \alpha ,\beta \in {{\mathbb {F}}}_{2^m}, \alpha \ne 1, \beta \ne 0. \end{aligned}$$

(2.2)

To prove (1) of Theorem 2, it is equivalent to proving

$$\begin{aligned} \varphi _3 \ne 0, \varphi _2^{\sigma }\varphi _3+\varphi _1 \varphi _3^{\sigma }=0 \mathrm{\;if\; and\; only\; if\;} \alpha ^2+\beta ^2+(1+\alpha )\beta =0. \end{aligned}$$

(2.3)

It is easy to see that $\varphi _3 \ne 0$ if and only if $\alpha \ne \beta$. Denote

$$\begin{aligned} F:=\varphi _2^{\sigma }\varphi _3+\varphi _1 \varphi _3^{\sigma }. \end{aligned}$$

Plugging the values of $\varphi _1,\varphi _2,\varphi _3$ from (2.1) into F, expanding and then collecting common terms, we can obtain

$$\begin{aligned} F= & {} \alpha ^2(1+\alpha )^{\sigma }\beta ^{2\sigma ^2+2\sigma }+(1+\alpha ) \beta ^{2\sigma ^2+3 \sigma +1}+(1+\alpha )^{\sigma ^2} \beta ^{\sigma ^2+3 \sigma +2} +\\&\alpha ^{2\sigma +2}(1+\alpha )^{\sigma ^2}\beta ^{\sigma ^2+\sigma }+ \alpha ^{2\sigma ^2}(1+\alpha )^{\sigma }\beta ^{2 \sigma +2}+\alpha ^{2\sigma ^2+2 \sigma }(1+\alpha ) \beta ^{\sigma +1}. \end{aligned}$$

Denote

$$\begin{aligned} Y=\alpha ^2+\beta ^2+(\alpha +1) \beta . \end{aligned}$$

(2.4)

The right hand side of F above can be further simplified, and we have

$$\begin{aligned} F=\beta ^{\sigma }\left( \varphi _3 Y^{\sigma ^2}+\left( \alpha \beta ^{\sigma ^2}+\beta \alpha ^{\sigma ^2} \right) ^2Y^{\sigma }+\varphi _3^{\sigma } Y\right) . \end{aligned}$$

(2.5)

Now suppose $Y=0$. It is clear that $F=0$. Moreover, if $\alpha =\beta$, then from $Y=0$ we have $\alpha =1$ or $\beta =0$, contradicting (2.2). So $\alpha \ne \beta$ and hence $\varphi _3 \ne 0$ as $\alpha , \beta$ satisfy (2.2).

On the other hand, suppose $F=0$ and $\alpha \ne \beta$. Since $\beta \ne 0$, we have

$$\begin{aligned} \varphi _3 Y^{\sigma ^2}+\left( \alpha \beta ^{\sigma ^2}+\beta \alpha ^{\sigma ^2}\right) ^2Y^{\sigma }+\varphi _3^{\sigma } Y=0. \end{aligned}$$

(2.6)

To study (2.6), we quote a result of Bluher:

Lemma 1

[1, Theorem 5.4] Let $\gcd (m,k)=1, b\in {{\mathbb {F}}}_{2^m}$ and $f(x)=x^{2^k+1}+bx+b$. Suppose $\gamma \in {{\mathbb {F}}}_{2^m}$ is a root of f(x). Then $\gamma$ is the only root of f(x) in ${{\mathbb {F}}}_{2^m}$ if and only if $\mathrm{{Tr}}_{1}^{m}(\xi )=1$. Here $\xi$ is the unique element in ${{\mathbb {F}}}_{2^m}$ satisfying the relation $\xi ^{2^k-1}=\frac{1}{\gamma +1}$.

Then we can prove

Lemma 2

Let m, k be odd integers with $\gcd (m,k)=1$, $\sigma =2^k$, $\alpha , \beta \in {{\mathbb {F}}}_{2^m}$ and $\alpha \ne \beta$. Assume that $\varphi _3= \left( \alpha ^{\sigma +1}+\beta ^{\sigma +1}\right) ^2$. Then the equation

$$\begin{aligned} \varphi _3 Y^{\sigma ^2}+\left( \alpha \beta ^{\sigma ^2}+ \beta \alpha ^{\sigma ^2}\right) ^{2}Y^{\sigma }+\varphi _3^{\sigma }Y=0 \end{aligned}$$

(2.7)

has exactly two solutions $Y=0$ and $Y=\alpha ^2+\beta ^2$ in ${{\mathbb {F}}}_{2^m}$.

Proof

It can be readily verified that both 0 and $\alpha ^2+\beta ^2$ are solutions of (2.7). Thus, it suffices to show that

$$\begin{aligned} \varphi _3Y^{\sigma ^2-1}+\left( \alpha \beta ^{\sigma ^2}+ \beta \alpha ^{\sigma ^2}\right) ^{2}Y^{\sigma -1}+\varphi _3^{\sigma }=0 \end{aligned}$$

(2.8)

has the unique solution $Y=\alpha ^{2}+\beta ^{2}$ in ${{\mathbb {F}}}_{2^m}$. Let $y=Y^{\sigma -1}$, then (2.8) becomes

$$\begin{aligned} \varphi _3 y^{\sigma +1}+\left( \alpha \beta ^{\sigma ^2}+ \beta \alpha ^{\sigma ^2}\right) ^{2}y+\varphi _3^{\sigma }=0, \end{aligned}$$

which can be further written as

$$\begin{aligned} y^{\sigma +1}+ay+b=0 \end{aligned}$$

due to the fact that $\varphi _3 \ne 0$, where

$$\begin{aligned} a=\frac{(\alpha \beta ^{\sigma ^2}+\beta \alpha ^{\sigma ^2})^2}{\varphi _3}, \quad b=\varphi _3^{\sigma -1}. \end{aligned}$$

Note that $a,b \ne 0$. Substituting y with $\frac{b}{a}x$ leads to

$$\begin{aligned} x^{\sigma +1}+b^{'}x+b^{'}=0 \end{aligned}$$

(2.9)

where $b^{'}=a^{\sigma +1}/b^\sigma$.

To complete the proof, we use Lemma 1. Since $\gcd (\sigma -1, 2^m-1)=1$, it suffices to prove that (2.9) has the unique solution $\gamma =\frac{a}{b}(\alpha ^{2}+\beta ^{2})^{\sigma -1}$.

With a straightforward calculation, we have

$$\begin{aligned} \xi ^{\sigma -1}=\frac{1}{\gamma +1}=\frac{\varphi _3^{\sigma }(\alpha +\beta )^2}{(\alpha \beta ^{\sigma ^2}+ \beta \alpha ^{\sigma ^2})^2(\alpha +\beta )^{2\sigma }+\varphi _3^{\sigma }(\alpha +\beta )^2} =\frac{\varphi _3^{\sigma -1}}{(\alpha +\beta )^{2(\sigma ^{2}-1)}}, \end{aligned}$$

which gives

$$\begin{aligned} \xi =\frac{\varphi _3}{(\alpha +\beta )^{2(\sigma +1)}}. \end{aligned}$$

Further, we can obtain

$$\begin{aligned} \mathrm{{Tr}}_{1}^{m}(\xi )=\mathrm{{Tr}}_{1}^{m}\left( \frac{\alpha ^{\sigma +1}+\beta ^{\sigma +1}}{(\alpha +\beta )^{\sigma +1}}\right) =1+\mathrm{{Tr}}_{1}^{m}\left( \frac{\alpha \beta ^{\sigma }+\beta \alpha ^{\sigma }}{(\alpha +\beta )^{\sigma +1}}\right) . \end{aligned}$$

Let $\epsilon =\alpha +\beta$. Then we have

$$\begin{aligned} \mathrm{{Tr}}_{1}^{m}\left( \frac{\alpha \beta ^{\sigma }+\beta \alpha ^{\sigma }}{(\alpha +\beta )^{\sigma +1}}\right) = \mathrm{{Tr}}_{1}^{m}\left( \frac{\alpha (\alpha +\epsilon )^{\sigma }+(\alpha +\epsilon ) \alpha ^{\sigma }}{\epsilon ^{\sigma +1}}\right) = \mathrm{{Tr}}_{1}^{m}\left( \frac{\alpha }{\epsilon }+\frac{\alpha ^{\sigma }}{\epsilon ^{\sigma }}\right) =0. \end{aligned}$$

This shows that $\mathrm{{Tr}}_{1}^{m}(\xi )=1$ and hence according to Lemma 1, the Eq. (2.9) has the unique solution $\gamma \in {{\mathbb {F}}}_{2^m}$. This completes the proof of Lemma 2. $\square$

Now we resume our proof of (1) in Theorem 2. From (2.6) and Lemma 2, we find that either $Y=0$ or $Y=\alpha ^2+\beta ^2$. On the other hand, since $Y=\alpha ^2+\beta ^2+(\alpha +1)\beta$ (see (2.4)), $\alpha \ne 1$ and $\beta \ne 0$, it is clear that $Y \ne \alpha ^2+\beta ^2$. Thus we conclude that $Y=0$. This proves (2.3) and hence concludes the proof of part (1) of Theorem 2.

3 Proof of part (2) of Theorem 2

We first derive a univariate polynomial expression of $V_R$ (see also [8, 9]). Let $n=2m$ and $\omega$ be a root of $x^2+x+1=0$ in ${{\mathbb {F}}}_{2^n}$. Since m is odd, $\{1,\omega \}$ is a basis of ${{\mathbb {F}}}_{2^n}$ over ${{\mathbb {F}}}_{2^m}$ and ${{\mathbb {F}}}_{2^m}^2$ is isomorphic to ${{\mathbb {F}}}_{2^n}$ under the map

$$\begin{aligned} z=(x,y)\mapsto x+\omega y, \qquad \forall x, y\in {{\mathbb {F}}}_{2^m}. \end{aligned}$$

Hence every element $z\in {{\mathbb {F}}}_{2^n}$ can be uniquely represented as $z=x+\omega y$ with $x,y\in {{\mathbb {F}}}_{2^m}$. This together with ${\overline{z}}=x+{\overline{\omega }}y$, where ${\overline{z}}:=z^{2^m}$, one obtains

$$\begin{aligned} x={\overline{\omega }}z+\omega {\overline{z}},\;\; y=z+{\overline{z}}. \end{aligned}$$

Substituting z with $\omega ^2 z$ gives

$$\begin{aligned} V_{R}(x,y)=V_{R}(z)=\omega ^2\left( e_{1}z^{2^k+1}+e_{2}{\overline{z}}^{2^k+1}+e_{3}z^{2^k}{\overline{z}}+e_{4}z{\overline{z}}^{2^k}\right) , \end{aligned}$$

where

$$\begin{aligned} \begin{array}{llllll} e_{1}&{}=&{}1+\alpha +\alpha ^{2^k+1}+\beta ^{2^k+1},\;&{}e_{2}&{}=&{}1+\alpha ^{2^{k}}+\alpha ^{2^k+1}+\beta ^{2^k+1}, \\ e_{3}&{}=&{}1+\alpha +\alpha ^{2^{k}},\;&{}e_{4}&{}=&{}\alpha +\alpha ^{2^{k}}+\alpha ^{2^k+1}+\beta ^{2^k+1}. \end{array} \end{aligned}$$

Thus, the closed butterfly $V_R$ defined by (1.1) is linear equivalent to the polynomial

$$\begin{aligned} f(x)=e_{1}x^{2^k+1}+e_{2}{\overline{x}}^{2^k+1}+e_{3}x^{2^k}{\overline{x}}+e_{4}x{\overline{x}}^{2^k}. \end{aligned}$$

(3.1)

Since $(\alpha , \beta ) \in \Gamma$, by (1) of Theorem 2, $\alpha , \beta \in {{\mathbb {F}}}_{2^m}^*$ satisfy $\alpha ^2+\beta ^2+\alpha \beta +1=0$. Using $\beta =\theta \alpha +1$ for some $\theta \in {{\mathbb {F}}}_{2^m}^*$, we find that a common solution of $(\alpha ,\beta ) \in \Gamma$ is given by

$$\begin{aligned} (\alpha ,\beta )=\left( \frac{1}{1+\theta +\theta ^2},\frac{\theta ^2}{1+\theta +\theta ^2}\right) , \quad \theta \in {{\mathbb {F}}}_{2^m}^*. \end{aligned}$$

Using the above expression, the quadrinomial (3.1) is linear equivalent to

$$\begin{aligned} F(x):=c_{1}x^{2^k+1}+c_{2}{\overline{x}}^{2^k+1}+c_{3}x^{2^k}{\overline{x}}+c_{4}x{\overline{x}}^{2^k}, \end{aligned}$$

(3.2)

where the coefficients $c_i=e_i\alpha ^{-(2^k+1)}$ and are explicitly given by

$$\begin{aligned} \left\{ \begin{array}{lll} c_{1}&{}=&{}1+\theta +\theta ^2+(\theta +\theta ^2)^{2^k+1}+\theta ^{2(2^k+1)}, \\ c_{2}&{}=&{}(1+\theta +\theta ^2)^{2^k}+(\theta +\theta ^2)^{2^k+1}+\theta ^{2(2^k+1)}, \\ c_{3}&{}=&{}1+(\theta +\theta ^2)^{2^k+1}, \\ c_{4}&{}=&{}(1+\theta +\theta ^2)^{2^{k}+1}+(\theta +\theta ^2)^{2^k+1}+\theta ^{2(2^k+1)}. \end{array} \right. \end{aligned}$$

(3.3)

Thus we can conclude that the closed butterfly $V_{R}(x,y)$ defined by (1.1) is linear equivalent to F(x) defined by (3.2). Then, we can complete the proof of (2) of Theorem 2 by proving Lemma 3.

Lemma 3

Let $n=2m$, m odd, $\gcd (n,k)=1$, $\theta \in {{\mathbb {F}}}_{2^m}^*$ and F(x) be the polynomial defined by (3.2) and (3.3). Then F(x) is linear equivalent to the Gold function $x^{2^{k-m}+1}$ on ${{\mathbb {F}}}_{2^n}$.

Proof

Denote $g(x)=x^{2^k} {\overline{x}}$, $L_1(x)=Ax+B{\overline{x}}$ and $L_2(x)=Cx+D{\overline{x}}$, where the coefficients $A,B,C,D \in {{\mathbb {F}}}_{2^n}$. First, we need to find $A,B,C,D \in {{\mathbb {F}}}_{2^n}$ such that

$$\begin{aligned} C g \left( Ax+B {\overline{x}}\right) +D \overline{g \left( Ax+B {\overline{x}}\right) }=F(x). \end{aligned}$$

(3.4)

Denote the left hand side of (3.4) to be H(x), we can obtain

$$\begin{aligned} H(x)= & {} (CA^{2^k}{\overline{B}}+DA {\overline{B}}^{2^k})x^{2^k+1} +(C{\overline{A}}B^{2^k}+D{\overline{A}}^{2^k} B){\overline{x}}^{2^k+1}+\\&(CA^{2^k}{\overline{A}}+DB {\overline{B}}^{2^k})x^{2^k}{\overline{x}} +(CB^{2^k}{\overline{B}}+DA {\overline{A}}^{2^k})x{\overline{x}}^{2^k}. \end{aligned}$$

Now take the values

$$\begin{aligned} \left\{ \begin{array}{l} A=1,\\ B=1+\theta , \\ C=\theta +\theta ^{2^k}+\theta ^{2^k+1}, \\ D=1+\theta ^{2^k+1}.\end{array} \right. \end{aligned}$$

(3.5)

It can be readily verified that

$$\begin{aligned} \left\{ \begin{array}{lll} CA^{2^k}{\overline{B}}+DA {\overline{B}}^{2^k}&{}=&{}1+\theta +\theta ^2+(\theta +\theta ^2)^{2^k+1}+\theta ^{2(2^k+1)}, \\ C{\overline{A}}B^{2^k}+D{\overline{A}}^{2^k} B&{}=&{} (1+\theta +\theta ^2)^{2^k}+(\theta +\theta ^2)^{2^k+1}+\theta ^{2(2^k+1)},\\ CA^{2^k}{\overline{A}}+DB {\overline{B}}^{2^k}&{}=&{} 1+(\theta +\theta ^2)^{2^k+1},\\ CB^{2^k}{\overline{B}}+DA {\overline{A}}^{2^k}&{}=&{}(1+\theta +\theta ^2)^{2^{k}+1}+(\theta +\theta ^2)^{2^k+1}+\theta ^{2(2^k+1)}. \end{array} \right. \end{aligned}$$

Hence under the values of (3.5), Eq. (3.4) holds. Then, to complete the proof, it suffices to prove that both $L_1(x)$ and $L_2(x)$ are permutations. Note that $L_1(x)$ and $L_2(x)$ are permutations if and only if $A \ne B$ and $C \ne D$ respectively. Obviously $A\ne B$ since $\theta \in {{\mathbb {F}}}_{2^m}^*$. On the other hand, if $C = D$, then we have $1+\theta +\theta ^{2^k}=0$. Noting that m is odd, taking trace on both sides, we have

$$\begin{aligned}0=\mathrm{{Tr}}_1^m\left( 1+\theta +\theta ^{2^k}\right) =\mathrm{{Tr}}_1^m(1)=1,\end{aligned}$$

which is a contradiction. Thus $C \ne D$. So both $L_1(x)$ and $L_2(x)$ are permutations on ${{\mathbb {F}}}_{2^n}$. This shows that F(x) is linear equivalent to g(x). Clear g(x) is linear equivalent to the Gold function $x^{2^{k-m}+1}$. $\square$

4 Proof of Theorem 3

First recall the following lemma:

Lemma 4

[13] Let n, k be positive integers with $\gcd (n,k)=1$. For any $a \in {{\mathbb {F}}}_{2^n}$, the equation $x^{2^k}+x=a$ has either 0 or 2 solutions in ${{\mathbb {F}}}_{2^n}$. Moreover, it has two solutions in ${{\mathbb {F}}}_{2^n}$ if and only if $\mathrm{{Tr}}_1^n(a)=0$.

Now we start the proof of Theorem 3. Let $z=x+{\overline{x}}$, then the equation $L_{\mu ,\nu }(x)=0$ becomes

$$\begin{aligned} x^{2^k}+x+\mu z+\nu =0. \end{aligned}$$

(4.1)

Taking $2^m$-th power on both sides of (4.1) and adding them together gives

$$\begin{aligned} z^{2^k}+(1+\mu +{\overline{\mu }})z+\nu +{\overline{\nu }}=0. \end{aligned}$$

(4.2)

Taking $2^k$-th power consecutively on both sides of (4.1), one can also obtain

$$\begin{aligned} x+x^{2^{km}}=x+{\overline{x}}=\sum _{i=0}^{m-1}(\mu z+\nu )^{2^{ki}}. \end{aligned}$$

Hence solving $L_{\mu ,\nu }(x)=0$ for $x \in {{\mathbb {F}}}_{2^n}$ is equivalent to solving the system of equations (4.1), (4.2) and

$$\begin{aligned} \sum _{i=0}^{m-1}(\mu z+\nu )^{2^{ki}}+z=0 \end{aligned}$$

(4.3)

for $x \in {{\mathbb {F}}}_{2^n}$ and $z \in {{\mathbb {F}}}_{2^m}$. Note that $\sum _{i=0}^{m-1}(\mu z+\nu )^{2^{ki}}+z\in \mathbb {F}_2$.

Without checking the solvability of (4.3), since $\gcd (n,k)=1$, for any $\mu$ and $\nu$, (4.2) has at most two solutions for $z \in {{\mathbb {F}}}_{2^m}$, and for each such z, (4.1) has at most two solutions for $x \in {{\mathbb {F}}}_{2^n}$, hence the equation $L_{\mu ,\nu }(x)=0$ has at most 4 solutions. Also observe that whenever $z \in {{\mathbb {F}}}_{2^m}$ is a solution to (4.2) that satisfies (4.3), one always has

$$\begin{aligned} \mathrm{{Tr}}_1^n\left( \mu z+\nu \right) =\mathrm{{Tr}}_1^m\left( \mu z+\nu +\overline{\mu z+\nu }\right) =z+{\overline{z}}=0, \end{aligned}$$

hence for such z, by Lemma 4, (4.1) is always solvable with two solutions $x \in {{\mathbb {F}}}_{2^n}$. We conclude that the number of solutions of $L_{\mu ,\nu }(x)=0$ equals two times the number of $z \in {{\mathbb {F}}}_{2^n}$ satisfying (4.2) and (4.3).

Now we study in more details the solvability of (4.2) and (4.3).

Case 1 $1+\mu +{\overline{\mu }}=0$.

In this case, (4.2) has a unique solution z such that $z^{2^k}=\nu +{\overline{\nu }}$, and (4.3) is equivalent to

$$\begin{aligned} \sum _{i=0}^{m-1}\left( \mu ^{2^k} z^{2^k}+\nu ^{2^k}\right) ^{2^{ki}}=z^{2^k}, \end{aligned}$$

and this proves part (1) (i) of Theorem 3.

Case 2 $1+\mu +{\overline{\mu }}\ne 0$.

Let $\xi$, $\Delta$ be defined by (1.5) and $z=\xi \rho$, then (4.2) becomes

$$\begin{aligned} \rho ^{2^k}+\rho =\Delta \end{aligned}$$

(4.4)

which has solutions for $\rho \in {{\mathbb {F}}}_{2^m}$ if and only if $\mathrm{{Tr}}_1^m(\Delta )=0$.

We now assume that $\mathrm{{Tr}}_1^m(\Delta )=0$. The two solutions $z_1,z_2 \in {{\mathbb {F}}}_{2^m}$ to (4.2) satisfy the relation

$$\begin{aligned} z_1+z_2=\xi . \end{aligned}$$

Using $\lambda ^{2^k}+\lambda =\mu \xi$, we have

$$\begin{aligned} \sum _{j=1}^2 \left( \sum _{i=0}^{m-1} \left( \mu z_{j}+\nu \right) ^{2^{ki}}+z_{j}\right) = \sum _{i=0}^{m-1}\left( \mu \xi \right) ^{2^{ki}}+\xi =\lambda +{\overline{\lambda }}+\xi \in \mathbb {F}_2. \end{aligned}$$

Subcase 2.1 $\lambda +{\overline{\lambda }}=\xi +1$. In this case it is easy to see that among $z_1$ and $z_2$, exactly one element satisfies (4.3), hence the Eq. $L_{\mu ,\nu }(x)=0$ has two solutions. This proves part (1) (ii) of Theorem 3.

Subcase 2.2 ${\overline{\lambda }}+\lambda =\xi$. In this case, either both $z_1$ and $z_2$ satisfy (4.3) or neither satisfy (4.3), hence the equation $L_{\mu ,\nu }(x)=0$ has either 4 or 0 solution. We will prove below that these $z_i$’s satisfy (4.3) if and only if

$$\begin{aligned} \mathrm{{Tr}}_{1}^{n}\left( \frac{\lambda ^{2^k}{\overline{\nu }} }{\xi ^{2^k}}\right) =0, \end{aligned}$$

hence verifying part (2) of Theorem 3.

Let $z=\xi \rho$ be a solution to (4.2) where $\rho \in {{\mathbb {F}}}_{2^m}$ satisfies (4.4). Denote by h(z) the left hand side of Eq. (4.3). We have

$$\begin{aligned} h(z)= \sum _{i=0}^{m-1} \left( \mu \xi \rho +\nu \right) ^{2^{ki}}+\xi \rho . \end{aligned}$$

The quantity h(z) can be simplified further: using (4.4) and the relation $\sum _{i=0}^{m-1}\left( \mu \xi \right) ^{2^{ki}}=\lambda +{\overline{\lambda }}=\xi$ we can obtain

$$\begin{aligned} \sum _{i=0}^{m-1}(\mu \xi \rho )^{2^{ki}}= & {} \sum _{i=1}^{m-1}(\mu \xi )^{2^{ki}}\rho ^{2^{ki}}+\mu \xi \rho =\sum _{i=1}^{m-1}(\mu \xi )^{2^{ki}}\left( \rho +\sum _{j=0}^{i-1}\Delta ^{2^{kj}} \right) +\mu \xi \rho \nonumber \\= & {} \rho \sum _{i=0}^{m-1}(\mu \xi )^{2^{ki}}+\sum _{i=1}^{m-1}(\mu \xi )^{2^{ki}}\sum _{j=0}^{i-1}\Delta ^{2^{kj}}\nonumber \\= & {} \rho \xi +\sum _{i=1}^{m-1}(\mu \xi )^{2^{ki}}\sum _{j=0}^{i-1}\Delta ^{2^{kj}}. \end{aligned}$$

(4.5)

As for the second term on the right side of (4.5), using $\mathrm{{Tr}}_1^m(\Delta )=\sum _{i=0}^{m-1}\Delta ^{2^{ki}}=0$, one obtains

$$\begin{aligned} \sum _{i=1}^{m-1} \sum _{j=0}^{i-1} (\mu \xi )^{2^{ki}} \Delta ^{2^{kj}}= & {} \sum _{j=0}^{m-2}\Delta ^{2^{kj}}\sum _{i=j+1}^{m-1}(\mu \xi )^{2^{ki}} =\sum _{j=0}^{m-2}\Delta ^{2^{kj}}\sum _{i=j+1}^{m-1}(\lambda ^{2^k}+\lambda )^{2^{ki}}\nonumber \\= & {} \sum _{j=0}^{m-2}\Delta ^{2^{kj}}(\lambda ^{2^{k(j+1)}}+\lambda ^{2^{km}})\nonumber \\= & {} \sum _{j=0}^{m-2}(\lambda ^{2^k}\Delta )^{2^{kj}}+\Delta ^{2^{k(m-1)}}\lambda ^{2^{km}}\nonumber \\= & {} \sum _{j=0}^{m-1}(\lambda ^{2^k}\Delta )^{2^{kj}}. \end{aligned}$$

(4.6)

Combining (4.5) and (4.6) we can easily find

$$\begin{aligned} h(z)=\sum _{i=0}^{m-1} \left( \lambda ^{2^k}\Delta +\nu \right) ^{2^{ki}}. \end{aligned}$$

Observing that

$$\begin{aligned} \lambda ^{2^k}\Delta +\nu =\frac{\lambda ^{2^k}}{\xi ^{2^k}}({\overline{\nu }}+\nu )+\nu =\frac{\lambda ^{2^k}{\overline{\nu }}+{\overline{\lambda }}^{2^k} \nu }{\xi ^{2^k}}, \end{aligned}$$

we obtain

$$\begin{aligned} h(z)= \mathrm{{Tr}}_1^n \left( \frac{\lambda ^{2^k}{\overline{\nu }}}{\xi ^{2^k}}\right) . \end{aligned}$$

Hence Eq. (4.3) is equivalent to

$$\begin{aligned} \mathrm{{Tr}}_{1}^{n}\left( \frac{\lambda ^{2^k}{\overline{\nu }} }{\xi ^{2^k}}\right) =0, \end{aligned}$$

and in this case, the equation $L_{\mu ,\nu }(x)=0$ has 4 solutions. This completes the proof of part (2) of Theorem 3.

Case 3 $\nu =0, 1+\mu +{\overline{\mu }} \ne 0$ and $\lambda +{\overline{\lambda }}=\xi$. In this final case, Eq. (4.2) has two solutions $z_1=0, z_2=\xi$ which both satisfy (4.3). Returning to (4.1), the corresponding four roots of $L_{\mu ,\nu }(x)=0$ are given by $0,1,\lambda , \lambda +1$. This proves part (3) of Theorem 3. Now Theorem 3 is proved.

5 Conclusion

In this note we further studied the cryptographically strong permutations obtained from the closed butterfly function in [8]. We represented the conditions in [8] in a much simpler way and showed that these cryptographically strong permutations are linear equivalent to Gold functions. Moreover, we proved a criterion for solving a new type of equations over finite fields, which is of independent interest.