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

HAL
open science

# Cryptanalyse algébrique de la permutation GRIFFIN

Axel Lemoine

► To cite this version:

Axel Lemoine. Cryptanalyse algébrique de la permutation GRIFFIN. Informatique [cs]. 2023. hal-04716702

HAL Id: hal-04716702

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

Submitted on 1 Oct 2024

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 Attribution 4.0 International License
Cryptanalyse algébrique de la permutation GRIFFIN

Axel Lemoine

Sous la supervision de Léo Perrin

EPI COSMIQ, Inria Paris

1er octobre 2024

# Fiche de synthèse

## Contexte général

La cryptographie a vu ces dernières années l'apparition de nouveaux systèmes de preuves dans le contexte des preuves à divulgation nulle de connaissance (Zero-Knowledge proofs). Ces systèmes de preuves, tels que zk-SNARK et zk-STARK [4], doivent être implémentés conjointement avec des primitives symétriques (fonctions de hachage, chiffrements par blocs) ayant un cahier des charges nouveau comprenant notamment l'exigence de fonctionner nativement sur des corps premiers de grande taille. L'essentiel de l'arsenal du cryptanalyste symmétricien, comme les cryptanalyses linéaire et différentielle [5, 12], a été développé pour des primitives fonctionnant nativement sur $F_2$ (cas du DES [7]), ou éventuellement sur des extensions de $F_2$ (cas de l'AES qui fonctionne sur $F_{256}$). Le cas des corps premiers de grandes taille semble propice à l'introduction de méthode algébriques qui ont pu tomber en désuétude par le passé, en particulier la cryptanalyse algébrique, multivariée comme univariée. Les auteurs de nouveaux designs s'intéressent généralement à la cryptanalyse algébrique multivariée pour estimer la valeur des paramètres de leur système qui garantiront une sécurité voulue face aux attaques algébriques résultant d'un encodage relativement naïf. En effet, ce genre de précaution ne donne aucune certitude quant à l'inexistence d'attaques algébriques plus rusées, comme le montre l'exemple du cryptosystème Jarvis qui a été attaqué avec succès grâce à un calcul de base de Gröbner [1].

## Le problème étudié

Le but de ce stage était de tenter de nouvelles approches afin d'évaluer la sécurité de la permutation GRIFFIN [10]. Il s'agit d'un prototype de fonctions bijectives de $F_p^t \to F_p^t$ vouées à être utilisées dans une structure en éponge afin de construire des fonctions de hachage. La sécurité d'un tel outil cryptographique peut être évaluée par la difficulté du problème CICO (Constrained Input - Constrained Output). La prolifération des schémas dits *orientés arithmétisation* ou *STARK-friendly* impose aux cryptographes un rythme intense pour apporter la cryptanalyse nécessaire à la standardisation de ces schémas.
## La contribution

Il eût été optimiste de chercher à monter un attaque réelle et efficace sur un outil cryptographique conçu par des chercheurs professionnels. Dès lors, tout nouveau résultat concernant la cryptanalyse de GRIFFIN constitue un apport scientifique. J'ai donc exploré plusieurs angles d'attaques dans l'espoir d'aboutir à la constatation que les garanties de sécurité prévues par les auteurs étaient trop optimistes. J'ai cherché à adapter des attaques algébriques univariées récentes [3] au cas de GRIFFIN, à reproduire les résultats des auteurs de GRIFFIN quant à la résistance de leur outil contre les attaques algébriques multivariées standards et à élaborer des stratégies sur-mesure pour améliorer la performance de ces dernières attaques. J'ai en particulier observé qu'il était possible de paralléliser les attaques univariées données dans [3], ce qui mène à un léger gain en temps et un gain potentiellement significatif en mémoire. Plus récemment, j'ai contribué à définir une attaque algébrique multivariée plus sophistiquée permettant d'esquiver le calcul de la base de Gröbner. Ce travail, mené conjointement avec des chercheurs de Simula UiB à Bergen, est encore en cours.

## Les arguments en faveur de sa validité

Comme mentionné plus haut, la permutation GRIFFIN est une permutation de $\mathbb{F}_p^t$. Le nombre entier $t$ est appelé *nombre de branches* et peut prendre plusieurs valeurs de 3 à 24. GRIFFIN est redoutablement efficace lorsque le nombre de branches devient élevé, alors que notre approche de cryptanalyse multivariée devient plus dangereuse précisément dans ces cas, d'où sa pertinence. Par ailleurs, GRIFFIN est particulièrement optimisé lorsque le cardinal du corps premier sous-jacent vaut $p = 2^{64} - 2^{32} + 1$. Or l'optimization temps-mémoire mentionnée plus haut exploite la friabilité de $p - 1$ et devient donc intéressante précisément dans les cas d'usage de GRIFFIN.

## Bilan et perspectives

La question de savoir si nos travaux mèneront effectivement à la constatation que la sécurité de GRIFFIN doit être revue à la baisse doit encore être approfondie. Par ailleurs, certains collègues ont remarqué qu'une approche similaire à celle de nos travaux concernant GRIFFIN pourrait mener à des résultats intéressant sur Arion [13], une autre permutation. Cependant, le compromis temps-mémoire évoqué plus haut et permettant de moduler les attaques univariées ne dépend que du nombre premier $p$ et peut donc être considérablement généralisé.
Table des matières

<table><tr><td>1</td><td>La permutation GRIFFIN</td><td>4</td></tr><tr><td></td><td>subsection1.1 Spécification de GRIFFIN4</td><td></td></tr><tr><td>1.2</td><td>Les origines de GRIFFIN</td><td>6</td></tr><tr><td></td><td>subsection1.3 Comment évaluer la sécurité d'un tel outi2?7 Attaques algébriques univariées sur GRIFFIN</td><td>9</td></tr><tr><td></td><td>subsection2.1 Fonctionnement de l'attaque9</td><td></td></tr><tr><td>2.2</td><td>Parallélisation des attaques algébriques univariées</td><td>10</td></tr><tr><td></td><td>section3 Attaques algébriques multivariées11</td><td></td></tr><tr><td>3.1</td><td>Un premier modèle</td><td>11</td></tr><tr><td></td><td>subsection3.2 Influence de la couche linéaire sur la résistance aux attaques multivariées14</td><td></td></tr></table>
# 1 La permutation GRIFFIN

## 1.1 Spécification de GRIFFIN

La permutation GRIFFIN se décompose en plusieurs composants prenant chacun la forme d'une couche linéaire et d'une couche non linéaire. Nous reprenons ici pour l'essentiel la section 5.1 de [10].

**Définition 1.1.1 (Permutation GRIFFIN).** La permutation GRIFFIN $G : \mathbb{F}_p^t \to \mathbb{F}_p^t$ est définie par

$$G(\cdot) := \mathcal{F}_{R-1} \circ \cdots \circ \mathcal{F}_1 \circ \mathcal{F}_0(M \times \cdot)$$

où $t \in \{3, 4, 8, 12, 16, 20, 24\}$ est le nombre de branches, $R \ge 1$ est le nombre de tours, $M \in \mathbb{F}_p^{t \times t}$ est une matrice inversible et $\mathcal{F}_i(\cdot) = c^{(i)} + M \times S(\cdot)$ avec $c^{(i)} \in \mathbb{F}_p^t$ une constante choisie aléatoirement et $S : \mathbb{F}_p^t \to \mathbb{F}_p^t$ la couche non linéaire spécifiée ci-après.

**Remarque 1.1.1.** La dernière constante $c^{(R-1)}$ ne jouant aucun rôle cryptographique, elle sera systématiquement choisie nulle. Le choix des autres paramètres est spécifié dans la section 5.1 de [10]. Essentiellement, un GRIFFIN avec $t = 3$ requiert un nombre $R = 16$ de tours, tandis qu'un GRIFFIN avec $t \ge 12$ demande seulement $R = 10$ tours.

La matrice $M$ doit vérifier certaines propriétés afin de jouer au mieux son rôle de diffusion. Traditionnellement, on demande à ce que ce genre de matrice soit MDS, c'est à dire que le code de matrice génératrice

$$\mathcal{G} := (I_t | M)$$

atteigne la borne de Singleton.

L'usage de matrices MDS en cryptographie a été suggéré en 1994 par Serge Vaudenay [15] pour leurs propriétés optimales de diffusion. Une caractérisation des matrices MDS peut en effet prendre la forme suivante :

**Proposition 1.1.1.** Une matrice $M \in \mathbb{F}_q^{t \times t}$ est MDS si et seulement si pour tous $(x, y) \in \mathbb{F}_q^t \times \mathbb{F}_q^t$ et $s \in \{1, \dots, t\}$, on a

$$w_H(x - y) = s \implies w_H(Mx - My) \ge t - s + 1 \quad (1)$$

où $w_H(\cdot)$ désigne le poids de Hamming. Notons que cette propriété est optimale.

**Démonstration.** La propriété 1 signifie que le code $\{(x, Mx) | x \in \mathbb{F}_q^t\} \subset \mathbb{F}_q^{2t}$ doit avoir pour distance minimale au moins $t + 1$. Autrement dit, le code de matrice génératrice $(I_t | M)$ atteint la borne de Singleton. $\square$

Pour la couche linéaire de GRIFFIN, les auteurs suggèrent

$$M_3 = \begin{pmatrix} 2 & 1 & 1 \\ 1 & 2 & 1 \\ 1 & 1 & 2 \end{pmatrix} \quad \text{pour } t = 3, \text{ et } M_4 = \begin{pmatrix} 5 & 7 & 1 & 3 \\ 4 & 6 & 1 & 1 \\ 1 & 3 & 5 & 7 \\ 1 & 1 & 4 & 6 \end{pmatrix} \quad \text{pour } t = 4.$$
Pour $t = 4t'$, les auteurs recommandent de prendre la matrice

$$M = \begin{pmatrix} 2M_4 & M_4 & \cdots & M_4 \\ M_4 & 2M_4 & \cdots & M_4 \\ \vdots & \vdots & \ddots & \vdots \\ M_4 & M_4 & \cdots & 2M_4 \end{pmatrix}$$

Notons que, au contraire des deux premières, la matrice ci-dessus n’est pas MDS.

**Définition 1.1.2** (Couche non linéaire). Soient $d \ge 3$ le plus petit nombre premier qui ne divise pas $p-1$ et $(\alpha_i, \beta_i)_{i=2,...,t-1} \in \mathbb{F}_p^{\times} \setminus \{(0,0)\}$ deux à deux distincts et tels que $\alpha_i^2 - 4\beta_i$ n’est pas un carré modulo $p$. La couche non linéaire de GRIFFIN est donnée par

$$S: \begin{cases} \mathbb{F}_p^t \\ (x_0, \dots, x_{t-1}) \end{cases} \to \begin{cases} \mathbb{F}_p^t \\ (y_0, \dots, y_{t-1}) \end{cases}$$

avec

$$y_i = \begin{cases} x_0^{1/d} & \text{si } i=0, \\ x_1^d & \text{si } i=1, \\ x_2 \times (L_2(y_0, y_1, 0)^2 + \alpha_2 L_2(y_0, y_1, 0) + \beta_2) & \text{si } i=2, \\ x_i \times (L_i(y_0, y_1, x_{i-1})^2 + \alpha_2 L_i(y_0, y_1, x_{i-1}) + \beta_i) & \text{sinon,} \end{cases}$$

où les $L_i : \mathbb{F}_p^3 \to \mathbb{F}_p$ sont des fonctions linéaires de la forme $L_i(z_0, z_1, z_2) = \gamma_i z_0 + z_1 + z_2$ avec les $\gamma_i \in \mathbb{F}_p^\times$ deux à deux distincts.

**Remarque 1.1.2.** Il est essentiel que $\alpha_i^2 - 4\beta_i$ ne soit pas un carré modulo $p$ pour assurer l'invertibilité de la couche non linéaire.

En termes de schéma, la couche non linéaire de GRIFFIN peut être représentée comme sur la figure 1.1.

<figure><img src="image_3.png" /><figcaption>FIGURE 1.1 – Couche non linéaire de GRIFFIN, avec $t = 4$. On a posé $Q_i = L_i^2 + \alpha_i L_i + \beta_i$.</figcaption></figure>

Les flèches horizontales dans la figure 1.1 montrent bien que la couche non linéaire de GRIFFIN réalisée de la *diffusion*. Les auteurs ont relevé ceci comme un avantage de la construction Horst explicitée
dans la sous-section suivante. Nous verrons dans la section 3 que cela ne permet cependant pas de se passer d'une couche linéaire solide, notamment pour se prémunir des attaques algébriques.

## 1.2 Les origines de GRIFFIN

Le but des auteurs de GRIFFIN était de construire une fonction de hachage dite STARK-friendly. Autrement dit, le cahier des charges (en plus de la sécurité) demande un faible coût d'implémenta- tion selon les critères définis par le modèle de calcul utilisé. Essentiellement, l'objectif est de pouvoir prouver dans un contexte zero-knowledge la connaissance d'une préimage à un certain $y = \mathcal{H}(x)$ avec un coût minimal. Souvent, le coût en question se résume au nombre de multiplications ef- fectuées, mais dans certains cas le nombre d'additions doit aussi être considéré (comme dans la métrique Plonk par exemple [9]).

Les auteurs sont partis de ce qu'ils estimaient être des désavantages des schémas SPN apparais- sant notamment dans *Rescue* [2] et *POSEIDON* [11]. La rigidité du schéma SPN impliquent selon eux une limitation des performances dans certains cas d'usages. Ils en sont donc venus à travailler sur un nouveau type de schéma appelé *Horst*.

**Définition 1.2.1 (Schéma Horst).** Soient $G : \mathbb{F}_q \to \mathbb{F}_q^\times$ et $F : \mathbb{F}_q \to \mathbb{F}_q$. Le schéma Horst sur $\mathbb{F}_q^2$ est défini par

$$ (y, x) \mapsto (x, y \times G(x) + F(x)) $$

Lorsque $G \equiv 1$, on retrouve un schéma de Feistel.

Cette définition permet de relier la sécurité de Horst à celle d'un schéma Feistel qui a largement été étudiée par le passé.

Pour GRIFFIN, qui était voué depuis le départ à fonctionner sur un nombre plus élevé de branches, les auteurs généralisent le schéma Horst :

**Définition 1.2.2 (Horst généralisé).** Soit $t \ge 2$. Pour tout $i \in \{0, \dots, t-2\}$, soient $G_i : \mathbb{F}_q^{i+1} \to \mathbb{F}_q^\times$ et $F_i : \mathbb{F}_q^{i+1} \to \mathbb{F}_q$. Le schéma Horst généralisé sur $\mathbb{F}_q^t$ est la fonction $x \mapsto y$ avec

$$ y_i := \begin{cases} x_{i+1} \times G_i(x_0, \dots, x_i) + F_i(x_0, \dots, x_i) & \text{si } i \in \{0, \dots, t-2\} \\ x_0 & \text{sinon.} \end{cases} $$

Dans la construction finale de GRIFFIN, la fonction $F_i$ est choisie nulle. Pour assurer l'inverti- bilité, les fonctions $G_i$ ne doivent pas s'annuler. Les auteurs sont parvenus à construire de telles fonctions en considérant des fonctions quadratiques dont le discriminant n'est pas un carré dans $\mathbb{F}_p$.

**Remarque 1.2.1.** Comme on l'a vu dans la définition 1.1.2, les deux premières coordonnées de la couche non linéaire sont passées à travers une boîte-S prenant la forme d'une fonction puissance inversible. Lorsque $p-1$, il faut alors passer au degré 5, puis 7 et ainsi de suite. La force du schéma utilisé dans GRIFFIN, en particulier lorsque le nombre de branches devient élevé, vient du fait que toutes les autres branches restent en degré 3, là où un SPN verra son degré augmenté sur chaque branche.
## 1.3 Comment évaluer la sécurité d'un tel outil ?

GRIFFIN est un outil cryptographique servant de brique pour construire des fonctions de hachage, notamment via une construction en éponge dont le fonctionnement est illustré dans la figure 1.2.

<figure><img src="image_4.png" /><figcaption>FIGURE 1.2 – Fonction de hachage en éponge. La permutation GRIFFIN joue le rôle de la permutation f.</figcaption></figure>

Les membres de la team Keccak<fnref n="1" /> expliquent dans leur spécification<fnref n="2" /> que la sécurité d'une permutation s'évalue en fonction de la difficulté du problème CICO sous-jacent, dont nous donnons un cas particulier ici.

**Problème 1.3.1 (CICO).** Soient $f: \mathbb{F}_p^t \to \mathbb{F}_p^t$ une permutation aléatoire et $1 \le r < t$ un entier. Le but du problème CICO d'instance $(f, r)$ est de trouver $x \in \{0\}^r \times \mathbb{F}_p^{t-r}$ tel que $f(x) \in \{0\}^r \times \mathbb{F}_p^{t-r}$.

Au cours de ce stage, j'ai essayé d'étudier le comportement de ce problème CICO lorsqu'il est effectivement instancié à partir d'une permutation aléatoire uniforme. En me restreignant au cas $r = 1$ dans la définition précédente, je suis parvenu au résultat suivant.

**Proposition 1.3.1.** Pour une permutation $f: \mathbb{F}_p^t \to \mathbb{F}_p^t$, on pose

$$ \mathrm{CICO}(f) = \{x \in \{0\} \times \mathbb{F}_p^{t-1}, f(x) \in \{0\} \times \mathbb{F}_p^{t-1}\} $$

Supposons que $f$ est une permutation aléatoire **uniforme**. Alors $\mathrm{CICO}(f)$ est un sous-ensemble aléatoire de $\{0\} \times \mathbb{F}_p^{t-1}$ et pour tout $S \subseteq \{0\} \times \mathbb{F}_p^{t-1}$, on a

$$ \mathbb{P}(\mathrm{CICO}(f) = S) = \frac{\binom{p^t - p^{t-1}}{p^{t-1} - |S|}}{\binom{p^t}{p^{t-1}}} $$

En conséquence, la variable aléatoire discrète $|\mathrm{CICO}(f)|$ suit une loi hypergéométrique de paramètres $(p^{t-1}, 1/p, p^t)$ et son espérance vaut $p^{t-2}$.

La preuve de cette proposition sera donnée en annexe et fait intervenir quelques techniques non triviales de combinatoire.

<footnote n="1">1. Guido Bertoni, Joan Daemen, Michaël Peeters et Gilles Van Assche.</footnote>

<footnote n="2">2. https://keccak.team/files/CSF-0.1.pdf</footnote>
Les attaques algébriques (multivariées comme univariées) cherchent en général une solution au problème CICO le long d'une droite. En faisant l'inventaire du nombre de contraintes et du nombre de degrés de liberté, on s'attend à obtenir ainsi une seule solution. C'est ce que j'ai pu obtenir dans le résultat suivant, lui aussi démontré en annexe.

**Proposition 1.3.2.** Soient $f : \mathbb{F}_p^t \to \mathbb{F}_p^t$ une permutation aléatoire uniforme et $(d) \subseteq \{0\} \times \mathbb{F}_p^{t-1}$ une droite quelconque. Alors $\mathbb{E}[|(d) \cap \text{CICO}(f)|] = 1$.

J'ai cherché à être plus précis et en particulier à estimer la probabilité d'obtenir un nombre $k$ de solutions donné. L'expression de la proposition 1.3.1 ne m'a pas permis de conclure. Cependant, j'ai pu faire l'observation suivante : si

$$f: \begin{cases} \mathbb{F}_p^t \\ (x_0, \dots, x_{t-1}) \end{cases} \to \begin{cases} \mathbb{F}_p^t \\ (f_0(x_0, \dots, x_{t-1}), \dots, f_{t-1}(x_0, \dots, x_{t-1})) \end{cases}$$

alors $\text{CICO}(f) = \{(0, x_1, \dots, x_{t-1}) \mid f_0(0, x_1, \dots, x_{t-1}) = 0\}$. Ainsi, l'ensemble recherché est donné par les lieux d'annulation d'une fonction aléatoire. Cependant, la contrainte qui exige que $f$ soit bijective empêche $f_0(0, \cdot)$ d'être une fonction aléatoire uniforme de $\mathbb{F}_p^{t-1}$ dans $\mathbb{F}_p$. Pour autant, on reste tenté par l'idée d'approximer $f_0(0, \cdot)$ par une fonction aléatoire uniforme. C'est ainsi qu'on en vient à considérer un autre modèle d'ensemble aléatoire, introduit dans la proposition suivante.

**Proposition 1.3.3.** Étant donné $f_0 : \mathbb{F}_p^{t-1} \to \mathbb{F}_p$, on considère l'ensemble

$$\mathcal{C}_{f_0} = \{(0, x_1, \dots, x_{t-1}) \in \{0\} \times \mathbb{F}_p^{t-1} \mid f_0(x_1, \dots, x_{t-1}) = 0\}$$

Si $f_0 : \mathbb{F}_p^{t-1} \to \mathbb{F}_p$ est aléatoire uniforme, alors pour tout $S \subseteq \{0\} \times \mathbb{F}_p^{t-1}$, on a

$$\mathbb{P}(\mathcal{C}_{f_0} = S) = \frac{(p-1)^{p^{t-1}-|S|}}{p^{p^{t-1}}}. $$

Il n'est pas du tout clair à ce stade que la distribution de $\mathcal{C}_{f_0}$ soit proche de celle de $\text{CICO}(f)$. C'est pourtant ce que l'on observe en pratique. Rappelons la définition de la distance en variation totale entre deux variables aléatoires/distributions :

**Définition 1.3.1 (distance en variation totale).** Soient $\mu, \nu$ deux mesures de probabilités définies sur un espace probabilisable $(\Omega, \mathcal{A})$. La distance en variation totale entre $\mu$ et $\nu$ est la quantité

$$d_{\text{TV}}(\mu, \nu) := 2 \sup_{A \in \mathcal{A}} |\mu(A) - \nu(A)|$$

Si $X, Y$ sont deux variables aléatoires sur $(\Omega, \mathcal{A}, \mathbb{P})$, on note $d_{\text{TV}}(X, Y) = d_{\text{TV}}(\mathbb{P}_X, \mathbb{P}_Y)$.

Mes simulations tendent à corroborer ce qui reste à l'heure actuelle une simple conjecture.

**Conjecture 1.3.1.** Soient $f : \mathbb{F}_p^t \to \mathbb{F}_p^t$ une permutation aléatoire uniforme et $f_0 : \mathbb{F}_p^{t-1} \to \mathbb{F}_p$ une fonction aléatoire uniforme. Alors $\lim_{p \to +\infty} d_{\text{TV}}(\text{CICO}(f), \mathcal{C}_{f_0}) = 0$.

Soit maintenant $(d) \subseteq \{0\} \times \mathbb{F}_p^{t-1}$ une droite quelconque. Écrivons une paramétrisation de $(d)$ :

$$(d) = \{(0, \alpha_1 s + \beta_1, \dots, \alpha_{t-1} s + \beta_{t-1}) \mid s \in \mathbb{F}_p\}.$$
On peut alors montrer que si $f_0 : \mathbb{F}_p^{t-1} \to \mathbb{F}_p$ est une fonction aléatoire uniforme, alors la fonction

$$ \tilde{f}_0 : \begin{cases} \mathbb{F}_p & \to \mathbb{F}_p \\ s & \mapsto f_0(0, \alpha_1 s + \beta_1, \dots, \alpha_{t-1} s + \beta_{t-1}) \end{cases} $$

est une fonction aléatoire uniforme. Ainsi, son vecteur des valeurs $(\tilde{f}_0(s))_{s \in \mathbb{F}_p}$ définit une collection de variables aléatoires uniformes indépendantes à valeurs dans $\mathbb{F}_p$. Le nombre de ces variables qui s'annulent suit alors une loi binomiale de paramètres $(p, 1/p)$. Dans ces conditions, on obtient le corollaire suivant.

**Corollaire 1.3.1.** Pour tout $k \le p$, on a $\mathbb{P}(|\mathcal{C}_{f_0} \cap (d)| = k) = \binom{p}{k} \left(\frac{1}{p}\right)^k \left(1 - \frac{1}{p}\right)^{p-k}$. En conséquence, lorsque $p$ tend vers l'infini, la distribution de $|\mathcal{C}_{f_0} \cap (d)|$ converge en variation totale vers une loi de poisson de paramètre $\lambda = 1$. En particulier, la probabilité que $\mathcal{C}_{f_0} \cap (d) = \emptyset$ tend vers $1/e \approx 0.3679$.

La conjecture 1.3.1 ne permet pas d’en déduire que la valeur $1/e$ s’applique aussi au cas du problème CICO, car il y a une double limite à lever. Cela dit, la table suivante montre, pour $p = 241$ et $t = 3$, la proportion d’instances de GRIFFIN<fnref n="3" /> ne présentant aucune solution au problème CICO le long de la droite d’équation $x_1 + x_2 = 0$.

<table><caption>TABLE 1 – Proportion d'instances de GRIFFIN donnant 0 solution au problème CICO le long de la droite $x_1 + x_2 = 0$.</caption><thead><tr><th>Nombre d'instances</th><th>1000</th><th>10000</th><th>30000</th><th>100000</th></tr></thead><tbody><tr><td>Proportion donnant 0 solution</td><td>37.8%</td><td>36.51%</td><td>37.04%</td><td>36.901%</td></tr></tbody></table>

# 2 Attaques algébriques univariées sur GRIFFIN

## 2.1 Fonctionnement de l'attaque

Une approche possible pour résoudre le problème CICO consiste à chercher une solution le long d'un certain espace paramétré par une unique variable que nous représenterons par une indéterminée $X$. Autrement dit, chaque entrée de la permutation est une fonction<fnref n="4" /> de $X$, notons $e_i(X)$, $i = 0, \dots, t - 1$. Pour conclure, il reste donc à effectuer les deux étapes suivantes :

* exécuter formellement la permutation $f$ sur les entrées $e_i(X) : f(e_0(X), \dots, e_{t-1}(X)) = (s_0(X), \dots, s_{t-1}(X))$, avec $e_0(X) = 0$;

* trouver les racines de $s_0(X)$.

**Remarque 2.1.1.** Les calculs n'ont pas véritablement lieu dans $\mathbb{F}_p[X]$ mais dans $\mathbb{F}_p[X]/(X^p - X)$.

Le coût de la première étape sera détaillé plus bas. Pour la seconde, il s'agit d'un problème bien connu, à savoir la factorisation dans $\mathbb{F}_p[X]$ d'un polynôme de degré $d$. Les algorithmes les plus efficaces exigent $O(d \log(d)(\log(d) + \log(p)) \log \log(d))$ opérations dans $\mathbb{F}_p$. Pour ce qui est de GRIFFIN, le coût de son évaluation est donné dans la proposition suivante.

<footnote n="3">3. Les constantes sont choisies aléatoirement. Les coefficient $\alpha_2$ et $\beta_2$ sont choisis aléatoirement parmi les paramètres autorisés et $\gamma_2 = 1$.</footnote>

<footnote n="4">4. Nécessairement polynomiale.</footnote>
**Proposition 2.1.1.** Soit $G: \mathbb{F}_p^t \to \mathbb{F}_p^t$ une instance de GRIFFIN à $R$ tours et $t$ branches. Le coût d'évaluation de GRIFFIN en terme d'opérations dans $\mathbb{F}_p$ vaut

i) $O(R(\log(p) + t^2))$ pour une entrée dans $\mathbb{F}_p^t$;

ii) $O(Rp(\log^2(p) + t \log(p) + t^2p)) = O(Rt^2p^2)$ pour une entrée univariée.

**Démonstration.** À chaque tour, on doit effectuer

— Une exponentiation rapide coûtant $O(\log(p))$ (resp. $O(p \log^2(p))$);

— $t-1$ calculs pour les autres branches coûtant chancun $O(1)$ (resp. $O(p \log(p))$ opérations;

— Une multiplication matricielle coûtant $O(t^2)$ dans le cas d'une entrée scalaire et $O(t^2p)$ dans le cas univarié (la matrice étant à coefficient scalaires et non polynomiaux).

Notons qu'on a fait l'hypothèse ici que les polynômes apparaissant dans le calcul univarié étaient denses à cause de l'exponentiation élevée à la première branche. $\square$

Ainsi, une attaque univariée de ce type ne semble pas bien prometteuse dans le cas de GRIFFIN, essentiellement car les polynômes apparaissant sont denses. Les attaques univariées mises en oeuvre dans [3] sont particulièrement efficaces sur POSEIDON [14] car le degré des polynômes calculés n'augmente qu'exponentiellement avec le nombre de tours. Avec GRIFFIN, même en trouvant un moyen de sauter un ou plusieurs tours, le coût de la factorisation finale restera toujours plus élevé que celui de l'exploration exhaustive de la droite le long de laquelle on cherche à résoudre le problème CICO.

## 2.2 Parallélisation des attaques algébriques univariées

Dans un contexte autre que celui de la cryptanalyse de GRIFFIN spécifiquement, il se peut que les attaques univariées présentent un intérêt significatif par rapport à la recherche exhaustive. Cela ne rend pas ces attaques gratuites pour autant, non seulement en temps mais aussi (et surtout) en mémoire. Le procédé détaillé ici consiste à paralléliser ces attaques lorsque cela est possible, conduisant à un gain en temps marginal et un gain en mémoire significatif (si les threads sont exécutés séquentiellement et non en parallèle).

La remarque 2.1.1 revient à dire qu'effectuer les calculs modulo $X^p - X$ consiste à rechercher les solutions dans l'ensemble $\{x \in \mathbb{F}_p \mid x^p - x = 0\} = \mathbb{F}_p$. Lorsque $p$ est un grand nombre premier, $p-1$ est pair et il est possible de chercher une solution dans le sous-groupe de $\mathbb{F}_p^\times$ constitué des éléments ayant une racine carrée, à savoir $\{x \in \mathbb{F}_p \mid x^{\frac{p-1}{2}} = 1\}$. Son complémentaire dans $\mathbb{F}_p^\times$ est l'ensemble $\{x \in \mathbb{F}_p \mid x^{\frac{p-1}{2}} = -1\}$. Tout ce que l'on vient de faire, c'est utiliser une factorisation de $X^p - X$ pour en déduire une partition de $\mathbb{F}_p$ dont chaque ensemble est défini par une équation simple, permettant ainsi des calculs rapides. Le degré des équations en question est ici divisé par deux, ce qui accélère légèrement les calculs et donne un facteur 2 en gain mémoire si l'on choisit d'explorer ces deux ensembles successivement.

**Lemme 2.2.1.** Soit $p = 2^s q + 1$ un nombre premier. Alors il existe $\omega_s \in \mathbb{F}_p$ une racine primitive $2^s$-ième de l'unité et on a dans $\mathbb{F}_p[X]$

$$X^p - X = X \prod_{i=1}^{2^s} (X^q - \omega_s^i).$$
L'idée est alors d'effectuer les calculs modulo $M_i(X) := X^q - \omega_s^i$ pour tout $i = 1, \dots, 2^s$. Calculer modulo $M_i(X)$ revient à explorer l'ensemble $\{x \in \mathbb{F}_p, x^q = \omega_s^i\}$. Les polynômes prennent alors une taille $q$ au lieu de $p$. De plus, le coût de la multiplication de deux tels polynômes prend alors $O(q \log q)$ au lieu de $O(p \log p)$. Au total, lorsqu'on parcourt tous ces ensembles, le facteur $\log p$ devient $\log q$ ce qui reste un gain en temps. On résume cette situation dans l'algorithme suivant.

<caption>**Algorithmme 1 :** Parallélisation d'une attaque univariée</caption>

**Entrées** : Instance de GRIFFIN G sur $\mathbb{F}_p^t$ avec $p = 2^s q + 1$, vecteur initial $e(X)$, générateur $g$ de $\mathbb{F}_p^\times$

**Résultat** : $x \in \mathbb{F}_p$ tel que $G(e(x)) \in \{0\} \times \mathbb{F}_p^{t-1}$

1 initialization;
2 $i \leftarrow 1$;
3 $\omega \leftarrow g^q$; // $\omega$ est une racine primitive $2^s$-ième de l'unité
4 $M(X) \leftarrow X^q - \omega$;
5 **tant que** $i \le 2^s$ **faire**
6 $\quad$ Calculer $G(e(X)) = (u(X), \star, \dots, \star)$ mod $M(X)$;
7 $\quad$ $v(X) \leftarrow \gcd(u(X), M(X))$;
8 $\quad$ $L \leftarrow \{x \in \mathbb{F}_p, v(x) = 0\}$;
9 $\quad$ **si** $L \ne \emptyset$ **alors**
10 $\quad\quad$ **return** $L[0]$;
11 $\quad$ **sinon**
12 $\quad\quad$ $i \leftarrow i + 1$;
13 $\quad\quad$ $M(X) \leftarrow X^q - \omega^i$;
14 $\quad$ **fin**
15 **fin**

Chaque passage dans la boucle peut être effectué en parallèle, ce qui permet à l'attaquant de
réaliser un compromis temps-mémoire selon ses capacités. Notons que l'idée présentée ici est assez
générale : il peut être intéressant de travailler modulo des facteurs creux de $X^p - X$ pour accélérer
les calculs et/ou obtenir un gain mémoire.

3 Attaques algébriques multivariées

3.1 Un premier modèle

Dans cette section, on considère une permutation GRIFFIN G à trois branches et R tours. Une approche possible pour les attaques algébriques consiste à désigner par $(X_i, Y_i, Z_i)$ l'état en sortie de la couche non linéaire $S$ du tour $i$, pour $i \in \{0, \dots, R-1\}$. On écrit alors les équations reliant l'état du tour $i$ à l'état du tour $i+1$ selon le schéma de la figure 3.1.

Supposons que l'on cherche une solution au problème CICO le long d'une droite paramétrée par

$$
\lambda \mapsto (a_0\lambda + b_0, a_1\lambda + b_1, a_2\lambda + b_2).
$$

Ceci permet, dans le cas multivarié, d'avoir autant d'équations que d'inconnues et d'obtenir un idéal 0-dimensionnel, ce qui est préférable pour la résolution du système.
<figure><img src="image_5.png" /><figcaption>FIGURE 3.1 – Mise en équation multivariée de GRIFFIN</figcaption></figure>

Le problème CICO est alors défini par trois équations initiales :

$$
\begin{cases}
X_0^d - (2a_0 + a_1 + a_2)\lambda - 2b_0 - b_1 - b_2 = 0 \\
Y_0 - ((a_0 + 2a_1 + a_2)\lambda + b_0 + 2b_1 + b_2)^d = 0 \\
Z_0 - ((a_0 + a_1 + 2a_2)\lambda + b_0 + b_1 + 2b_2)((\gamma X_0 + Y_0)^2 + \alpha(\gamma X_0 + Y_0) + \beta) = 0,
\end{cases}
$$

puis 3 × (R − 1) équations de transitions pour tout i ∈ {0 , . . . , R − 2} :

$$
\left\{
\begin{array}{l}
X_{i+1}^d - 2X_i - Y_i - Z_i - c_0^{(i)} = 0 \\
Y_{i+1} - (X_i + 2Y_i + Z_i + c_1^{(i)})^d = 0 \\
Z_{i+1} - (X_i + Y_i + 2Z_i + c_2^{(i)}((\gamma X_{i+1} + Y_{i+1})^2 + \alpha(\gamma X_{i+1} + Y_{i+1}) + \beta) = 0,
\end{array}
\right.
$$

et une équation finale définissant le problème CICO :

$$
2X_{R-1} + Y_{R-1} + Z_{R-1} = 0.
$$

Nous obtenons une modélisation algébrique du problème CICO, c’est-à-dire un idéal de l’anneau
**R** := ℂₚ[X, Xᵢ, Yᵢ, Zᵢ | i = 0, ..., R - 1].

Rappelons rapidement comment fonctionne la résolution d'un système d'équations polynomiales.
Nous détaillons ici une stratégie standard, mais il en existe plein d'autres comme nous le verrons
dans la suite.

Soit donc **R** := ℂ[X₁, ..., Xₙ] un anneau de polynômes en *n* variables sur un corps *F*. La première chose à fixer est la manière dont on va comparer les différents monômes entre eux, notamment afin d'identifier un monôme dominant.

**Définition 3.1.1 (Ordre admissible).** Pour α = (α₁, ..., αₙ) ∈ Zn≥₀, on écrira Xα := Xα₁ ... Xαₙ.
Un ordre monomial admissible < est une relation d'ordre totale sur l'ensemble des monômes<fnref n="5" /> de
**R** vérifiant

$$
\bullet \forall \alpha \in \mathbb{Z}_{\ge 0}^n, 1 < X^{\alpha};
$$

• X^α < X^β = ⇒ ∀γ ∈ Zn≥0, X^α+γ < X^β+γ.

<footnote n="5">5. Ou sur $\mathbb{Z}_{\ge 0}^n$ de manière équivalente.</footnote>
Soit maintenant $I = (f_1, \dots, f_m) \subset \mathbf{R}$ un idéal de l'anneau $\mathbf{R}$. Pour calculer la variété définie par les équations $I$, i.e l'ensemble

$$V(I) = \{(x_1, \dots, x_n) \in \mathbb{F}^n \mid \forall i \in \{1, \dots, m\}, f_i(x_1, \dots, x_m) = 0\},$$

on procède tout d'abord par le calcul d'une base de Gröbner [6].

**Définition 3.1.2** (Base de Gröbner). Soit $< \text{un ordre monomial admissible. Si } f \in \mathbf{R}, \text{ on note LM}(f)$ le monôme dominant de $f$ par rapport à l'ordre $<$. Une base de Gröbner de $I$ pour l'ordre $<$ est un sous ensemble fini $G = \{g_1, \dots, g_t\} \subset I$ tel que l'idéal monomial engendré par les monômes dominants de $G$ soit égal à l'idéal monomial engendré par les termes de tête des éléments de $I$. Une telle base est dite réduite si pour tout $g \in G$, aucun terme de $g$ n'est divisible par le terme de tête d'un autre élément de $G$.

Citons les propriétés des bases de Gröbner qui nous seront utiles dans la suite. Nous référons
à [6] pour plus de détails.

**Proposition 3.1.1.** Soient $I \subset \mathbf{R}$ un idéal et $< \text{un ordre monomial admissible. Alors } I \text{ admet une unique base de Gröbner réduite } G \text{ pour cet ordre et}$

$i) (G) = I;$

ii) Pour tout $f \in \mathbf{R}$, il existe un unique $r \in \mathbf{R}$ vérifiant

$\bullet f - r \in I;$

• aucun terme de r n'est divisible par le terme de tête d'un des éléments de G.

iii) Si $< \text{ est l'ordre lexicographique et si } I \text{ est un idéal générique tel que } V(I) \text{ est fini sur } \bar{\mathbb{F}},$ alors $G$ est en position SHAPE, autrement dit il existe $w_1, \dots, w_{n-1}, h \in \bar{\mathbb{F}}[X_n]$ tel que $G = \{h(X_n), X_1 - w_1(X_n), \dots, X_{n-1} - w_{n-1}(X_n)\}$.

La troisième propriété permet bien-sûr de résoudre le système. On cherche donc à calculer une
base de Gröbner pour cet ordre lexicographique. La stratégie usuelle consiste à exécuter les alo-
githmes les plus efficaces pour un ordre monomial plus optimal 6, puis à exécuter un algorithme de
changement d'ordre qui convertit la base calculée en une base de Gröbner pour l'ordre lexicogra-
phique. Lorsque l'idéal est 0-dimensionnel, c'est-à-dire lorsque

$$\#\{(x_1, \dots, x_n) \in \bar{\mathbb{F}}^n \mid \forall f \in I, f(x_1, \dots, x_n) = 0\} < \infty,$$

ou de manière équivalente, lorsque

$$D_I := \dim_{\bar{\mathbb{F}}} \left( \bar{\mathbb{F}}[X_1, \dots, X_n] / I \right) < \infty,$$

alors il est possible d'exécuter l'algorithme FGLM [8] pour changer d'ordre, ce qui requiert $O(nD_I^3)$ opérations dans $\mathbb{F}$. Le calcul de la base de Gröbner en lui-même requiert, via l'algorithme F5, une complexité en $O\left(nD_{reg}\binom{n+D_{reg}-1}{D_{reg}}^\omega\right)$ où $D_{reg}$ est le degré de régularité de l'idéal $I$.

<footnote n="6">6. Vis-à-vis du calcul d'une base de Gröbner. On pense notamment à l'ordre gradué lexicographique renversé, ou Grevlex.</footnote>
## 3.2 Influence de la couche linéaire sur la résistance aux attaques multi-variées

Nous avons détaillé dans la section précédente un modèle algébrique décrivant le problème CICO pour GRIFFIN. Les coefficients apparaissant dans les polynômes générant notre idéal dépendent de plusieurs composants, en particulier la couche linéaire de GRIFFIN. Si le rôle de cette dernière est très bien compris en ce qui concerne les attaques différentielles et linéaires, son impact sur la complexité des attaques algébriques reste encore à étudier.

Afin d'avoir les résultats les plus parlants possibles, nous avons comparé le temps de calcul d'une base de Gröbner pour trois différentes versions d'un GRIFFIN à 6 branches 7 et 3 tours modulo $p = 47$. L'exposant de la couche non linéaire vaut $d = 3$. Les différentes constantes sont choisies comme précisé plus haut et nous ne les indiquerons pas explicitement ici.

Les trois modèles différeront donc par leurs constantes mais surtout par leur couche linéaire qui prendra l'une des trois valeurs suivantes :

$$ M_1 = \begin{pmatrix} 16 & 11 & 13 & 12 & 10 & 3 \\ 6 & 1 & 1 & 9 & 3 & 9 \\ 2 & 1 & 9 & 11 & 6 & 14 \\ 3 & 3 & 13 & 7 & 15 & 14 \\ 2 & 15 & 11 & 6 & 4 & 9 \\ 6 & 4 & 5 & 7 & 14 & 3 \end{pmatrix}, M_2 = \begin{pmatrix} 4 & 2 & 2 & 2 & 1 & 1 \\ 2 & 4 & 2 & 1 & 2 & 1 \\ 2 & 2 & 4 & 1 & 1 & 2 \\ 2 & 1 & 1 & 4 & 2 & 2 \\ 1 & 2 & 1 & 2 & 4 & 2 \\ 1 & 1 & 2 & 2 & 2 & 4 \end{pmatrix} \text{ et } M_3 = \begin{pmatrix} 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \end{pmatrix}, $$

La première matrice est une matrice MDS obtenue en écrivant sous forme systématique une matrice génératrice d'un code de Reed-Solomon. La deuxième matrice est construite selon la méthode utilisée par les auteurs de GRIFFIN, c'est-à-dire qu'elle prend la forme

$$ M_2 = \begin{pmatrix} 2M & M \\ M & 2M \end{pmatrix} $$

où $M$ est la matrice utilisée pour un GRIFFIN à trois branches. La matrice $M_3$ est une matrice de permutation présentant donc des propriétés de diffusion particulièrement mauvaises. Nous avons enfin ajouté une dernière colonne au tableau représentant le temps de calcul obtenu pour des matrices inversibles aléatoire ne présentant aucune propriété de diffusion en particulier. Les temps de calcul pour obtenir une base de Gröbner pour l'ordre grevlex pour chacun de ces modèles est retranscrit dans la table 2.

Une matrice de permutation donnant un temps de résolution fulgurant n'est absolument pas surprenant. Les polynômes générés par une telle matrice étaient par ailleurs de taille bornée, là où les autres systèmes avaient tendance à être denses. Notons que ce temps de calcul très faible prouve que la diffusion réalisée par la couche non linéaire de GRIFFIN ne permet en rien de se passer d'une couche linéaire forte.

Une couche MDS ou la couche utilisée par GRIFFIN semblent fournir des performances assez intéressantes en comparaison avec le cas générique d'une matrice inversible quelconque. Notons d'ailleurs que le prototype de matrice utilisé dans GRIFFIN, bien que non MDS, obtient des performances supérieures à la matrice MDS que nous avons testée.

<footnote n="7">7. Une telle version n'est pas prévue par les auteurs de GRIFFIN bien que rien n'empêche leur construction d'exister dans ce cas aussi.</footnote>
<table><caption>TABLE 2 – Temps de calcul de la base de Gröbner Grevlex pour les différentes couches linéaires. Les calculs sont réalisés sur Magma.</caption><thead><tr><th>Essai \ Couche linéaire</th><th>M<sub>1</sub></th><th>M<sub>2</sub></th><th>M<sub>3</sub></th><th>Aléatoire</th></tr></thead><tbody><tr><td>1</td><td>4051s</td><td>5170s</td><td>5s</td><td>3565s</td></tr><tr><td>2</td><td>4176s</td><td>5352s</td><td>5s</td><td>2144s</td></tr><tr><td>3</td><td>4277s</td><td>5384s</td><td>5s</td><td>4509s</td></tr></tbody></table>

## 3.3 Une nouvelle approche pour les attaques multivariées

Le contenu de cette partie est le fruit d'un travail mené conjointement avec nos partenaires de l'équipe Simula UiB à Bergen. On commence par établir un nouveau modèle algébrique du problème CICO pour GRIFFIN, dans lequel une nouvelle variable est introduite à chaque tour afin d'éviter l'explosion du degré par la puissance $1/d$.

Dans toute la suite, on considère une instance du problème CICO dont l'entrée est paramétrée par une seule variable $X$. À chaque tour $i \in \{1, \dots, R-1\}$, on rajoute une variable $Z_i$ qui modélise la première composante de l'état au tour $i-1$ élevée à la puissance $1/d$. On procède de même pour le tour initial et on rajoute donc une variable $Z_0$.

**Proposition 3.3.1.** Dans les conditions discutées ci-dessus, la modélisation algébrique du problème CICO associé à une permutation GRIFFIN à R tours prend la forme d'un idéal $I = (f_0, \dots, f_{R-1}, g)$ avec $f_i = Z_i^d - h_i$ où $h_i \in \mathbb{F}_p[X, Z_0, \dots, Z_{i-1}]$ et $g \in \mathbb{F}_p[X, Z_0, \dots, Z_{R-1}]$.

La proposition suivante donnera plus de détails, nous ne prouverons donc que cette dernière. L'idée est tout simplement d'écrire l'état du tour $i$ en fonction de toutes les variables introduites tout en gardant trace du lien entre la nouvelle variable $Z_i$ et les variables précédentes. On peut reprendre le schéma 3.1 avec cette modélisation pour obtenir la figure 3.2.

<figure><img src="image_6.png" /><figcaption>FIGURE 3.2 – État de GRIFFIN du tour $i$ au tour $i+1$, avec $\mathbf{Z}_i := (X, Z_1, \dots, Z_i)$.</figcaption></figure>

La figure 3.2 nous aide à établir la relation de récurrence entre les différents tours :

**Proposition 3.3.2.** L'état en sortie de la couche non linéaire du tour $i \in \{0, \dots, R-1\}$ est noté $(Z_i, P_i, Q_i)$. Si $(e_0(X), e_1(X), e_2(X))$ est l'entrée de la permutation, alors on a

$$ \begin{cases} P_0(X) = (e_0(X) + 2e_1(X) + e_2(X))^d \\ Q_0(X) = (e_0(X) + e_1(X) + 2e_2(X))((\gamma Z_0 + P_0)^2 + \alpha(\gamma Z_0 + P_0) + \beta). \end{cases} $$
Pour tout $i \in \{0, \dots, R-2\}$, on a les relations de récurrence

$$ egin{cases} P_{i+1} = (Z_i + 2P_i + Q_i + c_1^{(i)})^d \\ Q_{i+1} = (Z_i + P_i + 2Q_i + c_2^{(i)})(\gamma Z_{i+1} + P_{i+1})^2 + \alpha(\gamma Z_{i+1} + P_{i+1}) + \beta. \end{cases} \quad (2) $$

De plus, les polynômes de la proposition 3.3.1 valent, pour $i \ge 1$

$$ f_i = Z_i^d - 2Z_{i-1} - P_{i-1} - Q_{i-1} - c_0^{(i-1)} \text{ et } g = 2Z_{R-1} + P_{R-1} + Q_{R-1} $$

$$ \text{et enfin } f_0 = Z_0^d - 2e_0(X) - e_1(X) - e_2(X). $$

La proposition 3.3.2 permet de prédire le degré des différents polynômes intervenant dans l'idéal décrivant le problème CICO, et ce en chaque variable. L'idée de nos partenaires de Simula UiB a été d'exploiter la forme spécifique des polynômes $f_i$ pour éviter le calcul d'une base de Gröbner en définissant un ordre monomial adéquat.

**Définition 3.3.1** (Ordre pondéré). Soit $\mathbb{F}[X_1, \dots, X_n]$ un anneau de polynômes en $n$ variables sur un corps $\mathbb{F}$. On appellera ordre monomial pondéré de vecteur de poids $w = (w_1, \dots, w_n) \in \mathbb{Z}_{>0}^n$ tout ordre monomial < défini par

$$ X^{\alpha} < X^{\beta} \iff \left\{ \begin{array}{ll} \displaystyle \sum_{i=1}^{n} w_i \alpha_i < \sum_{i=1}^{n} w_i \beta_i & \\ \text{ou} & \\ \displaystyle \sum_{i=1}^{n} w_i \alpha_i = \sum_{i=1}^{n} w_i \beta_i \text{ et } \sum_{i=2}^{n} w_i \alpha_i < \sum_{i=2}^{n} w_i \beta_i & \text{etc.} \end{array} \right. $$

**Définition 3.3.2** (Ordre GRIFFIN). On considère cette fois l'anneau $\mathbb{F}_p[X, Z_0, \dots, Z_{R-1}]$ par lequel on modélise le problème CICO pour GRIFFIN. On appellera ordre GRIFFIN l'ordre monomial pondéré de vecteur de poids $w = (d, 2, 2d+2, (2d+1)^2+1, \dots, (2d+1)^{R-1}+1)$.

Cet ordre monomial est construit de manière à pouvoir prévoir les termes dominants des polynômes $f_i$. Nos collègues norvégiens avaient l'intuition qu'il fallait en effet poser, dans le cas $d=3$, la contrainte

$$ 3 \times wt(Z_i) > 7^i wt(X) $$

de façon à assurer que le monôme dominant de $f_i$ (noté $\text{LM}(f_i)$) soit égal à $Z_i^3$. Ils prévoyaient également que le monôme dominant de $g$ serait une puissance pure de $X$. Les termes dominants des différents polynômes sont deux à deux premiers entre eux, ce qui assure qu’ils forment une base de Gröbner. Une première contribution que j’ai apportée à ce stade a été de généraliser l’ordre GRIFFIN à $d$ quelconque et de rédiger une preuve des conjectures de nos collègues. Pour démontrer que cet ordre est bien choisi, commençons par le lemme suivant.

**Lemme 3.3.1.** On reprend les notations de la proposition 3.3.2. On suppose que les entrées $e_i(X)$ sont de degré $\le 1$, et que $e_0+2e_1+e_2$ et $e_0+e_1+2e_2$ sont de degré 1. Alors pour l'ordre GRIFFIN et pour tout $i \in \{0, \dots, R-1\}$,

$$ \text{LM}(P_i) = X^{d(2d+1)^i} \text{ et } \text{LM}(Q_i) = X^{(2d+1)^{i+1}}. $$

$$ \text{En conséquence, } \text{LM}(f_i) = Z_i^d \text{ et } \text{LM}(g) = X^{(2d+1)^R} $$
Démonstration. On procède par induction.

i = 0 : On a P₀(X) = (e₀(X)+2e₁(X)+e₂(X))ⁿ. Comme LM(e₀(X)+2e₁(X)+e₂(X)) = X par hypothèse, on a LM(P₀) = Xⁿ. Notons que Xⁿ > Z₀ car d × d > 2. Ainsi LM(Q₀) = X × LM(P₀)² = X × X²ⁿ = X²ⁿ⁺¹.

i = i + 1 : Soit i ∈ {0, ..., R − 2}. On suppose que le lemme est vrai au rang i. En utilisant les relations de récurrence (2) de la proposition 3.3.2, on obtient

$$
\mathrm{LM}(P_{i+1}) = \mathrm{LM}(Z_i + 2P_i + Q_i + c_1^{(i)})^d.
$$

Remarquons d'abord que Zᵢ < LM(Qᵢ) car (2d + 1)ᵢ + 1 < d × (2d + 1)ᵢ⁺¹. Ainsi,

$$
\mathrm{LM}(P_{i+1}) = \mathrm{LM}(Q_i)^d = X^{d(2d+1)^{i+1}}.
$$

De plus $\mathrm{LM}(P_{i+1}) > Z_{i+1} \ \mathrm{car} \ d \times d(2d+1)^{i+1} > (2d+1)^{i+1} + 1$. Ainsi,

$$
\begin{align*}
\mathrm{LM}(Q_{i+1}) &= \mathrm{LM}(Q_i) \times \mathrm{LM}(P_{i+1})^2 \\
&= X^{(2d+1)^{i+1}} \times X^{2d(2d+1)^{i+1}} \\
&= X^{(2d+1)^{i+1}(1+2d)} \\
&= X^{(2d+1)^{i+2}}.
\end{align*}
$$

Ainsi la première partie du lemme est prouvée. Comme $f_0 = Z_0^d - 2e_0(X) - e_1(X) - e_2(X)$, on a bien $\mathrm{LM}(f_0) = Z_0^d \ \mathrm{car} \ d \times 2 > d$. Pour $i \ge 1$, on a $f_i = Z_i^d - 2Z_{i-1} - P_{i-1} - Q_{i-1} - c_0^{(i-1)}$ et comme $d \times ((2d+1)^i + 1) > d \times (2d+1)^i$, le résultat s'ensuit. Enfin

$$
\mathrm{LM}(g) = \mathrm{LM}(2Z_{R-1} + P_{R-1} + Q_{R-1}) = \mathrm{LM}(Q_{R-1}) = X^{(2d+1)^R}
$$

et le lemme est démontré.

□

Les termes de tête de $f_i$ et de $g$ sont deux à deux premiers entre eux, ce qui nous conduit au résultat suivant.

**Proposition 3.3.3.** *Les polynômes {$f_0, \dots, f_{R-1}, g$} de la proposition 3.3.1 forment une base de Gröbner pour l'idéal qu'ils engendrent muni de l'ordre GRIFFIN.*

En conséquence, le coût de résolution du système algébrique devient essentiellement le temps
d'exécution de l'algorithme FGLM [8]. Cet algorithme nécessite que l'idéal *I* en question soit de
dimension 0, et sa complexité devient $O(RD_I^3)$ où $D_I = \dim_{\mathbb{F}_p}(\mathbb{F}_p[X, Z_0, \dots, Z_{R-1}]/I)$. Des expé-
riences sur le système de calcul formel magma ont conduit les chercheurs de Simula à conjecturer
que $D_I = 21^R$ dans le cas $d=3$ (ils avaient d'abord intuité ce résultat en utilisant la borne de
Bézout). J'ai pu apporter une preuve de ce résultat généralisé à un exposant *d* quelconque (pro-
position 3.3.4). Mon intuition était qu'il suffisait, pour calculer $D_I$, de compter les "monômes sous
l'escalier" comme illustré sur la figure 3.3.
<figure><img src="image_7.png" /><figcaption>FIGURE 3.3 – Illustration d'un quotient d'un anneau de polynômes. Les points blancs représentent les monômes non réductibles par la base de Gröbner. Ils engendrent le quotient en tant qu' $\mathbb{F}_p$-espace vectoriel.</figcaption></figure>

**Proposition 3.3.4.** L'idéal $I = (f_0, \dots, f_{R-1}, g)$ est $0$-dimensionnel et

$$D_I := \dim_{\mathbb{F}_p} (\mathbb{F}_p[X, Z_0, \dots, Z_{R-1}]/I) = (2d^2 + d)^R.$$

*Démonstration.* Les termes de tête d'une base de Gröbner de $I$ contiennent tous une puissance pure de chaque variable, donc l'espace vectoriel $\mathbb{F}_p[X, Z_0, \dots, Z_{R-1}]/I$ est de dimension finie. De plus, par définition d'une base de Gröbner [6], pour tout $f \in \mathbb{F}_p[X, Z_0, \dots, Z_{R-1}]$, il existe un unique polynôme multivarié $r$ tel que

* $f - r \in I$;

* aucun terme de $r$ n'est divisible par un de termes de tête de la base de Gröbner.

En d'autres termes, l'espace $\mathbb{F}_p[X, Z_0, \dots, Z_{R-1}]/I$ est engendré par les (classes des) monômes $X^\alpha Z_0^{\delta_0} \dots Z_{R-1}^{\delta_{R-1}}$ tels que

$$0 \le \alpha < (2d+1)^R \text{ et } 0 \le \delta_i < d \text{ pour } i = 0, \dots, R-1.$$

Ces (classes de) monômes induisent une famille libre dans le quotient par unicité du reste. Ainsi la dimension de l'espace quotient est-elle égale au nombre de tels monômes, qui vaut précisément $(2d+1)^R \times d \times \dots \times d = (2d^2 + d)^R$. $\square$

On connaît donc l'asymptotique de la complexité de la résolution du système algébrique décrivant le problème CICO pour GRIFFIN. La pertinence de ce modèle provient des remarques suivantes.

**Remarque 3.3.1.** Le nombre de variables ne varie pas avec le nombre de branches, pas plus que les degrés des polynômes. En revanche, le nombre de tours diminue avec le nombre de branches, ce qui résulte en un avantage considérable pour l'exécution de FGLM. En revanche, le temps de calcul des polynômes $f_i$ et $g$ croît avec le nombre de branches (linéairement en celui-ci). Mais il s'agit d'un coût que l'on peut s'autoriser à payer car l'avantage du côté de FGLM est cubique. Enfin, toute attaque visant à outrepasser un tour devient particulièrement pertinente, puisqu'elle divise par $(2d^2 + d)^3$ le coût de FGLM par tour passé.

**Remarque 3.3.2.** Les polynômes $f_i$ et $g$ étant de degré très élevé dans cette modélisation, il peut être intéressant de réduire ces polynômes à la volée pour gagner en espace mémoire au coût d'un
temps de calcul plus long pour la base de Gröbner. À chaque fois qu'une variable $Z_i$ apparaît à un degré $\ge 3$ dans l'un des calculs, on peut utiliser la relation $Z_i^3 = h_i(X, Z_0, \dots, Z_{i-1})$ pour faire descendre le degré en $Z_i$ à moins que 2. Ceci permet d'avoir recourt à moins de mémoire. Algébriquement, cela revient essentiellement à calculer $f_{i+1}$ dans $\mathbf{R}/(f_0, \dots, f_{i-1})$.
Conclusion

Ce travail s'est donc presque exclusivement orienté vers la résolution du problème CICO pour la permutation GRIFFIN. J'ai souhaité effectuer une étude du problème CICO pour une permutation aléatoire afin de pouvoir prédire le comportement des algorithmes mis en oeuvre pour sa résolution. Cette étude a mené à des résultats non triviaux aidant à anticiper le nombre de solutions sorties par les algorithmes.

Si GRIFFIN ne s'est pas révélé particulièrement vulnérable aux attaques algébriques univariées, les travaux menés dans cette direction ont néanmoins permis le développement d'un algorithme parallélisable pour ce type d'attaques. L'idée principale de ce résultat peut être réutilisée même dans le cas des attaques multivariées lorsque qu'une variable en particulier apparaît en haut degré au contraire de toutes les autres.

Les auteurs de GRIFFIN ont utilisé un type de schéma différent des SPN plus habituels, à savoir la construction Horst se rapprochant du schéma de Feistel. Ils ont ainsi réussi à n'avoir qu'une seule fonction puissance de haut degré par tour dans la couche non linéaire, ce qui rend GRIFFIN particulièrement efficace dans le cas où le nombre de branches est élevé. Cependant, bien qu'une telle couche non linéaire apporte de la diffusion dans la primitive, cela reste insuffisant pour se passer d'une couche linéaire solide. De plus, n'avoir qu'une seule fonction puissance de haut degré semble être un pari audacieux puisque c'est précisément cela qui permet à la dernière modélisation algébrique présentée dans ce travail d'être efficace, en particulier quand le nombre de branches augmente.
Références

[1] Martin R. Albrecht, Carlos Cid, Lorenzo Grassi, Dmitry Khovratovich, Reinhard Lüftenegger, Christian Rechberger, and Markus Schofnegger. Algebraic cryptanalysis of STARK-friendly designs : Application to MARVELlous and MiMC. In Steven D. Galbraith and Shiho Moriai, editors, *Advances in Cryptology – ASIACRYPT 2019, Part III*, volume 11923 of *Lecture Notes in Computer Science*, pages 371–397. Springer, Heidelberg, December 2019.

[2] Abdelrahaman Aly, Tomer Ashur, Eli Ben-Sasson, Siemen Dhooghe, and Alan Szepieniec. Design of symmetric-key primitives for advanced cryptographic protocols. Cryptology ePrint Archive, Report 2019/426, 2019. https://eprint.iacr.org/2019/426.

[3] Augustin Bariant, Clémence Bouvier, Gaëtan Leurent, and Léo Perrin. Algebraic attacks against some arithmetization-oriented primitives. *IACR Transactions on Symmetric Cryptology*, 2022(3):73–101, 2022.

[4] Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin, Eran Tromer, and Madars Virza. SNARKs for C : Verifying program executions succinctly and in zero knowledge. In Ran Canetti and Juan A. Garay, editors, *Advances in Cryptology – CRYPTO 2013, Part II*, volume 8043 of *Lecture Notes in Computer Science*, pages 90–108. Springer, Heidelberg, August 2013.

[5] Eli Biham and Adi Shamir. Differential cryptanalysis of DES-like cryptosystems. In Alfred J. Menezes and Scott A. Vanstone, editors, *Advances in Cryptology – CRYPTO’90*, volume 537 of *Lecture Notes in Computer Science*, pages 2–21. Springer, Heidelberg, August 1991.

[6] David Cox, John Little, and Donal OShea. *Ideals, Varieties, and Algorithms : An Introduction to Computational Algebraic Geometry and Commutative Algebra*. Springer Science & Business Media, 2013.

[7] Data encryption standard. National Bureau of Standards, NBS FIPS PUB 46, U.S. Department of Commerce, January 1977.

[8] Faugère, Jean-Charles and Gianni, Patrizia and Lazard, Daniel and Mora, Teo. Efficient computation of zero-dimensional Gröbner bases by change of ordering. *Journal of Symbolic Computation*, 16(4):329–344, 1993.

[9] Ariel Gabizon, Zachary J. Williamson, and Oana Ciobotaru. PLONK : Permutations over lagrange-bases for oecumenical noninteractive arguments of knowledge. Cryptology ePrint Archive, Report 2019/953, 2019. https://eprint.iacr.org/2019/953.

[10] Lorenzo Grassi, Yonglin Hao, Christian Rechberger, Markus Schofnegger, Roman Walch, and Qingju Wang. A new feistel approach meets fluid-SPN : Griffin for zero-knowledge applications. Cryptology ePrint Archive, Report 2022/403, 2022. https://eprint.iacr.org/2022/403.

[11] Lorenzo Grassi, Dmitry Khovratovich, Christian Rechberger, Arnab Roy, and Markus Schofnegger. Poseidon : A new hash function for zero-knowledge proof systems. In Michael Bailey and Rachel Greenstadt, editors, *USENIX Security 2021 : 30th USENIX Security Symposium*, pages 519–535. USENIX Association, August 2021.

[12] Mitsuru Matsui and Atsuhiro Yamagishi. A new method for known plaintext attack of FEAL cipher. In Rainer A. Rueppel, editor, *Advances in Cryptology – EUROCRYPT’92*, volume 658 of *Lecture Notes in Computer Science*, pages 81–91. Springer, Heidelberg, May 1993.

[13] Arnab Roy, Matthias Johann Steiner, and Stefano Trevisani. Arion : Arithmetization-oriented permutation and hashing from generalized triangular dynamical systems, 2023.
[14] Sinem Sav, Apostolos Pyrgelis, Juan Ramón Troncoso-Pastoriza, David Froelicher, Jean-Philippe Bossuat, Joao Sa Sousa, and Jean-Pierre Hubaux. POSEIDON: Privacy-preserving federated neural network learning. In *ISOC Network and Distributed System Security Symposium – NDSS 2021*. The Internet Society, February 2021.

[15] Serge Vaudenay. On the need for multipermutations : Cryptanalysis of MD4 and SAFER. In Bart Preneel, editor, *Fast Software Encryption – FSE’94*, volume 1008 of *Lecture Notes in Computer Science*, pages 286–297. Springer, Heidelberg, December 1995.
Annexe : démonstations des propositions de la sous-section 1.3

**Lemme 3.3.2.** Soient E un ensemble fini de cardinal n, A ⊂ E un sous-ensemble de cardinal k ≤ n et F : E → E une bijection aléatoire uniforme. Alors F(A) suit une loi uniforme parmi les sous-ensemble de cardinal k de E.

Démonstration. Soit $B \subset E$ de cardinal $k$. Pour prouver le lemme, il suffit de compter le nombre de permutations de $E$ qui envoient $A$ sur $B$. Une telle permutation est donnée par le choix, pour chaque élément de $A$, d’un élément de $B$ (ce qui implique $k!$ possibilités) ainsi que par le choix, pour chacun des $n-k$ éléments à l’extérieur de $A$, d’un des $n-k$ éléments à l’extérieur de $B$. Cela donne donc $k! \times (n-k)!$, de sorte que

$$ \mathbb{P}(F(A) = B) = \frac{k! \times (n-k)!}{n!} = \frac{1}{\binom{n}{k}}. $$

On retrouve bien une loi uniforme sur l'ensemble des sous-ensembles de E de cardinal k. $\square$

**Remarque 3.3.3.** Si $F : E \to E$ est une bijection aléatoire uniforme, alors alors son inverse $F^{-1}$ suit également une loi uniforme. Cela peut notamment être vu comme une conséquence du lemme précédent en considérant l'inversion en tant que permutation de l'ensemble des permutations de E.

Démonstration de la proposition 1.3.1. Soient donc $G : \mathbb{F}_p^t \to \mathbb{F}_p^t$ une bijection aléatoire uniforme et $S \subset \{0\} \times \mathbb{F}_p^{t-1}$. D'après la discussion précédente, $G^{-1}(\{0\} \times \mathbb{F}_p^{t-1})$ est un sous-ensemble (de $\mathbb{F}_p^t$) aléatoire uniforme de cardinal $p^{t-1}$. Il prend donc ses valeurs parmi $\binom{p^t}{p^{t-1}}$ possibilités. Pour conclure, il suffit, étant donné $S \subset \{0\} \times \mathbb{F}_p^{t-1}$, de compter le nombre de sous-ensembles $U \subset \mathbb{F}_p^t$ tels que $U \cap (\{0\} \times \mathbb{F}_p^{t-1}) = S$. Choisir un tel sous-ensemble se résume à choisir $p^{t-1} - |S|$ éléments dans $\mathbb{F}_p^\times \times \mathbb{F}_p^{t-1}$, ce qui donne $\binom{p^t-p^{t-1}}{|S|}$ choix possibles. On en déduit

$$ \mathbb{P}(\text{CICO}(G) = S) = \frac{\binom{p^t}{p^{t-1}} \binom{p^{t-1}}{|S|}}{\binom{p^t}{p^{t-1}}}. $$

On constate que cette quantité ne dépend que du cardinal de l'ensemble considéré. Par conséquent, pour tout $k \in \{0, \dots, p^{t-1}\}$, on a

$$ \mathbb{P}(|\text{CICO}(G)| = k) = \frac{\binom{p^{t-1}}{k} \binom{p^t-p^{t-1}}{p^{t-1}-k}}{\binom{p^t}{p^{t-1}}}, $$

ce qui correspond à une loi hypergéométrique de paramètres $(p^{t-1}, 1/p, p^t)$. $\square$

L'ensemble CICO(G) est donc un sous-ensemble aléatoire dont la loi ne dépend que du cardinal. Dans un tel cas, il est possible de calculer le cardinal de son intersection avec un sous-ensemble quelconque (déterministe). Essentiellement, l'espérance de ce cardinal est une fraction de l'espérance initiale correspondant au ratio du cardinal de l'ensemble par lequel on intersecte et du cardinal de l'espace ambiant.

**Lemme 3.3.3.** Soient E un ensemble fini de cardinal $n > 0$ et $U \subset E$ un sous-ensemble aléatoire tel qu'il existe une fonction $\Phi : \{0, \dots, n\} \to [0, 1]$ telle que pour tout $A \subset E$, $\mathbb{P}(U = A) = \Phi(|A|)$.

Alors pour tout sous-ensemble $A \subset E$, on a $\mathbb{E}[|A \cap U|] = \frac{|A| \times \mathbb{E}[|U|]}{|E|}.$
Démonstration. Soit $x \in E$. On va calculer la probabilité que $x \in U$. On a

$$ \mathbb{P}(x \in U) = \sum_{B \subset E, x \in B} \mathbb{P}(U = B) = \sum_{k=1}^{n} \binom{n-1}{k-1} \Phi(k) = \frac{1}{n} \sum_{k=0}^{n} k \binom{n}{k} \Phi(k) = \frac{\mathbb{E}[|U|]}{n}. $$

Soit $A \subset E$. Alors $|A \cap U| = \sum_{x \in A} 1_{x \in U}$, et en passant à l'espérance,

$$ \mathbb{E}[|A \cap U|] = \sum_{x \in A} \mathbb{E}[1_{x \in U}] = \sum_{x \in A} \mathbb{P}(x \in U) = \frac{|A| \times \mathbb{E}[|U|]}{n}. $$

Ainsi le lemme est démontré. $\square$

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

Démonstration de la proposition 1.3.2. Soit donc $G$ une permutation aléatoire uniforme de $\mathbb{F}_p^t$. En appliquant les résultats précédents, on trouve

$$ \mathbb{E}[|(d) \cap \text{CICO}(G)|] = \frac{p \times p^{t-2}}{p^{t-1}} = 1. $$

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

Démonstration de la proposition 1.3.3. Une fonction aléatoire $f : \mathbb{F}_p^{t-1} \to \mathbb{F}_p$ n'est rien d'autre qu'une collection de $p^{t-1}$ variables aléatoires indépendantes uniformes à valeurs dans $\mathbb{F}_p$. Ainsi $\mathscr{C}_f = S$ si et seulement si les $|S|$ variables correspondantes valent 0 (avec probabilité $1/p$) et si les $p^{t-1} - |S|$ autres variables sont non nulles (avec probabilité $p^{\frac{t-1}{p}}$). On en déduit

$$ \mathbb{P}(\mathscr{C}_f = S) = \frac{1}{p^{|S|}} \times \left(\frac{p-1}{p}\right)^{p^{t-1}-|S|} = \frac{(p-1)^{p^{t-1}-|S|}}{p^{p^{t-1}}}. $$

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