nach oben

Applicable Algebra in Engineering, Communication and Computing

Open Access 21.10.2024 | Original Paper

A degree bound for the c-boomerang uniformity of permutation monomials

verfasst von: Matthias Johann Steiner

Erschienen in: Applicable Algebra in Engineering, Communication and Computing

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Patentsuche

Aus

Abstract

Let $\mathbb{F}_q$ be a finite field of characteristic p. In this paper we prove that the c-Boomerang Uniformity, $c \ne 0$, for all permutation monomials $x^d$, where $d > 1$ and $p \not \mid d$, is bounded by $\left\{ \begin{array}{ll} d^2, & c^2 \ne 1, \\ d \cdot (d - 1), & c = - 1, \\ d \cdot (d - 2), & c = 1 \end{array} \right\} .$ Further, we utilize this bound to estimate the c-boomerang uniformity of a large class of generalized triangular dynamical systems, a polynomial-based approach to describe cryptographic permutations of $\mathbb{F}_{q}^{n}$, including the well-known substitution–permutation network.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

1 Introduction

Differential cryptanalysis [5] introduced by Biham & Shamir is one of the most successful attack vectors against symmetric key ciphers and hash functions which exploits a statistical bias in the propagation of an input difference $\varvec{\Delta }_I$ to an output difference $\varvec{\Delta }_O$. A generalization of the differential attack is the boomerang attack [44] introduced by Wagner. In a boomerang attack a cipher ${\mathcal{C}}$ is split into two subciphers ${\mathcal{C}} = {\mathcal{C}}_1 \circ {\mathcal{C}}_2$. One sets up a differential for ${\mathcal{C}}_1$ and one for ${\mathcal{C}}_2$, and then tries to connect them to a differential for the full cipher ${\mathcal{C}}$, see [11, Fig. 1]. For a generalization of the boomerang attack to hash functions we refer to [27]. Murphy [35] pointed out that for S-box-based ciphers two differentials could be incompatible for a boomerang attack. In several works [6, 14, 15] conditions for the compatibility of the differentials were studied. In particular, it was proposed to split the cipher as ${\mathcal{C}} = {\mathcal{C}}_1 \circ {\mathcal{C}}_m \circ {\mathcal{C}}_2$, where the middle part ${\mathcal{C}}_m$ is responsible for the propagation of the differential. To formalize analysis of the differential propagation probability for ${\mathcal{C}}_m$, Cid et al. introduced the Boomerang Connectivity Table (BCT) [11] analog to the Differential Distribution Table (DDT). In essence, given a differential for ${\mathcal{C}}_1$ with probability p, one for ${\mathcal{C}}_2$ with probability q and assume that the propagation probability for ${\mathcal{C}}_m$ is r, then the expected probability for the entire boomerang differential is $p^2 \cdot q^2 \cdot r$. Obviously, the lower r the higher the expected resistance of the cipher ${\mathcal{C}}$ against the boomerang attack. In analogy to the differential uniformity, Boura & Canteaut introduced the boomerang uniformity [7], that is the maximum entry of the BCT for non-trivial input–output differences, to express the susceptibility of S-boxes against boomerang attacks.

With recent advancements in Multi-Party Computation (MPC) and Zero-Knowledge (ZK) proof systems new ciphers and hash functions have been introduced for efficient applications of these cryptographic technologies. Many modern MPC & ZK protocols are defined over a prime field $\mathbb{F}_{p}$, where $p \ge 2^{60}$, and for efficient implementation ciphers and hash functions should be native in $\mathbb{F}_{p}$. Moreover, as main performance measure they require a low number of multiplications for evaluation in $\mathbb{F}_{p}$. In the literature, such designs are also known as Arithmetization-Oriented (AO) designs. Examples for recently introduced AO ciphers and hash functions are LowMC [3], MiMC [2], GMiMC [1], Hades [22], Rescue [4], Poseidon [20] & Poseidon2 [21], Ciminion [13], Reinforced Concrete [19], Griffin [18], Anemoi [9], Hydra [24] and Arion [38]. At round level, many of these primitives utilize low degree power permutations $x^d$, where $d \in \{ 3, 5, 7 \}$. While the boomerang uniformity for normalized permutation polynomials up to degree 6 has been worked out by hand [45], a general bound for the boomerang uniformity of $x^d$ over large prime fields $\mathbb{F}_{p}$ is unknown yet.

We also note that prime field-based ciphers have been recently investigated as possible designs with high resistance against side-channel attacks [10, 23, 32]. For these reasons we believe it is crucial that classical cryptanalysis tools over $\mathbb{F}_{2^n}$ are generalized to arbitrary finite fields $\mathbb{F}_{q}$.

Hence, our main goal in this work is to derive a degree bound for the boomerang uniformity of power permutations over large finite fields as tool for cryptanalysis and design of AO ciphers and hash functions.

Recently, Ellingsen et al. [16] introduced so-called c-scaled differences as tool to study potential statistical biases in S-boxes. Stănică [40] utilized the same approach to generalize the BCT to c-scaled differences. Since their introduction, these notions have seen a lot of attention in the literature, see e.g. [7, 25, 26, 34, 41‐43]. In particular, we recommend the excellent survey article by Mesnager et al. [33]. Articles in this line of research usually focus on estimations of the c-differential/boomerang uniformity of permutations with good analytical structure. In a simplifying manner we classify these permutations into the following categories:

Variants of the inverse permutation $x^{-1}$.
Quadratic permutations over binary fields.
Special permutations, e.g. Gold functions.
Special permutations over special fields.

Unfortunately, these bounds for the (c-)DDT/BCT are usually unsuitable to evaluate the resistance of low degree power permutations $x^d$ over large prime fields $\mathbb{F}_{p}$ against statistical biases.

1.1 Our results

As our main result, we prove in Sect. 3 the following bound for the c-boomerang uniformity of power permutations over $\mathbb{F}_{q}$.

Theorem 1.1

(Corollary 3.6) Let $\mathbb{F}_{q}$ be a finite field of characteristic p, let $c \in \mathbb{F}_{q}^\times$, and let $d \in \mathbb{Z}_{> 1}$ be such that $\gcd (d, q - 1) = 1$ and $p \not \mid d$. Then

(1)

$\beta _{x^d, c} \le {\left\{ \begin{array}{ll} d^2, & c^2 \ne 1, \\ d \cdot (d - 1), & c = -1, \\ d \cdot (d - 2), & c = 1. \end{array}\right. }$

(2)

$\beta _{x^\frac{1}{d}, c} \le {\left\{ \begin{array}{ll} d^2, & c^2 \ne 1, \\ d \cdot (d - 1), & c = -1, \\ d \cdot (d - 2), & c = 1. \end{array}\right. }$

Stănică has proven that for any permutation F over $\mathbb{F}_{q}$ the c-boomerang uniformity can be computed by finding the number of solutions of two c-differentials for F, see [42, Theorem 4]. We can view these differentials as two polynomials in two variables, so each polynomial defines a plane curve in $\mathbb{P}^{2}_{\mathbb{F}_{q}}$ after homogenization. Therefore, the number of joint solutions is simply upper bounded by the intersection number of these two plane curves. Provided that these curves do not have any common irreducible components, then Bézout’s theorem asserts that the intersection number is given by the product of the degrees of the curves, see [17, Theorem 5.61]. For the requirement of Bézout’s theorem, in Sect. 3 we will prove that one of the curves is irreducible and that the other curve is not a multiple of the irreducible one. This will yield the bounds from above theorem.

A natural question is the tightness of our estimations. In Sect. 4, for small d we have performed Gröbner basis computations for the c-boomerang equations. Once such a basis is known, we can estimate the number of solutions of the c-boomerang equations in the algebraic closure ${\overline{\mathbb{F}_{q}}}$ with standard techniques. In our experiments a simple structure for the leading monomials emerged in the c-boomerang Gröbner bases. Provided that this structure holds for any $d \in \mathbb{Z}_{> 1}$ over a prime field $\mathbb{F}_{p}$, we can prove tightness of our inequalities in the sense that generic polynomial-based methods, which only use that $\mathbb{F}_{p}$ is a prime field and d is a power permutation, cannot improve upon our estimation.

In the final part of the paper, Sect. 5, we study the c-uniformities of permutations of $\mathbb{F}_{q}^{n}$ based on the Generalized Triangular Dynamical System (GTDS) [37]. The GTDS is a generic polynomial framework that unifies the most prominent block cipher design strategies, being the Substitution–Permutation Network and the Feistel Network, in a single primitive. For large classes of GTDS we will prove bounds on the c-differential uniformity as well as the c-boomerang uniformity.

While explicit cryptanalytic applications are beyond the scope of this work, we note that attacks which exploit a high c-differential/boomerang uniformity with $c \ne 1$ are not known yet. We stress that our main interest is to provide tools for the cryptanalysis of AO designs in the classical case with $c = 1$. The reason why we analyze the generic case $c \in \mathbb{F}_{q}^\times$ is quite simple. First, our approach via Bézout’s theorem can address all cases in one go. Second, to estimate the classical BCT of a class of GTDS-based permutations we explicitly need the c-boomerang uniformity of $x^d$ for an arbitrary $c \in \mathbb{F}_{q}^\times$.

2 Preliminaries

Let k be a field, then we denote with ${\bar{k}}$ the algebraic closure of k. We denote the multiplicative group of a field with $k^\times = k \setminus \{ 0 \}$. Elements of a vector space ${\textbf{a}} \in k^n$ are denoted with small bold letters, and matrices ${\textbf{M}} \in k^{m \times n}$ are denoted by capital bold letters. Moreover, we denote by ${\textbf{M}} {\textbf{a}}$ the matrix–vector product.

Let $f \in k [x_1, \dots , x_n]$ be a polynomial, and let $x_0$ be an additional variable. We call

$$\begin{aligned} f^\text{hom}(x_0, \dots , x_n) = x_0^{\deg \left( f \right) } \cdot f \left( \frac{x_1}{x_0}, \dots , \frac{x_n}{x_0} \right) \in k [x_0, \dots , x_n] \end{aligned}$$

(1)

the homogenization of f with respect to $x_0$.

By $\mathbb{F}_{q}$ we denote the finite field with q many elements. It is well-known that for $d \in \mathbb{Z}_{\ge 1}$ the power function $x \mapsto x^d$ induces a permutation over $\mathbb{F}_{q}$ if and only if $\gcd (d, q - 1) = 1$, see [31, 7.8. Theorem]. If not specified otherwise we denote the inverse of $x^d$ by $x^\frac{1}{d}$, where $\frac{1}{d}$ represents the unique integer $1 \le e \le q - 2$ such that $e \cdot d \equiv 1 \mod (q - 1)$.

2.1 c-differential uniformity

Key quantity to measure the capabilities of differential cryptanalysis is the so-called differential uniformity [36] of a function. Ellingsen et al. [16] generalized this concept by admitting c-scaled differences.

Definition 2.1

(c-differential uniformity, [16, Definition 1]) Let $\mathbb{F}_{q}$ be a finite field, let $c \in \mathbb{F}_{q}^\times$, and let $F: \mathbb{F}_{q}^{n}\rightarrow \mathbb{F}_{q}^{m}$ be a function.

(1)

Let $\varvec{\Delta x} \in \mathbb{F}_{q}^{n}$ and $\varvec{\Delta y} \in \mathbb{F}_{q}^{m}$. The entry of the c-Differential Distribution Table (c-DDT) of F at $(\varvec{\Delta x}, \varvec{\Delta y})$ is defined as

$$\begin{aligned} _{c}\delta _F (\varvec{\Delta x}, \varvec{\Delta y}) = \left| \left\{ {\textbf{x}} \in \mathbb{F}_{q}^{n}\mid F ({\textbf{x}} + \varvec{\Delta x}) - c \cdot F ({\textbf{x}}) = \varvec{\Delta y} \right\} \right| . \end{aligned}$$

(2)

The c-differential uniformity of F is defined as

$$\begin{aligned} _{c} \delta (F) = \max \left\{ _{c}\delta _F (\varvec{\Delta x}, \varvec{\Delta y}) \mid \varvec{\Delta x} \in \mathbb{F}_{q}^{n},\ \varvec{\Delta y} \in \mathbb{F}_{q}^{m},\ \varvec{\Delta x} \ne {\textbf{0}} \ \text{if} \ c = 1 \right\} . \end{aligned}$$

Obviously, for $c = 1$ we obtain the usual notion of differential uniformity. For power functions, bounding the c-differential uniformity is straight-forward when the characteristic does not divide the exponent.

Lemma 2.2

Let $\mathbb{F}_{q}$ be a finite field of characteristic p, let $c \in \mathbb{F}_{q}^\times$, and let $d \in \mathbb{Z}_{> 1}$ be such that $p \not \mid d$. Then $_{c} \delta \big ( x^d \big ) \le d$.

Proof

Let $\Delta x \in \mathbb{F}_{q}^\times$ and $\Delta y \in \mathbb{F}_{q}$. For $c \ne 1$, $(x + \Delta x)^d - c \cdot x^d = \Delta y$ is a non-trivial polynomial of degree d, so it as $\le d$ many roots in $\mathbb{F}_{q}$. For $c = 1$, $\sum _{i = 0}^{d - 1} \left( {\begin{array}{c}d\\ i\end{array}}\right) \cdot (\Delta x)^{d - i} \cdot x^i = \Delta y$ has the leading term $d \cdot \Delta x$ since $p \not \mid d$, so it is a non-trivial polynomial of degree $d - 1$ which has lass than d roots in $\mathbb{F}_{q}$. $\square$

2.2 c-boomerang uniformity

Now let us recall the definition of the c-boomerang uniformity.

Definition 2.3

(c-boomerang uniformity, [40, Remark 1]) Let $\mathbb{F}_{q}$ be a finite field, let $c \in \mathbb{F}_{q}^\times$, and let $F: \mathbb{F}_{q}^{n}\rightarrow \mathbb{F}_{q}^{m}$ be a function.

(1)

Let ${\textbf{a}} \in \mathbb{F}_{q}^{n}$ and ${\textbf{b}} \in \mathbb{F}_{q}^{m}$. The entry of the c-Boomerang Connectivity Table (c-BCT) of F at $({\textbf{a}}, {\textbf{b}})$ is defined as

$${}_{c} {\mathcal{B}}_F ({\textbf{a}}, {\textbf{b}}) = \left| \left\{ ({\textbf{x}}, {\textbf{y}}) \in \mathbb{F}_{q}^{n}\times \mathbb{F}_{q}^{n}\; \bigg \vert \; \begin{aligned} F ({\textbf{x}} + {\textbf{y}})&- c \cdot F ({\textbf{x}}) = {\textbf{b}} \\ c \cdot F ({\textbf{x}} + {\textbf{y}} + {\textbf{a}})&- F ({\textbf{x}} + {\textbf{a}}) = c \cdot {\textbf{b}} \end{aligned} \right\} \right| . $$

(2)

The c-boomerang uniformity of F is defined as

$$\begin{aligned} \beta _{F, c} = \max _{\begin{array}{c} {\textbf{a}} \in \mathbb{F}_{q}^{n}\setminus \{ {\textbf{0}}\}, \\ {\textbf{b}} \in \mathbb{F}_{q}^{m}\setminus \{ {\textbf{0}} \} \end{array}} {\,}_{c} {{\mathcal{B}}_{F}} ({\textbf{a}}, {\textbf{b}}). \end{aligned}$$

Remark 2.4

Let $F: \mathbb{F}_{q}^{n}\rightarrow \mathbb{F}_{q}^{n}$ be a permutation. Stănică originally defined the c-BCT only for permutations [40, Definition 3]

$$\begin{aligned} _{c} {\mathcal{B}}_F ({\textbf{a}}, {\textbf{b}}) = \left| \left\{ {\textbf{x}} \in \mathbb{F}_{q}^{n}\; \bigg \vert \; F^{-1} \left( c^{-1} \cdot F ({\textbf{x}} + {\textbf{a}}) + {\textbf{b}} \right) - F^{-1} \big ( c \cdot F ({\textbf{x}}) + {\textbf{b}} \big ) = {\textbf{a}} \right\} \right| . \end{aligned}$$

(2)

For $c = 1$ this coincides with the original BCT definition [11, Definition 3.1] over $\mathbb{F}_{2^n}$. Moreover, Definition 2.3 (1) and Equation (2) are equivalent for permutations [40, Theorem 4] but Definition 2.3 (1) is more general since it can also be applied to non-permutations.

Ideally, we would like to have a similar relationship for the c-BCT of $x^d$ and $x^\frac{1}{d}$ as in [40, Proposition 5] for the c-DDT. After some algebraic manipulations we indeed can derive two differential equations for $x^\frac{1}{d}$ starting from the c-boomerang equations for $x^d$, though only for $c = 1$ we again obtain a boomerang equation system.

Lemma 2.5

Let $\mathbb{F}_{q}$ be a finite field, let $c \in \mathbb{F}_{q}^\times$, and let $d \in \mathbb{Z}_{> 1}$ be such that $\gcd (d, q - 1) = 1$. Then

$${}_{c} {\mathcal{B}}_{x^d} (a, b) = \left| \left\{ (x, y) \in \mathbb{F}_{q}^2 \; \Bigg \vert \; \begin{aligned} (x + y)^\frac{1}{d}&- c^{-\frac{1}{d}} \cdot x^\frac{1}{d} = c^{-\frac{1}{d}} \cdot a \\ c^{-\frac{1}{d}} \cdot (x + y + b)^\frac{1}{d}&- \left( x + \frac{b}{c} \right) ^\frac{1}{d} = c^{-\frac{1}{d}} \cdot a \end{aligned} \right\} \right|.$$

Proof

In the c-boomerang equations we first do the substitution $z = x + y$, then we rearrange the system

$$\begin{aligned}&z^d = c \cdot x^d + b, \\&(x + a)^d = c \cdot (z + a)^d - c \cdot b. \end{aligned}$$

Since d induces a permutation over $\mathbb{F}_{q}$, for any $(x, z) \in \mathbb{F}_{q}^2$ this system of equations is equivalent to

$$\begin{aligned}&z = \left( c \cdot x^d + b \right) ^\frac{1}{d}, \\&x + a = c^\frac{1}{d} \cdot \left( (z + a)^d - b \right) ^\frac{1}{d}. \end{aligned}$$

Moreover, for $\mathbb{F}_{q}$-valued solutions we can perform the substitutions ${\hat{x}} = x^d$ and ${\tilde{z}} = (z + a)^d$, this then yields the equivalent system of equations

$$\begin{aligned} {\tilde{z}}^\frac{1}{d} - a&= \left( c \cdot {\hat{x}} + b \right) ^\frac{1}{d}, \\ {\hat{x}}^\frac{1}{d} + a&= c^\frac{1}{d} \cdot \left( {\tilde{z}} - b \right) ^\frac{1}{d}. \end{aligned}$$

Now we perform the substitution ${\hat{z}} = {\tilde{z}} - b$, divide the first equation by $c^\frac{1}{d}$ and rearrange the equations

$$\begin{aligned}&c^{-\frac{1}{d}} \cdot \left( {\hat{z}} + b \right) ^\frac{1}{d} - \left( {\hat{x}} + \frac{b}{c} \right) ^\frac{1}{d} = c^{-\frac{1}{d}} \cdot a, \\&{\hat{z}}^\frac{1}{d} - c^{-\frac{1}{d}} \cdot {\hat{x}}^\frac{1}{d} = c^{-\frac{1}{d}} \cdot a. \end{aligned}$$

After a final substitution ${\hat{z}} = {\hat{x}} + {\hat{y}}$ we obtain the claim. $\square$

Let $\mathbb{F}_{q}$ be a finite field of characteristic p, an additive character of $\mathbb{F}_{q}$ is a map $\chi : \mathbb{F}_{q}\rightarrow \left\{ z \in \mathbb{C} \mid \left| z \right| = 1 \right\}$ such that $\chi (x + y) = \chi (x) \cdot \chi (y)$. Let ${{\,\textrm{Tr}\,}}_{\mathbb{F}_{q}/ \mathbb{F}_{p}}: \mathbb{F}_{q}\rightarrow \mathbb{F}_{p}$ be the trace function, then

$$\begin{aligned} \chi _1 (x) = \exp \left( 2 \cdot i \cdot \pi \cdot {{\,\textrm{Tr}\,}}_{\mathbb{F}_{q}/ \mathbb{F}_{p}} (x) \right) \end{aligned}$$

(3)

is called the fundamental character of $\mathbb{F}_{q}$. It is well-known that any additive character $\chi$ of $\mathbb{F}_{q}$ is of the form $\chi (x) = \chi _1 (a \cdot x)$ for some $a \in \mathbb{F}_{q}$, see [31, 5.7. Theorem]. To the best of our knowledge, closest to an estimation of the c-boomerang uniformity of $x^d$ is the following characterization of the c-BCT in terms of character sums due to Stănică.

Theorem 2.6

[42, Theorem 1] Let $\mathbb{F}_{q}$ be a finite field, let $c \in \mathbb{F}_{q}^\times$, and let $d \in \mathbb{Z}_{\ge 1}$. For $a \in \mathbb{F}_{q}^\times$ and $b \in \mathbb{F}_{q}$ the c-Boomerang Connectivity Table entry $_{c} {\mathcal{B}}_{x^d} (a, a^d \cdot b)$ of $x^d$ is given by

$$\begin{aligned} \frac{1}{q} \cdot \left( _{c} \delta _{x^d} (1, b) + _{c^{-1}} \delta _{x^d} (1, b) \right) + 1 + \frac{1}{q^2} \cdot \sum _{\begin{array}{c} \alpha , \beta \in \mathbb{F}_{q}, \\ \alpha \cdot \beta \ne 0 \end{array}} \chi _1 \big ( -b \cdot (\alpha + \beta ) \big ) \cdot S_{\alpha , \beta } \cdot S_{-\alpha \cdot c, -\beta \cdot c^{-1}}, \end{aligned}$$

with

$$\begin{aligned} S_{\alpha , \beta } = \sum _{x \in \mathbb{F}_{q}} \chi _1 \left( \alpha \cdot x^d \right) \cdot \chi _1 \left( \beta \cdot \left( x + 1 \right) ^d \right) . \end{aligned}$$

Combined with [43, Theorem 4] one could then compute entries of the c-BCT via character sums. Though, the AO designs mentioned in the introduction are all defined over prime fields $p \ge 2^{60}$, and over such fields these computations are simply infeasible in practice.

Finally, let us compute the c-boomerang uniformity for a special class of polynomials. Over a finite field $\mathbb{F}_{p^n}$, a polynomial of the form

$$\begin{aligned} f (x) = \sum _{i = 1}^{n - 1} a_i \cdot x^{p^i} \end{aligned}$$

is called a linearized polynomial since $f (x + y) = f (x) + f (y)$ for all $x, y \in \mathbb{F}_{p^n}$.

Lemma 2.7

Let $\mathbb{F}_{q}$ be a finite field, let $a, b \in \mathbb{F}_{q}$ and $c \in \mathbb{F}_{q}^\times$, and let $f \in \mathbb{F}_{q}[x]$ be a linearized permutation polynomial. Then

$$\begin{aligned} _{c} {\mathcal{B}}_f (a, b) = {\left\{ \begin{array}{ll} 1, & c^2 \ne 1, \\ 0, & c = -1,\ a \ne 0, \\ q, & c = -1,\ a = 0, \\ q, & c = 1. \end{array}\right. } \end{aligned}$$

Proof

We have for the boomerang equation that, see Remark 2.4,

$$\begin{aligned}&f^{-1} \Big ( c^{-1} \cdot f (x + a) + b \Big ) - f^{-1} \Big ( c \cdot f (x) + b \Big ) \\&= f^{-1} \Big ( c^{-1} \cdot f (x + a) \Big ) - f^{-1} \Big ( c \cdot f (x) \Big ) \\&= f^{-1} \Big ( \big ( c^{-1} - c \big ) \cdot f (x) \Big ) + f^{-1} \big ( c^{-1} \cdot f (a) \big ) \\&= a. \end{aligned}$$

Rearranging and application of f to both sides yields

$$\begin{aligned} \left( c^{-1} - c \right) \cdot f (x) = \left( 1 - c^{-1} \right) \cdot f (a). \end{aligned}$$

If $c^2 \ne 1$, then this equation has a unique solution. If $c = -1$, then $2 \cdot f (a) = 0$, so depending on a we either have zero or q many solutions. Finally if $c = 1$, then both sides vanish, so it has q solutions. $\square$

Therefore, for the remainder of the paper we are only going to study non-linearized permutation monomials.

2.3 Plane curves

Let R be a ring, then ${{\,\textrm{Spec}\,}}(R) = \{ {\mathfrak {p}} \subset R \mid {\mathfrak {p}} \text{ prime ideal} \}$ is called the spectrum of R. Also, ${{\,\textrm{Spec}\,}}(R)$ can be equipped with the Zariski topology, see [17, §2.1]. A locally ringed space $(X, {\mathcal{O}}_X)$ is a topological space X together with a sheaf of commutative rings ${\mathcal{O}}_X$ on X. If in addition $(X, {\mathcal{O}}_X)$ is isomorphic to $\big ( {{\,\textrm{Spec}\,}}(R), {\mathcal{O}}_{{{\,\textrm{Spec}\,}}(R)} \big )$ for some ring R, then $(X, {\mathcal{O}}_X)$ is called an affine scheme. A scheme $(X, {\mathcal{O}}_X)$ is a locally ringed space that admits an open covering $X = \bigcup _i U_i$ of affine schemes $(U_i, {\mathcal{O}}_X \vert _{U_i})$. For a scheme $(X, {\mathcal{O}}_X)$ the ring $\Gamma (X, {\mathcal{O}}_X) = {\mathcal{O}}_X (X)$ is also known as the global sections of X. For a general introduction into the theory of schemes we refer to [17].

Let R be a ring, then the n-dimensional affine space $\mathbb{A}^{n}_{R}$ is defined to be the scheme ${{\,\textrm{Spec}\,}}\big ( R [x_1, \dots , x_n] \big )$. Moreover, the n-dimensional projective space $\mathbb{P}^{n}_{R}$ over R can be constructed by gluing $n + 1$ copies of the affine space $\mathbb{A}^{n}_{R}$, see [17, §3.6]. Note that there also exists a natural morphism of schemes $p: \mathbb{A}^{n + 1}_{R} {\setminus } \{ 0 \} \rightarrow \mathbb{P}^{n}_{R}$. Now let $R [X_0, \dots , X_n]$ be graded via the degree, and let $I \subset R [X_0, \dots , X_n]$ be a homogeneous ideal. Analog to the construction of p one can construct a scheme ${\mathcal{V}}_+ (I)$ together with a closed immersion $\iota : {\mathcal{V}}_+ (I) \rightarrow \mathbb{P}^{n}_{R}$, ${\mathcal{V}}_+ (I)$ is also called the vanishing scheme of I, see [17, §3.7].

Now let k be a field, it is well-known that $\mathbb{P}^{n}_{k}$ and any closed subspace of it are separated and of finite type over k. Let $F, G \in k [X_0, X, Y]$ be homogeneous polynomials, then ${\mathcal{V}}_+ (F) \subset \mathbb{P}^{2}_{k}$ is called a plane curve over k. Moreover, we have for the scheme-theoretic intersection of two plane curves, see [17, Example 4.38],

$$\begin{aligned} {\mathcal{V}}_+ (F) \cap {\mathcal{V}}_+ (G) = {\mathcal{V}}_+ (F, G) \subset \mathbb{P}^{2}_{k}. \end{aligned}$$

(4)

A classical problem in algebraic geometry is to count the number of intersection points of two plane curves together with their multiplicities.

Definition 2.8

[17, Definition 5.60] Let k be a field, and let $C, D \subset \mathbb{P}^{2}_{k}$ be two plane curves such that $Z:= C \cap D$ is a k-scheme of dimension 0. Then we call $i (C, D):= \dim _k \big ( \Gamma (Z, {\mathcal{O}}_Z) \big )$ the intersection number of C and D. For $z \in Z$ we call $i_z (C, D):= \dim _k ({\mathcal{O}}_{Z, z})$ the intersection number of C and D at z.

It can be easily seen that

$$\begin{aligned} i (C, D) = \sum _{z \in C \cap D} i_z (C, D). \end{aligned}$$

(5)

By Bézout’s famous theorem, for two plane curves that do not have any common irreducible components the intersection number is simply the product of the degrees of the curves.

Theorem 2.9

(Bézout’s theorem, [17, Theorem 5.61]) Let k be a field, and let $C = {\mathcal{V}}_+ (F)$ and $D = {\mathcal{V}}_+ (G)$ be plane curves in $\mathbb{P}^{2}_{k}$ given by polynomials without a common factor. Then

$$\begin{aligned} i (C, D) = \deg \left( F \right) \cdot \deg \left( G \right) . \end{aligned}$$

In particular, the intersection $C \cap D$ is non-empty and consists of a finite number of closed points.

2.4 Gröbner bases

Let k be a field, and let > be a term order on $P = k [x_1, \dots , x_n]$. For an ideal $I \subset P$ a >-Gröbner basis is a finite generating set ${\mathcal{G}} \subset I$ such that

$$\begin{aligned} \big ( {{\,\textrm{LM}\,}}_> (f) \mid f \in I \big ) = \big ( {{\,\textrm{LM}\,}}_> (g) \mid g \in {\mathcal{G}} \big ). \end{aligned}$$

(6)

With Gröbner bases one can solve many computational problems like the ideal membership problem or the computation of the affine variety ${\mathcal{V}} \left( I \right) \subset \mathbb{A}^{n}_{k}$. For a general introduction to Gröbner bases we refer to [12, 28, 29].

Let ${{\,\textrm{LM}\,}}_> \left( I \right) = \big ( {{\,\textrm{LM}\,}}_> (f) \mid f \in I \big )$ denote the ideal of leading monomials, and assume in addition that $\dim \left( P / I \right) = 0$. Then it is well-known that, see [12, Chapter 5 §3 Proposition 7],

$$\begin{aligned} \left| {\mathcal{V}} \left( I \right) \right| \le \dim _k \big ( P / {{\,\textrm{LM}\,}}_> (I) \big ) < \infty , \end{aligned}$$

(7)

and the first inequality becomes an equality if k is algebraically closed and I is radical.

3 Generalized c-boomerang equations for monomials

As an alternative approach to Theorem 2.6, to estimate the c-boomerang uniformity of $x^d$ we study the following system of equations in two variables.

Definition 3.1

Let $\mathbb{F}_{q}$ be a finite field, let $d \in \mathbb{Z}_{> 1}$, and let $c_1, \dots , c_5 \in \mathbb{F}_{q}$. Then we call

$$\begin{aligned} {\mathcal{F}} (d, c_1, \dots , c_5) = \left\{ \begin{array}{ c c c c } z^d & - & c_1 \cdot x^d & = c_2, \\ (z + 1)^d & - & c_3 \cdot (x + c_4)^d & = c_5, \end{array} \right. \end{aligned}$$

the generalized boomerang equation system for $x^d$.

Note that we can transform any c-boomerang equations

$$\begin{aligned}&(x + y)^d - c \cdot x^d = b, \\&c \cdot (x + y + a)^d - (x + a)^d = c \cdot b \end{aligned}$$

(8)

into this shape by dividing both equations by $a^d$, the second equation by c, and then performing the substitutions

$$\begin{aligned}\begin{array}{llll}&{\hat{z}} = \frac{x + y}{a}, \qquad & {\hat{x}} = \frac{x}{a}, \qquad & c_1 = c, \\&c_2 = c_5 = \frac{b}{a^d}, \qquad & c_3 = c^{-1}, \qquad & c_4 = 1. \end{array}\end{aligned}$$

(9)

To bound the number of solutions of the generalized boomerang equation system we need two lemmata.

Lemma 3.2

Let $\mathbb{F}_{q}$ be a finite field of characteristic p, let $d \in \mathbb{Z}_{> 1}$ be such that $\gcd (d, q - 1) = 1$ and $p \not \mid d$, and let $a, b \in \mathbb{F}_{q}^\times$ be such that $b^d = a$. Then $x^d - a$ factors as

$$\begin{aligned} x^d - a = (x - b) \cdot g (x), \end{aligned}$$

where $g \in \mathbb{F}_{q}[x]$ does not have any roots in $\mathbb{F}_{q}$.

Proof

For $a,b \ne 0$, we have the factorization

$$\begin{aligned} x^d - a = (x - b) \cdot \left( \sum _{i = 0}^{d - 1} a_i \cdot x^i \right) , \end{aligned}$$

where

$$\begin{aligned} -b \cdot a_0&= -a, \\ a_0 - b \cdot a_1&= 0, \\&\ldots \\ a_{d - 2} - b \cdot a_{d - 1}&= 0, \\ a_{d - 1}&= 1. \end{aligned}$$

Therefore, $a_i = \frac{a}{b^{i + 1}}$ and henceforth $g (x) = \frac{a}{b} \cdot \sum _{i = 0}^{d - 1} \left( \frac{x}{b} \right) ^i$. Also, note that $a_{d - 1} = \frac{a}{b^d} = \frac{a}{a} = 1$ by the assumption. Let us verify that b is not a root of g:

$$\begin{aligned} g (b) = \frac{a}{b} \cdot \sum _{i = 0}^{d - 1} \left( \frac{b}{b} \right) ^i = \frac{a}{b} \cdot d \ne 0, \end{aligned}$$

since the characteristic p does not divide d. On the other hand, $x^d = a$ must have a unique solution in $\mathbb{F}_{q}$, see [31, 7.1. Lemma], so g cannot have any roots in $\mathbb{F}_{q}$. $\square$

Lemma 3.3

Let $\mathbb{F}_{q}$ be a finite field of characteristic p, let $d \in \mathbb{Z}_{> 1}$ be such that $\gcd \left( d, q - 1\right) = 1$ and $p \not \mid d$, and let $a, b \in \mathbb{F}_{q}^\times$. Then

$$\begin{aligned} z^d - a \cdot x^d - b \end{aligned}$$

is irreducible over ${\overline{\mathbb{F}_{q}}}$.

Proof

Let $f = z^d - a \cdot x^d - b$ and let $R = {\overline{\mathbb{F}_{q}}} [x]$, we are going to apply Eisenstein’s irreducibility criterion [30, Chapter IV §3 Theorem 3.1] over R[z]. Then f has the coefficients $a_d = 1$, $a_{d - 1}, \dots , a_1 = 0$ and $a_0 = a \cdot x^d - b$. By Lemma 3.2 we have the factorization

$$\begin{aligned} a \cdot x^d + b = (x - c) \cdot g (x), \end{aligned}$$

where $c \in \mathbb{F}_{q}^\times$ is the unique solution of $x^d = -\frac{b}{a}$ and $g \in \mathbb{F}_{q}[x]$ does not have any roots over $\mathbb{F}_{q}$. Now we choose the prime ideal ${\mathfrak {p}} = (x - c) \subset R$, then trivially we have that $a_0, \dots , a_{d - 1} \in {\mathfrak {p}}$ and $a_d \notin {\mathfrak {p}}$. Since c cannot be a root of g(x) in the algebraic closure ${\overline{\mathbb{F}_{q}}}$ (if it were, then g(x) would have roots over $\mathbb{F}_{q}$) we also have that $a_0 \notin {\mathfrak {p}}^2$. So by Eisenstein’s criterion f is irreducible over $\mathbb{F}_{q}$ as well as ${\overline{\mathbb{F}_{q}}}$. $\square$

Now we can use Bézout’s theorem to upper bound the number of solutions of the generalized boomerang equation.

Theorem 3.4

Let $\mathbb{F}_{q}$ be a finite field of characteristic p, let $d \in \mathbb{Z}_{> 1}$ be such that $\gcd (d, q - 1) = 1$ and $p \not \mid d$, and let $c_1, \dots , c_5 \in \mathbb{F}_{q}^\times$. Then the generalized boomerang equation system ${\mathcal{F}} (d, c_1, \dots , c_5)$ has at most $d^2$ many solutions over the algebraic closure ${\overline{\mathbb{F}_{q}}}$.

Proof

For ease of reading we denote the algebraic closure of $\mathbb{F}_{q}$ as $k = {\overline{\mathbb{F}_{q}}}$. Let ${\mathcal{F}} (d, c_1, \dots ,c_5) = \{ f_1, f_2 \} \subset k [z, x]$ be the generalized boomerang equation system. First we homogenize the polynomial system with respect to the variable $X_0$, and we denote the homogenizations as $F_1 = f_1^\text{hom}$ and $F_2 = f_2^\text{hom}$. Then $F_1$ and $F_2$ define plane curves over k, i.e. closed subschemes $C = {\mathcal{V}}_+ (F_1)$ and $D = {\mathcal{V}}_+ (F_2)$ of $\mathbb{P}^{2}_{k}$. Note that factorization of a polynomial is invariant under homogenization, see [29, Proposition 4.3.2], so by Lemma 3.3$F_1$ is irreducible in $k [X_0, Z, X]$. To apply Bézout’s theorem we have to verify that $F_1$ and $F_2$ do not have a common factor, so let us take a look at the inhomogeneous equations

$$\begin{aligned} f_1&= z^d - c_1 \cdot x^d - c_2, \\ f_2&= (z + 1)^d - c_3 \cdot (x + c_4)^d - c_5. \end{aligned}$$

Suppose they have a common factor, since $f_1$ is irreducible by Lemma 3.3 we can then only have that $f_2 = \alpha \cdot f_1$, where $\alpha \in k^\times$. On the other hand, since by assumption d is not a power of the characteristic p we have for some $1 \le i \le d - 1$ that $\left( {\begin{array}{c}d\\ i\end{array}}\right) \ne 0$ in $\mathbb{F}_{q}$. I.e., the monomial $z^i$ is present in $f_2$ and therefore $f_2$ cannot be a multiple of $f_1$. So, by Bézout’s theorem [17, Theorem 5.61] we have for the intersection number of C and D that

$$\begin{aligned} i \big ( C, D \big ) = \deg \left( F_1 \right) \cdot \deg \left( F_2 \right) = d^2. \end{aligned}$$

On the other hand, by definition of the intersection number we have that

$$\begin{aligned} i \big ( C, D \big )&= \sum _{z \in C \cap D} \dim _k \left( {\mathcal{O}}_{C \cap D, z} \right) \\&\ge \sum _{z \in C \cap D} 1, \end{aligned}$$

where the latter inequality follows from $k \hookrightarrow {\mathcal{O}}_{C \cap D, z}$. By [17, Lemma 5.59] $C \cap D$ is a zero-dimensional scheme, now let $x \in C \cap D$ be a point. Then there exists an affine open subscheme $U = {{\,\textrm{Spec}\,}}(A) \subset C \cap D$ such that $x \in U$. Moreover, by [17, Lemma 5.7] $0 \le \dim (U) \le \dim (C \cap D) = 0$, hence x corresponds to a maximal ideal ${\mathfrak {m}}_x \in U$. Since $C \cap D$ is a closed subscheme of $\mathbb{P}^{2}_{k}$ it is of finite type, therefore U is also of finite type. By Hilbert’s Nullstellensatz [17, Theorem 1.17] $k \subset A / {\mathfrak {m}}_x$ is a finite field extension, so by [17, Proposition 3.33] this already implies that x is closed in $C \cap D$. In particular, every point in our intersection is closed. Further, recall the set of k-valued points, see [17, Example 5.3],

$$\begin{aligned} C\cap D (k) = {\mathcal{V}}_+ (F_1, F_2) \big ( k \big )&= {{\,\textrm{Hom}\,}}_{k} \Big ( {{\,\textrm{Spec}\,}}\big ( k \big ), {\mathcal{V}}_+ (F_1, F_2) \Big ) \\&= \left\{ {\textbf{x}} \in \mathbb{P}^{2}_{k} \big ( k \big ) \; \bigg \vert \; F_1 ({\textbf{x}}) = F_2 ({\textbf{x}}) = 0 \right\} . \end{aligned}$$

Since k is algebraically closed and ${\mathcal{V}}_+ (F_1, F_2)$ is of finite type there is a one-to-one bijection between the closed points of ${\mathcal{V}}_+ (F_1, F_2)$ and the k-valued points of ${\mathcal{V}}_+ (F_1, F_2)$, see [17, Corollary 3.36]. Summing up all these observations we have derived the inequality

$$\begin{aligned} \left| \left\{ {\textbf{x}} \in \mathbb{P}^{2}_{k} \; \bigg \vert \; F_1 ({\textbf{x}}) = F_2 ({\textbf{x}}) = 0 \right\} \right| \le d^2. \end{aligned}$$

Finally, let $U_0 = \left\{ (X_0, Z, X) \in \mathbb{P}^{2}_{k} \; \bigg \vert \; T \ne 0 \right\}$, then we can compute the affine solutions of $f_1 = f_2 = 0$ via, see [12, Chapter 8 §2 Proposition 6],

$$\begin{aligned} \left\{ (z, x) \in k^2 \; \bigg \vert \; f_1 (z, x) = f_2 (z, x) = 0 \right\} = \left\{ {\textbf{x}} \in \mathbb{P}^{2}_{k} \; \bigg \vert \; F_1 ({\textbf{x}}) = F_2 ({\textbf{x}}) = 0 \right\} \cap U_0. \end{aligned}$$

So also the number of affine solutions to the generalized boomerang equation system ${\mathcal{F}} (d, c_1, \dots , c_5)$ is bounded by $d^2$ over k. $\square$

For the application to $c = 1$ we will additionally exploit the factorization of difference polynomials $f (x) - f (y) = 0$.

Lemma 3.5

Let k be a field, and let $f \in k [x]$ be a non-constant polynomial. Then

$$\begin{aligned} f (x) - f (y) = (x - y) \cdot g (x, y) \in k [x, y], \end{aligned}$$

where $g \in k [x, y]$ is some non-zero polynomial.

Proof

Let $d = \deg \left( f \right)$, we have that

$$\begin{aligned} f (x) - f (y) = \sum _{l = 1}^{d} a_l \cdot (x^l - y^l). \end{aligned}$$

So it is sufficient to show the claim for $(x^l - y^l)$. But then for $l \ge 2$

$$\begin{aligned} (x - y) \cdot \left( \sum _{\begin{array}{c} i \ge 0,\\ j \ge 0, \\ i + j = l - 1 \end{array}} x^i \cdot y^j \right) = x^l + \underbrace{\left( \sum _{\begin{array}{c} i \ge 0,\\ j \ge 1, \\ i + j = l - 1 \end{array}} x^{i + 1} \cdot y^j \right) }_{= \sigma _1} - \underbrace{\left( \sum _{\begin{array}{c} i \ge 1,\\ j \ge 0, \\ i + j = l - 1 \end{array}} x^i \cdot y^{j + 1} \right) }_{= \sigma _2} - y^l. \end{aligned}$$

In $\sigma _1$ we perform an index shift $i \mapsto i - 1$ and in $\sigma _2$ we perform an index shift $j \mapsto j - 1$ which yields

$$\begin{aligned} \sigma _1 = \sigma _2 = \sum _{\begin{array}{c} i \ge 1, \\ j \ge 1, \\ i + j = l \end{array}} x^i \cdot y^j, \end{aligned}$$

so the claim follows. $\square$

Application of Theorem 3.4 and Lemma 3.5 now yields our bound on the c-boomerang uniformity of power permutations $x^d$.

Corollary 3.6

Let $\mathbb{F}_{q}$ be a finite field of characteristic p, let $c \in \mathbb{F}_{q}^\times$, and let $d \in \mathbb{Z}_{> 1}$ be such that $\gcd (d, q - 1) = 1$ and $p \not \mid d$. Then

(1)

$\beta _{x^d, c} \le {\left\{ \begin{array}{ll} d^2, & c^2 \ne 1, \\ d \cdot (d - 1), & c = -1, \\ d \cdot (d - 2), & c = 1. \end{array}\right. }$

(2)

$\beta _{x^\frac{1}{d}, c} \le {\left\{ \begin{array}{ll} d^2, & c^2 \ne 1, \\ d \cdot (d - 1), & c = -1, \\ d \cdot (d - 2), & c = 1. \end{array}\right. }$

Proof

For (1):

For $c^2 \ne 1$ the claim follows from Theorem 3.4 and the transformation of the c-boomerang equations into a generalized boomerang equation system, see Equation (9).
For $c^2 = 1$, we take a closer look at the c-boomerang equations for some $a \cdot b \ne 0$
$$\begin{aligned} f_1&= z^d - c \cdot x^d - b, \\ f_2&= (z + a)^d - c^{-1} \cdot (x + a)^d - b. \end{aligned}$$
Then
$$\begin{aligned} f_1 - f_2 = \left( z^d - (z + a)^d \right) - c \cdot \left( x^d - (x + a)^d \right) , \end{aligned}$$
and by expanding the binomial theorem for $(z + a)^d$ and $(x + a)^d$ we see that $\deg \left( f_1 - f_2 \right) \le d - 1$. Again by Lemma 3.3 we know that $f_1$ is irreducible, so the homogenizations of $f_1$ and $f_1 - f_2$ cannot share any irreducible components, and we can again apply Bézout’s theorem to bound the number of solutions analog to Theorem 3.4. This yields the claim for $c = -1$.
For $c = 1$, we can exploit by Lemma 3.5 that
$$\begin{aligned} f_1 - f_2 = \left( z^d - (z + a)^d \right) - \left( x^d - (x + a)^d \right) = g (z) - g (x) = (z - x) \cdot {\tilde{g}} (z, x), \end{aligned}$$
where $g \in \mathbb{F}_{q}[x]$ is a non-constant univariate polynomial with $\deg \left( g \right) \le d - 1$ and ${\tilde{g}} \in \mathbb{F}_{q}[z, x]$ is a non-zero polynomial with $\deg \left( {\tilde{g}} \right) \le d - 2$. But then a root of $f_1 - f_2$ is either a root of $z - x = 0$ or ${\tilde{g}} = 0$. In the first case, we can substitute $z = x$ into $f_1$ which yields $0 = b$. So if $b \ne 0$, then $z - x = 0$ cannot contribute any solutions to the boomerang equations. Hence, to estimate the $\mathbb{F}_{q}$-valued solutions we can restrict to $f_1 = {\tilde{g}} = 0$, and by the irreducibility of $f_1$ we can again apply Bézout’s theorem to their homogenizations analog to Theorem 3.4.

For (2), recall that by Lemma 2.5

$$\begin{aligned} _{c} {\mathcal{B}}_{x^\frac{1}{d}} (a, b) = \left| \left\{ (x, y) \in \mathbb{F}_{q}^2 \; \bigg \vert \; \begin{aligned} (x + y)^d&- c^{-d} \cdot x^d = c^{-d} \cdot a \\ c^{-d} \cdot (x + y + b)^d&- \left( x + \frac{b}{c} \right) ^d = c^{-d} \cdot a \end{aligned} \right\} \right| . \end{aligned}$$

(10)

Also note that our permutation exponent d has to be odd. For $p \ne 2$ this is obvious, and for $p = 2$ it follows from the assumption that $p \not \mid d$. In particular, for $c^2 = 1$ we have that $c^d = c^{-d} = c$.

For $c^2 \ne 1$, we can transform Eq. (10) into a generalized boomerang equation system by dividing both equations by $b^d$, the second equation by $c^{-d}$ and the substitutions ${\hat{z}} = \frac{x + y}{b}$ and ${\hat{x}} = \frac{x}{b}$. Then we can again apply Theorem 3.4.
For $c^2 = 1$, after the substitution $z = x + y$ and multiplication by c Eq. (10) reduces to
$$\begin{aligned} f_1&= z^d - c \cdot x^d - c \cdot a, \\ f_2&= (z + b)^d - c \cdot (x + c \cdot b)^d - a. \end{aligned}$$
Then
$$\begin{aligned} f_1 - f_2 = \left( z^d - (z + b)^d \right) - c \cdot \left( x^d - (x + c \cdot b)^d \right) + a \cdot (1 - c). \end{aligned}$$
So for $c = -1$ we can again pass to $f_1 = f_1 - f_2 = 0$, and for $c = 1$ we can apply the factorization trick of Lemma 3.5 for the application of Bézout’s theorem.

$\square$

Corollary 3.7

Let $\mathbb{F}_{p^n}$ be a finite field, let $c \in \mathbb{F}_{p^n}^\times$, let $d \in \mathbb{Z}_{> 1}$ be such that $\gcd (d, p^n - 1) = 1$ and $p \not \mid d$, and let $1 \le i < n$. Then

(1)

$\beta _{x^{d \cdot p^i}, c} \le {\left\{ \begin{array}{ll} d^2, & c^2 \ne 1, \\ d \cdot (d - 1), & c = -1, \\ d \cdot (d - 2), & c = 1. \end{array}\right. }$

(2)

$\beta _{x^\frac{1}{d \cdot p^i}, c} \le {\left\{ \begin{array}{ll} d^2, & c^2 \ne 1, \\ d \cdot (d - 1), & c = -1, \\ d \cdot (d - 2), & c = 1. \end{array}\right. }$

Proof

Note that $(d \cdot p^i) \cdot p^{n - i} \equiv d \cdot p^n \equiv d \mod (p^n - 1)$, which implies that $\left( x^{d \cdot p^i} \right) ^{p^{n - i}} \equiv x^d \mod \left( x^{p^n} - x \right)$. For (1), we set up the c-boomerang equations for $x^{d \cdot p^i}$, then we raise them to the $p^{n - i}$-th power. For (2), we set up c-boomerang equations for $x^\frac{1}{d \cdot p^i}$, raise them to the $p^i$-th power, and then transform them into the equations from Lemma 2.5. Then the claim follows from Corollary 3.6. $\square$

Remark 3.8

For an arbitrary permutation polynomial $F \in \mathbb{F}_{q}[x]$, if one can prove that the polynomial

$$\begin{aligned} F (x + y) - c \cdot F (x) - b \end{aligned}$$

is irreducible for over ${\overline{\mathbb{F}_{q}}}$ for all $b, c \in \mathbb{F}_{q}^\times$, and that the polynomial

$$\begin{aligned} c \cdot F (x + y + a) - F (x + a) - c \cdot b \end{aligned}$$

has at least one term that is not present in $F (x + y) - c \cdot F (x) - b$ for all $a, b, c \in \mathbb{F}_{q}^\times$, then one can also prove via Bézout’s theorem that $\beta _{F, c} \le \deg \left( F \right) ^2$.

3.1 The cases $a = 0$ & $b = 0$

For completeness, let us also compute the c-BCT table entry for a permutation monomial $x^d$ when either $a = 0$ or $b = 0$.

Lemma 3.9

Let $\mathbb{F}_{q}$ be a finite field, let $d \in \mathbb{Z}_{> 1}$ be such that $\gcd \left( d, q - 1 \right) = 1$ and $p \not \mid d$, and let $a, b, c \in \mathbb{F}_{q}^\times$. Then

(1)

$_{c} {\mathcal{B}}_{x^d} (0, b) = {\left\{ \begin{array}{ll} 1, & c^2 \ne 1, \\ q, & c^2 = 1. \end{array}\right. }$

(2)

$_{c} {\mathcal{B}}_{x^d} (a, 0) = {\left\{ \begin{array}{ll} 1, & c^2 \ne 1, \\ 0, & c = -1, \\ q, & c = 1. \end{array}\right. }$

(3)

$_{c} {\mathcal{B}}_{x^d} (0, 0) = {\left\{ \begin{array}{ll} 1, & c^2 \ne 1, \\ q, & c^2 = 1. \end{array}\right. }$

Proof

For (1), by Definition 2.3 we have that

$$\begin{aligned}z^d - c \cdot x^d &= b, \\ z^d - c^{-1} \cdot x^d &= b \\ \Rightarrow \left( c^{-1} - c \right) \cdot x^d &= 0. \end{aligned}$$

If $c^2 = 1$, then the left-hand side vanishes, so there are q solutions for x. If $c^2 \ne 1$, then there is a unique solution for x.

For (2), by Remark 2.4 we have that

$$\begin{aligned} \left( c^{-1} \cdot (x + a)^d \right) ^\frac{1}{d} - \left( c \cdot x^d \right) ^\frac{1}{d} &= a \\ c^{-\frac{1}{d}} \cdot (x + a) - c^\frac{1}{d} \cdot x &= a \\ \Rightarrow \left( c^{-\frac{1}{d}} - c^\frac{1}{d} \right) \cdot x &= \left( 1 - c^{-\frac{1}{d}} \right) \cdot a. \end{aligned}$$

We have that $c^{-\frac{1}{d}} = c^\frac{1}{d}$ if and only if $c^2 = 1$, else there is a unique solution for x. If $c = 1$, then the left and the right-hand side vanish, so we have q solutions for x. If $c = -1$, then recall that $p \not \mid d$ implies that d is odd, so the left-hand side vanishes, but the right one does not, and we have 0 solutions for x.

For (3), by Definition 2.3 we have that

$$\begin{aligned}&z^d - c \cdot x^d = 0, \\&z^d - c^{-1} \cdot x^d = 0. \end{aligned}$$

So for $c - c^{-1} \ne 0$ we have a unique solution for x and henceforth also for z, otherwise we have q possible solutions for (z, x). $\square$

4 On the tightness of the c-boomerang uniformity bound

In this section we investigate tightness of our inequalities from Corollary 3.6 for small exponents d over prime fields. First, we perform Gröbner basis computations of the c-boomerang equations. For specified $a, b \in \mathbb{F}_{q}^\times$ we can set up the c-boomerang ideal $(f_1, f_2) \subset \mathbb{F}_{q}[z, x]$, and compute its degree reverse lexicographic (DRL) Gröbner basis. Given a Gröbner basis we can then estimate the number of solutions over ${\overline{\mathbb{F}_{q}}}$ with standard Gröbner basis techniques, see Eq. (7). However, for a generic treatment we consider a and b as symbolic invertible variables, i.e. we work over the transcendent field extension $\mathbb{F}_{q}\subset \mathbb{F}_{q}(a, b)$. Provided we can then also compute a DRL Gröbner basis for $(f_1, f_2)$, and that the coefficients of monomials in the basis are well-defined for all $a, b \in \mathbb{F}_{q}^\times$, then we computationally yield a generic bound for the number of solutions of the c-boomerang equations.

Second, we exhaustively compute the c-boomerang table over small prime fields to observe whether our upper bounds are met.

4.1 Symbolic Gröbner basis computations

Let us shortly outline the methodology for our symbolic Gröbner basis computations. We assume that $\mathbb{F}_{q}$ is a prime field, and that $d \in \mathbb{Z}_{> 1}$ induces a permutation over $\mathbb{F}_{q}$. Of course, for actual computations in a computer algebra program like SageMath [39] we have to specify a prime q. However, for a generic treatment we can apply another trick. For a fixed $c \in \mathbb{F}_{q}$, we interpret the c-boomerang equations

$$\begin{aligned} f_1&= z^d - c \cdot x^d - b, \\ f_2&= (z + a)^d - c^{-1} \cdot (x + a)^d - b, \end{aligned}$$

(11)

as symbolic polynomials over $\mathbb{Q} (a, b) [z, x]$ instead of $\mathbb{F}_{q}(a, b) [z, x]$. Next we compute the reduced DRL Gröbner basis ${\mathcal{G}} = \{ g_1, \dots , g_m \} \subset (f_1, f_2)$, where $z >_{DRL} x$. In addition, we assume that the leading coefficient of all $g_i$ is 1. We can then express the $f_i$’s and the $g_j$’s as

$$\begin{aligned} f_i&= \sum _{j = 1}^{m} h_{i, j} \cdot g_j, \end{aligned}$$

(12)

$$\begin{aligned} g_j&= {\hat{h}}_1 \cdot f_1 + {\hat{h}}_2 \cdot f_2 , \end{aligned}$$

(13)

where $h_{i, j}, {\hat{h}}_1, {\hat{h}}_2 \in \mathbb{Q} (a, b) [z, x]$. The decomposition in Eq. (12) can for example be found via multivariate division by remainder, see [12, §3]. For the decomposition in Eq. (13) we have to manually store the path to construct the Gröbner basis to compute the ${\hat{h}}_i$’s. To project the Gröbner basis to $\mathbb{F}_{q}$ for a specific q, we inspect the denominators of the coefficients of all $h_{i, j}$, ${\hat{h}}_i$ and $g_j$ in $\mathbb{Q} (a, b)$. If all denominators are coprime to q, then we can project ${\mathcal{G}}$ and Eq. (12) to $\mathbb{F}_{q}(a, b) [z, x]$ by simply taking all coefficients modulo q. Next we verify that the sum decompositions in Eqs. (12) and (13) are non-zero modulo q. If the answer is yes, then we also found the DRL Gröbner basis of $(f_1, f_2) \subset \mathbb{F}_{q}(a, b) [z, x]$. Thus, under minor restrictions on q we can use our generic Gröbner basis computations over $\mathbb{Q} (a, b) [z, x]$ to obtain a computational upper bound on the c-boomerang uniformity of permutation monomials.

In Appendix A.1 we provide a SageMath [39] script to compute the generic DRL Gröbner basis for the c-boomerang equations.

4.1.1 $c^2 \ne 1$

The case $c^2 \ne 1$ can actually be settled by hand.

Lemma 4.1

Let $\mathbb{F}_{q}$ be a finite field, let $d \in \mathbb{Z}_{> 1}$ be such that $\gcd \left( d, q - 1 \right) = 1$, and let $c \in \mathbb{F}_{q}^\times$ be such that $c^2 \ne 1$. Then $\beta _{x^d, c} \le d^2$.

Proof

We pick arbitrary $a, b \in \mathbb{F}_{q}^\times$, and we consider the difference of the c-boomerang polynomials (Eq. (11))

$$\begin{aligned} f_1 - f_2 = \left( z^d - (z + a)^d \right) - \left( c \cdot x^d - c^{-1} \cdot (x + a)^d \right) , \end{aligned}$$

and by expanding the binomial theorem we see that

$$\begin{aligned}&\deg \left( z^d - (z + a)^d \right) \le d - 1, \nonumber \\&c \cdot x^d - c^{-1} \cdot (x + a)^d = \left( c - c^{-1} \right) \cdot x^d + {\tilde{f}} (x), \end{aligned}$$

(14)

where $\deg \left( {\tilde{f}} \right) \le d - 1$. Moreover, $c - c^{-1} = 0$ if and only if $c^2 = 1$. Now we take the DRL term order with $z >_{DRL} x$, then we have the following leading monomials

$$\begin{aligned} {{\,\textrm{LM}\,}}_{DRL} \left( f_1 \right) = z^d, \qquad {{\,\textrm{LM}\,}}_{DRL} \left( f_1 - c^{-1} \cdot f_2 \right) = x^d. \end{aligned}$$

Then by [12, Chapter 2 §9 Theorem 3, Proposition 4] $\{ f_1, f_1 - f_2 \}$ is a DRL Gröbner basis for the ideal $\left( f_1, f_2 \right) \subset \mathbb{F}_{q}[z, x]$. Applying [12, Chapter 5 §3 Proposition 7] we then conclude that the equations $f_1 = f_2 = 0$ have at most $d^2$ many solutions. $\square$

Remark 4.2

(1)

The proof also applies to $b = 0$, but we fully solved this case in Lemma 3.9.

(2)

The proof generalizes to any permutation polynomial $f \in \mathbb{F}_{q}[x]$.

With Eq. (14) we can also see why we had to resort to Bézout’s theorem for $c^2 = 1$. In that case

$$\begin{aligned} f_1 - f_2 = \left( z^d - (z + a)^d \right) - c \cdot \left( x^d - (x + a)^d \right) , \end{aligned}$$

(15)

and the argument of the proof will fail, because we have the symmetry relation $\big ( f_1 - f_2 \big ) (z, x) = -c \cdot \big ( f_1 - f_2 \big ) (x, z)$. So for the leading monomial of $f_1 - f_2$ DRL will always decide for a power of z. Hence, to replicate the lemma we would have to trace a Gröbner basis algorithm like Buchberger’s algorithm for arbitrary d, a, b as well as $c = \pm 1$ which quickly becomes too difficult to handle by hand.

4.1.2 $c^2 = 1$

For $d \in \{ 3, 5, 7, 11, 129, 257 \}$ we computed the symbolic DRL Gröbner basis using SageMath over $\mathbb{Q} (a, b)$. In Table 1 we report the leading monomials of these Gröbner bases. Additionally, in Appendix B we report the symbolic DRL Gröbner bases for $d = 3, 5$. By visual inspection of these bases we can see that every coefficient is a polynomial in $\mathbb{Q} [a, b]$. The computations have been performed on an Intel Core i7-10700 with 64 GB RAM. The Gröbner bases for $d \le 129$ have been found within less than one minute, and the Gröbner basis for $d = 257$ has been found within 20 minutes.

Table 1

Leading monomials of generic $\pm 1$-boomerang Gröbner bases over $\mathbb{Q} (a, b)$

d	$c = -1$	$c = 1$
3	$x^4,\ z \cdot x^2,\ z^2$	$x^3,\ z$
5	$x^8,\ z \cdot x^4,\ z^4$	$x^7,\ z \cdot x^4,\ z^3$
7	$x^{12},\ z \cdot x^6,\ z^6$	$x^{11},\ z \cdot x^6,\ z^5$
11	$x^{20},\ z \cdot x^{10},\ z^{10}$	$x^{19},\ z \cdot x^{10},\ z^9$
129	$x^{256},\ z \cdot x^{128},\ z^{128}$	$x^{255},\ z \cdot x^{128},\ z^{127}$
257	$x^{512},\ z \cdot x^{256},\ z^{256}$	$x^{511},\ z \cdot x^{256},\ z^{255}$

From these leading monomials we derive the following conjecture.

Conjecture 4.3

Let $q > 2$ be a prime, let $d \in \mathbb{Z}_{> 1}$ be such that $\gcd \left( d, q - 1 \right) = 1$, and let $a, b \in \mathbb{F}_{q}^\times$. Let $c = \pm 1$, and let

$$\begin{aligned} f_1&= z^d - c \cdot x^d - b, \\ f_2&= (z + a)^d - c^{-1} \cdot (x + a)^d - b. \end{aligned}$$

Then the reduced DRL Gröbner basis of $(f_1, f_2) \subset \mathbb{F}_{q}[z, x]$, where $z >_{DRL} x$, has leading monomials

$$\begin{aligned} {\left\{ \begin{array}{ll} x^{2 \cdot (d - 1)},\ z \cdot x^{d - 1},\ z^{d - 1}, & c = -1, \\ x^{2 \cdot (d - 1) - 1},\ z \cdot x^{d - 1},\ z^{d - 2}, & c = 1. \end{array}\right. } \end{aligned}$$

Corollary 4.4

Under Conjecture 4.3,

(1)

$\beta _{x^d, -1} \le d \cdot (d - 1)$.

(2)

$\beta _{x^d, 1} \le d \cdot (d - 2)$.

Proof

Under the conjecture we can compute $\dim _{\mathbb{F}_{q}} \big ( \mathbb{F}_{q}[z, x] / (f_1, f_2) \big )$ by counting the number of monomials not contained in the ideal of leading terms, and then estimate the number of $\mathbb{F}_{q}$-valued solutions via [12, Chapter 5 §3 Proposition 7].

For $c = -1$, the monomials 1, $x^i$, $z^j \cdot x^k$ and $z^l$, where $1 \le i \le 2 \cdot (d - 1) - 1$, $1 \le j \le d - 2$, $1 \le k \le d - 2$ and $1 \le l \le d - 2$ are not contained in the ideal of leading terms. Then $1 + \big ( 2 \cdot (d - 1) - 1 \big ) + (d - 2)^2 + (d - 2) = d \cdot (d - 1)$.

For $c = 1$, the monomials 1, $x^i$, $z^j \cdot x^k$ and $z^l$, where $1 \le i \le 2 \cdot (d - 1) - 2$, $1 \le j \le d - 3$, $1 \le k \le d - 2$ and $1 \le l \le d - 3$ are not contained in the ideal of leading terms. Then $1 + \big ( 2 \cdot (d - 1) - 2 \big ) + (d - 3) \cdot (d - 2) + (d - 3) = d \cdot (d - 2)$. $\square$

So under Conjecture 4.3, without taking any further arithmetic relations of $\mathbb{F}_{q}$ and d into account, our upper bounds from Corollary 3.6 are tight in the sense that polynomial-based estimations cannot obtain a sharper bound.

4.2 Examples over small prime fields

For small primes $q \in \{ 11, 17, 23, 29, 107 \}$ and $d \in \{ 3, 5 \}$ we exhaustively¹ computed the c-boomerang uniformities via SageMath, we display our results in Table 2. In Appendix A.2 we provide a simple SageMath script for this purpose. In all our examples, for $c = 1$ and $d = 3$ our upper bound from Corollary 3.6 is met. Moreover, in most of our examples the ideals for the maximal displayed c-boomerang uniformities are radical. So the inequalities will eventually become tight over a sufficiently large field extension²$\mathbb{F}_{q}\subset \mathbb{F}_{q^n}$ for some $n \in \mathbb{Z}_{\ge 1}$ provided of course that also $\gcd \left( d, q^n - 1 \right) = 1$. Two exceptions for non-radical c-boomerang ideals are $q = 17$, $c = 1$, $a = b = 1$ and $d = 5$ which achieves $\beta _{x^5, 1} = 4$, and $q = 29$, $c = 1$, $a = 1$, $b = 3$ and $d = 5$ which achieves $\beta _{x^5, 1} = 7$.

Table 2

c-Boomerang uniformities of $d \in \{ 3, 5 \}$ over the prime fields $q \in \{ 11, 17, 23, 29, 107 \}$

	$d = 3$			$d = 5$
q	$c^2 \ne 1$	$c = -1$	$c = 1$	$c^2 \ne 1$	$c = -1$	$c = 1$
11	(8, 4)	2	3	n.a	n.a	n.a
17	(10, 4)	4	3	n.a	n.a	4
23	(20, 4)	4	3	(5, 5)	6	5
29	(8, 6)	4	3	(2, 5)	2	7
107	(2, 6)	6	3	(16, 7)	5	4

In the columns for $c^2 \ne 1$ we list tuples $(c, \beta _{x^d, c})$ where c is such that $\beta _{x^d, c}$ is maximal among all $c \in \mathbb{F}_{q}^\times {\setminus } \{ \pm 1 \}$. Uniformities where our upper bounds from Corollary 3.6 are larger than q are not displayed

In Table 3 we report more parameters found via exhaustive search for which Corollary 3.6 is tight.

Table 3

c-Boomerang uniformity parameters for which Corollary 3.6 is tight

q	c	d	b	$_c {\mathcal{B}}_{x^d} \left( 1, b \right)$
11	1	3	2	3
29	1	3	11	3
101	1	3	8	3
101	$-1$	3	44	6
107	1	3	1	3
107	$-1$	3	1	6
1429	1	5	298	15

5 c-uniformities of the generalized triangular dynamical system

The Generalized triangular dynamical system (GTDS) [37] is a polynomial-based approach to describe cryptographic permutations over finite fields. It unifies the dominant block cipher strategies, being the Substitution–Permutation Network (SPN) and the Feistel Network, in a common primitive. As discussed in [37, §4] almost all proposed symmetric key block ciphers can be considered as GTDS-based ciphers.

Definition 5.1

(Generalized triangular dynamical system, [37, Definition 6]) Let $\mathbb{F}_{q}$ be a finite field, and let $n \ge 1$. For $1 \le i \le n$, let $p_i \in \mathbb{F}_{q}[x]$ be permutation polynomials, and for $1 \le i \le n - 1$, let $g_i, h_i \in \mathbb{F}_{q}[x_{i + 1}, \dots , x_n]$ be polynomials such that the polynomials $g_i$ do not have zeros over $\mathbb{F}_{q}$. Then we define a generalized triangular dynamical system ${\mathcal{F}} = \{ f_1, \dots , f_n \}$ as follows

$$\begin{aligned} f_1(x_1,\dots ,x_n)&= p_1(x_1) \cdot g_1(x_2,\dots ,x_n) + h_1(x_2,\dots ,x_n), \\ f_2(x_1,\dots ,x_n)&= p_2(x_2) \cdot g_2(x_3,\dots ,x_n) + h_2(x_3,\dots ,x_n), \\&\dots \\ f_{n-1}(x_1,\dots ,x_n)&= p_{n-1}(x_{n-1}) \cdot g_{n-1}(x_n) + h_{n-1}(x_n), \\ f_n(x_1,\dots ,x_n)&= p_n(x_n). \end{aligned}$$

It is easy to see that if all $p_i$’s are univariate permutations and the $g_i$’s do not have any zeros over $\mathbb{F}_{q}$, then the GTDS is invertible, see [37, Proposition 7].

5.1 c-differential distribution table of the generalized triangular dynamical system

In [37, Theorem 17] the differential uniformity of the GTDS was bounded in terms of the degrees of the univariate permutation polynomials $p_i$ and the Hamming weight of the input difference. To familiarize ourselves with the proving technique we now generalize this result to $c \ne 1$. As preparation, we recall a lemma.

Lemma 5.2

[37, Lemma 16] Let $\mathbb{F}_{q}$ be a finite field, and let $f \in \mathbb{F}_{q}[x] / (x^q - x)$. Then $\delta (f) < q$ if and only if $\deg \big ( f(x + a) - f(x) \big ) > 0$ for all $a \in \mathbb{F}_{q}^\times$. In particular, if $\delta (f) < q$ then $\delta (f) < \deg \left( f \right)$.

Theorem 5.3

Let $\mathbb{F}_{q}$ be a finite field, let $n \ge 1$ be an integer, let $c \in \mathbb{F}_{q}{\setminus } \{ 0, 1 \}$, and let ${\mathcal{F}}: \mathbb{F}_{q}^{n}\rightarrow \mathbb{F}_{q}^{n}$ be a GTDS. Let $p_1, \dots , p_n \in \mathbb{F}_{q}[x] / (x^q - x)$ be the univariate permutation polynomials of the GTDS ${\mathcal{F}}$ such that for every i one has $\delta (p_i) < q$. Let $\varvec{\Delta x}, \varvec{\Delta y} \in \mathbb{F}_{q}^{n}$. Then the c-Differential Distribution Table of ${\mathcal{F}}$ at $\varvec{\Delta x}$ and $\varvec{\Delta y}$ is bounded by

$$\begin{aligned} _{c} \delta _{\mathcal{F}} ( \varvec{\Delta x}, \varvec{\Delta y} ) \le \deg \left( p_n \right) \cdot \prod _{i = 1}^{n - 1} \left\{ \begin{array}{ll} \deg \left( p_i \right) , & \varvec{\Delta x}_i \ne 0, \\ q, & \varvec{\Delta x}_i = 0 \end{array}\right\} . \end{aligned}$$

Proof

Suppose we are given the c-differential equation

$$\begin{aligned} {\mathcal{F}} ({\textbf{x}} + \varvec{\Delta x}) - c \cdot {\mathcal{F}} ({\textbf{x}}) = \varvec{\Delta y}. \end{aligned}$$

(16)

Then, the last component of the differential equation only depends on the variable $x_n$, i.e.,

$$\begin{aligned} p_n (x_n + \varvec{\Delta x}_n) - c \cdot p_n (x_n) = \varvec{\Delta y}_n. \end{aligned}$$

Recall from Lemma 2.2 that this polynomial always has the leading monomial $(1 - c) \cdot x^{\deg \left( p_n \right) }$, therefore we can have at most $\deg \left( p_n \right)$ many solutions for $x_n$ in $\mathbb{F}_{q}$.

Now suppose we have a solution for the last component, say ${\hat{x}}_n \in \mathbb{F}_{q}$. Then, we can substitute it in Eq. (16) into the $(n - 1)$-th component

$$\begin{aligned} f_{n - 1} (x_{n - 1} + \varvec{\Delta x}_{n - 1}, {\hat{x}}_n + \varvec{\Delta x}_n) - c \cdot f_{n - 1} (x_{n - 1}, {\hat{x}}_n) = \varvec{\Delta y}_{n - 1}. \end{aligned}$$

Since ${\hat{x}}_n$ is a field element we can reduce this equation to

$$\begin{aligned} \alpha \cdot p_{n - 1} (x_{n - 1} + \varvec{\Delta x}_{n - 1} ) - c \cdot \beta \cdot p_{n - 1} (x_{n - 1}) + \gamma = \varvec{\Delta y}_{n - 1}, \end{aligned}$$

(17)

where $\alpha , \beta , \gamma \in \mathbb{F}_{q}$ and $\alpha , \beta \ne 0$. Now we have to do a case distinction on the various case for $\alpha$, $\beta$, and $\varvec{\Delta x}_{n - 1}$.

For $\alpha \ne c \cdot \beta$, we obtain a polynomial with leading monomial $(\alpha - c \cdot \beta ) \cdot x^{\deg \left( p_{n - 1} \right) }$, therefore we can have at most $\deg \left( p_{n - 1} \right)$ many solutions for $x_{n - 1}$ in $\mathbb{F}_{q}$.
For $\alpha = c \cdot \beta$, we obtain a rescaled 1-differential equation for $p_{n - 1}$.
- If $\varvec{\Delta x}_{n - 1} = 0$, then the equation becomes constant, so it can have at most q many solutions for $x_{n - 1}$.
- If $\varvec{\Delta x}_{n - 1} \ne 0$, then we obtain a proper 1-differential equation for $p_{n - 1}$, so by Lemma 5.2 we can have at most $\deg \left( p_{n - 1} \right)$ many solutions for $x_{n - 1}$ in $\mathbb{F}_{q}$.

Since in general we do not know which case for $\alpha$ and $\beta$ applies, we have to estimate the number of solutions for $\varvec{\Delta x}_{n - 1} = 0$ by q, since we could end up with a constant equation. On the other, hand if $\varvec{\Delta x}_{n - 1} \ne 0$ all possible cases are non-trivial and can have at most $\deg \left( p_{n - 1} \right)$ many solutions.

Inductively, we now work upwards through the branches to derive the claim. $\square$

Let ${{\,\textrm{wt}\,}}: \mathbb{F}_{q}^{n}\rightarrow \mathbb{Z}$ denote the Hamming weight of a vector, i.e. the number of non-zero entries of a vector. Moreover, let ${\textbf{a}} \in \mathbb{F}_{q}^{n}$, then we denote the restriction of ${\textbf{a}}$ to its first k entries by ${\textbf{a}} \vert ^k$.

Corollary 5.4

Let $\mathbb{F}_{q}$ be a finite field, let $n \ge 1$ be an integer, let $c \in \mathbb{F}_{q}{\setminus } \{ 0, 1 \}$, and let ${\mathcal{F}}: \mathbb{F}_{q}^{n}\rightarrow \mathbb{F}_{q}^{n}$ be a GTDS. Let $p_1, \dots , p_n \in \mathbb{F}_{q}[x] / (x^q - x)$ be the univariate permutation polynomials of the GTDS ${\mathcal{F}}$, and let $\varvec{\Delta x}, \varvec{\Delta y} \in \mathbb{F}_{q}^{n}$. If for all $1 \le i \le n$ one has that $1 < \deg \left( p_i \right) \le d$ and $\delta (p_i) < q$, then

$$\begin{aligned} _{c} \delta _{\mathcal{F}} (\varvec{\Delta x}, \varvec{\Delta y}) \le d \cdot q^{n - 1 - {{\,\textrm{wt}\,}}\big ( \varvec{\Delta x} \vert ^{n - 1} \big )} \cdot d^{{{\,\textrm{wt}\,}}\big ( \varvec{\Delta x} \vert ^{n - 1} \big )}. \end{aligned}$$

In particular,

$$\begin{aligned} {{\,{\mathbb{P}}\,}}\left[ {\mathcal{F}} \!: \varvec{\Delta x} \rightarrow _{ _{c} \delta } \varvec{\Delta y} \right] \le \frac{d}{q} \cdot \left( \frac{d}{q} \right) ^{{{\,\textrm{wt}\,}}\big ( \varvec{\Delta x} \vert ^{n - 1} \big )}. \end{aligned}$$

Proof

The first claim follows from Lemma 5.2 and Theorem 5.3, the bound for the probability follows from the first and division by $q^n$. $\square$

5.2 c-boomerang connectivity table of a class of generalized triangular dynamical systems

Utilizing the generalized boomerang equations, we can also estimate the c-boomerang uniformity of a GTDS provided that $h_i = 0$ for all i.

Theorem 5.5

Let $\mathbb{F}_{q}$ be a finite field of characteristic p, let $n \ge 1$ be an integer, and let ${\mathcal{F}}: \mathbb{F}_{q}^{n}\rightarrow \mathbb{F}_{q}^{n}$ be a GTDS such that for all $1 \le i \le n$

(i)

$p_i (x) = x^{d_i}$ with $\gcd \left( d_i, q - 1\right) = 1$ and $p \not \mid d_i$, and

(ii)

$h_i = 0$.

Let ${\textbf{a}}, {\textbf{b}} \in \mathbb{F}_{q}^{n}\setminus \{ {\textbf{0}} \}$, and let $c \in \mathbb{F}_{q}^\times$. Then the c-Boomerang Connectivity Table of ${\mathcal{F}}$ at ${\textbf{a}}$ and ${\textbf{b}}$ is bounded by

$$\begin{aligned} _{c} {\mathcal{B}}_{\mathcal{F}} ({\textbf{a}}, {\textbf{b}}) \le \left\{ \begin{array}{ll} 1, & d_n = 1,\ c^2 \ne 1, \\ 0, & d_n = 1,\ c = -1,\ a_n \ne 0, \\ q, & d_n = 1,\ c = -1,\ a_n = 0, \\ q, & d_n = 1,\ c = 1, \\ q, & d_n> 1,\ a_n \cdot b_n = 0, \\ d_n^2, & d_n> 1,\ a_n \cdot b_n \ne 0 \end{array} \right\} \cdot \prod _{i = 1}^{n - 1} \left\{ \begin{array}{ll} q, & d_i = 1, \\ q, & a_i \cdot b_i = 0, \\ d_i^2, & d_i > 1,\ a_n \cdot b_n \ne 0 \end{array} \right\} . \end{aligned}$$

Proof

Suppose we are given the boomerang equation system

$$\begin{aligned}{\mathcal{F}} ({\textbf{z}}) &- c \cdot {\mathcal{F}} ({\textbf{x}}) = {\textbf{b}}, \\ c \cdot {\mathcal{F}} ({\textbf{z}} + {\textbf{a}}) &- {\mathcal{F}} ({\textbf{x}} + {\textbf{a}}) = c \cdot {\textbf{b}}. \end{aligned}$$

(18)

Then, the last components of the boomerang equations only depend on the variable $x_n$, i.e.,

$$\begin{aligned} p_n (z_n) &- c \cdot p_n (x_n) = b_n, \\ c \cdot p_n (z_n + a_n) &- p_n (x_n + a_n) = c \cdot b_n. \end{aligned}$$

Now we do a case distinction.

If $\deg \left( p_n \right) = 1$, then we can apply Lemma 2.7, so depending on $a_n$ and c we can either have 0, 1 or q solutions for $(z_n, x_n)$.
If $\deg \left( p_n \right) > 1$ and $a_n \cdot b_n = 0$, the boomerang equations for $p_n$ might not be fully determined, so in this case we can have at most q many solutions for $(z_n, x_n)$, see Lemma 3.9.
If $\deg \left( p_n \right) > 1$ and $a_n \cdot b_n \ne 0$, then by Corollary 3.6 we have at most $d_n^2$ solutions for $(z_n, x_n)$.

Now suppose we have a solution for the last component, say $({\hat{z}}_n, {\hat{x}}_n) \in \mathbb{F}_{q}^2$. Then, we can substitute it in Eq. (18) into the $(n - 1)$-th component

$$\begin{aligned} f_{n - 1} (z_{n - 1}, {\hat{z}}_n) &- c \cdot f_{n - 1} (x_{n - 1}, {\hat{x}}_n) = b_{n - 1}, \\ c \cdot f_{n - 1} (z_{n - 1} + a_{n - 1}, {\hat{z}}_n + a_n) &- f_{n - 1} (x_{n - 1}, {\hat{x}}_n) = c \cdot b_{n - 1}. \end{aligned}$$

Since ${\hat{z}}_n$, ${\hat{x}}_n$ are field elements we can reduce these equations to

$$\begin{aligned} \alpha \cdot p_{n - 1} (z_{n - 1}) &- c \cdot \beta \cdot p_{n - 1} (x_{n - 1}) = b_{n - 1}, \\ c \cdot \gamma \cdot p_{n - 1} (z_{n - 1} + a_{n - 1}) &- \delta \cdot p_{n - 1} (x_{n - 1} + a_{n - 1}) = c \cdot b_{n - 1}, \end{aligned}$$

where $\alpha , \beta , \gamma , \delta \in \mathbb{F}_{q}^\times$. Now we have to do a case distinction on the possible cases for $a_{n - 1}, b_{n - 1}$ and $\deg \left( p_{n - 1} \right)$.

If $\deg \left( p_{n - 1} \right) = 1$, then in principle it might happen that both equations become constant and that the left-hand sides coincide with the right-hand sides. Then the c-boomerang uniformity is maximal, i.e. we have to bound it by q.
If $a_{n - 1} \cdot b_{n - 1} = 0$, then the equation system might not be fully determined. In that case we have to use the trivial upper bound q.
If $a_{n - 1} \cdot b_{n - 1} \ne 0$, then we divide both equations by $a_{n - 1}^d$, the first equation by $\alpha$ and the second one by $c \cdot \gamma$. After a substitution analog to Eq. (8), we obtain a generalized boomerang equation system with the coefficients
$$\begin{aligned} c_1 = \frac{c \cdot \beta }{\alpha }, \quad c_2 = \frac{b_{n - 1}}{\alpha \cdot a_{n - 1}^{d_{n - 1}}}, \quad c_3 = \frac{\delta }{c \cdot \gamma }, \quad c_4 = 1, \quad c_5 = \frac{b_{n - 1}}{\gamma \cdot a_{n - 1}^{d_{n - 1}}}. \end{aligned}$$
So by Theorem 3.4 the generalized boomerang equation system ${\mathcal{F}} (d_{n - 1}, c_1, \dots , c_5)$ has at most $d_{n - 1}^2$ many solutions in $\mathbb{F}_{q}^2$.

Inductively, we now work upwards through the branches to derive the claim. $\square$

Let ${\textbf{a}}, {\textbf{b}} \in \mathbb{F}_{q}^{n}$, then we denote their Hadamard product with

$$\begin{aligned} {\textbf{a}} \odot {\textbf{b}} = (a_i)_{1 \le i \le n} \odot (b_i)_{1 \le i \le n} = (a_i \cdot b_i)_{1 \le i \le n}, \end{aligned}$$

(19)

i.e. their pointwise product. Utilizing this notation we have a convenient representation of the theorem.

Corollary 5.6

(i)

$p_i (x) = x^{d_i}$ with $\gcd \left( d_i, q - 1\right) = 1$ and $p \not \mid d_i$, and

(ii)

$h_i = 0$.

Let ${\textbf{a}}, {\textbf{b}} \in \mathbb{F}_{q}^{n}\setminus \{ {\textbf{0}} \}$, and let $c \in \mathbb{F}_{q}^\times$. If for all $1 \le i \le n$ one has that $1 < d_i \le d$, then

$$\begin{aligned} _{c} {\mathcal{B}}_{\mathcal{F}} ({\textbf{a}}, {\textbf{b}}) \le q^{n - {{\,\textrm{wt}\,}}({\textbf{a}} \odot {\textbf{b}})} \cdot d^{2 \cdot {{\,\textrm{wt}\,}}({\textbf{a}} \odot {\textbf{b}})}. \end{aligned}$$

In particular,

$$\begin{aligned} {{\,{\mathbb{P}}\,}}\left[ {\mathcal{F}} \!: {\textbf{a}} \rightarrow _{ _{c} {\mathcal{B}}} {\textbf{b}} \right] \le \left( \frac{d^2}{q} \right) ^{{{\,\textrm{wt}\,}}({\textbf{a}} \odot {\textbf{b}})}. \end{aligned}$$

Proof

The first claim follows from Theorem 5.5, the bound for the probability follows from the first and division by $q^n$. $\square$

For the Boomerang Connectivity Table of substitution layer of the classical SPN we can improve Theorem 5.5 even further.

Corollary 5.7

Let $\mathbb{F}_{q}$ be a finite field of characteristic p, let $n \ge 1$ be an integer, let $d_1, \dots , d_n \in \mathbb{Z}_{> 1}$ be such that $\gcd \left( d_i, q - 1 \right) = 1$ and $p \not \mid d_i$ for all $1 \le i \le n$, and let ${\mathcal{S}}: \left( x_1, \dots , x_n \right) ^\intercal \mapsto \left( x_1^{d_1}, \dots , x_n^{d_n} \right) ^\intercal$. Let ${\textbf{a}}, {\textbf{b}} \in \mathbb{F}_{q}^{n}{\setminus } \left\{ {\textbf{0}} \right\}$, and let $c \in \mathbb{F}_{q}^\times$. The c-Boomerang Connectivity Table of ${\mathcal{S}}$ at ${\textbf{a}}$ and ${\textbf{b}}$ is bounded by

$$\begin{aligned} _c {\mathcal{B}}_{\mathcal{S}} \left( {\textbf{a}}, {\textbf{b}} \right) \le \prod _{i = 1}^{n} \left\{ \begin{array}{ll} \left\{ \begin{array}{ll} 1, & c^2 \ne 1, \\ q, & c^2 = 1 \end{array} \right\} , & a_i \cdot b_i = 0, \\ \left\{ \begin{array}{ll} d_i^2, & c^2 \ne 1, \\ d_i \cdot (d_i - 1), & c = -1, \\ d_i \cdot (d_i - 2), & c = 1 \end{array} \right\} ,&a_i \cdot b_i \ne 0 \end{array}\right\} . \end{aligned}$$

In particular, for $c = 1$ and $d_i \le d$ for all $1 \le i \le n$

$$\begin{aligned} {{\,{\mathbb{P}}\,}}\left[ {\mathcal{S}} \!: {\textbf{a}} \rightarrow _{\mathcal{B}} {\textbf{b}} \right] \le \left( \frac{d \cdot (d - 2)}{q} \right) ^{{{\,\textrm{wt}\,}}\left( {\textbf{a}} \odot {\textbf{b}} \right) }. \end{aligned}$$

Proof

For ${\mathcal{S}}$ we have n parallel c-boomerang equation systems. Then the first claim follows from application of Corollary 3.6 and Lemma 3.9. The second claim then follows from the first and division by $q^n$. $\square$

Of course, we would also like to estimate the c-boomerang uniformity for non-zero $h_i$’s. Though, this significantly complicates our estimation approach. For illustration, let us consider

$$\begin{aligned} f_1 (x_1, x_2)&= x_1^{d_1} \cdot g_1 (x_2) + h_1 (x_2), \\ f_2 (x_2)&= x_2^{d_2}, \end{aligned}$$

(20)

where $d_1, d_2 \in \mathbb{Z}_{> 1}$ induce permutations over $\mathbb{F}_{q}$ and $h_1 \in \mathbb{F}_{q}[x]$ is non-constant. Let ${\textbf{a}}, {\textbf{b}} \in \mathbb{F}_{q}^2$, for $a_2 \ne 0$ the c-boomerang equations for $f_2$ have at most $d_2^2$ many solutions for $x_2$. Further, the c-boomerang equations for $f_1$ become

$$\begin{aligned} z_1^{d_1} \cdot g_1 (z_2) - c \cdot x_1^{d_1} \cdot g_1 (x_2)&= b_1 + c \cdot h_1 (x_2) - h_1 (z_2), \\ c \cdot (z_1 + a_1)^{d_1} \cdot g_1 (z_2 + a_2)&- (x_1 + a_1)^{d_1} \cdot g_1 (x_2 + a_2) \\ &= c \cdot b_1 + h_1 (x_2 + a_2) - c \cdot h_1 (z_2 + a_2). \end{aligned}$$

(21)

Therefore, to estimate the number of solutions of this equation via Theorem 3.4, we in addition have to show that the polynomial systems

$$\begin{aligned} z_2^{d_2} - c \cdot x_2^{d_2} &= b_2, \\ c \cdot (z_2 + a_2)^{d_2} - (x_2 + a_2)^{d_2} &= c \cdot b_2, \\ h_1 (z_2) - c \cdot h_1 (x_2) &= b_1, \end{aligned}$$

(22)

and

$$\begin{aligned} z_2^{d_2} - c \cdot x_2^{d_2} &= b_2, \\ c \cdot (z_2 + a_2)^{d_2} - (x_2 + a_2)^{d_2} &= c \cdot b_2, \\ c \cdot h_1 (z_2 + a_2) - h_1 (x_2 + a_2) &= c \cdot b_1, \end{aligned}$$

(23)

do not admit any solutions in $\mathbb{F}_{q}$. We can view these polynomial systems as intersection of three plane curves, though a priori there is no reason why the curves coming from $h_1$ are not generated by the two other ones. For example for $h_1 (x) = x^{d_2}$ and $b_1 = b_2$, the $h_1$ polynomials in Eqs. (22) and (23) do not add any new information at all, moreover for that parameter choice the right-hand sides of Eq. (21) both become zero, so we cannot use Theorem 3.4 to estimate the number of solutions.

5.2.1 The propagation probability of a block cipher round

Recall from the introduction that in a boomerang attack we split a cipher into ${\mathcal{C}} = {\mathcal{C}}_1 \circ {\mathcal{C}}_m \circ {\mathcal{C}}_2$, set up differentials for ${\mathcal{C}}_1$ and ${\mathcal{C}}_2$, and try to connect them via ${\mathcal{C}}_m$. We finish this paper with a short discussion how to apply Corollary 5.6 to a GTDS-based block cipher for the estimation of the propagation probability in case ${\mathcal{C}}_m$ is given by a single round function of ${\mathcal{C}}$. Let $\mathbb{F}_{q}$ be a finite field, let $n \ge 1$ be an integer, let ${\mathcal{F}}: \mathbb{F}_{q}^{n}\rightarrow \mathbb{F}_{q}^{n}$ be a GTDS, let ${\textbf{A}} \in \mathbb{F}_{q}^{n \times n}$ be an invertible matrix, and let ${\textbf{c}}_i \in \mathbb{F}_{q}^{n}$ be a constant. Then we define the i-th round function as

$$\begin{aligned} {\mathcal{R}}^{(i)}: \mathbb{F}_{q}^{n}\times \mathbb{F}_{q}^{n}&\rightarrow \mathbb{F}_{q}^{n}, \\ ({\textbf{x}}, {\textbf{k}}_i)&\mapsto {\textbf{A}} {\mathcal{F}} ({\textbf{x}}) + {\textbf{c}}_i + {\textbf{k}}_i, \end{aligned}$$

(24)

where ${\textbf{k}}_i$ denotes the i-th round key. For an integer $r \ge 1$ a block cipher ${\mathcal{C}}$ is then simply the r-fold composition of round functions

$$\begin{aligned} {\mathcal{C}}: \mathbb{F}_{q}^{n}\times \left( \mathbb{F}_{q}^{n}\right) ^{r + 1}&\rightarrow \mathbb{F}_{q}^{n}, \\ ({\textbf{x}}, {\textbf{k}}_0, \dots , {\textbf{k}}_r)&\mapsto {\mathcal{R}}^{(r)} \circ \cdots \circ {\mathcal{R}}^{(1)} ({\textbf{x}} + {\textbf{k}}_0), \end{aligned}$$

(25)

where composition is taken with respect to the plaintext variable ${\textbf{x}}$.

By Definition 2.3 the c-BCT entry at ${\textbf{a}}, {\textbf{b}} \in \mathbb{F}_{q}^{n}$ for ${\mathcal{R}}^{(i)}$ is then given by the number of solutions of

$$\begin{aligned}&{\mathcal{R}}^{(i)} ({\textbf{z}}) - c \cdot {\mathcal{R}}^{(i)} ({\textbf{x}}) = {\textbf{b}}, \\&c \cdot {\mathcal{R}}^{(i)} ({\textbf{z}} + {\textbf{a}}) - {\mathcal{R}}^{(i)} ({\textbf{x}} + {\textbf{a}}) = c \cdot {\textbf{b}}. \end{aligned}$$

(26)

Substituting our definition of round functions, see Eq. (24), into these equations we obtain after rearranging

$$\begin{aligned}&{\mathcal{F}} ({\textbf{z}}) - {\mathcal{F}} ({\textbf{x}}) = {\textbf{A}}^{-1} \big ( {\textbf{b}} + (c - 1) \cdot ({\textbf{c}}_i + {\textbf{k}}_i) \big ), \\&c \cdot {\mathcal{F}} ({\textbf{z}} + {\textbf{a}}) - {\mathcal{F}} ({\textbf{x}} + {\textbf{a}}) = {\textbf{A}}^{-1} \big ( c \cdot {\textbf{b}} + (1 - c) \cdot ({\textbf{c}}_i + {\textbf{k}}_i) \big ). \end{aligned}$$

(27)

In particular, if $c = 1$ and ${\mathcal{F}}$ satisfies the assumptions of Corollary 5.6, then the corollary provides a convenient tool to estimate the propagation probability in a boomerang attack on a block cipher.

E.g., let us consider Hades [22], a family of AO SPN ciphers for MPC, or its derived hash functions Poseidon [20] and Poseidon2 [21] for ZK. Let $d, p \in \mathbb{Z}_{> 1}$ be such that p is a prime and $d > 1$ is the smallest integer such that $\gcd \left( d, p - 1 \right) = 1$. The Hades permutation over $\mathbb{F}_{p}^{n}$ is divided into $2 \cdot r_f$ outer “full” SPN rounds and $r_p$ inner “partial” SPN rounds

$$\begin{aligned} \textsc {Hades} _{\pi } ({\textbf{x}}) = {\mathcal{R}}_f \circ {\mathcal{R}}_p \circ {\mathcal{R}}_f ({\textbf{x}}). \end{aligned}$$

(28)

As the name suggests, full rounds ${\mathcal{R}}_f$ apply a SPN with full Substitution Layer

$$\begin{aligned} {\mathcal{S}}: \begin{pmatrix} x_1 \\ \vdots \\ x_n \end{pmatrix} \mapsto \begin{pmatrix} x_1^d \\ \vdots \\ x_n^d \end{pmatrix}, \end{aligned}$$

(29)

but partial rounds ${\mathcal{R}}_p$ apply the power permutation only to the first component

$$\begin{aligned} {\mathcal{P}}: \begin{pmatrix} x_1 \\ \vdots \\ x_n \end{pmatrix} \mapsto \begin{pmatrix} x_1^d \\ x_2 \\ \vdots \\ x_n \end{pmatrix}. \end{aligned}$$

(30)

Trivially, the full and the partial SPNs are GTDS instances. As we saw in Corollary 5.7, the probability for a full Substitution layer is given by

$$\begin{aligned} {{\,{\mathbb{P}}\,}}\left[ {\mathcal{S}}: {\textbf{a}} \rightarrow _{{\mathcal{B}}} {\textbf{b}} \right] \le \left( \frac{d \cdot (d - 2)}{q} \right) ^{{{\,\textrm{wt}\,}}\left( {\textbf{a}} \odot {\textbf{b}} \right) }. \end{aligned}$$

(31)

Moreover, the probability for the partial substitution layer follows straight-forward with Lemma 2.7 and Corollary 3.6

$$\begin{aligned} {{\,{\mathbb{P}}\,}}\left[ {\mathcal{P}}: {\textbf{a}} \rightarrow _{{\mathcal{B}}} {\textbf{b}} \right] \le {\left\{ \begin{array}{ll} 1, & a_1 \cdot b_1 = 0, \\ \frac{d \cdot (d - 2)}{q}, & a_1 \cdot b_1 \ne 0. \end{array}\right. } \end{aligned}$$

(32)

Therefore, with our results one can estimate the resistance of the full as well as the partial SPN layer of Hades, Poseidon and Poseidon2 against boomerang cryptanalysis.

6 Conclusion

In this paper we proved that the c-boomerang uniformity of permutation monomials $x^d$ and $x^\frac{1}{d}$, where d is not divisible by the characteristic p, is bounded by $d^2$. We also applied this bound to estimate the c-BCT table entries for a class of vector-valued cryptographic permutations, among them the well-known Substitution–Permutation Network. In the future, we hope to see refinements of our methods that allow to estimate the c-BCT entries of a full GTDS.

Acknowledgements

The author thanks the anonymous reviewers for their valuable suggestions and comments which improved both the quality and the presentation of this paper.

Conflict of interest

The author declares no Conflict of interest.

Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

`A SageMath` scripts

A.1 Generic Gröbner basis computations

A.2 Exhaustive c-boomerang uniformities computation

B Symbolic $\pm 1$-Boomerang Gröbner bases for small exponents

B.1 $d = 3$

B.1.1 $c = -1$

$$\begin{aligned} g_1&= x^{4} + 2 a x^{3} + \frac{2}{3} a^{2} z x + \frac{5}{3} a^{2} x^{2} \nonumber \\&\quad + \left( \frac{1}{3} a^{3} - \frac{1}{2} b\right) z + \left( a^{3} - \frac{1}{2} b\right) x + \frac{2}{9} a^{4} - \frac{1}{2} a b, \end{aligned}$$

(33)

$$\begin{aligned} g_2&= z x^{2} - x^{3} + a z x - a x^{2} - \frac{1}{3} a^{2} z - a^{2} x - \frac{2}{3} a^{3} + b, \end{aligned}$$

(34)

$$\begin{aligned} g_3&= z^{2} + x^{2} + a z + a x + \frac{2}{3} a^{2}. \end{aligned}$$

(35)

B.1.2 $c = 1$

$$\begin{aligned} g_1&= x^{3} + \frac{3}{2} a x^{2} + \frac{3}{2} a^{2} x + \frac{1}{2} a^{3} + \frac{1}{2} b, \end{aligned}$$

(36)

$$\begin{aligned} g_2&= z + x + a. \end{aligned}$$

(37)

B.2 $d = 5$

B.2.1 $c = -1$

$$\begin{aligned} g_1&= x^{8} + 4 a x^{7} + 2 a^{2} z^{3} x^{3} + 8 a^{2} x^{6} + 3 a^{3} z^{3} x^{2} + 3 a^{3} z^{2} x^{3} \nonumber \\&\quad + 10 a^{3} x^{5} + \frac{9}{5} a^{4} z^{3} x + \frac{19}{5} a^{4} z^{2} x^{2} \end{aligned}$$

(38)

$$\begin{aligned} \phantom {g_1}&\phantom {=}+ \frac{9}{5} a^{4} z x^{3} + \frac{42}{5} a^{4} x^{4} + \left( \frac{2}{5} a^{5} - \frac{1}{2} b\right) z^{3} \nonumber \\&\quad + \left( 2 a^{5} - \frac{1}{2} b\right) z^{2} x + \left( 2 a^{5} - \frac{1}{2} b\right) z x^{2} \nonumber \\ \phantom {g_1}&\phantom {=}+ \left( \frac{26}{5} a^{5} - \frac{1}{2} b\right) x^{3} + \left( \frac{2}{5} a^{6} - a b\right) z^{2} + \left( a^{6} - a b\right) z x \nonumber \\&\quad + \left( \frac{11}{5} a^{6} - a b\right) x^{2} + \left( \frac{1}{5} a^{7} - a^{2} b\right) z \nonumber \\ \phantom {g_1}&\phantom {=}+ \left( \frac{3}{5} a^{7} - a^{2} b\right) x + \frac{2}{25} a^{8} - \frac{1}{2} a^{3} b, \nonumber \\ g_2&= z x^{4} - x^{5} + 2 a z x^{3} - 2 a x^{4} - 2 a^{2} z^{3} + 2 a^{2} z x^{2} \nonumber \\&\quad - 4 a^{2} x^{3} - 3 a^{3} z^{2} + a^{3} z x - 4 a^{3} x^{2} \end{aligned}$$

(39)

$$\begin{aligned} \phantom {g_1}&\phantom {=}- \frac{8}{5} a^{4} z - 2 a^{4} x - \frac{4}{5} a^{5} + b, \nonumber \\ g_3&= z^{4} + x^{4} + 2 a z^{3} + 2 a x^{3} + 2 a^{2} z^{2} + 2 a^{2} x^{2} + a^{3} z + a^{3} x + \frac{2}{5} a^{4}. \end{aligned}$$

(40)

B.2.2 $c = 1$

$$\begin{aligned} g_1&= x^{7} + \frac{7}{2} a x^{6} + 2 a^{2} z^{2} x^{3} + 10 a^{2} x^{5} + 3 a^{3} z^{2} x^{2} + 2 a^{3} z x^{3} \nonumber \\&\quad + \frac{65}{4} a^{3} x^{4} + 6 a^{4} z^{2} x + \frac{13}{2} a^{4} z x^{2} \end{aligned}$$

(41)

$$\begin{aligned} \phantom {g_1}&\phantom {=}+ \frac{49}{2} a^{4} x^{3} + \left( \frac{5}{2} a^{5} + \frac{1}{4} b\right) z^{2} + \left( \frac{19}{2} a^{5} + \frac{1}{2} b\right) z x \nonumber \\&\quad + \left( 24 a^{5} + \frac{3}{4} b\right) x^{2} + \left( \frac{19}{4} a^{6} + \frac{1}{2} a b\right) z \nonumber \\ \phantom {g_1}&\phantom {=}+ \left( 15 a^{6} + a b\right) x + \frac{9}{2} a^{7} + \frac{5}{2} a^{2} b, \nonumber \\ g_2&= z x^{4} - x^{5} + 2 a z x^{3} - 2 a x^{4} - 2 a^{2} z^{2} x - 6 a^{2} x^{3} \nonumber \\&\quad - a^{3} z^{2} - 3 a^{3} z x - 8 a^{3} x^{2} - 2 a^{4} z - 6 a^{4} x - 2 a^{5} - b, \end{aligned}$$

(42)

$$\begin{aligned} g_3&= z^{3} + z^{2} x + z x^{2} + x^{3} + 2 a z^{2} + 2 a z x + 2 a x^{2} + 2 a^{2} z + 2 a^{2} x + a^{3}. \end{aligned}$$

(43)

For an exhaustive c-BCT enumeration of $x^d$, it is sufficient to set $a = 1$ and enumerating only over $(c, b) \in \mathbb{F}_{q}^\times \times \mathbb{F}_{q}^\times$.

Let k be a perfect field, and let A and B be reduced k-algebras. By [8, Chapter V §15.5 Theorem 3] the tensor product $A \otimes _k B$ is reduced. Moreover, finite fields are perfect [8, Chapter V §1.5 Proposition 5]. Thus, if $I \subset \mathbb{F}_{q}[x_1, \dots , x_n]$ is radical, then the extension $I \otimes _{\mathbb{F}_{q}} \mathbb{F}_{q^n} \subset \mathbb{F}_{q^n} [x_1, \dots , x_n]$ is also radical.

Albrecht, M.R., Grassi, L., Perrin, L., Ramacher, S., Rechberger, C., Rotaru, D., Roy, A., Schofnegger, M.: Feistel structures for MPC, and more. In: Sako, K., Schneider, S., Ryan, P.Y.A. (eds.) ESORICS 2019: 24th European Symposium on Research in Computer Security, Part II. Lecture Notes in Computer Science, vol. 11736, pp. 151–171. Springer, Heidelberg (2019). https://doi.org/10.1007/978-3-030-29962-0_8CrossRef

Albrecht, M.R., Grassi, L., Rechberger, C., Roy, A., Tiessen, T.: MiMC: Efficient encryption and cryptographic hashing with minimal multiplicative complexity. In: Cheon, J.H., Takagi, T. (eds.) Advances in Cryptology—ASIACRYPT 2016, Part I. Lecture Notes in Computer Science, vol. 10031, pp. 191–219. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53887-6_7CrossRef

Albrecht, M.R., Rechberger, C., Schneider, T., Tiessen, T., Zohner, M.: Ciphers for MPC and FHE. In: E. Oswald, M. Fischlin (eds.) Advances in Cryptology—EUROCRYPT 2015, Part I. Lecture Notes in Computer Science, vol. 9056, pp. 430–454. Springer, Heidelberg (2015).https://doi.org/10.1007/978-3-662-46800-5_17

Aly, A., Ashur, T., Ben-Sasson, E., Dhooghe, S., Szepieniec, A.: Design of symmetric-key primitives for advanced cryptographic protocols. IACR Trans. Symmetr. Cryptol. 2020(3), 1–45 (2020). https://doi.org/10.13154/tosc.v2020.i3.1-45CrossRef

Biham, E., Shamir, A.: Differential cryptanalysis of DES-like cryptosystems. In: A.J. Menezes, S.A. Vanstone (eds.) Advances in Cryptology—CRYPTO’90. Lecture Notes in Computer Science, vol. 537, pp. 2–21. Springer, Heidelberg (1991). https://doi.org/10.1007/3-540-38424-3_1

Biryukov, A., Khovratovich, D.: Related-key cryptanalysis of the full AES-192 and AES-256. In: M. Matsui (ed.) Advances in Cryptology—ASIACRYPT 2009. Lecture Notes in Computer Science, vol. 5912, pp. 1–18. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-10366-7_1

Boura, C., Canteaut, A.: On the boomerang uniformity of cryptographic sboxes. IACR Trans. Symmetr. Cryptol. 2018(3), 290–310 (2018). https://doi.org/10.13154/tosc.v2018.i3.290-310CrossRef

Bourbaki, N.: Algebra II: Chapters 4–7, 1 edn. Elements of Mathematics. Springer Berlin (2003). https://doi.org/10.1007/978-3-642-61698-3

Bouvier, C., Briaud, P., Chaidos, P., Perrin, L., Salen, R., Velichkov, V., Willems, D.: New design techniques for efficient arithmetization-oriented hash functions: Anemoi permutations and Jive compression mode. In: H. Handschuh, A. Lysyanskaya (eds.) Advances in Cryptology—CRYPTO 2023, Part III. Lecture Notes in Computer Science, vol. 14083, pp. 507–539. Springer, Heidelberg (2023). https://doi.org/10.1007/978-3-031-38548-3_17

10.

Cassiers, G., Masure, L., Momin, C., Moos, T., Standaert, F.X.: Prime-field masking in hardware and its soundness against low-noise SCA attacks. IACR Trans. Cryptogr. Hardw. Embedd. Syst. 2023(2), 482–518 (2023). https://doi.org/10.46586/tches.v2023.i2.482-518CrossRef

11.

Cid, C., Huang, T., Peyrin, T., Sasaki, Y., Song, L.: Boomerang connectivity table: A new cryptanalysis tool. In: J.B. Nielsen, V. Rijmen (eds.) Advances in Cryptology—EUROCRYPT 2018, Part II. Lecture Notes in Computer Science, vol. 10821, pp. 683–714. Springer, Heidelberg (2018). https://doi.org/10.1007/978-3-319-78375-8_22

12.

Cox, D.A., Little, J., O’Shea, D.: Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra, 4th edn. Undergraduate Texts in Mathematics. Springer International Publishing (2015). https://doi.org/10.1007/978-3-319-16721-3

13.

Dobraunig, C., Grassi, L., Guinet, A., Kuijsters, D.: Ciminion: Symmetric encryption based on Toffoli-gates over large finite fields. In: A. Canteaut, F.X. Standaert (eds.) Advances in Cryptology—EUROCRYPT 2021, Part II. Lecture Notes in Computer Science, vol. 12697, pp. 3–34. Springer, Heidelberg (2021). https://doi.org/10.1007/978-3-030-77886-6_1

14.

Dunkelman, O., Keller, N., Shamir, A.: A practical-time related-key attack on the KASUMI cryptosystem used in GSM and 3G telephony. In: T. Rabin (ed.) Advances in Cryptology—CRYPTO 2010. Lecture Notes in Computer Science, vol. 6223, pp. 393–410. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-14623-7_21

15.

Dunkelman, O., Keller, N., Shamir, A.: A practical-time related-key attack on the KASUMI cryptosystem used in GSM and 3G telephony. J. Cryptol. 27(4), 824–849 (2014). https://doi.org/10.1007/s00145-013-9154-9MathSciNetCrossRef

16.

Ellingsen, P., Felke, P., Riera, C., Stănică, P., Tkachenko, A.: C-differentials, multiplicative uniformity, and (almost) perfect c-nonlinearity. IEEE Trans. Inf. Theory 66(9), 5781–5789 (2020). https://doi.org/10.1109/TIT.2020.2971988MathSciNetCrossRef

17.

Görtz, U., Wedhorn, T.: Algebraic Geometry I: Schemes, 2nd edn. Springer Studium Mathematik - Master. Springer Fachmedien Wiesbaden (2020). https://doi.org/10.1007/978-3-658-30733-2

18.

Grassi, L., Hao, Y., Rechberger, C., Schofnegger, M., Walch, R., Wang, Q.: Horst meets fluid-SPN: Griffin for zero-knowledge applications. In: H. Handschuh, A. Lysyanskaya (eds.) Advances in Cryptology—CRYPTO 2023, Part III. Lecture Notes in Computer Science, vol. 14083, pp. 573–606. Springer, Heidelberg (2023). https://doi.org/10.1007/978-3-031-38548-3_19

19.

Grassi, L., Khovratovich, D., Lüftenegger, R., Rechberger, C., Schofnegger, M., Walch, R.: Reinforced Concrete: A fast hash function for verifiable computation. In: H. Yin, A. Stavrou, C. Cremers, E. Shi (eds.) ACM CCS 2022: 29th Conference on Computer and Communications Security, pp. 1323–1335. ACM Press, Los Angeles (2022). https://doi.org/10.1145/3548606.3560686

20.

Grassi, L., Khovratovich, D., Rechberger, C., Roy, A., Schofnegger, M.: Poseidon: A new hash function for zero-knowledge proof systems. In: M. Bailey, R. Greenstadt (eds.) USENIX Security 2021: 30th USENIX Security Symposium, pp. 519–535. USENIX Association (2021)

21.

Grassi, L., Khovratovich, D., Schofnegger, M.: Poseidon2: A faster version of the Poseidon hash function. In: N. El Mrabet, L. De Feo, S. Duquesne (eds.) AFRICACRYPT 23: 14th International Conference on Cryptology in Africa. Lecture Notes in Computer Science, vol. 14064, pp. 177–203. Springer, Sousse (2023). https://doi.org/10.1007/978-3-031-37679-5_8

22.

Grassi, L., Lüftenegger, R., Rechberger, C., Rotaru, D., Schofnegger, M.: On a generalization of substitution-permutation networks: the HADES design strategy. In: A. Canteaut, Y. Ishai (eds.) Advances in Cryptology – EUROCRYPT 2020, Part II. Lecture Notes in Computer Science, vol. 12106, pp. 674–704. Springer, Heidelberg (2020).https://doi.org/10.1007/978-3-030-45724-2_23

23.

Grassi, L., Masure, L., Méaux, P., Moos, T., Standaert, F.X.: Generalized Feistel ciphers for efficient prime field masking. In: M. Joye, G. Leander (eds.) Advances in Cryptology—EUROCRYPT 2024, Part III. Lecture Notes in Computer Science, vol. 14653, pp. 188–220. Springer, Heidelberg (2024).https://doi.org/10.1007/978-3-031-58734-4_7

24.

Grassi, L., Øygarden, M., Schofnegger, M., Walch, R.: From Farfalle to Megafono via Ciminion: The PRF Hydra for MPC applications. In: C. Hazay, M. Stam (eds.) Advances in Cryptology—EUROCRYPT 2023, Part IV. Lecture Notes in Computer Science, vol. 14007, pp. 255–286. Springer, Heidelberg (2023). https://doi.org/10.1007/978-3-031-30634-1_9

25.

Hasan, S.U., Pal, M., Stănică, P.: Boomerang uniformity of a class of power maps. Des. Codes Crypt. 89(11), 2627–2636 (2021). https://doi.org/10.1007/s10623-021-00944-xMathSciNetCrossRef

26.

Hasan, S.U., Pal, M., Stănică, P.: The binary Gold function and its c-boomerang connectivity table. Cryptogr. Commun. 14(6), 1257–1280 (2022). https://doi.org/10.1007/s12095-022-00573-8MathSciNetCrossRef

27.

Joux, A., Peyrin, T.: Hash functions and the (amplified) boomerang attack. In: A. Menezes (ed.) Advances in Cryptology—CRYPTO 2007. Lecture Notes in Computer Science, vol. 4622, pp. 244–263. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-74143-5_14

28.

Kreuzer, M., Robbiano, L.: Computational Commutative Algebra 1, 1st edn. Springer, Berlin (2000). https://doi.org/10.1007/978-3-540-70628-1CrossRef

29.

Kreuzer, M., Robbiano, L.: Computational Commutative Algebra 2, 1st edn. Springer, Berlin (2005). https://doi.org/10.1007/3-540-28296-3CrossRef

30.

Lang, S.: Algebra, 3rd edn. Springer, New York (2002). https://doi.org/10.1007/978-1-4613-0041-0CrossRef

31.

Lidl, R., Niederreiter, H.: Finite Fields. Encyclopedia of mathematics and its applications, 2nd edn. Cambridge Univ. Press, Cambridge (1997)

32.

Masure, L., Méaux, P., Moos, T., Standaert, F.X.: Effective and efficient masking with low noise using small-Mersenne-prime ciphers. In: C. Hazay, M. Stam (eds.) Advances in Cryptology—EUROCRYPT 2023, Part IV. Lecture Notes in Computer Science, vol. 14007, pp. 596–627. Springer, Heidelberg (2023). https://doi.org/10.1007/978-3-031-30634-1_20

33.

Mesnager, S., Mandal, B., Msahli, M.: Survey on recent trends towards generalized differential and boomerang uniformities. Cryptogr. Commun. 14(4), 691–735 (2022). https://doi.org/10.1007/s12095-021-00551-6MathSciNetCrossRef

34.

Mesnager, S., Tang, C., Xiong, M.: On the boomerang uniformity of quadratic permutations. Des. Codes Crypt. 88(10), 2233–2246 (2020). https://doi.org/10.1007/s10623-020-00775-2MathSciNetCrossRef

35.

Murphy, S.: The return of the cryptographic boomerang. IEEE Trans. Inf. Theory 57(4), 2517–2521 (2011). https://doi.org/10.1109/TIT.2011.2111091MathSciNetCrossRef

36.

Nyberg, K.: Differentially uniform mappings for cryptography. In: T. Helleseth (ed.) Advances in Cryptology—EUROCRYPT’93. Lecture Notes in Computer Science, vol. 765, pp. 55–64. Springer, Heidelberg (1994). https://doi.org/10.1007/3-540-48285-7_6

37.

Roy, A., Steiner, M.J.: Generalized triangular dynamical system: an algebraic system for constructing cryptographic permutations over finite fields. Cryptology ePrint Archive, Paper 2024/1316 (2024). https://eprint.iacr.org/2024/1316. Accepted into Selected Areas in Cryptography 2024

38.

Roy, A., Steiner, M.J., Trevisani, S.: Arion: arithmetization-oriented permutation and hashing from generalized triangular dynamical systems. arXiv:2303.04639 (2023). Version: 3

39.

SageMath, the Sage Mathematics Software System (Version 10.3) (2024). https://www.sagemath.org

40.

Stănică, P.: Investigations on c-boomerang uniformity and perfect nonlinearity. Discrete Appl. Math 304, 297–314 (2021). https://doi.org/10.1016/j.dam.2021.08.002MathSciNetCrossRef

41.

Stănică, P.: Low c-differential and c-boomerang uniformity of the swapped inverse function. Discrete Math. 344(10), 112543 (2021). https://doi.org/10.1016/j.disc.2021.112543MathSciNetCrossRef

42.

Stănică, P.: Using double Weil sums in finding the c-boomerang connectivity table for monomial functions on finite fields. Appl. Algebra Eng. Commun. Comput. 34(4), 581–602 (2023). https://doi.org/10.1007/s00200-021-00520-9MathSciNetCrossRef

43.

Stănică, P., Riera, C., Tkachenko, A.: Characters, Weil sums and c-differential uniformity with an application to the perturbed gold function. Cryptogr. Commun. 13(6), 891–907 (2021). https://doi.org/10.1007/s12095-021-00485-zMathSciNetCrossRef

44.

Wagner, D.: The boomerang attack. In: L.R. Knudsen (ed.) Fast Software Encryption—FSE’99. Lecture Notes in Computer Science, vol. 1636, pp. 156–170. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48519-8_12

45.

Wang, Y.P., Wang, Q., Zhang, W.G.: Boomerang uniformity of normalized permutation polynomials of low degree. Appl. Algebra Eng. Commun. Comput. 31(3), 307–322 (2020). https://doi.org/10.1007/s00200-020-00431-1MathSciNetCrossRef

Titel: A degree bound for the c-boomerang uniformity of permutation monomials
verfasst von: Matthias Johann Steiner
Publikationsdatum: 21.10.2024
Verlag: Springer Berlin Heidelberg
Erschienen in: Applicable Algebra in Engineering, Communication and Computing
Print ISSN: 0938-1279
Elektronische ISSN: 1432-0622
DOI: https://doi.org/10.1007/s00200-024-00670-6

d	\(c = -1\)	\(c = 1\)
3	\(x^4,\ z \cdot x^2,\ z^2\)	\(x^3,\ z\)
5	\(x^8,\ z \cdot x^4,\ z^4\)	\(x^7,\ z \cdot x^4,\ z^3\)
7	\(x^{12},\ z \cdot x^6,\ z^6\)	\(x^{11},\ z \cdot x^6,\ z^5\)
11	\(x^{20},\ z \cdot x^{10},\ z^{10}\)	\(x^{19},\ z \cdot x^{10},\ z^9\)
129	\(x^{256},\ z \cdot x^{128},\ z^{128}\)	\(x^{255},\ z \cdot x^{128},\ z^{127}\)
257	\(x^{512},\ z \cdot x^{256},\ z^{256}\)	\(x^{511},\ z \cdot x^{256},\ z^{255}\)

Springer Professional

A degree bound for the c-boomerang uniformity of permutation monomials

Abstract

Publisher's Note

1 Introduction

1.1 Our results

2 Preliminaries

2.1 c-differential uniformity

2.2 c-boomerang uniformity

2.3 Plane curves

2.4 Gröbner bases

3 Generalized c-boomerang equations for monomials

3.1 The cases \(a = 0\) & \(b = 0\)

4 On the tightness of the c-boomerang uniformity bound

4.1 Symbolic Gröbner basis computations

4.1.1 \(c^2 \ne 1\)

4.1.2 \(c^2 = 1\)

4.2 Examples over small prime fields

5 c-uniformities of the generalized triangular dynamical system

5.1 c-differential distribution table of the generalized triangular dynamical system

5.2 c-boomerang connectivity table of a class of generalized triangular dynamical systems

5.2.1 The propagation probability of a block cipher round

6 Conclusion

Acknowledgements

Conflict of interest

Publisher's Note

`A SageMath` scripts

A.1 Generic Gröbner basis computations

A.2 Exhaustive c-boomerang uniformities computation

B Symbolic \(\pm 1\)-Boomerang Gröbner bases for small exponents

B.1 \(d = 3\)

B.1.1 \(c = -1\)

B.1.2 \(c = 1\)

B.2 \(d = 5\)

B.2.1 \(c = -1\)

B.2.2 \(c = 1\)

Premium Partner

	\(d = 3\)			\(d = 5\)
q	\(c^2 \ne 1\)	\(c = -1\)	\(c = 1\)	\(c^2 \ne 1\)	\(c = -1\)	\(c = 1\)
11	(8, 4)	2	3	n.a	n.a	n.a
17	(10, 4)	4	3	n.a	n.a	4
23	(20, 4)	4	3	(5, 5)	6	5
29	(8, 6)	4	3	(2, 5)	2	7
107	(2, 6)	6	3	(16, 7)	5	4

q	c	d	b	\(_c {\mathcal{B}}_{x^d} \left( 1, b \right)\)
11	1	3	2	3
29	1	3	11	3
101	1	3	8	3
101	\(-1\)	3	44	6
107	1	3	1	3
107	\(-1\)	3	1	6
1429	1	5	298	15

Springer Professional

Abstract

Publisher's Note

1 Introduction

1.1 Our results

2 Preliminaries

2.1 c-differential uniformity

2.2 c-boomerang uniformity

2.3 Plane curves

2.4 Gröbner bases

3 Generalized c-boomerang equations for monomials

3.1 The cases \(a = 0\) & \(b = 0\)

4 On the tightness of the c-boomerang uniformity bound

4.1 Symbolic Gröbner basis computations

4.1.1 \(c^2 \ne 1\)

4.1.2 \(c^2 = 1\)

4.2 Examples over small prime fields

5 c-uniformities of the generalized triangular dynamical system

5.1 c-differential distribution table of the generalized triangular dynamical system

5.2 c-boomerang connectivity table of a class of generalized triangular dynamical systems

5.2.1 The propagation probability of a block cipher round

6 Conclusion

Acknowledgements

Conflict of interest

Publisher's Note

A SageMath scripts

A.1 Generic Gröbner basis computations

A.2 Exhaustive c-boomerang uniformities computation

B Symbolic \(\pm 1\)-Boomerang Gröbner bases for small exponents

B.1 \(d = 3\)

B.1.1 \(c = -1\)

B.1.2 \(c = 1\)

B.2 \(d = 5\)

B.2.1 \(c = -1\)

B.2.2 \(c = 1\)

`A SageMath` scripts