Résumé technique : Complexité de la résolution de systèmes d'équations de même degré

Énoncé du problème

La sécurité de nombreux schémas cryptographiques, particulièrement en cryptographie multivariée et dans les contextes post-quantiques, repose sur la difficulté computationnelle de résoudre des systèmes d'équations polynomiales multivariées sur des corps finis. La complexité de la résolution de tels systèmes via les méthodes de bases de Gröbner est principalement régie par le degré de régularité ($d_{reg}$) et le degré de résolution (solving degree). Bien que le degré de régularité fournisse une borne supérieure sur la complexité des calculs de bases de Gröbner, il est souvent difficile de le calculer ou de l'estimer pour des systèmes de taille cryptographique.

La pratique courante repose sur l'hypothèse heuristique que les systèmes sont semi-réguliers (ou cryptographiquement semi-réguliers), ce qui permet d'obtenir des formules explicites pour le degré de régularité. Cependant, cette hypothression n'est pas toujours valide ; il existe des choix de paramètres et des corps où aucune séquence semi-régulière n'existe. Par conséquent, il est nécessaire d'établir des bornes supérieures prouvées, non heuristiques, sur le degré de régularité et le degré de résolution qui s'appliquent aux systèmes où le degré de régularité est fini, sans dépendre de l'hypothèse de semi-régularité.

Méthodologie

Les auteurs abordent le problème en utilisant des outils de l'algèbre commutative, en se concentrant spécifiquement sur les systèmes où l'idéal généré par les parties de plus haut degré des polynômes contient une séquence régulière de $n$ polynômes dans un degré $D$ donné.

1. Cadre : Le document considère un système $F = \{f_1, \dots, f_m\}$ de $m$ polynômes en $n$ variables sur un corps $F$. L'analyse suppose que les parties de plus haut degré $f_1^{top}, \dots, f_m^{top}$ sont linéairement indépendantes et que le système est régulier au degré $D$ (ce qui signifie que l'idéal généré par les parties de plus haut degré contient une séquence régulière de $n$ polynômes de degré $D$).
2. Réduction aux idéaux LPP : Pour borner la régularité de Castelnuovo-Mumford (qui est égale au degré de régularité quand celui-ci est fini), les auteurs utilisent la conjecture d'Eisenbud-Green-Harris (EGH). Cette conjecture postule que, parmi tous les idéaux homogènes contenant une séquence régulière de degrés spécifiques, l'idéal Lex-Plus-Powers (LPP) possède la régularité maximale.
3. Analyse combinatoire : Les auteurs construisent des idéaux LPP spécifiques associés aux paramètres donnés ($n, m, D$). En analysant la structure de ces idéaux sous l'ordre lexicographique, ils déterminent la régularité de l'idéal LPP, qui sert de borne supérieure pour la régularité du système original (sous réserve de la conjecture EGH).
4. Équations de corps : La méthodologie est étendue aux systèmes augmentés par des équations de corps ($x_i^q - x_i$), ce qui est crucial pour les systèmes sur des corps finis $\mathbb{F}_q$, particulièrement lorsque le degré des équations $D$ est supérieur ou égal à la taille du corps $q$.

Contributions clés et résultats

1. Bornes supérieures pour les systèmes réguliers au degré $D$ (sans équations de corps)

Le Théorème 23 fournit une borne supérieure précise pour le degré de régularité d'un système de $m$ équations de degré $D$ en $n$ variables, en supposant que le système est régulier au degré $D$.

• La borne dépend du nombre d'équations ($m$), de variables ($n$) et du degré ($D$).
• La formule implique l'identification d'entiers uniques $k$ et $t$ tels que $m-n$ se situe dans un intervalle spécifique défini par des sommes combinatoires ($\sigma_{k,t}$).
• La borne résultante est : $d_{reg}(F) \le (D - t) + (n - k)(D - 1)$.
• Cette borne est étroite (sharp) pour toutes les valeurs de $m, n, D$ et est atteinte par les systèmes où les parties de plus haut degré forment un idéal LPP spécifique.

Le Corollaire 27 traduit cela en une borne supérieure sur le degré de résolution pour les algorithmes mutants :
$$\text{solv. deg}_m(F) \le D - t + 1 + (n - k)(D - 1)$$

2. Bornes supérieures pour les systèmes avec équations de corps

Le document traite du cas où les équations de corps sont ajoutées au système, ce qui est essentiel lorsque $D \ge q$.

• Proposition 31 : Pour les systèmes très surdéterminés (où $m$ dépasse la dimension de l'espace des polynômes modulo les équations de corps), le degré de régularité est exactement $D$.
• Théorème 33 : Pour les systèmes où $q \le D \le n(q-1)$ et où les parties de plus haut degré sont linéairement indépendantes modulo les équations de corps, les auteurs fournissent une borne supérieure sur le degré de régularité.
  • La borne est dérivée de la position du $m$-ième monôme dans l'ordre lexicographique des monômes de degré $D$ modulo $(x_1^q, \dots, x_n^q)$.
  • La borne est exprimée en termes de $B = q - t + (n - k)(q - 1)$, où $k$ et $t$ sont déterminés par l'intervalle contenant $m$.
  • Selon les conditions spécifiques concernant $m, D$ et $t$, la borne est soit $B$, soit $B-1$.

Le Corollaire 34 spécialise ces résultats pour les systèmes binaires ($q=2$), fournissant des formules simplifiées pour le degré de régularité et le degré de résolution pour les systèmes de degré $D$ sur $\mathbb{F}_2$.

3. Application à des schémas spécifiques

Les auteurs appliquent leurs bornes à des schémas cryptographiques concrets :

• Cubic Simple Matrix : Ils dérivent une borne prouvée $d_{reg} \le 2n - 1$, ce qui constitue la première borne prouvée pour ce système, contrastant avec les estimations heuristiques précédentes.
• Unbalanced Oil and Vinegar (UOV) : Les bornes sont appliquées aux systèmes UOV sur $\mathbb{F}_2$, démontrant comment le degré de régularité se comporte lorsque les équations de corps sont incluses.

Signification et affirmations

Le document affirme sa signification principalement en fournissant des bornes prouvées et non heuristiques sur la complexité de la résolution de systèmes polynomiaux.

• Fiabilité : Contrairement aux estimations basées sur l'hypothèse de semi-régularité (qui peut échouer pour certains paramètres), ces bornes s'appliquent à tout système où le degré de régularité est fini et où le système est régulier dans un degré donné.
• Généralité : Les résultats s'appliquent à des systèmes sur des corps arbitraires et couvrent à la fois les cas avec et sans équations de corps.
• Précision (Sharpness) : Les bornes sont décrites comme étant « étroites » (sharp), ce qui signifie qu'elles sont atteintes par des systèmes spécifiques (idéaux LPP), offrant ainsi une estimation réaliste du pire cas pour l'analyse de sécurité.
• Limites : Les auteurs reconnaissent explicitement que leurs bornes sont généralement moins serrées (c'est-à-dire plus élevées) que celles obtenues sous l'heuristique de la semi-régularité. Cependant, ils soutiennent que ce compromis est nécessaire pour éviter des hypothèses non prouvées, particulièrement dans les scénarios où les séquences semi-régulières n'existent pas.

Le travail ne propose pas de nouveaux algorithmes ou implémentations expérimentales, mais établit plutôt les limites théoriques de la complexité des méthodes de bases de Gröbner existantes (tant standards que mutantes) pour une large classe de systèmes polynomiaux pertinents pour la cryptographie.