A Class of Power Mappings with Low Boomerang Uniformity

Abstract

Let $f(x)=x^{\frac{q-3}{2}}$ be a power mapping over ${\mathbb {F}}_{q}$, where q is an odd prime power. The differential uniformity of f was determined by Helleseth and Sandberg [14] in 1997. In this paper, we study the boomerang uniformity of f via its differential properties. It is shown that f has low boomerang uniformity when $q \equiv 3 \pmod 4$.

1 Introduction

Substitution boxes (S-boxes for short) play a crucial role in the field of symmetric block ciphers. Let ${\mathbb {F}}_{q}$ be the finite field with q elements. For a function f from ${\mathbb {F}}_{q}$ to itself, the main tools to handle f regarding the differential attack are the difference distribution table (DDT for short) introduced by Biham and Shamir [2] and the differential uniformity which was introduced by Nyberg [21] in 1994. For any $a, b \in {\mathbb {F}}_{q}$, the DDT entry at point (a, b) , denoted by $\delta _f(a,b)$, is defined as

$$\begin{aligned} \delta _f(a,b)=\big | \{x \in {\mathbb {F}}_{q}: ~f(x+a)-f(x)=b\} \big | , \end{aligned}$$

where $\big | S \big |$ denotes the cardinality of the set S. The differential uniformity of the function f, denoted by ${\delta _f}$, is defined as

$$\begin{aligned} {\delta _f}=\max \{\delta _f(a,b): ~a \in {{\mathbb {F}}_{q}^*},~b \in {\mathbb {F}}_{q}\} , \end{aligned}$$

where ${\mathbb {F}}_{q}^*={\mathbb {F}}_{q}\setminus \{0\}$. When f is used as an S-box inside a cryptosystem, the smaller the value $\delta _f$ is, the better the contribution of f to the resistance against differential attack. When $\delta _f=1$ (respectively, $\delta _f=2$), the function f is called a perfect nonlinear (PN) function (respectively, an almost perfect nonlinear (APN) function). The recent results on cryptographic functions with low differential uniformity can be found in [1, 3, 5, 6, 13, 18, 22, 23, 25, 27, 29, 30, 34] and their references. More precisely, the readers can refer to a recent monograph [8], Chapter 11, which is written by Carlet.

Another important cryptanalytical technique on block ciphers is the boomerang attack introduced by Wagner [28], which is a variant of differential cryptanalysis. In order to analyze the boomerang attack of block ciphers in a better way, analogous to the DDT concerning differential attack, Cid $et\;al.$ [9] firstly proposed the boomerang connectivity table (BCT). Let f be a permutation from ${\mathbb {F}}_{2^n}$ to itself. For $a,b\in {\mathbb {F}}_{2^n}$, the BCT entry at point (a, b), denoted by $\beta _f(a,b)$, is defined as

$$\begin{aligned} \beta _f(a,b)=\big | \{x \in {\mathbb {F}}_{2^n}: ~f^{-1}(f(x+a)+b)+f^{-1}(f(x)+b)=a\} \big | . \end{aligned}$$

Further, to quantify the resistance of a function against the boomerang attack, Boura and Canteaut [4] introduced the concept of boomerang uniformity, which is the maximum value in the BCT excluding the first row and the first column. That is, the boomerang uniformity of the permutation f, denoted by $\beta _f$, is given by

$$\begin{aligned} \beta _f = \max \left\{ {{\beta _f}(a,b): ~a,b \in {\mathbb {F}}_{q}^*} \right\} \text{. } \end{aligned}$$

Similarly, the smaller the value $\beta _f$ is, the better the contribution of f to the resistance against boomerang attack. Recently, Li $et\;al.$ in [16] generalized the definition of $\beta _f(a,b)$ for any function f (not necessarily being a permutation) over ${\mathbb {F}}_{q}$. The BCT entry of f at point (a, b), denoted by $\beta _f(a,b)$, is the number of solutions $(x,y)\in {\mathbb {F}}_{q}\times {\mathbb {F}}_{q}$ of the following system of equations

$$ \left\{ \begin{array}{lll} f(x) - f(y) ~~~&{}=~ b \text{, } \\ f(x+a) - f(y+a) ~~~&{}=~ b \text{, } \end{array} \right. $$

where $a,b \in {\mathbb {F}}_{q}^*$. The research on cryptographic functions with low boomerang uniformity has been a hot issue in recent years, see for example [4, 9, 11, 16, 17, 20, 26, 33]. More precisely, for recent progress of cryptographic functions with known boomerang uniformity, the readers can refer to the survey article [19], which is written by Mesnager, Mandal and Msahli.

Power functions with low differential uniformity serve as good candidates for the design of S-boxes not only because of their strong resistance to differential attacks but also for the usually low implementation cost in hardware. The differential properties of power functions can be studied more easily due to their particular algebraic structures. Hence, the study on the boomerang uniformity of power mappings attracts a lot of attention. More precisely, when f is a power function, i.e., $f(x)=x^d$ for an integer d, one easily sees that ${\beta _f}(a,b) = {\beta _f}(1,\frac{b}{{{a^d}}})$ for any $a,b \in {\mathbb {F}_{q}^*}$. The boomerang properties of f are completely determined by the values of $\beta _f(1,b)$ as b runs through ${\mathbb {F}}_{q}^*$. Equivalently, we need to consider the number of solutions $(x,y)\in {\mathbb {F}}_{q} \times {\mathbb {F}}_{q}$ of the following equation system

$$ \left\{ \begin{array}{lll} x^d - y^d ~~~&{}= ~b \\ (x+1)^d - (y+1)^d ~~~&{}= ~b \end{array} \right. $$

for $b\in {\mathbb {F}}_q^*$. Although the power functions have good algebraic structures, there are only a few classes of power mappings with known boomerang uniformity in the literature. We list them in Table 1.

In this paper, we mainly study the boomerang uniformity of the power mapping $x^{\frac{q-3}{2}}$ over ${\mathbb {F}}_{q}$ via its differential properties, where $q\equiv 3 \pmod 4$ is an odd prime power. The rest of this paper is organized as follows. Section 2 first introduces some frequently-used notation, and then gives some lemmas which will be used later. Section 3 investigates the boomerang uniformity of $x^{\frac{q-3}{2}}$. Section 4 concludes this paper.

Table 1. Power functions with known boomerang uniformity over ${\mathbb {F}}_{p^n}$

2 Preliminaries

In this section, we introduce some frequently-used notation in this paper and give some lemmas which will be used in the following.

• q is an odd prime power.

• ${\mathbb {F}}_q$ is the finite field with q elements.

• Let $f(x)=x^{\frac{q-3}{2}}$ be a power mapping over ${\mathbb {F}}_q$.

• $\varDelta (x)=f(x+1)-f(x)=(x+1)^{\frac{q-3}{2}}-x^{\frac{q-3}{2}}$.

• For any $b \in {\mathbb {F}}_q$, let $\varDelta ^{-1}(b)=\{x~:~\varDelta (x)=b\}$ and $\delta (b)=| \varDelta ^{-1}(b) |$.

• Let $\chi (\cdot )$ be the quadratic multiplicative character over ${\mathbb {F}}_{q}^*$, i.e., for any $x\in {\mathbb {F}}_{q}^*$,

  $$\chi (x)=x^{\frac{q-1}{2}}=\left\{ \begin{array}{ll} 1,&{} \text { if } x \text { is a square element,} \\ -1,&{} \text { if } x \text { is a nonsquare element.} \\ \end{array} \right. $$

• For $i,j\in \{1,-1\}$, we define

  $$\begin{aligned} C_{i,j}=\{x\in {\mathbb {F}}_{q} \backslash \{0,-1\}:~\chi (x)=i \text { and } \chi (x+1)=j\}. \end{aligned}$$

The differential uniformity of f was determined by Helleseth and Sandberg in [14]. We have the following theorem.

Theorem 1

Let $q \equiv 3\pmod 4$ be a prime power. For $q > 7$, the differential uniformity of $f(x)=x^{\frac{q-3}{2}}$ is given by

$$\delta _f=\left\{ \begin{array}{ll} 1,&{}\text {if}~~q =27, \\ 2,&{}\text {if}~~\chi (5)=-1, \\ 3,&{}\text {if}~~\chi (5)=1. \\ \end{array} \right. $$

Moreover, the following lemma was shown in the proof of Theorem 1 in [14].

Lemma 1

Let $q \equiv 3\pmod 4$ be a prime power. With the notation introduced as above, we have

• (i) $\varDelta ^{-1}(0)=\{-\frac{1}{2}\}$ and $\delta (0)=1$.

• (ii) If $\chi (5)=-1$, then $\varDelta ^{-1}(1)=\{0\}$, $\varDelta ^{-1}(-1)=\{-1\}$ and $\delta (1)=\delta (-1)=1$.

• (iii) If $\chi (5)=1$, then $\delta (b)=3$ if and only if $b=\pm 1$. Moreover, $\varDelta ^{-1}(1)=\{0,\frac{\sqrt{5}-1}{2},\frac{\sqrt{5}+1}{2}\}$, $\varDelta ^{-1}(-1)=\{-1, \frac{-\sqrt{5}-1}{2}, \frac{-\sqrt{5}-3}{2}\}$ with $\chi (\frac{-1+\sqrt{5}}{2})=-1$, $\varDelta ^{-1}(1)=\{0,\frac{-\sqrt{5}-1}{2},\frac{1-\sqrt{5}}{2}\}$, $\varDelta ^{-1}(-1)=\{-1, \frac{\sqrt{5}-1}{2}, \frac{\sqrt{5}-3}{2}\}$ with $\chi (\frac{-1+\sqrt{5}}{2}) =1$.

• (iv) For $b\ne \pm 1$, we have $\delta (b)\le 2$. More precisely, if $\delta (b)=2$, i.e., the equation $\varDelta (x)=b$ has two distinct solutions, namely $x_1$ and $x_2$, then one of $x_1$ and $x_2$ is in $C_{1,1}\cup C_{-1,-1}$, and the other is in $C_{1,-1}\cup C_{-1,1}$.

3 The Boomerang Uniformity of the Power Function $x^{\frac{q-3}{2}}$ Over ${\mathbb {F}}_{q}$

In this section, we investigate the boomerang uniformity of the power mapping f via its differential properties. We denote by $\beta _f$ the boomerang uniformity of f. Our main result is shown as follows.

Theorem 2

Let q be an odd prime power with $q \equiv 3\pmod 4$. For $q\ne 7$ and $q\ne 27$, we have,

$$\beta _f \le \left\{ \begin{array}{ll} 4,&{}\text {if}~~\chi (5)=-1, \\ 6,&{}\text {if}~~\chi (5)=1. \\ \end{array} \right. $$

Proof

For any $b \in {\mathbb {F}}_{q}^*$, we consider the number of solutions $(x,y)\in {\mathbb {F}}_{q} \times {\mathbb {F}}_{q}$ of the following equation system

$$\begin{aligned} \left\{ \begin{array}{lll} x^{\frac{q-3}{2}} - y^{\frac{q-3}{2}} ~~~&{}=~ b \text{, }\\ (x+1)^{\frac{q-3}{2}} - (y+1)^{\frac{q-3}{2}} ~~~&{}=~ b \text{. } \\ \end{array} \right. \end{aligned}$$

(1)

If (x, y) is a solution of (1), we have $x \ne y$ since $b \ne 0$. Moreover, we have $\varDelta (x)=\varDelta (y)$ from (1).We assert that $\delta (\varDelta (x))=2$ or 3 by Lemma differential and $x \ne y$. We discuss in the following two cases.

Case 1. $\delta (\varDelta (x))=2$. It is clear that $\varDelta (x) \ne \pm 1$ by Lemma 1, then we have $x,y \ne 0,-1$. The equation system (1) becomes

$$\begin{aligned} \left\{ \begin{array}{lll} \chi (x)x^{-1} - \chi (y)y^{-1} ~~~&{}= ~b \text{, } \\ \chi (x+1)(x+1)^{-1} - \chi (y+1)(y+1)^{-1} ~~~&{}= ~b \text{. } \\ \end{array} \right. \end{aligned}$$

(2)

By Lemma 1 (iv), for each $x\in C_{i,j}$, $i,j\in \{1,-1\}$, there are two possible sets of y. We have the following 8 subcases, which we summarize in Table 2.

Table 2. Eight subcases from equation system (2)

Subcase I. $(x,y)\in C_{1,1}\times C_{1,-1}$. After a simple calculation, we obtain two quadratic equations as follows.

It is easy to see that $b\ne 2$ and $b\ne 0$, otherwise, we have $x=0$ or $y=-1$, a contradiction. If (3) has two solutions, namely $x_1$ and $x_2$, then $x_1x_2=-\frac{1}{b}$. We mention that $-1$ is a nonsquare element. When b is a square element, then $\chi (x_1x_2)=-1$, and at most one of $x_1$ and $x_2$ satisfies $x\in C_{1,1}$. Similarly, if (4) has two solutions, namely $y_1$ and $y_2$, then $(y_1+1)(y_2+1)=\frac{1}{b}$. When b is a nonsquare element, then $\chi ((y_1+1)(y_2+1))=-1$, and at most one of $y_1$ and $y_2$ satisfies $y\in C_{1,-1}$. By a discussion as above, we conclude that for any $b\in {\mathbb {F}}_q^*$, this subcase contributes at most 1 solution.

Subcase II. $(x,y)\in C_{1,1}\times C_{-1,1}$. In this subcase, we obtain two quadratic equations as follows.

It is easy to see that $b\ne -2$ and $b\ne 0$. If (5) (respectively, (6)) has two solutions, namely $x_1$ and $x_2$ (respectively, $y_1$ and $y_2$), then $(x_1+1)(x_2+1)=\frac{1}{b}$ (respectively, $y_1y_2=-\frac{1}{b}$). By a similar proof as for subcase I, we conclude that for any $b\in {\mathbb {F}}_q^*$, this subcase contributes at most 1 solution.

Subcase III. $(x,y)\in C_{1,-1}\times C_{1,1}$. We obtain two quadratic equations as follows.

$$\left\{ \begin{array}{lll} b^2(x+1)^2-(b^2+2)(x+1)-b ~~~&{}=~0, \\ b(b+2)y^2+(b^2+4b+2)y+b+2 ~~~&{}=~0. \end{array} \right. $$

Similar to the proof of subase I, this subcase contributes at most 1 solution.

Subcase IV. $(x,y)\in C_{1,-1}\times C_{-1,-1}$. Since $\frac{q-3}{2}$ is even, then (x, y) is a solution of (1) if and only if $(-x-1,-y-1)$ is a solution of (1). For any $y\in {\mathbb {F}}_q\setminus \{0,-1\}$, $y\in C_{1,1}$ if and only if $-y-1\in C_{-1,-1}$, $y\in C_{1,-1}$ (respectively, $C_{-1,1}$) if and only if $-y-1\in C_{1,-1}$ (respectively, $C_{-1,1}$). We conclude that the number of the solutions in this subcase is the same to that of subcase III.

Subcase V. $(x,y)\in C_{-1,1}\times C_{1,1}$. We obtain two quadratic equations as follows.

Similar to the proof of subcase I, this subcase contributes at most 1 solution.

For subcases VI, VII and VIII, we assert that the numbers of solutions in subcases VI and V (respectively, subcases VII and I, subcases VIII and II) are the same, similar to subcases IV and III. We conclude that the equation system (2) has at most one solution in each subcase.

Next we show that the equation system (2) cannot have solutions in subcase I and subcase V simultaneously. Otherwise, let $(x_1,y_1)\in C_{1,1}\times C_{1,-1}$ be a solution of (2) in subcase I and $(u_1,v_1)\in C_{-1,1}\times C_{1,1}$ be a solution of (2) in subcase V. Then

$$\begin{aligned} \chi (x_1)=1,~\chi (x_1+1)=1,~\chi (y_1)=1,~\chi (y_1+1)=-1, \end{aligned}$$

and

$$\begin{aligned} \chi (u_1)=-1,~\chi (u_1+1)=1,~\chi (v_1)=1,~\chi (v_1+1)=1. \end{aligned}$$

When we discard the condition on the values of the quadratic character, there is the other solution $(x_2,y_2)$ (respectively, $(u_2,v_2)$) of equations (3) and (4) (respectively, (7) and (8)). Considering quadratic equations (5) and (8), only one of their coefficients has a different sign. More precisely, we have

$$\begin{aligned} x_1+x_2=-\frac{b^2-4b+2}{b(b-2)}=-((v_1+1)+(v_2+1)) \end{aligned}$$

and

$$\begin{aligned} x_1x_2=-\frac{1}{b}=(v_1+1)(v_2+1). \end{aligned}$$

Then $x_1=-(v_2+1)$ and $x_2=-(v_1+1)$ since $x_1, v_1\in C_{1,1}$. Consequently,

$$\begin{aligned} \chi (b)=\chi (\frac{1}{b})=\chi (-(v_1+1)(v_2+1))=\chi (v_1+1)\chi (x_1)=\chi (x_1)=1. \end{aligned}$$

Similarly, considering quadratic equations (4) and (7), we have

$$\begin{aligned} u_1+u_2=-\frac{b^2+2}{b^2}=-((y_1+1)+(y_2+1)) \end{aligned}$$

and

$$\begin{aligned} u_1u_2=\frac{1}{b}=(y_1+1)(y_2+1). \end{aligned}$$

Then $u_1=-(y_2+1)$ and $u_2=-(y_1+1)$ since $u_1\in C_{-1,1}$ and $y_1\in C_{1,-1}$. Hence

$$\begin{aligned} \chi (b)=\chi (\frac{1}{b})=\chi ((y_1+1)(y_2+1))=\chi (-(y_1+1)u_1)=-\chi (y_1+1)\chi (u_1)=-1, \end{aligned}$$

which is a contradiction. Therefore, for any $b\in {\mathbb {F}}_{q}^*$, subcase I and subcase V cannot give solutions simultaneously, so they contribute at most one solution altogether. Similarly, subcases II and III contribute at most one solution altogether. That is to say, for any $b\in {\mathbb {F}}_{q}^*$, there are at most four solutions of (1) in this case.

Case 2. $\delta (\varDelta (x))=3$. By Lemma 1, we know that this case only occurs when $\chi (5)=1$ and $\varDelta (x)=\pm 1$. Note that $\frac{-1+\sqrt{5}}{2}\cdot \frac{-1-\sqrt{5}}{2}=-1$, without loss of generality, we assume that $\chi (\frac{-1+\sqrt{5}}{2})=-1$. Then we can obtain $\varDelta ^{-1}(1)=\{0,\frac{\sqrt{5}-1}{2},\frac{\sqrt{5}+1}{2}\}$ and $\varDelta ^{-1}(-1)=\{-1, -\frac{\sqrt{5}+1}{2}, -\frac{\sqrt{5}+3}{2}\}$ by Lemma 1 (iii).

We can list all possible pairs (x, y) with $\varDelta (x) =\varDelta (y)=\pm 1$. Plugging all pairs (x, y) into the first equation of the system (1), the corresponding b’s are obtained. We have the following table (Table 3).

Table 3. The Solutions of $\varDelta (x) =\varDelta (y)=\pm 1$ and Corresponding b

It is obvious that, for each $b\in \{\pm 1,~\pm \frac{\sqrt{5}+1}{2},~\pm \frac{\sqrt{5}-1}{2} \}$, the equation system (1) has two solutions in this case. For $b\in {\mathbb {F}}_{q}^* \backslash \{\pm 1,~\pm \frac{\sqrt{5}+1}{2},~\pm \frac{\sqrt{5}-1}{2} \}$ the equation system (1) has no solution in this case. Note that Case 2 only occurs when $\chi (5)=1$, the desired results follow.

Remark 1

By making a computer investigation, we have the boomerang uniformity of f is equal to 4 with $q=3^5$. In addition, the boomerang uniformity of f is equal to 6 with $q=131$. Therefore, we can conclude that our bound is tight.

4 Conclusion

In this paper, we mainly study the boomerang uniformity of the power function $x^{\frac{q-3}{2}}$ over ${\mathbb {F}}_{q}$ via their differential properties, where $q\equiv 3 \pmod 4$ is an odd prime power. It is shown that the power function has low boomerang uniformity. We mention that our approach may be used in determining the boomerang uniformity of other power mappings. It is worthy finding applications of power mappings with low boomerang uniformity in sequence designs, coding theory and combinatorial designs.