Infinite families of APN permutations in constrained trivariate classes over $\mathbb{F}_{2^m}$

1. Problématique et Contexte

La construction de polynômes de permutation sur les corps finis possédant une structure algébrique simple, tout en étant presque parfaitement non linéaires (APN), est un problème majeur en cryptographie et en théorie du codage. Les fonctions APN offrent une résistance optimale contre la cryptanalyse différentielle. Lorsqu'une telle fonction est également une permutation, elle constitue un bloc de construction idéal (S-box) combinant résistance différentielle et inversibilité.

Cependant, la construction d'APN permutations est notoirement difficile. Jusqu'à récemment, seules quelques familles infinies étaient connues, et l'existence de telles fonctions dans toutes les dimensions paires restait une question ouverte. Des travaux récents de Li et Kaleyski (2024) ont généralisé deux permutations APN quadratiques sporadiques (découvertes par Beierle et Leander en dimension 9) en deux familles infinies de fonctions trivariées sur $\mathbb{F}_{2^{3m}}$ avec des coefficients scalaires dans $\mathbb{F}_2$.

L'objectif de cet article est d'étendre ces travaux en permettant au coefficient scalaire $a$ de varier librement dans le corps $\mathbb{F}_{2^m}^*$, au lieu d'être restreint à 1. Les auteurs analysent deux familles généralisées, notées $G_a$ et $H_a$, et cherchent à caractériser leurs propriétés de permutation et APN, ainsi que leur équivalence avec les familles originales de Li-Kaleyski.

2. Méthodologie

Les auteurs utilisent une approche combinant l'algèbre linéaire, la théorie des corps finis et la géométrie algébrique.

• Définition des familles :
  Pour $m$ impair, $q=2^i$ avec $\gcd(i, m)=1$, et $a \in \mathbb{F}_{2^m}^*$, les deux familles sont définies sur $\mathbb{F}_{2^{3m}} \cong \mathbb{F}_{2^m}^3$ :

  1. $G_a(x, y, z) = (x^{q+1} + ax^qz + yz^q, \ x^qz + y^{q+1}, \ xy^q + ay^qz + z^{q+1})$
  2. $H_a(x, y, z) = (x^{q+1} + axy^q + yz^q, \ xy^q + z^{q+1}, \ x^qz + y^{q+1} + ay^qz)$

• Réduction à un problème univarié :
  La clé de la méthodologie est la réduction des propriétés de permutation et APN (qui concernent des systèmes d'équations multivariées complexes) à l'absence de racines d'un polynôme univarié spécifique dans $\mathbb{F}_{2^m}^*$.
  Les auteurs introduisent plusieurs polynômes équivalents (au sens de l'existence de racines non nulles), notamment :
  $$Q_a(T) = T^{q^2+q+1} + aT + 1$$
  Ils démontrent que la propriété de permutation et la propriété APN pour $G_a$ (et de manière analogue pour $H_a$) sont toutes deux équivalentes à l'absence de racines de $Q_a(T)$ dans $\mathbb{F}_{2^m}^*$.

• Outils de géométrie algébrique :
  Pour prouver l'existence de paramètres "bons" (c'est-à-dire des $a$ pour lesquels le polynôme n'a pas de racine), les auteurs étudient la courbe définie par l'équation $g(x) = g(y)$ où $g(u) = \frac{u^{d}+1}{u}$ et $d = q^2+q+1$. En utilisant le théorème de Hasse-Weil et le lemme d'Aubry-McGuire-Rodier, ils établissent que la courbe associée est absolument irréductible, ce qui permet de dériver une borne inférieure quantitative sur le nombre de tels paramètres.

• Étude de l'équivalence :
  L'équivalence CCZ (Carlet-Charpin-Zinoviev) est le critère standard pour distinguer les classes de fonctions APN. Pour les fonctions quadratiques avec $F(0)=0$, l'équivalence CCZ coïncide avec l'équivalence affine étendue (EA) et l'équivalence linéaire étendue (EL). Les auteurs analysent l'équivalence diagonale (un sous-ensemble de l'équivalence linéaire) pour déterminer quand les nouvelles familles sont équivalentes aux représentants originaux de Li-Kaleyski ($G_1$ et $H_1$).

3. Contributions et Résultats Clés

A. Caractérisation par les racines (Théorème 2.7 et 3.3)

Les auteurs prouvent que pour les familles $G_a$ et $H_a$, les trois conditions suivantes sont équivalentes :

1. Le polynôme $Q_a(T) = T^{q^2+q+1} + aT + 1$ n'a aucune racine dans $\mathbb{F}_{2^m}^*$.
2. La fonction est une permutation de $\mathbb{F}_{2^{3m}}$.
3. La fonction est APN sur $\mathbb{F}_{2^{3m}}$.

Cela réduit le problème complexe de la vérification APN/permutation à un problème de recherche de racines univarié. De plus, ils montrent que les conditions pour $G_a$ et $H_a$ sont "racine-équivalentes", impliquant que le même ensemble de paramètres $a$ fonctionne pour les deux familles.

B. Existence et Quantification (Théorème 2.12)

En utilisant la borne de Hasse-Weil sur la courbe de collision, les auteurs établissent une borne inférieure quantitative pour le nombre de paramètres $a$ "bons" (c'est-à-dire générant des permutations APN) :
$$|B_{m,q}| \geq 2^m + 1 - \frac{(d-1)(d-2)2^{m/2} - d}{d}$$
où $d = q^2+q+1$. Cela garantit l'existence d'une infinité de telles permutations pour tout $m$ impair.

C. Cas binaire ($q=2$) et récupération de Li-Kaleyski

Dans le cas où $q=2$ (donc $d=7$), les auteurs prouvent que $a=1$ est un bon paramètre si et seulement si $7 \nmid m$. Cela récupère exactement la famille de Li-Kaleyski. Pour $a \neq 1$ (et $7 \nmid m$), ils obtiennent de nouvelles permutations.

D. Résultats d'Inéquivalence (Théorèmes 4.2 et 4.5)

C'est l'une des contributions les plus significatives :

1. Équivalence avec les représentants originaux : $G_a$ (resp. $H_a$) est diagonalement équivalente à $G_1$ (resp. $H_1$) si et seulement si $a^{q^2+q+1} = 1$.
   • Pour $q=2$ et $7 \nmid m$, la condition $a^7=1$ implique $a=1$ (car $\gcd(7, 2^m-1)=1$). Ainsi, tous les autres paramètres bons $a \neq 1$ produisent des permutations APN CCZ-inequivalentes à celles de Li-Kaleyski.
2. Inéquivalence mutuelle entre familles : Pour $m > 4, m \neq 6$ et $7 \nmid m$, aucun membre de la famille $G_a$ n'est CCZ-équivalent à un membre de la famille $H_b$ (pour le même $q$).
   • Cela signifie que les deux familles fournissent des sources genuinément nouvelles et mutuellement inequivalentes de permutations APN.

4. Signification et Impact

• Expansion de l'ensemble connu : L'article démontre que les familles sporadiques découvertes par ordinateur ne sont pas des cas isolés, mais font partie de structures infinies beaucoup plus larges lorsque le coefficient scalaire est généralisé.
• Nouvelles classes CCZ : En prouvant que la plupart des paramètres $a$ génèrent des fonctions CCZ-inequivalentes aux connues, l'article enrichit considérablement le catalogue des S-boxes potentielles pour la cryptographie.
• Méthodologie robuste : La réduction du problème trivarié à un critère univarié via l'analyse des racines et l'utilisation de la géométrie algébrique pour l'existence offre un cadre puissant qui pourrait être appliqué à d'autres constructions de fonctions APN.
• Résolution de conjectures partielles : L'article confirme que la structure de Li-Kaleyski est un cas particulier ($a=1$) d'une famille plus large et établit rigoureusement l'existence de nouvelles classes pour $a \neq 1$.

5. Problèmes Ouverts

Les auteurs concluent en listant plusieurs questions ouvertes :

1. Caractériser algébriquement les bons paramètres $a$ lorsque $7 \mid m$ (cas où $a=1$ échoue).
2. Étendre les permutations trouvées pour $m=3$ à des familles infinies pour $m$ plus grands.
3. Étudier si des résultats analogues existent pour les dimensions paires ($m$ pair).
4. Généraliser ces constructions à des fonctions $n$-variées ($n > 3$).

En résumé, cet article fournit une caractérisation complète et quantitative de deux nouvelles familles infinies de permutations APN, prouvant leur richesse structurelle et leur inéquivalence avec les constructions connues, ce qui représente une avancée majeure dans la théorie des fonctions APN sur les corps finis.