Almost All Vectorial Functions Have Trivial Extended-Affine Stabilizers

Les auteurs démontrent qu'asymptotiquement presque toutes les fonctions vectorielles sur les corps finis possèdent un stabilisateur affine étendu trivial, ce qui implique que le nombre de classes d'équivalence est asymptotiquement égal à l'estimation naïve et que les fonctions avec des stabilisateurs non triviaux constituent un sous-ensemble exponentiellement rare, validant ainsi les stratégies d'échantillonnage aléatoire pour la conception de primitives cryptographiques.

L'essentiel

Voici une explication simple de ce papier de recherche, imagée comme si nous parlions d'un immense atelier de design plutôt que de mathématiques pures.

Le Grand Atelier des S-Boxes

Imaginez un immense atelier où l'on fabrique des S-Boxes. Ce sont des pièces maîtresses (des "cadenas" mathématiques) utilisées pour sécuriser vos communications, vos paiements et vos données. Ces pièces sont en réalité des fonctions mathématiques complexes qui transforment des nombres d'entrée en nombres de sortie.

Le problème, c'est qu'il y a des milliards de milliards de façons de construire ces pièces. Les cryptographes doivent en trouver de nouvelles qui sont très résistantes aux attaques. Mais comment savoir si deux pièces sont vraiment différentes ou si elles ne sont que des copies déguisées ?

C'est là que l'article intervient avec deux concepts clés :

1. L'Équivalence EA (Extended-Affine) : C'est comme dire que deux S-Boxes sont "identiques" si l'on peut les transformer l'une en l'autre en faisant simplement des rotations, des translations ou des mélanges simples (comme changer la couleur d'un objet sans changer sa forme).
2. Le Stabilisateur : C'est la mesure de la "symétrie" ou de la "rigidité" d'une pièce.
   • Si une pièce a un stabilisateur non trivial, c'est qu'elle possède une symétrie cachée : on peut la tourner ou la modifier légèrement et elle reste exactement la même. C'est comme une roue de vélo parfaitement ronde : peu importe comment vous la tournez, elle a l'air identique.
   • Si une pièce a un stabilisateur trivial, elle est unique et asymétrique. La moindre modification la change irrémédiablement.

La Grande Découverte : "Presque tout le monde est unique"

L'auteur, Keita Ishizuka, a prouvé quelque chose de très contre-intuitif mais rassurant :

Presque toutes les S-Boxes possibles sont "asymétriques" (elles ont un stabilisateur trivial).

Pour utiliser une analogie :
Imaginez que vous prenez une poignée de sable et que vous essayez de trouver un grain de sable qui a la forme parfaite d'une étoile de mer. C'est presque impossible. La plupart des grains de sable sont juste des petits cailloux irréguliers.
De la même manière, si vous choisissez une fonction mathématique au hasard dans l'immense univers des possibilités, il y a une probabilité quasi nulle qu'elle ait une symétrie cachée (un stabilisateur non trivial). Elle sera unique, "bizarre" et ne ressemblera à aucune autre par simple transformation.

Pourquoi est-ce une bonne nouvelle ?

Cela répond à deux questions cruciales pour les créateurs de systèmes de sécurité :

1. Le comptage (Combien de modèles différents existe-t-il ?)
Avant, on ne savait pas exactement combien de classes de S-Boxes différentes existaient. On devait faire des calculs complexes.

• L'analogie : Imaginez que vous avez un tas de 1 million de chaussettes. Si vous savez que presque aucune chaussette n'est "symétrique" (qu'on ne peut pas la retourner pour qu'elle ressemble à une autre), alors le nombre de paires uniques est simplement : Nombre total de chaussettes divisé par 2.
• Le résultat : L'article dit que le nombre de classes uniques est simplement le nombre total de fonctions divisé par le nombre de façons de les transformer. C'est une formule simple et exacte !

2. La recherche au hasard (Est-ce utile de tirer au sort ?)
Les cryptographes cherchent souvent de nouvelles S-Boxes en générant des fonctions au hasard (comme lancer des dés).

• Le risque : Si beaucoup de fonctions étaient des copies les unes des autres (ou avaient des symétries), on risquerait de passer des années à redécouvrir la même chose sous un autre nom. C'est comme chercher une aiguille dans une botte de foin, mais où toutes les aiguilles sont collées ensemble.
• La révélation : Puisque presque toutes les fonctions sont uniques, si vous en générez deux au hasard, il est statistiquement impossible qu'elles soient équivalentes. La probabilité de "collision" (trouver deux fonctions identiques) est si faible qu'elle est pratiquement nulle (plus petite que la probabilité de gagner à la loterie plusieurs fois de suite).

En résumé

Ce papier nous dit que l'univers des fonctions mathématiques utilisées en cryptographie est immense et incroyablement diversifié.

• Les fonctions "spéciales" (celles qui ont des symétries cachées) sont des rares exceptions, aussi rares que des étoiles filantes dans un ciel étoilé.
• La grande majorité des fonctions sont uniques.
• Conclusion pratique : Les chercheurs peuvent continuer à générer des fonctions au hasard pour trouver de nouvelles clés de sécurité sans avoir peur de perdre leur temps à redécouvrir ce qu'ils ont déjà. La méthode du "hasard" est non seulement efficace, mais elle est garantie de produire des résultats uniques.

C'est une validation mathématique puissante qui rassure sur la richesse et la diversité des outils disponibles pour protéger nos données.

Résumé technique

Voici un résumé technique détaillé de l'article « Almost All Vectorial Functions Have Trivial Extended-Affine Stabilizers » (Presque toutes les fonctions vectorielles ont des stabilisateurs affines étendus triviaux) par Keita Ishizuka.

1. Problématique et Contexte

Les fonctions booléennes vectorielles (applications de $\mathbb{F}_q^n$ vers $\mathbb{F}_q^m$) sont des composants fondamentaux de la cryptographie symétrique, servant notamment de boîtes de substitution (S-boxes) dans les chiffrements par blocs et les fonctions de hachage. La classification de ces fonctions repose sur des relations d'équivalence qui préservent leurs propriétés cryptographiques, telles que l'uniformité différentielle, le spectre de Walsh et le degré algébrique.

Deux relations d'équivalence majeures sont étudiées :

• Équivalence Affine Étendue (EA) : Deux fonctions sont EA-équivalentes si l'une peut être obtenue à partir de l'autre par composition avec des permutations affines sur le domaine et l'image.
• Équivalence CCZ (Carlet-Charpin-Zinoviev) : Une généralisation de l'équivalence EA basée sur l'équivalence affine des graphes des fonctions.

Deux questions fondamentales restent ouvertes concernant la structure de ces espaces de fonctions :

1. Classification : Combien existe-t-il de classes d'équivalence EA distinctes ? Le nombre réel correspond-il à l'estimation « naïve » (nombre total de fonctions divisé par la taille du groupe d'équivalence) ?
2. Échantillonnage aléatoire : Lors de la recherche de fonctions possédant des propriétés cryptographiques spécifiques (comme les fonctions APN ou AB) par génération aléatoire, quel est le risque de redondance (c'est-à-dire de retomber sur une fonction déjà découverte mais EA-équivalente) ?

Ces questions dépendent directement de la structure des stabilisateurs (le sous-groupe des transformations qui laissent une fonction inchangée). Si les stabilisateurs sont triviaux (ne contenant que l'identité), les classes d'équivalence sont de taille maximale, et l'estimation naïve est exacte.

2. Méthodologie

L'auteur utilise une approche probabiliste et combinatoire basée sur la théorie des groupes et le lemme de Burnside. La méthodologie se décompose en plusieurs étapes clés :

• Analyse des points fixes : L'étude commence par l'analyse des permutations affines non triviales. L'auteur démontre que pour une permutation affine $\sigma(x) = Px + a$ non triviale, l'ensemble des points fixes est soit vide, soit un sous-espace affine de dimension au plus $n-1$. Cela limite le nombre d'orbites de $\sigma$.
• Bornes sur les fonctions invariantes : Pour un élément non trivial $g = (A_{out}, A_{in})$ du groupe EA, l'auteur borne le nombre de fonctions $F$ telles que $g \cdot F = F$ (c'est-à-dire $A_{out} \circ F \circ A_{in} = F$).
  • En décomposant l'espace d'entrée en orbites sous l'action de la permutation d'entrée, il montre que la valeur de $F$ sur une orbite est fortement contrainte.
  • Il établit que le nombre de telles fonctions fixes est borné par $c^{mq^n}$ où $c < 1$ est une constante indépendante de la dimension $n$.
• Application de la borne d'union : En utilisant le théorème de l'union des probabilités, l'auteur somme les probabilités qu'une fonction aléatoire soit fixée par au moins un élément non trivial du groupe.
• Théorème de l'orbite-stabilisateur et Lemme de Burnside : Ces outils sont utilisés pour relier la taille des stabilisateurs au nombre total de classes d'équivalence et aux probabilités de collision.

3. Contributions Clés et Résultats Principaux

Le papier apporte les résultats suivants :

A. Théorème Principal : Trivialité Asymptotique des Stabilisateurs

Le résultat central (Théorème 3.4) prouve que pour une fonction vectorielle choisie uniformément au hasard dans l'espace des fonctions $\mathbb{F}_q^n \to \mathbb{F}_q^m$, la probabilité d'avoir un stabilisateur EA non trivial décroît super-exponentiellement avec la dimension.

• Formellement : $P(\text{Stab}(F) \neq \{id\}) \leq q^{-\Omega(m q^n)}$.
• Conséquence : Presque toutes les fonctions vectorielles ont un stabilisateur trivial. Les fonctions avec des stabilisateurs non triviaux forment un sous-ensemble exponentiellement rare.

B. Comptage des Classes d'Équivalence

En conséquence directe du résultat précédent, le nombre de classes d'équivalence EA est asymptotiquement égal à l'estimation naïve :
$$|\mathcal{F}/\Gamma| \sim \frac{|\mathcal{F}|}{|\Gamma|}$$
où $|\mathcal{F}| = q^{mq^n}$ est le nombre total de fonctions et $|\Gamma|$ la taille du groupe EA. L'erreur relative tend vers zéro. Cela confirme que l'action du groupe est asymptotiquement libre.

C. Probabilités de Collision

L'auteur dérive des bornes supérieures pour la probabilité que deux fonctions indépendamment échantillonnées soient équivalentes :

• Pour l'équivalence EA : La probabilité de collision est asymptotiquement égale à $|\Gamma| / |\mathcal{F}|$, soit $q^{-\Omega(q^n)}$.
• Pour l'équivalence CCZ : Des bornes supérieures similaires sont établies, bien que la question de la trivialité des stabilisateurs CCZ pour presque toutes les fonctions reste ouverte.
• Exemple concret (S-boxes 8-bit) : Pour des paramètres cryptographiques standards ($n=m=8, q=2$), la probabilité qu'une S-box aléatoire ait un stabilisateur non trivial est inférieure à $2^{-368}$, et la probabilité de collision EA est d'environ$2^{-1900}$.

4. Signification et Implications

Les résultats de cet article ont des implications majeures pour la conception de primitives cryptographiques :

1. Validation de l'échantillonnage aléatoire : Les stratégies de recherche par génération aléatoire de fonctions (pour trouver des fonctions APN, AB, ou d'autres propriétés optimales) sont validées théoriquement. Le risque de redondance (trouver plusieurs fois la même classe d'équivalence) est négligeable. Les chercheurs peuvent explorer l'espace des fonctions sans se soucier de la sur-représentation de certaines classes dues à des stabilisateurs non triviaux.
2. Structure de l'espace cryptographique : Il est démontré que les fonctions ayant des symétries internes (stabilisateurs non triviaux) sont extrêmement rares. La grande majorité des fonctions cryptographiques se trouvent dans des classes d'équivalence de taille maximale.
3. Simplification des modèles théoriques : Pour les dimensions élevées (pertinentes pour les chiffrements modernes comme AES), il est désormais justifié de supposer que l'action du groupe EA est libre, simplifiant ainsi les modèles de comptage et d'analyse de complexité.

En résumé, cet article établit que l'« exception » (les fonctions avec symétries) est statistiquement inexistante dans l'espace des fonctions vectorielles de grande dimension, fournissant une fondation théorique solide pour les méthodes de conception cryptographique basées sur le hasard.