<figure><img src="image_1.png" /></figure>

HAL
open science

# Practical Study on Solving Polynomial Systems corresponding to Algebraic Attacks on Symmetric Primitives

Baptiste Daumen

► To cite this version:

Baptiste Daumen. Practical Study on Solving Polynomial Systems corresponding to Algebraic Attacks on Symmetric Primitives. Computer Science [cs]. 2025. hal-05468019

HAL Id: hal-05468019

https://inria.hal.science/hal-05468019v1

Submitted on 21 Jan 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Practical Study on Solving Polynomial Systems corresponding to Algebraic Attacks on Symmetric Primitives

Baptiste Daumen supervised by Léo Perrin, COSMIQ team at INRIA Paris

Rapport de stage - Master 2 - September 8th, 2025

## General context

Cryptology is a general field of research that splits into two different disciplines: cryptography and cryptanalysis. The first refers to the science of encrypting a plaintext into a ciphertext. Primitives are the functions developed to do it, they are low level algorithms that aim to be used in security protocols. The second, the cryptanalysis, aims to estimate the security of the primitives. Indeed, these primitives must be resistant to different attacks in order to be considered as secure.

The primitives we study are permutations developed for new protocols such as Fully Homomorphic Encryption, Multi Party Computing and Zero-Knowledge Proof that impose constraints. For example, permutations must be defined over large finite fields. Common algorithms, such as AES, can't be adapted to these protocols which leads to the need to develop new primitives. This new family of functions is named Arithmetisation-Oriented Primitives (AOP).

These permutations differ by their underlying alphabet. Usual symmetric primitives are defined over $F_2^n$ where $n$ is an integer. AOP are them defined over $F_p^n$ where $p$ is a (very) large prime.

Thus, the security of these new primitives has to be estimated against usual attacks, such that differential and linear ones. Moreover, their particular structures make them vulnerable to algebraic attacks. Primitives are defined by many parameters that have an impact on the computation time and the security. Understanding how algebraic attacks work on these functions allows determining adequate parameters.

## Research problem

Algebraic attacks are well-suited to uncover weaknesses in AOP due to its strong algebraic structure. However, this research area remains relatively unexplored and is still not fully understood.

We focused on the algebraic attacks relying on the Gröbner basis theory. It is a mathematical concept studied for many decades that leads to many theoritical and practical results. Gröbner bases allow to find the solutions of a system of equations composed of multivariate polynomials.

An algebraic attack splits into two steps. First, model the problem corresponding to a specific attack as a polynomial system of equations and then solve it. The attacks are very practical, but understanding the mathematical structure of the equations is also fundamental.

Thus, two questions have raised. The first one concerns the tools used to do cryptanalysis. When attacks are performed on a computer algebra system, the functions used are black-boxes. In our case, the two main algorithms are the computation of a Gröbner basis and its transformation from a monomial order to another. We don't know what libraries, algorithms and heuristics are implemented in these black-boxes. Thus, we worked on understanding the tools proposed by the computer algebra system SageMath to apply algebraic attacks and comparing them to determine which of them are the most efficient.
The second question deals with the particular structure of the equations. Computation of Gröbner bases for random systems of equations have been studied in the literature mainly with a mathematical point of view. Depending on the assumptions made, some results on the time complexity of algorithms are established. For example, the algorithm F5 is very efficient in the case of homogeneous regular systems of equations for the DRL monomial order. However, the instances of system of equations studied in symmetric cryptography are very specific. The security of the primitives against algebraic attacks highly depends on the time complexity to find a Gröbner basis for the LEX order. Then the specificity of our systems may have an impact on the estimated time to find Gröbner bases, which could make some security arguments wrong if using general time estimations of algorithms. The specificity of our systems is double. First the polynomials are very sparse, only some monomials among the set of possible ones compose the polynomials. Second, these monomials are linked by the permutation. This particular structure is likely to have an influence on the time complexity. It has been observed by the authors of [BBL+24], where in this case the Gröbner basis is free for a custom monomial order. Improving the understanding of algorithm behavior on these instances has also been explored in [KLR24], with particular emphasis on the Anemoi permutation.

## Your contribution

Our work is structured around two main contributions. First, a state of the art of the libraries in SageMath to compute a Gröbner basis that aims to know what algorithms are used and what heuristics have been chosen to be implemented. Then, we performed experiments to compare these different algorithms and have determined which ones were the most efficient and relevant to use in our case. We also pointed out problems with the integration of some algorithms in SageMath.

Our second contribution is the development of a benchmarking framework to study the behaviour of the algorithms on the structured systems of equations coming from symmetric cryptography and the structure of the bases obtained. It allowed us to get some results concerning the parameters that affect the structure of the equations, the verification of some heuristics and to point out the specificity of our systems of equations.

## Arguments supporting its validity

The different results obtained come from the experiments conducted using the benchmarking framework developed. Thus, the scientific validity of our results relies on the experimental methodology implemented within the benchmarking system. The presentation of this system is done in Section 4.

The primitives studied are designed to resist against algebraic attacks so getting results on full-round variant is not possible in practice. Thus, experiments were carried out on reduced-round versions of the permutations. We tried to obtain results for the largest set of parameters possible, so we can extrapolate the conclusion made to the full-round primitive.

## Summary and future work

We contributed to this area by establishing a state of the art of the algorithms proposed in SageMath to compute Gröbner bases and developing a benchmarking system that allows to compare execution time of algebraic attacks on primitives and random ideals that are similar in their structure.

Using this framework, first results were obtained and give interesting observations that raise new questions. The main result concerns the ideal degree of systems corresponding to algebraic attacks that is lower than the expected one for random systems of similar shape.
Moreover, this framework could be used again on different primitives and modellings to continue the research on algebraic attacks and allow observations that aim to understand the structure of the permutations.

# 1 Preliminaries

## 1.1 Sponge construction

Sponge functions are cryptographic constructions that implement different cryptographic primitives. For example, they are used to defining hash functions. At the core of the sponge construction, a permutation is used to randomise the internal state. In the classical sponge construction, the internal state is a vector of bits. However, in AOP the internal state is a vector defined over a finite field.

<figure><img src="image_3.png" /><figcaption>Figure 1: Sponge construction over a finite field from [Jea16, Hash Functions, Sponge construction].</figcaption></figure>

The permutation $F$ must act like a random permutation. This criterion determines the security definition used in this report.

## 1.2 Security definition

What is expected from such a permutation is for it to be hard to control at the same time the input and the output. One way to describe it mathematically is the constrained-input constrained-output (CICO) problem.

**Definition 1.1 (CICO-ℓ Problem).** Let $F : \mathbb{F}_p^t \to \mathbb{F}_p^t$ be a permutation and $1 \le \ell < t$ an integer. The goal is to find $x \in \{0\}^\ell \times \mathbb{F}_p^{t-\ell}$ such that $F(x) \in \{0\}^\ell \times \mathbb{F}_p^{t-\ell}$.

CICO problem refers to the general problem, without specifying the number of zeroes to fix.

Knowing whether solutions to the CICO problem exist is not the fundamental matter. The goal is that the algorithms used to find at least a solution have a time complexity higher than the complexity of an exhaustive research (impossible in practice considering the size of the finite field). Performing an attack means to apply an algorithm (or many) which return(s) a solution (or many) to the problem considered. The time complexity of these algorithms must be evaluated in order to compare them to an exhaustive research. It is expected for secure primitive to have: $C_{alg} > 2^N$ where $N$ is the number of security bits wanted and $C_{alg}$ the time complexity of the algebraic attack.

In this report the notion of complexity used is the number of operations in the base field (arithmetic complexity). We focus mostly on time complexity. “$O$” refers to the Landau notation.

Considering the alphabet of definition of the permutations, $\mathbb{F}_p$, and the structure of the problem, a cryptanalysis tool to evaluate the hardness of the problem is the algebraic attack. The execution of this attack is in two parts: model the CICO problem into a system of equations and solve this system. Many methods allowing to model the CICO problem into a system of equations have been developed and are presented in this report.
## 1.3 Primitives and systems of equations modelling

Many parameters are used when defining a permutation. The number of rounds defines the number of iteration of the round function used. These iterations of the round function gives the full primitive function. The number of branches is the vector size of the internal state in the sponge function, so it is the size of the input vector of the permutation. The field characteristic is also a parameter of the permutation. These parameters have an impact on the computation time of the permutation and on its security. Primitives and modellings of the CICO problem are presented in this subsection.

### 1.3.1 Zerolith

Monolith [GKL$^{+}$24] is a family of permutations defined over a finite field, which are used in the design of hash functions. This permutation is structured in three different layers. The first layer, “Bars”, is a non-linear layer that is based on an S-box function. This layer is not studied in the experiments. The second layer is also a non-linear layer, it is named Bricks. It is a sequence of square and addition that increases the degree of the equations and also adds a lot of sparsity and structure in the equations. The last layer is the linear one, that is usual in symmetric cryptography. It is composed of a matrix multiplication and constants addition. There is no restriction on the number of rounds, branches and the field characteristic. We only focus on the permutation composed of the Bricks and linear layer. We call this new permutation Zerolith.

<figure><img src="image_4.png" /><figcaption>Figure 2: Zerolith round function from [GKL$^{+}$24, Figure 4].</figcaption></figure>

The CICO problem is modelled in such a way that the number of equations and the number of variables is the same. Thus, the number of solutions of the equation is finite. Let’s consider an instance of Zerolith with $t$ branches and an instance of the CICO problem where we want to find $0 \le n < t$ zeroes.

The input of the permutation chosen is $(0, \dots, 0, \sum_{i=0}^{n-1} \alpha_i^0 \times x_i, \dots, \sum_{i=0}^{n-1} \alpha_i^{t-n+1} \times x_i)$. The number of zeroes is $n$. We evaluate the permutation, using a certain number of rounds, on this input. Let’s note the output $P_0(x_0, \dots, x_{n-1}), \dots, P_{t-1}(x_0, \dots, x_{n-1})$. The system of equations derived to solve the CICO problem is then:

$$ \{P_0(x_0, \dots, x_{n-1}) = 0, P_1(x_0, \dots, x_{n-1}) = 0, \dots, P_{n-1}(x_0, \dots, x_{n-1}) = 0\}. $$

### 1.3.2 Anemoi

Anemoi [BBC$^{+}$23] is a family of permutations that operates on $F_p^{2\ell}$, where $p$ is prime and $\ell$ is a positive integer.

In order to solve CICO problems, two modellings of systems of equations are used. One is quite general, at each round, new variables are introduced and linked with the previous ones using round equations. The second modelling is specific to permutations using a high degree exponentiation $(.)^{\frac{1}{\alpha}}$,
<figure><img src="image_5.png" /><figcaption>(a) Anemoi round function</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>(b) Non-linear layer $\mathcal{H}$ in odd characteristic</figcaption></figure>

<caption>Figure 3: Description of Anemoi over prime fields with $\ell=1$ from [BBL$^+$24, Fig.4].</caption>

where $\alpha$ is the first integer larger or equal to 3 such that $\gcd(\alpha, p-1) = 1$. Thus, the characteristic of the field has a major influence on the degree of the polynomials. This approach is introduced in [BBL$^+$24]. Using a specific order, the Gröbner basis may be free to have (the system of equations is already a Gröbner basis). This modelling allows solving CICO-1 problems only. The number of rounds is free to choose.

**Round variables** This modelling is based on the introduction of new variables at each round. Let's do it for two variables ($\ell = 1$) in the case of Anemoi. Let's note $x_r$ and $y_r$ the input variables of the non-linear layer $\mathcal{H}$ and $x_{r+1}$ and $y_{r+1}$ the output variables.

While looking at the $\mathcal{H}$ function, we can write the equations linking the variables.

$$ \begin{cases} (y_r - y_{r+1})^{\alpha} + a \times y_{r+1}^2 - x_{r+1} = 0 \\ (y_r - y_{r+1})^{\alpha} + a \times y_r^2 - x_r + a^{-1} = 0 \end{cases} $$

Then to solve for instance the CICO-1 problem, we add two equations $x_0 = 0$ and $x_m = 0$, where $m$ is the number of rounds.

**Freelunch** Freelunch modelling allows solving CICO-1 problem. The input of the permutation chosen is $(0, \alpha_0^0 + \alpha_1^0 \times x_0, \dots, \alpha_0^{t-2} + \alpha_1^{t-2} \times x_0)$. At each round, we introduce a new variable which corresponds to the inversion of the low degree function, namely $(.)^{\frac{1}{\alpha}}$. The system of equations has a triangular shape:

$$ \left\{ \begin{aligned} x_1^{\alpha} - f_1(x_0) &= 0 \\ x_2^{\alpha} - f_2(x_0, x_1) &= 0 \\ \vdots \\ x_{n-1}^{\alpha} - f_{n-1}(x_0, \dots, x_{n-2}) &= 0 \\ f_n(x_0, \dots, x_{n-1}) &= 0. \end{aligned} \right. $$

The last equation corresponds to the first coordinate of the output vector.

### 1.3.3 Griffin-$\pi$

Griffin-$\pi$ is introduced in [GHR$^+$23]. It operates over $\mathbb{F}_p^\ell$, where $p$ is a prime and $\ell$ is in $\{3, 4\ell' | \ell' \ge 1\}$. The security of the round function of this permutation relies as well on an inversion of the low degree function (which leads to high degree exponentiation). The number of rounds and the field characteristic are free to choose. We also use the Freelunch modelling.
### 1.3.4 Number of solutions to the CICO problem

The number of solutions of the CICO problem found depends on the modelling and the coefficients $\alpha_i^j$ chosen in the input vector. It may happen that we do not find any solution or on the contrary that we find many of them. The Poisson distribution describes the probability to get 0, 1 or many solutions. Following the round variables modelling, we can compute the probability to get 1 or more solutions, namely $1 - e^{-1}$. More details are given in Appendix D.

## 1.4 Structure of the report

After introducing in this section the framework about the cryptographic permutations, the CICO problem modellings and the relevance of algebraic attacks on AOP, we describe the mathematical background and the algorithms used to solve systems of equations in Section 2. We discuss also their time complexity. Then, in Section 3, 4 and 5, we present our contributions: in Section 3 a state of the art of the libraries proposed in SageMath to compute Gröbner bases, in Section 4 the benchmarking framework developed in order to study the specificity of our systems of equations, and finally, in Section 5, the results obtained thanks to this framework. In Section 6, we conclude by giving the ideas at which we may look further to better understand the specificities of our equations.

# 2 Solving systems of multivariate polynomial equations

## 2.1 Gröbner basis theory

This section introduces the mathematical notion of Gröbner basis. The definitions and theorems used have been introduced by Bruno Buchberger in his PhD thesis (translated in English in [Buc06]). The main result of this section is an algorithm that computes Gröbner bases. The presentation is highly inspired by [CLO97, Chapter 2 and 3]. The references of sections given with no citations relate to this book.

### 2.1.1 Degree and dimension of ideals

In this report, we focus on 0-dimensional ideal, which means that the system of equations that generates the ideal has a finite number of solutions (counted with multiplicities) in the algebraic closure of the base field. It is made possible by having the same number of equations and variables. An important invariant of a 0-dimensional ideal is its degree.

**Definition 2.1** (Ideal degree from [Spa12, Definition 1.4]). Let $I \subset K[X]$ be a 0-dimensional ideal. Then $K[X]/I$ is a $K$-vector space of finite dimension. The dimension $\dim_K(K[X]/I)$ is called the degree of $I$ and is denoted by $\deg(I)$.

### 2.1.2 Monomials order

For the rest of the report, let's define the multivariate polynomial ring $R = \mathbb{F}_p[x_1, \dots, x_n]$, where $\mathbb{F}_p$ is the finite field of characteristic $p$ such that $p$ is a prime.

**Definition 2.2.** (i) A monomial is $x^\alpha = x_1^{\alpha_1} \cdots x_n^{\alpha_n}$ with $\alpha = (\alpha_1, \dots, \alpha_n) \in \mathbb{N}^n$.

(ii) A polynomial is $f = \sum_{\alpha \in \mathbb{N}^n} c_\alpha x^\alpha$ with $c_\alpha \in \mathbb{F}_p$ (finite sum).

(iii) The degree of $\deg(x^\alpha) = |\alpha| = \sum_{i=1}^n \alpha_i$ and $\deg(f) = \max_{\{\alpha|c_\alpha \neq 0\}} \deg(c_\alpha x^\alpha)$.
The monomial set is a key part of the Gröbner basis theory. We introduce an order over this set that plays a major role in the execution of the algebraic attack. Two orders are mainly used throughout the analysis: the lexicographic order and graded reverse lexicographic order.

**Definition 2.3** (Lexicographic Order - LEX, Chapter 2, Section 2, Definition 3). Let $\alpha \in \mathbb{N}^n$ and $\beta \in \mathbb{N}^n$. $\alpha >_{lex} \beta$ if the left-most nonzero entry of $\alpha - \beta$ is positive.

**Definition 2.4** (Graded Reverse Lexicographic Order - DRL, Chapter 2, Section 2, Definition 6). Let $\alpha \in \mathbb{N}^n$ and $\beta \in \mathbb{N}^n$. Then $\alpha >_{\text{grevlex}} \beta$ if:

$$|\alpha| = \sum_{i=1}^{n} \alpha_i > \sum_{i=1}^{n} \beta_i = |\beta|, \quad \text{or} \quad |\alpha| = |\beta| \text{ and the right-most nonzero entry of } \alpha - \beta \text{ is negative.}$$

Depending on the order chosen for the monomial set, we introduce different notions that are related to the monomials involved in a polynomial.

**Definition 2.5** (Chapter 2, Section 2, Definition 7). Let $f$ be a polynomial in $R$.

(i) The multidegree of $f$ is $\text{multideg}(f) = \max(\alpha \in \mathbb{N}^n | c_\alpha \neq 0)$.

(ii) The leading coefficient of $f$ is $\text{LC}(f) = a_{\text{multideg}(f)} \in \mathbb{F}_p$.

(iii) The leading monomial of $f$ is $\text{LM}(f) = x^{\text{multideg}(f)}$.

(iv) The leading term of $f$ is $\text{LT}(f) = \text{LC}(f) \cdot \text{LM}(f)$.

### 2.1.3 Gröbner basis

Let's $I$ be the studied ideal. Gröbner bases are special finite generative sets of the ideals. Their specificities lie in their leading terms. Indeed, these polynomials have minimal leading terms in the sense that they generate the entire ideal of the leading terms of $I$.

**Definition 2.6** (Leading term ideal, Chapter 2, Section 5, Definition 1). Let $I \subseteq k[x_1, \dots, x_n]$ be an ideal other than $\{0\}$, and fix a monomial ordering on $k[x_1, \dots, x_n]$. Then:

(i) We denote by $\text{LT}(I)$ the set of leading terms of nonzero elements of $I$. Thus,

$$\text{LT}(I) = \{cx^{\alpha} \mid \exists f \in I \setminus \{0\} \text{ with } \text{LT}(f) = cx^{\alpha}\}.$$

(ii) We denote by $\langle \text{LT}(I) \rangle$ the ideal generated by the elements of $\text{LT}(I)$.

**Definition 2.7** (Gröbner basis, Chapter 2, Section 5, Definition 5). Fix a monomial order over the ring $R$. Let $I$ be an ideal from $R$ that is different from $\{0\}$ and $G = \{g_1, \dots, g_m\}$ a finite subset of $I$. Then $G$ is called a Gröbner basis if

$$\langle \text{LT}(g_1), \dots, \text{LT}(g_t) \rangle = \langle \text{LT}(I) \rangle.$$

Three properties have to be highlighted. Gröbner bases are generative sets of $I$, there always exists a Gröbner basis, and there exists a unique reduced Gröbner basis that we refer as “the Gröbner basis”. Definitions and properties are given in Appendix A.

Buchberger gave another characterisation of the Gröbner bases in his PhD thesis. It is more convenient to use in an algorithmic manner, as described in the Buchberger's algorithm.
**Theorem 2.1** (Buchberger criterion, Chapter 2, Section 6, Theorem 6). A finite set of polynomials $\{f_1, f_2, \dots, f_n\} \subseteq R$ is a Gröbner basis of the ideal $I = \langle f_1, f_2, \dots, f_n \rangle$ with respect to a monomial order $\prec$ if and only if, for all $1 \le i < j \le n$, the S-polynomial

$$S(f_i, f_j) = \frac{\operatorname{lcm}(\operatorname{LT}(f_i), \operatorname{LT}(f_j))}{\operatorname{LT}(f_i)} \cdot f_i - \frac{\operatorname{lcm}(\operatorname{LT}(f_i), \operatorname{LT}(f_j))}{\operatorname{LT}(f_j)} \cdot f_j$$

reduces to zero modulo $\{f_1, f_2, \dots, f_n\}$.

The reduction in this case means the computation of the multivariate division algorithm on the S-polynomial modulo the set of polynomials. The algorithm is described in Appendix B.

## 2.2 Elimination order

This subsection introduces the notion of elimination order, that allows to solve systems of equations using Gröbner bases.

**Definition 2.8** (Chapter 2, Section 5, Definition 8). Let $I \subseteq R$ be an ideal. We denote by $V(I)$ the set

$$V(I) = \{(a_1, \dots, a_n) \in \mathbb{F}_p^n \mid f(a_1, \dots, a_n) = 0 \text{ for all } f \in I\}.$$

$V(I)$ is the set of the common roots of the polynomials in $I$.

**Proposition 2.1** (Chapter 2, Section 5, Proposition 9). Let $\{f_1, f_2, \dots, f_n\} \subseteq R$. If $I = \langle f_1, \dots, f_s \rangle$ then $V(I) = V(f_1, \dots, f_s)$, where $V(f_1, \dots, f_s)$ is the set of common roots of the set $\{f_1, \dots, f_s\}$.

From this proposition, we can deduce that all generative sets of $I$ have the same common roots.

**Definition 2.9** (Chapter 3, Section 1, Definition 1). Given $I = \langle f_1, \dots, f_s \rangle \subseteq k[x_1, \dots, x_n]$, the $\ell$-th elimination ideal $I_\ell$ is the ideal of $k[x_{\ell+1}, \dots, x_n]$ defined by

$$I_{\ell} = I \cap k[x_{\ell+1}, \dots, x_n].$$

**Theorem 2.2** (The elimination theorem, Chapter 3, Section 1, Theorem 2). Let $I \subseteq R$ be an ideal, and let $G$ be a Gröbner basis of $I$ with respect to the lexicographic order where $x_1 > x_2 > \dots > x_n$. Then, for every $0 \le \ell \le n$, the set

$$G_{\ell} = G \cap \mathbb{F}_{p}[x_{\ell+1}, \dots, x_n]$$

is a Gröbner basis of the $\ell$-th elimination ideal $I_\ell$.

From this theorem, we can deduce that the Gröbner basis for the lexicographic order allows the elimination of variables when finding the roots of the system generated by the basis, one by one.

A particular shape may occur, it is called in the literature: the shape position.

**Definition 2.10** ([FM17, Definition 3.1]). An ideal $I$ of $R$ is in shape position if its reduced Gröbner basis in the lexicographical order has the following form:

$$G = \{f_0(x_0), x_1 - f_1(x_0), \dots, x_{n-1} - f_{n-1}(x_0)\}.$$

For more mathematical details, when the shape position appears see [Bar04, Section 1.3.1]. The ideal degree for these ideals is $\deg(f_0)$ (univariate polynomial degree). The shape position for the lexicographical order is commonly supposed in algebraic attack assumptions. Not having a shape position for an elimination order may be seen as dependence between the solutions of the CICO problem, which is not expected of a permutation that must act as a random permutation.
## 2.3 Buchberger's algorithm and heuristics

The original algorithm to compute a Gröbner basis of an ideal is the Buchberger's algorithm. It was first proposed by Bruno Buchberger in his PhD Thesis where he proved the termination and the correctness. The presentation of this algorithm is also done in [CLO97, Chapter 2, Section 7, Theorem 2]. Algorithm 1 is taken from this book.

<caption>**Algorithm 1 Buchberger's Algorithm for Computing a Gröbner Basis**</caption>

**Require:** A set of polynomials $F = \{f_1, \dots, f_m\}$ in a polynomial ring
**Ensure:** A Gröbner basis $G$ for the ideal $\langle F \rangle$
1: $G \leftarrow F$
2: $P \leftarrow \{(f,g) \mid f,g \in G, f \neq g\}$
3: **while** $P \neq \emptyset$ **do**
4: &nbsp;&nbsp;&nbsp;&nbsp;Select a pair $(f,g)$ from $P$ and remove it
5: &nbsp;&nbsp;&nbsp;&nbsp;$S \leftarrow S(f,g)$
6: &nbsp;&nbsp;&nbsp;&nbsp;$r \leftarrow$ Reduction of $S$ modulo $G$
7: &nbsp;&nbsp;&nbsp;&nbsp;**if** $r \neq 0$ **then**
8: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**for all** $h \in G$ **do**
9: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$P \leftarrow P \cup \{(h,r)\}$
10: &nbsp;&nbsp;&nbsp;&nbsp;**end for**
11: &nbsp;&nbsp;&nbsp;&nbsp;$G \leftarrow G \cup \{r\}$
12: &nbsp;&nbsp;&nbsp;&nbsp;**end if**
13: &nbsp;&nbsp;&nbsp;&nbsp;**end while**
14: **return** $G$

In this algorithm there are many choices to do. They have no consequence on the termination and the correctness, but a major one on the time complexity.

The main choices are the monomial order, the pair selection and the order of $G$ in the reduction. Indeed, as $G$ is not yet a Gröbner basis, the reduction depends on the order of the elements in $G$. The most expensive part is the reduction of the S-polynomial. As these choices are related to this step, a lot of research has been done to find effective variations of Algorithm 1 namely, to find criteria to decrease the number of S-polynomials reduction and heuristics in the choices.

**Criteria to avoid reducing S-polynomial to 0.** What can tremendously slow down the full computation of the Gröbner basis is the reduction to 0 of S-polynomials. Indeed, these computations are useless, in the sense that they do not add any information to compute the basis. Buchberger found criteria that detect which pairs lead to S-polynomial reducing to 0. However, in some cases these criteria are far from being efficient: many S-polynomials still reduce to 0. The implementation of these criteria is developed in [GM88].

**Multi-reduction using linear algebra.** In 1999, Jean-Charles Faugère introduced a new idea in [Fau99], that is to “simulate” the reduction using linear algebra, and hence, allowing to reduce many S-polynomials in one step. This algorithm is named F4. Moreover, to optimise the linear algebra part, many algorithms have been developed which has made F4 very efficient (mainly for the DRL order).

**Signature based algorithm.** The signature is a notion introduced in [Fau02] which allows adding two criteria that avoid all the reduction to 0 of S-polynomial in the case where the input is a regular system. The original algorithm introduced by Faugère using the signature is F5. Since
then, many variations were developed [EF17]. This class of algorithms offers the most efficient
algorithms to find Gröbner bases, but suffers from a lack of open source implementations.

Numerous heuristics have been evaluated and shown to be effective for computing Gröbner bases.

* The normal strategy is described in [Fau99, Section 2.5]. This strategy first selects the pair(s) of polynomials such that the degree of their least common multiple is the smallest. This strategy is efficient using homogeneous polynomials. Homogeneous polynomials have all their monomials with the same degree. Every non-homogeneous polynomial may be homogenised using an additional variable. For each monomial, this variable is raised to a power and multiplied to the monomial such that the new monomial reaches the degree of the polynomial. For non-homogeneous polynomials this strategy may be quite inefficient if the monomial order is not degree compatible, as described in [GMN+91, Section 1].

* The “sugar strategy” is introduced in [GMN+91]. The Sugar is a degree associated to every polynomial and used to compare the pairs. The priority is given to low Sugar pairs (the ties are broken using an additional criteria). This strategy aims to simulate the degree of the homogenised polynomials. Indeed, one could homogenise the polynomials, use the normal strategy and then evaluate the extra variable at 1. However, the authors discuss of issues that may occur using this strategy. Thus, they introduce the Sugar degree which simulates the degree of the polynomials we would have if they were homogenised, but they keep original polynomials and select the pairs using this degree.

* An experimental result is that computing bases for the LEX order is longer than computing for the DRL order. In the case of the F4 algorithm, it has been designed to be efficient for this particular order. Thus, the strategy is to compute the Gröbner basis for the DRL order and then use an algorithm that changes the order and returns a Gröbner basis for the new order.

## 2.4 Term order change algorithms

Term order change algorithms take as input a Gröbner basis for a monomial order and return a basis for another order. They are mainly used to transform bases from the DRL order to the LEX one. The two main algorithms are FGLM and Gröbner Walk.

FGLM is presented in [FGLM93]. This algorithm allows changing the term order of the basis for ideals of dimension 0. Thus, this algorithm is likely to be suitable for our case. The algorithm is given in Appendix C.

The Gröbner Walk algorithm is more general and may be applied to any ideal. It is presented in [CKM97]. Due to the results obtained from the experiments in Section 5.2, this algorithm is not detailed in this report.

## 2.5 Gröbner basis computation time complexity

The complexity in time of the Buchberger's algorithm is not well understood. It highly depends on the strategies introduced in Section 2.3. However, some results are known related to the complexity.

The worst case complexity to compute a Gröbner basis is known for any field. There exists a system of equations with $n$ polynomials and $n$ variables of degree $D$ such that, for any order, the computation of a Gröbner basis is polynomial in $D^{2^n}$ [Bar04, Proposition 1.8]. However, this case is very rare. For 0-dimensional ideal, the worst complexity is polynomial in $D^n$, where $D$ is the maximal degree of the input polynomials [Bar04, Theorem 1.8.2].
A good measure for the complexity is the degree of regularity, that is, the maximal degree reached by a polynomial during the computation of the Gröbner basis. The Macaulay bound states that the degree of regularity is $1 + \sum_{j=0}^{n-1} (d_j - 1)$ where $d_j$ corresponds to the degree of the j-th polynomial [Spa12, Corollary 1.68]. This bound is reached for systems of homogenised polynomials. It is also used to estimate the degree of regularity of non-homogeneous systems of equations.

The complexities are better understood in the case of homogeneous ideals of dimension 0.

**Theorem 2.3** ([Spa12, Theorem 1.72]). Let $F = (f_1, \dots, f_m) \in K[X]^m$ be a family of homogeneous polynomials generating a 0-dimensional ideal. The complexity of computing a Gröbner basis (for any monomial ordering) of the ideal $\langle F \rangle$ is bounded by

$$ \mathcal{O}\left(m \binom{n + \mathrm{d}_{\mathrm{reg}}(F)}{\mathrm{d}_{\mathrm{reg}}(F)}^{\omega}\right), $$

where $\mathrm{d}_{\mathrm{reg}}(F)$ denotes the degree of regularity of $F$ and $\omega$ is the exponent of matrix multiplication.

## 2.6 Term order change algorithm time complexity

FGLM is the algorithm to change the term order in the case of 0 dimensional ideal. Its complexity is $\mathcal{O}(n \times D^3)$ where $n$ is the number of variables and $D$ the degree of the ideal [FGLM93, Theorem 5.1]. There have been improvements on this bound, mainly taking advantage at the sparsity of the matrices involved in the computation and using assumptions on the ideal [FM17].

## 2.7 Performing an algebraic attack

An algebraic attack is performed in three steps.

**Step 1 - Find a modelling system of equations S of the CICO problem.** Many techniques may be used to model the CICO problem into a polynomial system of equations. We presented the ones used in this report in Section 1.3.

**Step 2 - Compute the Gröbner basis G for the lexicographic order of S.** Let's note $I$ the ideal generated by the system obtained at Step 1. We need to find its Gröbner basis for the lexicographic order. We know that the Gröbner basis is a generative set for $I$ and according to Section 2.1, the original system and the Gröbner basis have the same roots. The importance of this step lies in the complexity to compute the Gröbner basis.

**Step 3 - Solve the system of equations described by G.** The structure of the Gröbner basis for the lexicographic order allows us to solve this system by finding roots of univariate polynomial in the base field: first find the roots of $f_0$ (only depending on $x_0$) then substitute the solutions in $f_1$ and find the roots in $x_1$ and so on. The position shape allows getting solutions by finding roots of a unique univariate polynomial. The solutions of such a system give some solutions of the CICO problem.

The computation of the roots for a univariate polynomial over a finite field is not discussed in this report because it is negligible compared to the rest.
## 2.8 Security evaluation based on attack time complexity

Looking at the three steps of an algebraic attack, the most costly one is often the second one. In this report, we focus on the experimental time complexities of the algorithms to perform this step. As the system we study are highly structured the usual bounds on complexity may not be relevant to use in order to derive appropriate security parameters. We detail these arguments.

* The systems of equations studied are highly structured. The polynomials involved in these systems are very sparse. Thus, they differ from random polynomials that contain all the monomials possible up to a certain degree (with high probability for finite fields of large characteristic). We observe that the usual bounds used to estimate the complexity of algorithms on this random ideals may not be tight enough compared to the reality of the computation. Extreme cases like in $[BBL^+24]$ give free Gröbner basis using a custom monomial order. Then the time complexity of Step 2 only depends on complexity of the order changing algorithm. Moreover, the system inherits of the structure of the permutation that may have an influence on the complexity, by linking in a particular the monomials.

* Most of the bounds are upper ones for the Gröbner basis computation, so they may give indication on the computation time of algorithms for average case but may not be used to lower bound computation time and ensure some security levels.

These remarks lead us to explore experimental solutions to estimate complexities. These complexities depend on the library implementations. Some choices in the implementation of algorithms may lead to very different complexities on our structured systems. Then, comparing computation time on different libraries and algorithms is relevant to understand the behavior of the algorithms.

# 3 Libraries in SageMath

SageMath is a free open-source computer algebra system. It is widely used and built on many libraries. We are interested in using tools proposed by SageMath to compute Gröbner bases. The study of these libraries to understand the algorithms used, and mostly the heuristics implemented is key to interpret the results of the experiments in Section 5. Indeed, a heuristic may be more adapted to the particular structure of our systems. More details on the libraries are given in Appendix D. The libraries studied are Singular, Macaulay2, Giac and msolve as they are usable in SageMath and are open-source. Magma being a closed-source software it is not possible to present it in details.

## 3.1 Singular

It is the default library used and installed by SageMath to compute Gröbner bases. It is written in C/C++, and proposes a wide range of algorithms to compute Gröbner basis: Buchberger's algorithm, different versions of it, a variation of F4 and F5. The documentation and the code source are available in [DGPS25].

* "std" is the implementation of the Buchberger's algorithm to which some heuristics have been added to make it efficient and usable in practice.

* "slimgb" is a based on the ideas of the F4 algorithm. It relies on the computation of many S-polynomial reductions in one step but doesn't take advantage of linear algebra techniques. Moreover, it tries to keep the coefficients and polynomials as small as possible to increase
efficiency. Even though we work over finite fields, as their characteristic may be very large (around $2^{256}$), it is interesting to prevent the growth of coefficients and polynomials.

* “sba” is the implementation of the F5 algorithm. The ideas used to implement the algorithm are presented in [Ede14].

* “stdfglm” computes the Gröbner basis for the DRL order, and then performs FGLM to change the order. “std” or “slimgb” are used to compute the first basis.

* “stdhilb” takes advantage of the Hilbert function. It is a function that describes the ideal. It is not presented in this report, as it was not studied deeply by lack of time.

## 3.2 Macaulay2

Macaulay2, [TES], is a software system that includes algorithms to compute Gröbner bases. The core algorithms are written in C/C++.

The global function to compute a Gröbner basis is `groebnerBasis`. This algorithm may be used with three different strategies.

* “gb” is the default strategy. It is Buchberger’s algorithm. Many options may be given to this algorithm. No details are given as results showed the inefficiency of Macaulay2 while computing Gröbner bases.

* “F4” is a Faugere-like algorithm. This strategy only works over finite fields of characteristic less than $2^{32}$. “F4” is still an experimental version.

* “MGB” stands for mathicGB that is a package used by Macaulay2. This package is independent of Macaulay2. For a description, refer to [RS12]. This package implements one of the many signature-based algorithms developed since the introduction of F5. This strategy only works over finite fields of characteristic less than $2^{32}$. “MGB” is still an experimental version.

## 3.3 Giac

Giac [PG24] is a C++ library which implements the Buchberger algorithm with linear algebra using the F4 algorithm. The limit for the characteristic of finite field is $2^{31}$. The description of the algorithm used by Giac is made in [Par18, Section 9.6]. The algorithm is described in 10 steps for computation over finite fields in “Buchberger algorithm with F4 linear algebra modulo a prime”. The main heuristics used are the Gebauer and Möller criterion [GM88], the selection strategy of F4 (all pairs of total minimum degree are selected to be reduced simultaneously) and at each step polynomials with leading monomial divisible by another leading monomial are discarded.

## 3.4 msolve

“msolve” [BES21] is a C package developed with the aim to solve multivariate polynomial systems. It focuses on the implementation of F4 algorithm for the DRL monomial order only and then uses the FGLM algorithm to get the Gröbner basis for a lexicographical order.

In SageMath, this library may be used to either compute only the Gröbner basis or to find the solutions of the system of equations (using the function “variety”).
## 3.5 Others

* Magma [BCP97] is a closed-source library that is known to be one of the most efficient to compute Gröbner bases. An interface with Sagemath does exist. Despite the fact that we cannot know what algorithms are used by the library, we study it because of its efficiency.

* SageMath has its own implementation of the Buchberger's algorithm. It uses the Python language. It is not studied as it is too slow compare to C/C++ implementation.

* Ginv is a library which implements an algorithm different from Buchberger's, as described in [BBM22]. It is called "involutive algorithms". As it differs from Buchberger's algorithm, it is not studied for now but should be, as it has many similarities and could be efficient for our use case.

# 4 A new benchmarking framework

Three questions have raised concerning algebraic attacks' complexity.

The first one concerns the libraries proposed by Sagemath to compute a Gröbner basis. We want to compare their efficiency. The goal of this comparison is double. First, it allows understanding which of the libraries are the most efficient to be used in practice for algebraic attacks. Second, these libraries implement different algorithms using different heuristics. Then it could be that one of them is more adapted to our structured systems of equations.

The second question concerns the permutation. We aim to better understand to what extent the structure of the permutation itself impacts the computation of the LEX Gröbner basis. Indeed, the permutation has not only an impact on the general structure of the systems of equations but also on the monomials involved in the polynomials.

The last question deals with the number of monomials involved in polynomials of systems of equations. The constants present in the round function of the primitive may increase the sparsity of a polynomial depending on their own sparsity. Then, we would like to also discover if this sparsity has an impact on the computation time of the LEX Gröbner basis or on the ideal properties.

We developed a benchmarking framework, in order to realise experiments that could give some answers to these questions. This framework allows performing a large amount of experiments at each execution. Thus, we present the functioning of a single experiment and the overall functioning that allows all experiments to be carried out. It is developed in SageMath.

## 4.1 Inputs

### 4.1.1 Parameters of an experiment

The parameters for an experiment are of two kinds depending on whether the system of equations corresponds to a CICO problem modelling or a random ideal with a specified structure used for comparison. These parameters are given in a Python dictionary.

Some parameters are common to both cases. The first two are the ID and the permutation. The ID allows identifying the experiment. It is useful for the outputs' management. The permutation is either the name of the actual permutation or "random". Then, the field characteristic, the monomial order for the first Gröbner basis, the algorithm to compute the basis, and its options are given.

The term order change algorithm is not yet a parameter that may be chosen.
<figure><img src="image_7.png" /><figcaption>Figure 4: Framework description</figcaption></figure>

**Systems corresponding to a CICO problem.** For a system corresponding to a CICO problem, many parameters are free to choose (in the set of possible parameters of the primitive): the number of rounds, the number of branches, the number of zeroes for the CICO problem, and the constants' sparsity. This sparsity corresponds to the number of zeroes in the constant vector of the round function. The constant sparsity is the same for every constant vectors in the permutation. However, at each round, the non-zero coefficients are randomly drawn. This sparsity allows changing the number of monomials in the polynomials of the system of equations. Indeed, adding a constant at each round and then performing some polynomial multiplications adds new monomials that decrease the sparsity of the polynomials. In the implementation a sparsity of 0 means that all the coefficients of the vector are 0. The matrix of the round function is fixed.

**Random structured systems of equations.** The experiments we want to perform have, among others, the aim to detect if beyond the sparsity of the equations, the fact that it comes from a permutation may lead to a special structure to the equations. Thus, we would like to compare the system of equations to random ones, which share the same structure. It means that each polynomial of the system of equation is composed of the same variables, has the same maximal degree and the same number of monomials. Finally, what changes between the polynomials are their monomials and coefficients.

So, for a random system, another parameter is used that defines its structure. It is a list of triplets composed of the variables involved in the polynomial, its maximum degree and its number of monomials.
**Reiterating an experiment** A last parameter gives the number of times we have to reiterate the same experiment. It is a relevant parameter for the random ideals. The number of monomials is constant but monomials change, which can have an impact on the computation time. We need to measure the variance on a certain number of repetition. The trade-off chosen for the number of repetition is 10. It makes the number of experiments reasonable in the amount of time given and is not too small to have relevant results. Moreover, while analysing the results we noticed that repeating an experiment many times for a primitive may also be relevant to determine whether some parameters have a real influence on the computations’ time.

### 4.1.2 Inputs of all experiments

Three timeouts are given as input for all the experiments done. The first two control the time taken to generate the system of equations and the time taken to compute the Gröbner basis for the LEX order. The first one is useful in the case of the random generation as it may take a long time for many variables and a high maximal degree. These two timeouts are defined in the configuration file (`config.conf`) of the full experimentation.

The third timeout is intrinsic to the cluster used. Indeed, the limitation to use a cluster is around 100 hours, so some parameters are never treated by lack of time if the amount of experiments to perform is too large.

## 4.2 Generation of the parameter file

### 4.2.1 Parameters for primitive

A Python file is filled by the user with the different parameters to test described in Section 4.1. For readability, the range of parameters are described as a list or dictionary in the python file.

Then, the `experimentation_parameters.py` script generates all the dictionaries of parameters from this description made in the Python file.

Finally, all these dictionaries are stored in a pickle<fnref n="1" /> file: `parameters.pkl`.

### 4.2.2 Parameters for random system

The random systems are generated to be compared to systems corresponding to CICO problem modellings. Then, we first need to have the results of experiments containing the structure of the systems of equations to generate random systems.

When we get these results, to define the parameters of an experiment for a random ideal, we collect the ID, the field characteristic, the monomial order, the algorithm to compute the Gröbner basis, its options, and the seed of the experiment of the primitive we want to compare. Then we collect in the output of this experiment the structure of the system of equations.

The number of iterations of the experiments may be changed compared to the initial one in the primitive experiment.

## 4.3 Order of the experiments

The large number of experiments and the time taken by each of them make the full experimentation impossible to do without adding optimisations and timeouts.

To maximise the number of experiments performed, we developed a multithreading process that allows to use every core of the CPUs. Each core of the CPU executes the same script

<footnote n="1">¹Pickle is the file extension used to store Python data efficiently.</footnote>
`execute_experimentation.sh`. Then, this core accesses the `ids.txt` file, where a list of IDs is written.

We first notice that the number of rounds and the number of branches are two parameters whose increase leads to a longer computation time. Then we can skip an experiment if another one which only differs with a smaller number of rounds or branches has timed out. Then the full set of parameters to treat during the full experiment is sorted in lists. Parameters of the same list differ only by their number of rounds and branches. As IDs of experiments are sorted in a manner ensuring that consecutive experiments have the same parameters except the number of rounds and branches, a list is identified only by the ID of the first experiment in it. These IDs are stored in the `ids.txt` file.

Thus, the process of the core reads the first ID of the file, removes it and performs all the experiments of the corresponding list. A lock is used to avoid resource conflicts on the `ids.txt` file.

## 4.4 Generation of systems of equations

The generation of systems of equations depends on whether the system is a modelling of the CICO problem or if it is a random ideal for comparison.

For a primitive the system of equations is generated using the parameters given for the permutation and the modelling of the CICO problem. The modelling is coded in a Python file called for the generation of the system.

For the random ideal, we use the structure of the equation given as a parameter. This structure is composed of the variables, the maximal degree and the number of monomials in the polynomials of the system. To instantiate a system with the adequate structure for each polynomial, a list of 0 and 1 shuffled uniformly at random is created. Consider the set of monomials composed of variables and whose degree is less than the maximum degree given by the structure parameter. The list has the same size as this set. The number of 1 is the number of monomials. The polynomial is initialised to 0. Then using the monomial order the set of monomials described above is generated, and we read the list: if there is a 1 we draw at random a non-zero coefficient, multiply it by the monomial and add this term to the polynomial.

## 4.5 Lexicographic Gröbner basis and ideal degree

In the `cico_solve.py`, script three algorithms are performed.

**Compute the Gröbner basis** using the algorithm given and its options.

**Transform the basis** depending on the monomial order chosen at the previous step. If it is LEX then nothing is done, otherwise for the DRL order we have to apply an algorithm to change the order. The default one is used in this version.

**Compute the ideal degree** in case of shape position. The algorithm returns one of three 3 different outputs: the ideal is not of dimension 0, the ideal is not in shape position or the degree of the ideal.

## 4.6 Outputs

The outputs of an experiment is a dictionary of five keys. The first key is the structure of the system of equations generated. It is the same as the input for a random ideal. Then, the generation time of the system, the computation time of the Gröbner basis and the time taken by the term order
change algorithm are output. The last key corresponds to the ideal degree. As an experiment may be reproduced many times, the output is a list of dictionaries.

If the experiment goes to its end, the timings are output. However, the experiments may fail, be timed out or be skipped. This behaviour is output as well.

The outputs are stored in a file named i.pkl, where "i" is the actual ID of the experiment.

## 4.7 Reproducibility

The randomness is controlled by a seed that is the same for all the experiments. It makes the experiments more reliable, in the sense that the constants randomly generated are going to be the same in the primitive for a given sparsity. If the number of rounds is the only parameter evolving then every equation at a specific round is identical.

Reiterating the same experiment will not return the same exact system of equations, we put in place a function that changes the seed in a deterministic way depending on the number of reiteration.

Moreover, fixing the seed allows the full reproducibility of the experiments.

## 4.8 Modularity

New primitives and different modellings of the CICO problem are easy to add. It could be adapted to model other algebraically friendly problems.

We aim in a new version to make the term order change algorithm a parameter to choose as well. Experiments led on different term order change algorithms have been made by changing this parameter in the code source itself.

# 5 Results from experiments

This section presents the results and the observations made thanks to the framework developed. We also discuss the limitations encountered during the experiments.

The experiments have been performed on the largest range of parameters of the primitives and the CICO problem modellings. The timeout that limits the generation of equations is of 100 seconds and the one to compute the Gröbner basis for LEX order is of 20000 seconds. Algorithms studied are (using SageMath's name): "libsingular:groebner", "libsingular:std", "libsingular:slimgb", "libsingular:stdfglm", "libsingular:stdhilb", "magma:GroebnerBasis", "giac:gbasis", and "msolve". The four modellings and primitives studied are the ones introduced in Section 1.3. We only perform one time each experiment for the primitives and 10 times for the random ideals.

## 5.1 Libraries comparisons

Macaulay2 algorithms have not been studied. Early experiments have shown that all the Macaulay2 algorithms were slower than Singular algorithms. They are around 10 times slower. Then, we decided to not use them in larger experiments.

"libsingular:sba" (F5 implementation of Singular) logged many crashes that seem to occur in the library itself. This algorithm was only usable for small systems of equations. The experiments that didn't crash are not enough to get relevant results to estimate the efficiency of "sba".

Experiments have not been done while changing the set of options of "libsingular:std". It should be done as a future work to estimate if one heuristic set is more efficient on our systems of equations.

We first observed from these comparisons that the efficiency of the algorithms depends on the experiment performed. This remark is especially true for Zerolith. However, general trends have
emerged. “magma:GroebnerBasis” is usually the most efficient algorithm. “giac:gbasis”, and “msolve” are very efficient algorithms as well. Singular algorithms appear to be slower than the other ones. The results of one such experiment are given Figure 5, it corresponds to CICO-1 problem-solving using Freelunch modelling. The field characteristic is $2^{16} + 7$, the constant sparsity is 2, the number of branches is 2, and the monomial order is DRL.

<figure><img src="image_8.png" /><figcaption>Figure 5: Algorithms comparison for Freelunch modelling of Anemoi</figcaption></figure>

<table><caption>Table 1: Outputs for the Gröbner basis computation (columns are the number of rounds)</caption><thead><tr><th></th><th>6</th><th>7</th><th>8</th><th>9</th><th>10</th><th>11</th></tr></thead><tbody><tr><td>libsingular:groebner</td><td>W</td><td>T</td><td>S</td><td>S</td><td>S</td><td>S</td></tr><tr><td>libsingular:std</td><td>W</td><td>T</td><td>S</td><td>S</td><td>S</td><td>S</td></tr><tr><td>libsingular:slimgb</td><td>W</td><td>T</td><td>S</td><td>S</td><td>S</td><td>S</td></tr><tr><td>libsingular:stdfglm</td><td>W</td><td>T</td><td>S</td><td>S</td><td>S</td><td>S</td></tr><tr><td>libsingular:stdhilb</td><td>W</td><td>T</td><td>S</td><td>S</td><td>S</td><td>S</td></tr><tr><td>giac:gbasis</td><td>W</td><td>F</td><td>T</td><td>S</td><td>S</td><td>S</td></tr><tr><td>msolve</td><td>W</td><td>F</td><td>T</td><td>S</td><td>S</td><td>S</td></tr><tr><td>magma:GroebnerBasis</td><td>W</td><td>F</td><td>F</td><td>F</td><td>F</td><td>F</td></tr></tbody></table>

## 5.2 Monomial order heuristic

The main heuristic applied in algebraic attack is that computing the Gröbner basis for the DRL order and applying a term order change algorithm is more efficient than computing directly a basis for the LEX order. In these experiments, we aimed to check that if heuristic is indeed applicable to our systems.

First, we observed that this heuristic was not verified while using the Gröbner Walk algorithm. Thus, we used FGLM, to verify this heuristic. For very small scale versions of primitives it may happen that LEX order is more efficient. However, for these very reduced variants, the timings may not be relevant as the general system processes take a large proportion of the computation. If we compute directly the Gröbner basis for the LEX order, then only one algorithm is called, whereas two are called if we compute the basis for DRL order and then use FGLM. For variants with more rounds and branches (closer to the full-round version of the primitive), we observed that the heuristic is verified for all the primitives and modellings of the CICO problem studied. It confirms that a more specified algorithm such as FGLM for 0 dimensional ideal is more appropriate. SageMath proposes other algorithms to change the term order. They have not been studied from lack of time.

Moreover, it has been observed that FGLM computation is almost every time the bottleneck of the computation compared to the computation of the first Gröbner basis.

## 5.3 Constants' sparsity influence

The influence of the constants' sparsity is a key observation as it gives first results about the influence of the polynomials' sparsity on computation times. We observed that this sparsity has no clear pattern of influence on the computation times or the degree of the ideal. It happens that for specific sparsity the computations could be greatly quicker or slower than others. We have to
look further at this behaviour as it could be possible that specific constants make the permutation weak. A first experiment to do would be to add repetitions to evaluate the variance at this specific parameters to evaluate if this behaviour corresponds to the sparsity itself or a specific constant vector. Examples are given in Appendix F.1.

## 5.4 Random ideals and primitives comparisons

The main observation comes from the comparison between the systems of equations corresponding to an algebraic attack and the random structured systems. We noticed that the ideal degree of the systems of equations coming from the modelling are lower for our systems of equations than expected for a random system with an identical structure.

We computed 10 systems of equations with the same structure, and it always returned the same degree of the ideal. Then the monomials involved seem not to have an influence on this property with a high probability, the timings obtained have also very low variances. However, our systems have an ideal degree lower than expected and also led to quicker computation of the LEX basis. It may be explained for FGLM because the ideal degree is involved in its complexity. However, we don't have explanation for the computation of the Gröbner basis. Examples are given in Appendix F.2.

## 5.5 Limitations in the experiments

Many limitations have been encountered while running the experiments. Two of them are presented as they appear to be the most constraining.

### 5.5.1 SageMath wrapper

The default library for computing Gröbner bases is Singular. It has its own interface. For the other libraries, a wrapper is used to transform the SageMath objects into objects understood by the C/C++ libraries. In this conversion a function implemented in SageMath is PolynomialSequence. It transforms the polynomials returned by the libraries into SageMath polynomials. We observed that for a certain size of polynomials (the size meaning the number of monomials) the PolynomialSequence function crashes. Observing the logs of the libraries, we have noticed that the Gröbner basis is computed but could not be converted into a SageMath object. It is a huge limitation in the experiments. Indeed, all the algorithms from the Singular library are often the slowest but are not facing this issue. Other libraries are more efficient and can compute Gröbner basis for larger parameters however the bases are not returned to SageMath even though they have been computed.

In Table 1, we present this limitation. A column corresponds to a number of rounds. "W" means that the computation in SageMath of the basis worked, "T" means that it timed out, "S" it was skipped and "F" that it failed. Looking at the log files, we observed that the outputs "F" of "giac:gbasis" and "msolve" at round 7, and those of "magma:GroebnerBasis" at round 7 and 8 correspond to the crash presented.

### 5.5.2 Field characteristic

We limited experiments on prime finite field with characteristic up to $2^{31}$ due to the constraints of the libraries that are optimised for this range. However, the characteristic used by the primitives are often large or very large (more than $2^{64}$). Then the results obtained from the experiments can't be extrapolated to a real algebraic attack. The experiments on smaller finite fields aim to better understand the behaviour of algorithms on the structure of the polynomials, in this sense the characteristic has a negligible influence.
# 6 Conclusion

The first results obtained from the experiments performed raised new questions. First, new experiments have to be done to confirm some observations, mainly the influence of the sparsity of the constants in the computation time.

The experiments also gave results about the mathematical structure of the ideal corresponding to the algebraic attack. Indeed, we observed that the degree of the ideal is lower than expected. We should analyse these systems mathematically to understand what is the cause of that property.

Then, the implementation issues should be more studied, and we could try to fix them to take advantage of the efficiency of some libraries.

Finally, the framework developed could be used for new experiments aiming at studying more specific behaviour and also could be upgraded to new version to add a larger choice on the parameters.

# Acknowledgements

Experiments presented in this paper were carried out using the Grid'5000 testbed, supported by a scientific interest group hosted by Inria and including CNRS, RENATER and several Universities as well as other organizations (see https://www.grid5000.fr).

This work was supported by the European Research Council (ERC grant agreement no. 101041545 "ReSCALE").

Je rédige la suite de ces remerciements en français, ma langue maternelle, dans laquelle je m'exprime plus aisément.

Dans un premier temps, je souhaite remercier Anne Canteaut pour m'avoir fait découvrir la cryptographie symétrique lors de son cours et pour m'avoir mis en relation avec Léo Perrin. Ainsi, j'ai pu réaliser mon stage au sein de l'équipe COSMIQ au Centre INRIA de Paris.

Je remercie également mon maître de stage Léo Perrin, qui m'a accompagné avec bienveillance et précision. Ses conseils avisés et sa disponibilité ont été précieux et ont favorisé mon entrée dans le monde de la recherche. Avec Yann Rotella, ils m'ont proposé de poursuivre en thèse sous leurs directions. Je leur suis très reconnaissant de la confiance qu'ils m'accordent.

Je tiens également à remercier toutes les personnes qui ont contribué à la réussite de ce stage au sein de l'équipe COSMIQ. L'ambiance conviviale au sein du laboratoire encourage la curiosité scientifique.

Enfin, je remercie le rapporteur Monsieur Hieu Phan, que j'ai eu la chance d'avoir comme professeur d'algèbre générale à Telecom Paris, ainsi que les jurys Messieurs Jean Goubault-Larrecq et Christoph Dürr, pour l'évaluation de mon travail.

# References

[Bar04] Magali Bardet. *Étude des systèmes algébriques surdéterminés. Applications aux codes correcteurs et à la cryptographie*. PhD thesis, Pierre and Marie Curie University, Paris, France, 2004.

[BBC+23] Clémence Bouvier, Pierre Briaud, Pyrros Chaidos, Léo Perrin, Robin Salen, Vesselin Velichkov, and Danny Willems. New design techniques for efficient arithmetization-oriented hash functions: Anemoi permutations and jive compression mode. In *Annual International Cryptology Conference*, pages 507–539. Springer, 2023.
[BBL<sup>24</sup>] Augustin Bariant, Aurélien Boeuf, Axel Lemoine, Irati Manterola Ayala, Morten Øygarden, Léo Perrin, and Håvard Raddum. The algebraic freelunch: Efficient gröbner basis attacks against arithmetization-oriented primitives. In *Annual International Cryptology Conference*, pages 139–173. Springer, 2024.

[BBM<sup>22</sup>] Yuri A Blinkov, Rustam E Bayramov, and Mikhail D Malykh. Ginv: software for calculation of gröbner involutive basis. In *Polynomial Computer Algebra*, pages 13–15, 2022.

[BCP<sup>97</sup>] Wieb Bosma, John Cannon, and Catherine Playoust. The Magma algebra system. I. The user language. *J. Symbolic Comput.*, 24(3-4):235–265, 1997. Computational algebra and number theory (London, 1993).

[BES<sup>21</sup>] Jérémy Berthomieu, Christian Eder, and Mohab Safey El Din. msolve: A Library for Solving Polynomial Systems. In *2021 International Symposium on Symbolic and Algebraic Computation*, 46th International Symposium on Symbolic and Algebraic Computation, pages 51–58, Saint Petersburg, Russia, July 2021. ACM.

[Bri<sup>10</sup>] Michael Brickenstein. Slimgb: Gröbner bases with slim polynomials. *Revista Matemática Complutense*, 23:453–466, 2010.

[Buc<sup>06</sup>] Bruno Buchberger. Bruno buchberger’s phd thesis 1965: An algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal. *J. Symb. Comput.*, 41(3-4):475–511, 2006.

[CKM<sup>97</sup>] Stéphane Collart, Michael Kalkbrener, and Daniel Mall. Converting bases with the gröbner walk. *J. Symb. Comput.*, 24(3/4):465–469, 1997.

[CLO<sup>97</sup>] David A. Cox, John Little, and Donal O’Shea. *Ideals, varieties, and algorithms - an introduction to computational algebraic geometry and commutative algebra* (2. ed.). Undergraduate texts in mathematics. Springer, 1997.

[DGPS<sup>25</sup>] Wolfram Decker, Gert-Martin Greuel, Gerhard Pfister, and Hans Schönemann. SINGULAR 4-4-1 — A computer algebra system for polynomial computations. http://www.singular.uni-kl.de, 2025.

[Ede<sup>14</sup>] Christian Eder. Signature-based gröbner basis algorithms in singular. *EACA 2014*, page 101, 2014.

[EF<sup>17</sup>] Christian Eder and Jean-Charles Faugère. A survey on signature-based algorithms for computing gröbner bases. *J. Symb. Comput.*, 80:719–784, 2017.

[Fau<sup>99</sup>] Jean-Charles Faugère. A new efficient algorithm for computing gröbner bases (f4). *Journal of pure and applied algebra*, 139(1-3):61–88, 1999.

[Fau<sup>02</sup>] Jean Charles Faugère. A new efficient algorithm for computing gröbner bases without reduction to zero (f 5). In *Proceedings of the 2002 international symposium on Symbolic and algebraic computation*, pages 75–83, 2002.

[FGLM<sup>93</sup>] Jean-Charles Faugère, Patrizia M. Gianni, Daniel Lazard, and Teo Mora. Efficient computation of zero-dimensional gröbner bases by change of ordering. *J. Symb. Comput.*, 16(4):329–344, 1993.
[FM17] Jean-Charles Faugère and Chenqi Mou. Sparse FGLM algorithms. *J. Symb. Comput.*, 80:538–569, 2017.

[GGM$^{+94}$] Hubert Grassmann, Gert-Martin Greuel, Bernd Martin, Wolfgang Neumann, Gerhard Pfister, Wilfred Pohl, Hans Schönemann, and Thomas Siebert. *Standard bases, syzygies and their implementation in SINGULAR*. Universität Kaiserslautern. Fachbereich Mathematik, 1994.

[GHR$^{+23}$] Lorenzo Grassi, Yonglin Hao, Christian Rechberger, Markus Schofnegger, Roman Walch, and Qingju Wang. Horst meets fluid-spn: Griffin for zero-knowledge applications. In Helena Handschuh and Anna Lysyanskaya, editors, *Advances in Cryptology - CRYPTO 2023 - 43rd Annual International Cryptology Conference, CRYPTO 2023, Santa Barbara, CA, USA, August 20-24, 2023, Proceedings, Part III*, volume 14083 of *Lecture Notes in Computer Science*, pages 573–606. Springer, 2023.

[GKL$^{+24}$] Lorenzo Grassi, Dmitry Khovratovich, Reinhard Lüftenegger, Christian Rechberger, Markus Schofnegger, and Roman Walch. Monolith: Circuit-friendly hash functions with new nonlinear layers for fast and constant-time implementations. *IACR Trans. Symmetric Cryptol.*, 2024(3):44–83, 2024.

[GM88] Rüdiger Gebauer and H. Michael Möller. On an installation of buchberger's algorithm. *J. Symb. Comput.*, 6(2/3):275–286, 1988.

[GMN$^{+91}$] Alessandro Giovini, Teo Mora, Gianfranco Niesi, Lorenzo Robbiano, and Carlo Traverso. "one sugar cube, please" or selection strategies in the buchberger algorithm. In Stephen M. Watt, editor, *Proceedings of the 1991 International Symposium on Symbolic and Algebraic Computation, ISSAC '91, Bonn, Germany, July 15-17, 1991*, pages 49–54. ACM, 1991.

[Jea16] Jérémy Jean. TikZ for Cryptographers. https://www.iacr.org/authors/tikz/, 2016.

[KLR24] Katharina Koschatko, Reinhard Lüftenegger, and Christian Rechberger. Exploring the six worlds of gröbner basis cryptanalysis: Application to anemoi. *IACR Cryptol. ePrint Arch.*, page 250, 2024.

[Par18] B. Parisse. Algorithmes de calcul formel et numérique, 2018.

[PG24] Bernard Parisse and Renée De Graeve. Giac/xcas, version 1.9.0. https://www-fourier.univ-grenoble-alpes.fr/~parisse/giac.html, 2024. Accessed: 2025-08-12.

[PZ22] Sonja Petrović and Shahrzad Zelenberg. Threaded gröbner bases: a macaulay2 package. *Journal of Software for Algebra and Geometry*, 11(1):123–127, 2022.

[RS12] Bjarke Hammersholt Roune and Michael Eugene Stillman. Practical gröbner basis computation. In Joris van der Hoeven and Mark van Hoeij, editors, *International Symposium on Symbolic and Algebraic Computation, ISSAC'12, Grenoble, France - July 22 - 25, 2012*, pages 203–210. ACM, 2012.

[Spa12] Pierre-Jean Spaenlehauer. *Solving multi-homogeneous and determinantal systems: algorithms, complexity, applications*. (Résolution de systèmes multi-homogènes et déterminants : algorithmes, complexité, applications). PhD thesis, Pierre and Marie Curie University, Paris, France, 2012.
[SS21] Jan Ferdinand Sauer and Alan Szepieniec. Sok: Gröbner basis algorithms for arithmetization oriented ciphers. *IACR Cryptol. ePrint Arch.*, page 870, 2021.

[TES] Amelia Taylor, David Eisenbud, and Mike Stillman. IntegralClosure: A *Macaulay2* package. Version 1.0. A *Macaulay2* package available at https://github.com/Macaulay2/M2/tree/master/M2/Macaulay2/packages.

[Yan98] Thomas Yan. The geobucket data structure for polynomials. *J. Symb. Comput.*, 25(3):285–293, 1998.

# A Uniqueness of the reduced Gröbner basis

The definition and the theorem given are taken from [CLO97, Chapter 2, Section 7].

**Definition A.1.** A reduced Gröbner basis for a polynomial ideal $I$ is a Gröbner basis $G$ for $I$ such that:

(i) $\mathrm{LC}(p) = 1$ for all $p \in G$.

(ii) For all $p \in G$, no monomial of $p$ lies in $\langle \mathrm{LT}(G \setminus \{p\}) \rangle$.

**Theorem A.1.** Let $I = \{0\}$ be a polynomial ideal. Then, for a given monomial ordering, $I$ has a reduced Gröbner basis, and the reduced Gröbner basis is unique.

# B Division algorithm in multivariate polynomial ring

The multivariate division algorithm is introduced in [CLO97, Chapter 2, Section 3, Theorem 3]. We use it in the reduction of the S-polynomials in the Buchberger’s algorithm.

The result of this algorithm depends on the order of $(f_1, \dots, f_s)$. However, using Gröbner makes it independent.

**Proposition B.1** ([CLO97], Chapter 2, Section 6, Proposition 1).

Let $I \subseteq k[x_1, \dots, x_n]$ be an ideal, and let $G = \{g_1, \dots, g_t\}$ be a Gröbner basis for $I$. Then, for any $f \in k[x_1, \dots, x_n]$, there exists a unique $r \in k[x_1, \dots, x_n]$ with the following two properties:

(i) No term of $r$ is divisible by any of the leading terms $\mathrm{LT}(g_1), \dots, \mathrm{LT}(g_t)$.

(ii) There exists $g \in I$ such that $f = g + r$.

In particular, $r$ is the remainder on division of $f$ by $G$, regardless of the order in which the elements of $G$ are listed when using the division algorithm.

# C FGLM algorithm

This section presents the FGLM algorithm. This algorithm has known many improvements over the last year. Algorithm 3 presents the main idea without any optimisations. This algorithm is the one introduced in [SS21, Section 4.1].

$\prec_{\mathrm{old}}$ is the monomial order for which we have a Gröbner basis and $G_{\mathrm{old}}$ is the basis.

$\prec_{\mathrm{new}}$ is the new monomial order for which we want the Gröbner basis.

*dict* is a dictionary that as for keys the monomials and as values the reduction of the monomials by $G_{\mathrm{old}}$.

The output $G_{\mathrm{new}}$ is the Gröbner basis for $\prec_{\mathrm{new}}$.
**Algorithm 2** Multivariate polynomial of $f$ by $(f_1, \dots, f_s)$

Require: $f_1, \dots, f_s, f$

Ensure: $q_1, \dots, q_s, r$ such that $f = q_1f_1 + \dots + q_sf_s + r$

1: $q_1 := 0, \dots, q_s := 0, r := 0$

2: $p := f$

3: **while** $p \neq 0$ **do**

4: &nbsp;&nbsp;&nbsp;&nbsp; $i := 1$

5: &nbsp;&nbsp;&nbsp;&nbsp; divisionoccurred := false

6: &nbsp;&nbsp;&nbsp;&nbsp; **while** $i \leq s$ divisionoccurred = false **do**

7: &nbsp;&nbsp;&nbsp;&nbsp; **if** $\text{LT}(f_i)$ divide $\text{LT}(p)$ **then**

8: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $q_i := q_i + \frac{\text{LT}(p)}{\text{LT}(f_i)}$

9: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $p := p - \left( \frac{\text{LT}(p)}{\text{LT}(f_i)} \right) f_i$

10: &nbsp;&nbsp;&nbsp;&nbsp; divisionoccurred := true

11: &nbsp;&nbsp;&nbsp;&nbsp; **else**

12: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $i := i + 1$

13: &nbsp;&nbsp;&nbsp;&nbsp; **end if**

14: &nbsp;&nbsp;&nbsp;&nbsp; **end while**

15: &nbsp;&nbsp;&nbsp;&nbsp; **if** divisionoccurred = false **then**

16: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $r := r + \text{LT}(p)$

17: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $p := p - \text{LT}(p)$

18: &nbsp;&nbsp;&nbsp;&nbsp; **end if**

19: &nbsp;&nbsp;&nbsp;&nbsp; **end while**

20: &nbsp;&nbsp;&nbsp;&nbsp; **return** $q_1, \dots, q_s, r$

**Algorithm 3** FGLM

Require: $\prec_{\text{new}}, G_{\text{old}}, \prec_{\text{old}}$

Ensure: $G_{\text{new}}$

1: $\text{dict} \leftarrow \emptyset$

2: $G_{\text{new}} \leftarrow \emptyset$

3: $\text{next\_monoms} \leftarrow \{1\}$

4: **while** $\text{next\_monoms} \neq \emptyset$ **do**

5: &nbsp;&nbsp;&nbsp;&nbsp; monom $\leftarrow \text{min}_{\prec_{\text{new}}} (\text{next\_monoms})$

6: &nbsp;&nbsp;&nbsp;&nbsp; $\text{next\_monoms} \leftarrow \text{next\_monoms} \setminus \{\text{monom}\}$

7: &nbsp;&nbsp;&nbsp;&nbsp; **if** there is no $g \in G_{\text{new}}$ such that $\text{LM}_{\prec_{\text{new}}}(g)$ divides monom **then**

8: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; reduced\_monom $\leftarrow$ full reduction of monom by $G_{\text{old}}$

9: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; **if** reduced\_monom + $\sum_{\nu \in \text{dict}} \omega_{\nu} \cdot \text{value}(\nu) = 0$ for some $\omega_{\nu} \in \mathbb{F}_p$ **then**

10: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $G_{\text{new}} \leftarrow G_{\text{new}} \cup \{\text{monom} + \sum_{\nu \in \text{dict}} \omega_{\nu} \cdot \nu\}$

11: &nbsp;&nbsp;&nbsp;&nbsp; **else**

12: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $\text{dict} \leftarrow \text{dict} \cup \{\text{monom} : \text{reduced\_monom}\}$

13: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $\text{next\_monoms} \leftarrow \text{next\_monoms} \cup \{x_i \cdot \text{monom} \mid i \in \{0, \dots, n-1\}\}$

14: &nbsp;&nbsp;&nbsp;&nbsp; **end if**

15: &nbsp;&nbsp;&nbsp;&nbsp; **end if**

16: &nbsp;&nbsp;&nbsp;&nbsp; **end while**

17: &nbsp;&nbsp;&nbsp;&nbsp; **return** $G_{\text{new}}$
# D Number of solutions of CICO problem depending on modelling

Let's compute the probability to get solution(s) to CICO problem following the modelling of introducing round variables. The input of the permutation chosen is

$$ (0, \dots, 0, \sum_{i=0}^{n-1} \alpha_i^0 \times X_i, \dots, \sum_{i=0}^{n-1} \alpha_i^{t-n+1} \times X_i) $$

Let's first compute the average number of solutions. The probability of getting a solution of CICO-n problem for a given input is $\frac{1}{p^n}$. Indeed, as the function is a permutation, the output is uniformly distributed over the codomain. Then the probability to get the first n coordinates equal to 0 is $\frac{1}{p^n}$. The cardinal of the domain we use is $p^n$. Finally, the average number of solutions we get is 1, as every draw is independent.

As the draws are independent, we can model the probability to get k solutions in a Poisson distribution. Then the probability is $P(k) = \frac{\lambda^k}{k!} \times e^{-\lambda}$ and using $\lambda = 1$, $P(k \neq 0) = 1 - e^{-1}$.

# E Libraries description

## E.1 Singular

### E.1.1 std

**Algorithm** The description of "std" made in this part is based on [GGM+94]. It is the standard algorithm to compute Gröbner bases, which is a more general implementation of the well ordering Buchberger's algorithm. It allows computing bases for semigroup ordering, which is not a case interesting for us. We restrict us to the well-ordering on monomials, which corresponds to usual ordering (LEX, DRL, ...).

It computes the unique reduced Gröbner basis. Many heuristics have been added to the original Buchberger's algorithm.

* After generating the set of S-polynomials, the first idea is to detect the pairs that lead to a 0 reduction. Buchberger gave two criteria usually referenced as the chain criterion and the coprime criterion. The optimal way to implement them is presented in [GM88].

* After removing, the useless S-polynomials, the choice of order to reduce S-polynomials is crucial for time complexity. "std" relies on two strategies: the normal strategy and the "sugar" strategy.

* Another choice left free in the Buchberger's algorithm is the order of the reducers of the S-polynomial (the set T in the specification). There are also two strategies: the normal strategy and the sugar strategy.

**Singular documentation and options** The procedure in Singular is "std". Information is provided in the documentation. The first argument given is the ideal for which we need to compute a Gröbner basis. Many others arguments may be given, mainly related to the Hilbert serie that may help the computation of the Gröbner basis.
### E.1.2 slimgb

**Algorithm** "slimgb" is also a variation of the Buchberger's algorithm. It uses many ideas from the F4 algorithm. It is designed to keep the coefficients and polynomials small. The algorithm is described in [Bri10]. The termination and correctness of the algorithm are proved. We present the idea used in this algorithm to improve the time and space complexities.

* The parallel reduction is one of the idea taken from F4. The procedure slimgbReduce reduces many S-polynomials in one step. However, it is different from F4 because it doesn't use linear algebra. In [Bri10, Section 3.5], the three operations that may be applied to a set of S-polynomials are introduced. The two first operate in the same way that the Gaussian reduction. Indeed, we reduce the S-polynomials using the input polynomials but also the S-polynomials themselves.

* The control of the size of the coefficients and polynomials. The notion of weighted length on polynomials is introduced. It allows comparisons of polynomials. This notion is used in the third operation. Usually, the input set F is not modified through the computation. But in this procedure, if one of the pair is found with the same leading monomial and is smaller (using weighted length) than an input polynomial, the pair takes the place of the input polynomial in the list of inputs.

**Singular documentation and options** The procedure in Singular is "slimgb". Information is provided in the documentation. The procedure takes as input the ideal for which we need to compute the Gröbner basis. No additional arguments may be given to the procedure. The monomial order has to be global, what fits with our use case.

The code source of this procedure is available in the files tgb.cc and tgbgauss.cc of the code source.

### E.1.3 sba

**Algorithm** This algorithm is based on the algorithm F5. Since the first release of this algorithm by Jean-Charles Faugère, many signature-based algorithms have been proposed. sba variations are presented in [Ede14]. The correctness of this algorithm is guaranteed for global orderings.

**Singular documentation and options** The procedure in Singular is "sba". Information is provided in the documentation. The procedure takes as input the ideal for which we need to compute the Gröbner basis. Two other optional arguments may be given. It is related to the orderings that are involved in the F5 algorithm implemented. It is advised that the DRL order should be prioritised as this algorithm may be slow for the LEX order.

The code source of this procedure is available in the file f5gb.cc.

### E.1.4 stdfglm

**Algorithm** This algorithm uses the FGLM algorithm to compute a Gröbner basis. This function may take two arguments. First the ideal for which, we want to compute a Gröbner basis and optionally, the ordering used to compute the first basis. If the second argument is not given then the DRL order is used. The first basis is computed by "groebner". It may be specified to use "std" or "slimgb".
**Singular documentation and options** The procedure in Singular is “stdfglm”. Information is provided in the documentation. The ideal must be of dimension 0 and the monomial ordering chosen must be global.

### E.1.5 stdhilb

**Algorithm** This algorithm uses the Hilbert driven Gröbner basis algorithm. It relies on the computation of the Gröbner basis of the homogenised polynomials and the Hilbert function, which is a function that describes the ideal.

**Singular documentation and options** The procedure in Singular is “stdhilb”. Information is provided in the documentation.

### E.1.6 groebner

The general procedure in Singular is “groebner”. It takes as input an ideal or a module and returns the Gröbner basis. Information is provided in the documentation. This procedure is global and gives access to different strategies and algorithms to compute a Gröbner basis.

### E.1.7 Set of options and Sagemath interface

Sagemath proposes an interface to access the set of options of Singular. This interface is described in the Sagemath documentation. Here is the list of options that may be useful in our case: prot, intStrategy, lazy, length, notSugar, notBuckets, redSB, redTail, redThrough, sugarCrit, cancelunit and contentSB.

### E.1.8 Global remarks

For the current implementations the characteristic of a prime field must be less or equal than $2^{32} - 1$. The polynomial representation used by “std” and “sba” is the Geobucket data structure introduced in [Yan98].

## E.2 Macaulay2

### E.2.1 Multithreading

Another way of speeding up the Buchberger's algorithm is to take advantage of many CPUs to share the computing load between different units. A package for Macaulay2 offers a multithreaded version of Buchberger's algorithm [PZ22]. When this article was released, the package was not integrated in the engine core of Macaulay2. However, during our experiments, we observed that multithreading was used by the function “gb”.

### E.2.2 Options in Macaulay2 and interfaces with Sagemath

The algorithm “gb” have many options proposed which mainly come from different heuristics proposed for the Buchberger's algorithm. Due to the experimental results obtained using the Macaulay2 library in Section 5.1 we don't describe these options.
## E.3 Giac

### E.3.1 gbasis

**Characteristic 0** A special algorithm is implemented for the case of characteristic 0. It allows computing more efficiently a probabilistic Gröbner basis. It is not presented as it is not relevant in our case.

**Giac documentation and options** The documentation of "gbasis" gives information about the procedure. The implementation of the Gröbner basis algorithm is on github. First, the Cocoa implementation was used to compute a Gröbner basis. Now, Giac uses a standalone implementation. According to the documentation, it still is possible to use the Cocoa implementation, and even the F5 implementation of Cocoa.

### E.3.2 Sagemath interface

Sagemath allows using the algorithm "gbasis" to compute Gröbner bases. The wrapper describes the inputs of the procedure `groebner_basis` when "giac:gbasis" is used.

* `gens` is the set of generators of the ideal from which we want a Gröbner basis

* `proba epsilon` (optional) is only relevant in the characteristic 0 case

* `threads` (optional) is only relevant in the characteristic 0 case

* `prot` (optional), is `False` by default, allows getting information about the computation process.

* `elim_variables`, not used in our case. It allows computing the Gröbner basis for the elimination ideal.

## F Examples of results from the experiments

### F.1 Constants' sparsity influence

<figure><img src="image_9.png" /><figcaption>Figure 6: Comparisons of LEX Gröbner basis computation for Zerolith permutation using CICO modelling from Section 6</figcaption></figure>

<figure><img src="image_10.png" /><figcaption>Figure 7: Comparisons of LEX Gröbner basis computation for Griffin permutation using CICO modelling from Section 7</figcaption></figure>
The parameters used for Figure 6 are 6 rounds, 4 branches, $2^{16}+7$ for the field characteristic, and the algorithm is "libsingular:groebner". We solve a CICO-2 problem. The ideal degree is constant for every constants' sparsity, it is 1024.

The parameters used for Figure 7 are 2 rounds, 4 branches, $2^{16}+7$ for the field characteristic, and the algorithm is "giac:gbasis". We solve a CICO-1 problem. The ideal degree is constant for every constants' sparsity, it is 441.

We insist on the fact that no pattern has been found for the sparsity influence. Other results gave that the sparsity could make the computation slower or quicker. Then, we have to perform other experiments with more repetition of the same experiment to decide whether a specific constant vector is responsible or the sparsity itself.

## F.2 Ideal degree comparisons

<figure><img src="image_11.png" /><figcaption>Figure 8: Comparisons of LEX Gröbner basis computation for Anemoi permutation using CICO modelling from Section 1.3.2 (Round variables) and random ideals with the same structure</figcaption></figure>

<figure><img src="image_12.png" /><figcaption>Figure 9: Comparisons of LEX Gröbner basis computation for Anemoi permutation using CICO modelling from Section 1.3.2 (Freelunch) and random ideals with the same structure</figcaption></figure>

The parameters used for Figure 8 are 2 branches, 0 for the constants' sparsity, $2^{16}+7$ for the field characteristic, and the algorithm is "libsingular:slimgb". We solve a CICO-1 problem. The ideal degree is $5^r$ for Anemoi and $9^r$ for the random ideals, where $r$ is the number of rounds.

The parameters used for Figure 9 are 2 branches, 2 for the constants' sparsity, $2^{16}+7$ for the field characteristic, and the algorithm is "magma:GroebnerBasis". We solve a CICO-1 problem. The ideal degree is $5^r$ for Anemoi and $6^r$ for the random ideals, where $r$ is the number of rounds.