🔢 mathématiques

Constructing Complete Permutations via the D-Class of Locally Crooked Permutations

Cet article introduit la classe D des permutations sur $\mathbb{F}_{2^{n+1}}$ pour caractériser et construire des permutations complètes via des conjugaisons locales, établissant leurs propriétés algébriques, leurs bornes cryptographiques et leur inéquivalence CCZ, tout en présentant des algorithmes qui énumèrent avec succès de nouvelles permutations complètes de $\delta=4$ .

Auteurs originaux : Li Shuai

Publié 2026-10-16

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Li Shuai

Article original sous licence CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Dans l'architecture cachée de la sécurité numérique moderne, il existe une classe d'objets mathématiques connus sous le nom de permutations complètes. Celles-ci ne sont pas de simples mélanges aléatoires de nombres ; ce sont des réarrangements hautement structurés où l'acte de déplacer un élément vers une nouvelle position et l'acte de le déplacer vers une position qui est la somme de son ancienne et de sa nouvelle position résultent tous deux en un ordre parfait et non chevauchant. Cette double exigence est cruciale pour la conception des boîtes de substitution, ou S-boxes, qui sont les composants primaires des systèmes de chiffrement qui brouillent les données pour en cacher le sens. Si ces composants sont trop prévisibles, le chiffrement peut être cassé ; s'ils sont trop chaotiques, ils deviennent inefficaces. Le défi pour les cryptographes a longtemps été de trouver le juste milieu : des permutations suffisamment complexes pour résister aux attaques sophistiquées, mais assez structurées pour être implémentées rapidement.

Une étude récente de Li Shuai, de l'Université de Ningxia, s'attaque à ce défi en explorant une famille spécifique de ces permutations à travers le prisme de la symétrie géométrique. La recherche se concentre sur une propriété appelée « courbure locale » (local crookedness), qui décrit comment une permutation se comporte lorsque son entrée est décalée d'une quantité spécifique. L'auteur introduit une nouvelle catégorie de ces fonctions, définie par un motif spécifique dans la manière dont leurs sorties changent. En traitant ces fonctions comme des éléments d'un groupe plus large qui peut être transformé par décalage, rotation ou échange de parties spécifiques des données, l'étude cartographie un paysage de possibilités. L'objectif était de voir si le mouvement au sein de ce paysage pouvait générer de nouvelles permutations supérieures offrant une meilleure protection contre la cryptanalyse différentielle, une méthode où les attaquants étudient comment de petits changements dans l'entrée affectent la sortie pour déduire la clé secrète.

Le cœur du travail implique une chaîne de construction qui part d'une permutation connue et bien élevée, puis applique une série d'opérations algébriques précises pour créer de nouvelles permutations. L'auteur définit un ensemble de règles spécifiques, ou « classe-D », que ces permutations doivent suivre pour rester valides. Au sein de cet ensemble, le chercheur prouve que la collection de permutations « levées » (lifted) — celles qui ont été étendues d'un espace plus petit vers un espace plus grand — possède une rigidité unique. Si l'on tente de modifier une seule permutation en utilisant un seul type d'opération, telle qu'un simple décalage ou une rotation linéaire, le résultat échoue généralement à rester une permutation complète valide. Cependant, l'étude démontre que la combinaison de deux opérations différentes dans une séquence spécifique brise cette rigidité. Cette combinaison permet au chercheur de naviguer dans l'espace des possibilités, passant d'une permutation valide à une autre sans perdre les propriétés essentielles requises pour la sécurité.

Pour rendre ce cadre théorique pratique, l'article développe deux algorithmes distincts. Le premier est une recherche par retour sur trace (backtracking) qui construit une permutation complète à partir de zéro, en veillant à chaque étape que les doubles exigences d'ordonnancement soient respectées. Le second est une recherche locale gloutonne (greedy local search) qui part d'une permutation existante et tente de l'améliorer en appliant les opérations combinées décrites précédemment. Cet algorithme agit comme un grimpeur cherchant un sommet plus élevé : il teste diverses petites modifications, mais n'accepte un changement que s'il améliore strictement la qualité cryptographique de la permutation. La qualité est mesurée par deux indicateurs principaux : l'uniformité différentielle, qui compte la fréquence du pire cas des motifs de sortie, et la non-linéarité, qui mesure l'écart entre la fonction et une simple équation linéaire. Une uniformité différentielle plus faible et une non-linéarité plus élevée sont généralement préférables pour la sécurité.

Les chercheurs ont testé ces méthodes sur un espace mathématique spécifique de taille 32, ce qui correspond à un système de 5 bits. En partant d'une permutation linéaire simple connue pour être faible, l'algorithme de recherche gloutonne a été exécuté cent fois. Les expériences ont produit plusieurs permutations ayant une uniformité différentielle de 4, une amélioration significative par rapport à la valeur de départ de 32. L'étude a également commencé avec cent permutations générées aléatoirement et a appliqué le même processus de recherche. Là encore, l'algorithme a systématiquement trouvé des permutations avec une uniformité différentielle de 4. Les résultats n'étaient pas seulement la découverte de meilleurs nombres ; les nouvelles permutations possédaient des « spectres » distincts, ou des motifs de fréquences de sortie, qui étaient différents les uns des autres et du point de départ. Cela prouve que la méthode ne produit pas seulement des variations d'un même objet, mais découvre véritablement de nouvelles classes distinctes de permutations sécurisées.

L'une des découvertes les plus frappantes concerne la relation entre ces nouvelles permutations et une classe célèbre de fonctions connues sous le nom de fonctions APN (Almost Perfect Nonlinear). Historiquement, de nombreuses constructions de permutations sécurisées reposaient sur le fait de partir de ces fonctions APN. Cependant, l'étude a révélé que les permutations générées par cette nouvelle méthode de conjugaison locale, bien qu'ayant la même excellente uniformité différentielle de 4, sont CCZ-inéquivalentes à celles dérivées des approches APN classiques. En fait, une permutation de référence basée sur une fonction APN bien connue a obtenu de moins bons résultats dans ce test spécifique, avec une uniformité différentielle de 8. Cela suggère que la nouvelle méthode explore une région différente du paysage mathématique, découvrant des permutations de haute qualité qui étaient auparavant inaccessibles aux techniques de construction standards.

L'article conclut en proposant une conjecture basée sur les preuves expérimentales : que l'ensemble de ces permutations levées est connecté. En d'autres termes, il semble possible d'atteindre toute permutation valide de cette famille à partir de n'importe quelle autre en suivant un chemin de ces modifications locales spécifiques. Bien que cette connectivité n'ait pas été mathématiquement prouvée, le fait que l'algorithme de recherche ait systématiquement trouvé des solutions de haute qualité à partir de points de départ divers fournit un solide soutien préliminaire à cette idée. L'étude laisse également ouverte la question de savoir si cette famille spécifique de permutations contient des fonctions encore plus fortes que celles trouvées, pouvant potentiellement atteindre la limite théorique de sécurité connue sous le nom d'APN. Pour l'instant, ce travail fournit un nouvel ensemble d'outils robustes pour générer des permutations sécurisées, démontrant qu'en comprenant les symétries locales de ces objets mathématiques, on peut construire de meilleures défenses pour le monde numérique.

Résumé Technique : Construction de Permutations Complètes via la Classe-D des Permutations Localement Tordues

Énoncé du Problème

Le document traite de la construction de Permutations Complètes (CP) sur les corps finis $\mathbb{F}_{2^n}$ . Une permutation $f$ est une CP si $f$ et l'application $x \mapsto f(x) + x$ sont toutes deux des permutations. Les CP sont cruciales en cryptographie, spécifiquement comme blocs de construction pour les boîtes S dans le cadre de Lai–Massey et pour la génération de carrés latins orthogonaux.

Bien que les CP soient liées aux Permutations Localement Tordues (LCP) sur $\mathbb{F}_{2^{n+1}}$ via la correspondance de Shuai–Li, les méthodes précédentes reposaient sur un chemin « fonction tordue $\to$ LCP $\to$ CP ». Cette approche était restrictive, car elle ne permettait pas de mouvement libre ou de génération de nouvelles LCP au sein de la classe elle-même. Le présent article cherche à surmonter cela en travaillant directement à l'intérieur de la classe LCP pour générer de nouvelles CP par des actions de groupes internes, augmentant ainsi l'espace de recherche des permutations cryptographiquement fortes.

Méthodologie

1. La Classe-D et l'Invariance

L'auteur introduit la classe-D, définie comme l'ensemble des permutations $f$ sur $\mathbb{F}_{2^{n+1}}$ telles que la dérivée dans une direction fixe $q_1 = 2^n$ a une image égale au complément d'un hyperplan fixe $H = \{x : x_n = 0\}$ .
$D = \{f \in S_q : \text{Im } \Delta_{q_1}f = K\}$
où $K = \mathbb{F}_{2^{n+1}} \setminus H$ .

L'article prouve que $D$ est fermé sous trois actions de groupes spécifiques :

Translation à gauche : $t_a \circ f$ pour tout $a \in \mathbb{F}_q$ .
Multiplication à gauche : $g \circ f$ pour tout $g$ dans le groupe linéaire général préservant $H$ ( $GL_H$ ).
Multiplication à droite : $f \circ h$ pour tout $h$ dans le centralisateur $C$ de l'involution permutant $H$ et $K$ .

De plus, la classe est fermée sous des translations locales spécifiques $t_{a,X}$ (translations restreintes à un sous-ensemble $X$ ) à condition que $X$ soit une union d'orbites d'un groupe diédral spécifique généré par la translation et l'involution conjuguée.

2. Rigidité et la Chaîne de Construction

L'auteur définit la sous-classe de CP élevée $D^\uparrow \subset D$ , composée des permutations de $D$ qui agissent comme l'identité sur le complément $K$ .

Rigidité : L'article prouve que $D^\uparrow$ est « rigide » sous toute opération unique issue des propriétés de fermeture ci-dessus (translation, multiplication linéaire, ou multiplication par le centralisateur). Une opération unique ne peut pas transformer une CP élevée en une autre CP élevée, à moins qu'elle ne soit l'identité.
Chaîne de Construction : Pour générer de nouvelles CP, l'auteur construit une chaîne impliquant un produit d'opérations :
$CP \xrightarrow{\text{élévation}} LCP \xrightarrow{\text{translation locale}} LCP' \xrightarrow{\text{correction par le centralisateur}} LCP'' \xrightarrow{\text{restriction}} \text{Nouvelle } CP$
Cette chaîne utilise des éléments de centralisateur localisés ( $g_{a,X_1}$ et $g_{a,X_2}$ ) pour « réparer » le défaut introduit par les translations locales, garantissant que le résultat reste dans $D^\uparrow$ .

3. Conjugaisons Locales

La construction produit deux conjugaisons locales spécifiques, $f_1$ et $f_2$ , définies sur le corps de base $\mathbb{F}_{2^n}$ :

$f_1$ : Une modification de $f$ sur un sous-ensemble $X_1 \subset H$ où $X_1$ est invariant sous un groupe diédral.
$f_2$ : Une modification impliquant l'inverse de $f$ sur un sous-ensemble $X_2$ où $X_2$ est invariant sous un groupe cyclique.
L'article fournit les conditions nécessaires et suffisantes pour que ces applications modifiées restent des CP.

4. Algorithmes

Deux algorithmes sont présentés pour implémenter la théorie :

Recherche par Backtracking Aléatoire : Génère des CP aléatoires à partir de zéro en maintenant des contraintes sur $f(x)$ et $f(x)+x$ .
Recherche Locale Gloutonne : Applique de manière itérative les conjugaisons locales ( $f_1, f_2$ ) à une CP initiale. Il n'accepte les mouvements que s'ils améliorent strictement une fonction de qualité basée sur le spectre différentiel complet (DDT) et le spectre de Walsh.

Résultats Clés

Contributions Théoriques

Preuve d'Invariance : A établi que la classe-D est invariante sous les actions de groupes et les translations locales spécifiées.
Théorème de Rigidité : A prouvé que la sous-classe de CP élevée $D^\uparrow$ ne peut pas être générée par des opérations simples, nécessitant la chaîne de construction composite.
Critères d'Inéquivalence CCZ : A dérivé des critères pour déterminer quand les nouvelles CP construites sont CCZ-inequivalentes à la graine (seed). Cela repose sur la vérification si la table de distribution différentielle (DDT) ou le multiensemble des coefficients absolus de Walsh change.
Bornes Cryptographiques : A dérivé des bornes pour l'uniformité différentielle ( $\delta$ ), la non-linéarité ($nl$) et le degré algébrique ( $\deg$ ) sous des modifications locales. Spécifiquement, $\delta$ varie au maximum de $2m$ où $m$ est la taille du sous-ensemble modifié.

Résultats Expérimentaux

Des expériences ont été menées sur $H \cong \mathbb{F}_{2^5}$ (32 éléments) :

Génération de CP avec $\delta=4$ : En partant d'une graine linéaire ( $\delta=32$ ) et de graines aléatoires, la recherche gloutonne a réussi à trouver plusieurs permutations complètes avec une uniformité différentielle $\delta=4$ .
Spectres Distincts : Les CP générées présentaient des spectres différentiels distincts par rapport aux unes et aux autres, ainsi qu'à une CP de référence de type Dillon (qui avait $\delta=8$ ).
Inequivalence CCZ : Les spectres différentiels distincts confirment que la construction produit de nouvelles classes d'inequivalence CCZ, et non de simples variantes affines de la graine.
Évidence de Connectivité : La convergence répétée vers des distributions indicatrices similaires à partir de différentes graines aléatoires fournit une preuve préliminaire que l'ensemble des CP élevées $D^\uparrow$ pourrait être connecté sous les mouvements de conjugaison locale.

Signification et Revendications

L'article affirme fournir un cadre algébrique systématique pour générer de nouvelles permutations complètes en exploitant la structure interne de la classe LCP.

Au-delà des Fonctions Tordues : Contrairement aux méthodes précédentes dépendant du point de départ d'une fonction tordue, cette approche permet d'explorer l'espace LCP pour trouver des CP.
Utilité Cryptographique : La méthode produit avec succès des CP avec une faible uniformité différentielle ( $\delta=4$ ), une propriété désirable pour les boîtes S, qui étaient plus difficiles à construire via la correspondance standard des fonctions tordues.
Aperçu Structurel : L'identification de la « rigidité » de $D^\uparrow$ et le rôle spécifique du centralisateur pour « réparer » les translations locales offrent une compréhension théorique plus profonde de la relation entre les LCP et les CP.
Problèmes Ouverts : L'auteur présente modestement la connectivité de $D^\uparrow$ et l'existence de fonctions APN au sein de cette classe comme des problèmes ouverts, suggérant que bien que les expériences soutiennent la connectivité, une preuve formelle est requise. Ils notent également que bien que les résultats suggèrent un lien potentiel avec les permutations APN, aucune permutation APN n'a été explicitement établie dans ce travail.