# What happens when you *don't* have tools? The case of algebraic cryptanalysis

Léo Perrin

► To cite this version:

Léo Perrin. What happens when you *don't* have tools? The case of algebraic cryptanalysis. SKCAM 2025 - Workshop on Symmetric-key Cryptanalysis Automation and Modelling, Mar 2025, Rome, Italy. hal-05467908

HAL Id: hal-05467908

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

Submitted on 20 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_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
What happens when you don't have tools?
The case of algebraic cryptanalysis

Léo Perrin¹

¹Inria, France

March 15, 2025
In this Presentation

A tool is a convenient abstraction layer above a specific know-how.
In this Presentation

A tool is a convenient abstraction layer above a specific know-how.

This comes **not** from my satisfaction with some tools...
In this Presentation

A tool is a convenient abstraction layer above a specific know-how.

This comes **not** from my satisfaction with some tools...

... but from their absence*!

* at least at the time when it happened
## Outline

1. Algebraic Attacks: a Case Study

2. What is a Tool?

3. Conclusion
# Plan of this Section

1. Algebraic Attacks: a Case Study

2. What is a Tool?

3. Conclusion
# Plan of this Section

## 1 Algebraic Attacks: a Case Study

- Symmetric Techniques for Advanced Protocols

- (Multivariate) Root Finding Attacks

- What Have We Learnt?

## 2 What is a Tool?

## 3 Conclusion
Securing Data

Usually, we secure **data** (at rest or in transit).

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

Usually, we secure **data** (at rest or in transit).

<figure><img src="image_3.png" /></figure>
Securing Data

Usually, we secure **data** (at rest or in transit).

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

Envelope: **Confidentiality**
(nobody can read it)

Seal: **Integrity**
(nobody can modify it)
# Securing Data

Usually, we secure **data** (at rest or in transit).

Envelope: **Confidentiality**
(nobody can read it)

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

Paul

Seal: **Integrity**
(nobody can modify it)

Signature: **Authentication**

(it was written by the right person)
Securing Computation

More and more protocols intend to secure computations.

FHE Fully Homomorphic Encryption

MPC Multi Party Computations

ZK-* Zero Knowledge- [ proof, argument... ]
Securing Computation

More and more protocols intend to secure computations.

FHE Fully Homomorphic Encryption

MPC Multi Party Computations

ZK-* Zero Knowledge- [ proof, argument... ]

These need (many) different types of symmetric primitives internally, and these are often
"Arithmetization-Oriented".
# What is Arithmetization?

"Arithmetization" depends on the subtleties of the **protocol** you work with!
# What is Arithmetization?

"Arithmetization" depends on the subtleties of the **protocol** you work with!

Example: Verifying if $y = c(ax + b)^{10} + x$ in R1CS

1. $t_0 = ax$

2. $t_1 = t_0 + b$

3. $t_2 = t_1 \times t_1$

4. $t_3 = t_2 \times t_2$

5. $t_4 = t_3 \times t_3$

6. $t_5 = t_2 \times t_4$

7. $t_6 = ct_5$

8. $y = t_6 + x$
# What is Arithmetization?

"Arithmetization" depends on the subtleties of the **protocol** you work with!

Example: Verifying if $y = c(ax + b)^{10} + x$ in R1CS

1. $t_0 = ax$

2. $t_1 = t_0 + b$

3. $t_2 = t_1 \times t_1$

4. $t_3 = t_2 \times t_2$

5. $t_4 = t_3 \times t_3$

6. $t_5 = t_2 \times t_4$

7. $t_6 = ct_5$

8. $y = t_6 + x$
# What is Arithmetization?

"Arithmetization" depends on the subtleties of the **protocol** you work with!

Example: Verifying if $y = c(ax + b)^{10} + x$ in R1CS

1. $t_0 = ax$

2. $t_1 = t_0 + b$

3. $t_2 = t_1 \times t_1$

4. $t_3 = t_2 \times t_2$

5. $t_4 = t_3 \times t_3$

6. $t_5 = t_2 \times t_4$

7. $t_6 = ct_5$

8. $y = t_6 + x$

This verification costs **R1CS 4 constants**
# What is Arithmetization?

"Arithmetization" depends on the subtleties of the **protocol** you work with!

Example: Verifying if $y = c(ax + b)^{10} + x$ in R1CS

1. $t_0 = ax$

2. $t_1 = t_0 + b$

3. $t_2 = t_1 \times t_1$

4. $t_3 = t_2 \times t_2$

5. $t_4 = t_3 \times t_3$

6. $t_5 = t_2 \times t_4$

7. $t_6 = ct_5$

8. $y = t_6 + x$

This verification costs R1CS 4 constants

- How to turn a computation into an arithmetic circuit depends on the operations allowed

- Its cost is also arithmetization-dependent—though low degree is usually welcome!
Symmetric Techniques for Advanced Protocols

MPC

FHE

ZK
Symmetric Techniques for Advanced Protocols

<table><thead><tr><th>MPC</th><th>FHE</th><th>ZK</th></tr></thead><tbody><tr><td>Masking</td><td>BGV</td><td>R1CS</td></tr><tr><td>MPC-in-the-head<br>(signatures...)</td><td>FV</td><td>AIR<br>...</td></tr><tr><td>PCF</td><td>TFHE</td><td>Plonk</td></tr><tr><td>VDF</td><td></td><td></td></tr></tbody></table>
Symmetric Techniques for Advanced Protocols

<table><thead><tr><th>MPC</th><th>FHE</th><th>ZK</th></tr></thead><tbody><tr><td colspan="3" style="text-align: center;">Arithmetization-Oriented</td></tr><tr><td>Masking</td><td>BGV</td><td>R1CS</td></tr><tr><td>MPC-in-the-head<br>(signatures...)</td><td>FV</td><td>AIR<br>...</td></tr><tr><td>PCF</td><td>TFHE</td><td>Plonk</td></tr><tr><td>VDF</td><td></td><td></td></tr></tbody></table>
Symmetric Techniques for Advanced Protocols

<figure><img src="image_6.png" /></figure>
Symmetric Techniques for Advanced Protocols

<figure><img src="image_7.png" /></figure>
# Symmetric Techniques for Advanced Protocols

<figure><img src="image_8.png" /></figure>
Symmetric Techniques for Advanced Protocols

<figure><img src="image_9.png" /></figure>
Symmetric Techniques for Advanced Protocols

<figure><img src="image_10.png" /></figure>
# Symmetric Techniques for Advanced Protocols

<figure><img src="image_11.png" /></figure>
Symmetric Techniques for Advanced Protocols

<figure><img src="image_12.png" /></figure>
Symmetric Techniques for Advanced Protocols

<figure><img src="image_13.png" /></figure>
Symmetric Techniques for Advanced Protocols

<figure><img src="image_14.png" /></figure>
# Symmetric Techniques for Advanced Protocols

<figure><img src="image_15.png" /></figure>
# Symmetric Techniques for Advanced Protocols

<figure><img src="image_16.png" /></figure>
# Symmetric Techniques for Advanced Protocols

<figure><img src="image_17.png" /></figure>
# Arithmetization-Orientated Designs

## What AO Often Means

The **evaluation** or the **verification** of the subfunctions involved must correspond to an arithmetic circuit with a **low number of multiplications**.
# Arithmetization-Orientated Designs

## What AO Often Means

The **evaluation** or the **verification** of the subfunctions involved must correspond to an arithmetic circuit with a **low number of multiplications**.

Disclaimer: *this is a massive over simplification*
# Arithmetization-Orientated Designs

## What AO Often Means

The **evaluation** or the **verification** of the subfunctions involved must correspond to an arithmetic circuit with a **low number of multiplications**.

Disclaimer: *this is a massive over simplification*

* Use of $x \mapsto x^d$, d "small"

* Big diffusion matrices

* For verif., $x \mapsto x^{1/d}$, d "small"
# Arithmetization-Orientated Designs

## What AO Often Means

The **evaluation** or the **verification** of the subfunctions involved must correspond to an arithmetic circuit with a **low number of multiplications**.

Disclaimer: *this is a massive over simplification*

* Use of $x \mapsto x^d$, d "small"

* Big diffusion matrices

* For verif., $x \mapsto x^{1/d}$, d "small"

## Example: Griffin

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

Source: PhD thesis of C. Bouvier, *Cryptanalysis and design of symmetric primitives*
*defined over large finite fields*
# Plan of this Section

## 1 Algebraic Attacks: a Case Study

- Symmetric Techniques for Advanced Protocols

- (Multivariate) Root Finding Attacks

- What Have We Learnt?

## 2 What is a Tool?

## 3 Conclusion
# Vulnerability to Algebraic Attacks

## Arithmetization-Oriented Verification
# Vulnerability to Algebraic Attacks

## Arithmetization-Oriented Verification

There must exist low degree arithmetic circuits that the successive internal states must satisfy.
# Vulnerability to Algebraic Attacks

## Arithmetization-Oriented Verification

There must exist low degree arithmetic circuits that the successive internal states must satisfy.

## Vulnerability to Algebraic Attacks
# Vulnerability to Algebraic Attacks

## Arithmetization-Oriented Verification

There must exist low degree arithmetic circuits that the successive internal states must satisfy.

## Vulnerability to Algebraic Attacks

There must exist a system of low degree equations that models an evaluation of the primitive.
# Vulnerability to Algebraic Attacks

## Arithmetization-Oriented Verification

There must exist low degree arithmetic circuits that the successive internal states must satisfy.

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

## Vulnerability to Algebraic Attacks

There must exist a system of low degree equations that models an evaluation of the primitive.
# Vulnerability to Algebraic Attacks

## Arithmetization-Oriented Verification

There must exist low degree arithmetic circuits that the successive internal states must satisfy.

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

## Vulnerability to Algebraic Attacks

There must exist a system of low degree equations that models an evaluation of the primitive.

> Enabling a low degree arithmetization of verification implies a potential vulnerability to algebraic attacks!!
# Generic System Solving: Steps and Tools

$$ \left\{ \begin{array}{l} p_1(x_1, \dots, x_N) = 0 \\ \vdots \\ p_{k-1}(x_1, \dots, x_N) = 0 \\ p_k(x_1, \dots, x_N) = 0 \end{array} \right. $$

## 1. Define system

## The Tools Used

**SAGE** Open source, mostly reliable...
# Generic System Solving: Steps and Tools

$$ 
\left\{ 
\begin{array}{l}
p_1(x_1, \dots, x_N) = 0 \\
\vdots \\
p_{k-1}(x_1, \dots, x_N) = 0 \\
p_k(x_1, \dots, x_N) = 0
\end{array}
\right. 
$$

## 1. Define system

## The Tools Used

**SAGE** Open source, mostly reliable... but slooow
# Generic System Solving: Steps and Tools

$$ \left\{ \begin{array}{l} p_1(x_1, \dots, x_N) = 0 \\ \vdots \\ p_{k-1}(x_1, \dots, x_N) = 0 \\ p_k(x_1, \dots, x_N) = 0 \end{array} \right. \qquad \left\{ \begin{array}{l} g_1(x_1, \dots, x_N) = 0 \\ \vdots \\ g_{k-1}(x_1, \dots, x_N) = 0 \\ g_k(x_1, \dots, x_N) = 0 \end{array} \right. $$

1. Define system

2. Find a GB (F4/F5)

## The Tools Used

**SAGE** Open source, mostly reliable... but slooow

**F4/F5** What makes it possible...
# Generic System Solving: Steps and Tools

$$ \begin{cases} p_1(x_1, \dots, x_N) = 0 \\ \vdots \\ p_{k-1}(x_1, \dots, x_N) = 0 \\ p_k(x_1, \dots, x_N) = 0 \end{cases} \quad \begin{cases} g_1(x_1, \dots, x_N) = 0 \\ \vdots \\ g_{\kappa-1}(x_1, \dots, x_N) = 0 \\ g_{\kappa}(x_1, \dots, x_N) = 0 \end{cases} $$

1. Define system

2. Find a GB (F4/F5)

## The Tools Used

**SAGE** Open source, mostly reliable... but slooooow

**F4/F5** What makes it possible...but Open source implementations hard to find, big difference in efficiency between public/proprietary implementations.
# Generic System Solving: Steps and Tools

$$ 
\left\{ 
\begin{array}{l} 
p_1(x_1, \dots, x_N) = 0 \\ 
\vdots \\ 
p_{k-1}(x_1, \dots, x_N) = 0 \\ 
p_k(x_1, \dots, x_N) = 0 
\end{array} 
\right. 
\quad 
\left\{ 
\begin{array}{l} 
g_1(x_1, \dots, x_N) = 0 \\ 
\vdots \\ 
g_{k-1}(x_1, \dots, x_N) = 0 \\ 
g_k(x_1, \dots, x_N) = 0 
\end{array} 
\right. 
$$

1. Define system

2. Find a GB (F4/F5)

## The Tools Used

**SAGE** Open source, mostly reliable... but slooooow

**F4/F5** What makes it possible...but Open source implementations hard to find, big difference in efficiency between public/proprietary implementations.

but things are getting better!
# Generic System Solving: Steps and Tools

$$ \begin{cases} p_1(x_1, \dots, x_N) = 0 \\ \vdots \\ p_{k-1}(x_1, \dots, x_N) = 0 \\ p_k(x_1, \dots, x_N) = 0 \end{cases} $$

1. Define system

$$ \begin{cases} g_1(x_1, \dots, x_N) = 0 \\ \vdots \\ g_{\kappa-1}(x_1, \dots, x_N) = 0 \\ g_{\kappa}(x_1, \dots, x_N) = 0 \end{cases} $$

2. Find a GB (F4/F5)

$$ \begin{cases} g_1^*(x_1, \dots, x_N) = 0 \\ \vdots \\ g_{N-1}^*(x_{N-1}, x_N) = 0 \\ g_N^*(x_N) = 0 \end{cases} $$

3. Change order to lex

## The Tools Used

**SAGE** Open source, mostly reliable... but sloooow

**F4/F5** What makes it possible...but Open source implementations hard to find, big difference in efficiency between public/proprietary implementations.

but things are getting better!

**FGLM** No "practical" issues...
# Generic System Solving: Steps and Tools

$$ egin{cases} p_1(x_1, \dots, x_N) = 0 \\ \vdots \\ p_{k-1}(x_1, \dots, x_N) = 0 \\ p_k(x_1, \dots, x_N) = 0 \end{cases} $$

1. Define system

$$ egin{cases} g_1(x_1, \dots, x_N) = 0 \\ \vdots \\ g_{\kappa-1}(x_1, \dots, x_N) = 0 \\ g_{\kappa}(x_1, \dots, x_N) = 0 \end{cases} $$

2. Find a GB (F4/F5)

$$ egin{cases} g_1^*(x_1, \dots, x_N) = 0 \\ \vdots \\ g_{N-1}^*(x_{N-1}, x_N) = 0 \\ g_N^*(x_N) = 0 \end{cases} $$

3. Change order to lex

## The Tools Used

**SAGE** Open source, mostly reliable... but sloooow

**F4/F5** What makes it possible... but Open source implementations hard to find, big difference in efficiency between public/proprietary implementations.

but things are getting better!

**FGLM** No "practical" issues... but lots of variants with very different complexities
# Generic System Solving: Steps and Tools

$$ egin{cases} p_1(x_1, \dots, x_N) = 0 \\ \vdots \\ p_{k-1}(x_1, \dots, x_N) = 0 \\ p_k(x_1, \dots, x_N) = 0 \end{cases} $$

1. Define system

$$ egin{cases} g_1(x_1, \dots, x_N) = 0 \\ \vdots \\ g_{\kappa-1}(x_1, \dots, x_N) = 0 \\ g_{\kappa}(x_1, \dots, x_N) = 0 \end{cases} $$

2. Find a GB (F4/F5)

$$ egin{cases} g_1^*(x_1, \dots, x_N) = 0 \\ \vdots \\ g_{N-1}^*(x_{N-1}, x_N) = 0 \\ g_N^*(x_N) = 0 \end{cases} $$

3. Change order to lex

$$ g_N^*(x_N) = 0 \rightarrow x_N $$

4. Univariate root

## The Tools Used

**SAGE** Open source, mostly reliable... but sloooow

**F4/F5** What makes it possible... but Open source implementations hard to find, big difference in efficiency between public/proprietary implementations.

but things are getting better!

**FGLM** No "practical" issues... but lots of variants with very different complexities

**Berlekamp-Rabin** Easy to re-implement
# The Freelunch Approach

Steps 2 and 3 are both computationally costly, but not for the same reasons. For most AOPs, step 2 dominates in practice...

$$ \begin{cases} p_1(x_1, \dots, x_N) = 0 \\ \vdots \\ p_{k-1}(x_1, \dots, x_N) = 0 \\ p_k(x_1, \dots, x_N) = 0 \end{cases} $$

1. Define system

$$ \begin{cases} g_1(x_1, \dots, x_N) = 0 \\ \vdots \\ g_{\kappa-1}(x_1, \dots, x_N) = 0 \\ g_{\kappa}(x_1, \dots, x_N) = 0 \end{cases} $$

2. Find a GB

$$ \begin{cases} g_1^*(x_1, \dots, x_N) = 0 \\ \vdots \\ g_{N-1}^*(x_{N-1}, x_N) = 0 \\ g_N^*(x_N) = 0 \end{cases} $$

$$ g_N^*(x_N) = 0 \rightarrow x_N $$

3. Change order to lex

4. Univariate root
# The Freelunch Approach

Steps 2 and 3 are both computationally costly, but not for the same reasons. For most AOPs, step 2 dominates in practice...

$$ egin{cases} p_1(x_1, \dots, x_N) = 0 \\ \vdots \\ p_{k-1}(x_1, \dots, x_N) = 0 \\ p_k(x_1, \dots, x_N) = 0 \end{cases} $$

1. Define system

$$ egin{cases} g_1(x_1, \dots, x_N) = 0 \\ \vdots \\ g_{\kappa-1}(x_1, \dots, x_N) = 0 \\ g_{\kappa}(x_1, \dots, x_N) = 0 \end{cases} $$

2. Find a GB

$$ egin{cases} g_1^*(x_1, \dots, x_N) = 0 \\ \vdots \\ g_{N-1}^*(x_{N-1}, x_N) = 0 \\ g_N^*(x_N) = 0 \end{cases} $$

3. Change order to lex

$$ g_N^*(x_N) = 0 \rightarrow x_N $$

4. Univariate root

We can skip it!
# Freelunch Crypanalysis: Results

https://eprint.iacr.org/2024/347

Bariant, Augustin, et al. *The algebraic FreeLunch: Efficient Gröbner basis attacks against arithmetization-oriented primitives.* Annual International Cryptology Conference. Cham: Springer Nature Switzerland, 2024.

<table><thead><tr><th rowspan="2">Name</th><th rowspan="2">α/e</th><th colspan="7">Number of branches</th></tr><tr><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>8</th><th>≥ 12</th></tr></thead><tbody><tr><td rowspan="2">Griffin</td><td>3</td><td>0</td><td>120 (16)</td><td>112 (15)</td><td>0</td><td>0</td><td>76 (11)</td><td>64 (10)</td></tr><tr><td>5</td><td>0</td><td>141 (14)</td><td>110 (11)</td><td>0</td><td>0</td><td>81 (9)</td><td>74 (9)</td></tr><tr><td rowspan="3">Arion</td><td>3</td><td>0</td><td>128 (6)</td><td>134 (6)</td><td>114 (5)</td><td>119 (5)</td><td>98 (4)</td><td>0</td></tr><tr><td>5</td><td>0</td><td>132 (6)</td><td>113 (5)</td><td>118 (5)</td><td>122 (5)</td><td>101 (4)</td><td>0</td></tr><tr><td>3</td><td>0</td><td>104 (5)</td><td>84 (4)</td><td>88 (4)</td><td>92 (4)</td><td>98 (4)</td><td>0</td></tr><tr><td>α-Arion</td><td>5</td><td>0</td><td>83 (4)</td><td>87 (4)</td><td>91 (4)</td><td>94 (4)</td><td>101 (4)</td><td>0</td></tr><tr><td rowspan="4">Anemoi</td><td>3</td><td>118 (21)</td><td>0</td><td>-</td><td>0</td><td>-</td><td>-</td><td>-</td></tr><tr><td>5</td><td>156 (21)</td><td>0</td><td>-</td><td>0</td><td>-</td><td>-</td><td>-</td></tr><tr><td>7</td><td>174 (20)</td><td>0</td><td>-</td><td>0</td><td>-</td><td>-</td><td>-</td></tr><tr><td>11</td><td>198 (19)</td><td>0</td><td>-</td><td>0</td><td>-</td><td>-</td><td>-</td></tr></tbody></table>
# Plan of this Section

## 1 Algebraic Attacks: a Case Study

- Symmetric Techniques for Advanced Protocols

- (Multivariate) Root Finding Attacks

- What Have We Learnt?

## 2 What is a Tool?

## 3 Conclusion
# Post-Mortem

From the designers’ perspective

**SAGE** Did what it was supposed to do
# Post-Mortem

From the designers’ perspective

**SAGE** Did what it was supposed to do

**F4/F5** Turned out to be entirely irrelevant
# Post-Mortem

From the designers’ perspective

**SAGE** Did what it was supposed to do

**F4/F5** Turned out to be entirely irrelevant

**FGLM** Was replaced by a dedicated variant
# Post-Mortem

## From the designers’ perspective

**SAGE** Did what it was supposed to do

**F4/F5** Turned out to be entirely irrelevant

**FGLM** Was replaced by a dedicated variant

**Berlekamp-Rabin** Did what it was supposed to do
# Post-Mortem

## From the designers’ perspective

**SAGE** Did what it was supposed to do

**F4/F5** Turned out to be entirely irrelevant

**FGLM** Was replaced by a dedicated variant

Berlekamp-Rabin Did what it was supposed to do

■ Attackers didn’t improve the tools, they **created new ones**
# Post-Mortem

## From the designers’ perspective

**SAGE** Did what it was supposed to do

**F4/F5** Turned out to be entirely irrelevant

**FGLM** Was replaced by a dedicated variant

Berlekamp-Rabin Did what it was supposed to do

- Attackers didn't improve the tools, they **created new ones**
  in particular, a technique to build dedicated monomial orderings
# Post-Mortem

## From the designers’ perspective

**SAGE** Did what it was supposed to do

**F4/F5** Turned out to be entirely irrelevant

**FGLM** Was replaced by a dedicated variant

Berlekamp-Rabin Did what it was supposed to do

* Attackers didn’t improve the tools, they **created new ones**
in particular, a technique to build dedicated monomial orderings

* Designers’ relied on the assumption that the F4/F5 → FGLM → Univariate root finding chain was the **only** multivariate root-finding tool.
# Post-Mortem

## From the designers’ perspective

**SAGE** Did what it was supposed to do

**F4/F5** Turned out to be entirely irrelevant

**FGLM** Was replaced by a dedicated variant

Berlekamp-Rabin Did what it was supposed to do

* Attackers didn't improve the tools, they **created new ones**
in particular, a technique to build dedicated monomial orderings

* Designers' relied on the assumption that the F4/F5 → FGLM → Univariate root finding chain was the **only** multivariate root-finding tool.

* Inefficient/proprietary software limited the designers' ability to **prototype** attacks.
What Did We Need?

A better ability to prototype

A better interface with another field
# What Did We Need?

A better ability to prototype

- Derive systems of equations corresponding to different modeling

A better interface with another field
# What Did We Need?

## A better ability to prototype

* Derive systems of equations corresponding to different modeling

* Test in practical time the efficiency of different algorithms

## A better interface with another field
# What Did We Need?

## A better ability to prototype

* Derive systems of equations corresponding to different modeling

* Test in practical time the efficiency of different algorithms

## A better interface with another field

* Underlying assumptions when using the $F4/F5 \rightarrow FGLM \rightarrow$ Univariate root finding
# What Did We Need?

## A better ability to prototype

* Derive systems of equations corresponding to different modeling

* Test in practical time the efficiency of different algorithms

## A better interface with another field

* Underlying assumptions when using the $F4/F5 \rightarrow FGLM \rightarrow$ Univariate root finding

* Deeper understanding of each step
# What Did We Need?

## A better ability to prototype

* Derive systems of equations corresponding to different modeling

* Test in practical time the efficiency of different algorithms

## A better interface with another field

* Underlying assumptions when using the $F4/F5 \rightarrow FGLM \rightarrow$ Univariate root finding

* Deeper understanding of each step

We needed better tools!
# Plan of this Section

1. Algebraic Attacks: a Case Study

2. What is a Tool?

3. Conclusion
# Plan of this Section

1. Algebraic Attacks: a Case Study

2. What is a Tool?

* Some General Thoughts

* The Tools Needed for Root Finding Attacks

3. Conclusion
# Lessons from the MILP and Root Finding Case

## Root Finding

* The chain F4/F5 → FGLM → Univariate root finding is great for generic systems, but ours are very structured

* Finer grained knowledge allowed the freelunch attacks...
# Lessons from the MILP and Root Finding Case

## Root Finding

* The chain F4/F5 → FGLM → Univariate root finding is great for generic systems, but ours are very structured

* Finer grained knowledge allowed the freelunch attacks...

* ... and will allow better security arguments
# Lessons from the MILP and Root Finding Case

## Root Finding

* The chain F4/F5 → FGLM → Univariate root finding is great for **generic** systems, but ours are very structured

* Finer grained knowledge allowed the freelunch attacks...

* ... and will allow better security arguments

## MILP

Questions for the audience:

*Do we always use the "standard" solving method? Have we looked into a deeper integration?*
# Lessons from the MILP and Root Finding Case

## Root Finding

* The chain F4/F5 → FGLM → Univariate root finding is great for **generic** systems, but ours are very structured

* Finer grained knowledge allowed the freelunch attacks...

* ... and will allow better security arguments

## MILP

Questions for the audience:

*Do we always use the "standard" solving method? Have we looked into a deeper integration?*

We can't be experts in all fields: we need a way to "hide" some of the complexity to make it usable, while **understanding enough** to find optimization directions.
# Lessons from the MILP and Root Finding Case

## Root Finding

* The chain F4/F5 → FGLM → Univariate root finding is great for **generic** systems, but ours are very structured

* Finer grained knowledge allowed the freelunch attacks...

* ... and will allow better security arguments

## MILP

Questions for the audience:

*Do we always use the "standard" solving method? Have we looked into a deeper integration?*

We can't be experts in all fields: we need a way to "hide" some of the complexity to make it usable, while understanding enough to find optimization directions.

There is a "correct" level of abstraction that we must find
# The Purposes of Tools

When do we talk about “tools”?
# The Purposes of Tools

When do we talk about “tools”?

1. MILP is a convenient **tool** to study differential trails.
# The Purposes of Tools

## When do we talk about “tools”?

1. MILP is a convenient **tool** to study differential trails.

2. Ideally, we should have **tools** that can convincingly say "this is primitive is secure"
# The Purposes of Tools

## When do we talk about “tools”?

1. MILP is a convenient **tool** to study differential trails.

2. Ideally, we should have **tools** that can convincingly say “this is primitive is secure”

3. The low performance of some **tools** prevented primitive designers from **prototyping** attacks
# The Purposes of Tools

## When do we talk about “tools”?

1. MILP is a convenient **tool** to study differential trails.

2. Ideally, we should have **tools** that can convincingly say “this is primitive is secure”

3. The low performance of some **tools** prevented primitive designers from **prototyping** attacks

4. We wished the **tools** to solve multivariate root finding problems were easier (for us!) to understand and use.
# The Purposes of Tools

## When do we talk about “tools”?

1. MILP is a convenient **tool** to study differential trails.

2. Ideally, we should have **tools** that can convincingly say "this is primitive is secure"

3. The low performance of some **tools** prevented primitive designers from **prototyping** attacks

4. We wished the **tools** to solve multivariate root finding problems were easier (for us!) to understand and use.

> That's a lot "tools"! And yet...
# The Purposes of Tools

## When do we talk about “tools”?

1. MILP is a convenient **tool** to study differential trails.

2. Ideally, we should have **tools** that can convincingly say "this is primitive is secure"

3. The low performance of some **tools** prevented primitive designers from **prototyping** attacks

4. We wished the **tools** to solve multivariate root finding problems were easier (for us!) to understand and use.

> That's a lot "tools"! And yet...

## Definition (“Tool”)

A **tool** is a convenient abstraction layer above a specific know-how.
# Plan of this Section

1. Algebraic Attacks: a Case Study

2. What is a Tool?

■ Some General Thoughts

■ The Tools Needed for Root Finding Attacks

3. Conclusion
# A Prototyping Wish-List

I wish I had open source and efficient tools to...
# A Prototyping Wish-List

I wish I had open source and efficient tools to...

- Generate (and test!) a modeling of a round function using non-linear equations
# A Prototyping Wish-List

I wish I had open source and efficient tools to...

- Generate (and test!) a modeling of a round function using non-linear equations

- Handle fields of many different sizes
# A Prototyping Wish-List

I wish I had open source and efficient tools to...

- Generate (and test!) a modeling of a round function using non-linear equations

- Handle fields of many different sizes

- Manipulate multivariate polynomials efficiently: arithmetic, composition, **reduction**, **different monomial orderings**...
# A Prototyping Wish-List

I wish I had open source and efficient tools to...

- Generate (and test!) a modeling of a round function using non-linear equations

- Handle fields of many different sizes

- Manipulate multivariate polynomials efficiently: arithmetic, composition, **reduction**, **different monomial orderings**...

- Estimate the complexity of some “standard” algorithms: FGLM? F4/F5?
# A Prototyping Wish-List

I wish I had open source and efficient tools to...

- Generate (and test!) a modeling of a round function using non-linear equations

- Handle fields of many different sizes

- Manipulate multivariate polynomials efficiently: arithmetic, composition, **reduction**, **different monomial orderings**...

- Estimate the complexity of some "standard" algorithms: FGLM? F4/F5?

- Suggest the best known algorithm for some problems
# MIDC: Towards Sound Security Arguments?

The resolution of a multivariate system of equations can be approached in many ways, but the **ideal degree** is an **inherent property** of the system

→ a sounder basis for security arguments!
# MIDC: Towards Sound Security Arguments?

The resolution of a multivariate system of equations can be approached in many ways, but the **ideal degree** is an **inherent property** of the system

→ a sounder basis for security arguments!

## Monotonous Ideal Degree Conjecture

A method to find a reasonable lower bound for the ideal degree.

https://eprint.iacr.org/2024/605

$$ 
\left\{ 
\begin{array}{l}
x_0^{d_0} - P'_0(x_0, \dots, x_{n-1}) \\
x_1^{d_1} - P'_1(x_0, \dots, x_{n-1}) \\
\quad \dots \\
x_{b-1}^{d_{b-1}} - P'_{b-1}(x_0, \dots, x_{n-1}) \\
P_b(x_0, \dots, x_{n-1}) \\
P_{b+1}(x_0, \dots, x_{n-1}) \\
\quad \dots \\
P_{n-1}(x_0, \dots, x_{n-1})
\end{array}
\right\} \text{basal part}
$$
Plan of this Section

1. Algebraic Attacks: a Case Study

2. What is a Tool?

3. Conclusion
Conclusion

What is a Tool?

IMHO: a *convenient layer of abstraction* above a specific *know-how*.

Past Issues with Algebraic Attacks

- No convenient approach to estimate attack complexity
# Conclusion

## What is a Tool?

IMHO: a *convenient layer of abstraction above a specific know-how*.

## Past Issues with Algebraic Attacks

- No convenient approach to estimate attack complexity

- No convenient software tooling to write down relevant equations
# Conclusion

## What is a Tool?

IMHO: a *convenient layer of abstraction* above a *specific know-how*.

## Past Issues with Algebraic Attacks

- No convenient approach to estimate attack complexity

- No convenient software tooling to write down relevant equations

- No convenient software to solve them (SAGE -> Magma)
# Conclusion

## What is a Tool?

IMHO: a *convenient layer of abstraction* above a *specific know-how*.

## Past Issues with Algebraic Attacks

- No convenient approach to estimate attack complexity

- No convenient software tooling to write down relevant equations

- No convenient software to solve them (SAGE -> Magma)

... But there is hope!

- the MIDC could be used to build security arguments,

- future software tools will ease prototyping of algebraic attacks!
# Conclusion

## What is a Tool?

IMHO: a convenient layer of abstraction above a specific know-how.

## Past Issues with Algebraic Attacks

- No convenient approach to estimate attack complexity

- No convenient software tooling to write down relevant equations

- No convenient software to solve them (SAGE -> Magma)

... But there is hope!

- the MIDC could be used to build security arguments,

- future software tools will ease prototyping of algebraic attacks!

Thank you!