🔢 mathematics

Triprojective almost perfect nonlinear permutations and functions

Cet article présente une vaste famille de permutations presque non linéaires (APN) pour les espaces vectoriels finis de dimensions impaires divisibles par trois, ainsi que des fonctions APN non bijectives pour les dimensions paires, toutes caractérisées par une structure triprojective induite par le groupe linéaire général $\mathrm{GL}(3,2^m)$ .

Auteurs originaux : Faruk Göloğlu, Lukas Kölsch

Publié 2026-05-19

📖 6 min de lecture🧠 Analyse approfondie

CC0 1.0

Auteurs originaux : Faruk Göloğlu, Lukas Kölsch

Article original placé dans le domaine public sous CC0 1.0 (http://creativecommons.org/publicdomain/zero/1.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

Imaginez que vous êtes un serrurier maître d'œuvre tentant de concevoir le coffre-fort ultime. Dans le monde de la sécurité numérique, les « serrures » sont des fonctions mathématiques utilisées pour brouiller les données afin que les pirates ne puissent pas retrouver le message original. Le document dont vous parlez est un plan de construction pour un nouveau type de serrure incroyablement robuste.

Voici l'histoire de ce que les auteurs, Faruk Gölöglu et Lukas Kölsch, ont découvert, expliquée sans le jargon mathématique lourd.

L'Objectif : Le Brouilleur Parfait

En cryptographie, il existe un type spécifique de serrure appelé une S-Box (Boîte de Substitution). Imaginez une S-Box comme une machine qui prend un ensemble d'entrées (comme une combinaison de nombres) et rejette un ensemble de sorties complètement différent.

Le danger provient d'une méthode appelée « cryptanalyse différentielle ». Imaginez un voleur tentant de crack votre coffre-fort en remarquant des motifs : « Si je tourne le cadran d'un cran vers la droite, le son de la serrure change d'une quantité spécifique. Si je le tourne de deux crans, le son change différemment. » Si la serrure réagit de manière trop prévisible à de petits changements, le voleur peut remonter le fil pour trouver la clé.

Pour arrêter cela, les mathématiciens recherchent des fonctions APN (Presque Parfaitement Non Linéaires). Ce sont les « serrures parfaites » où un minuscule changement dans l'entrée provoque un changement chaotique et imprévisible dans la sortie. Le but est de faire en sorte que, peu importe comment le voleur modifie l'entrée, la sortie ressemble à du bruit aléatoire.

Le Grand Défi : Le Problème de la « Dimension Paire »

Pendant longtemps, les mathématiciens savaient comment construire ces serrures parfaites pour certaines tailles de données (spécifiquement, lorsque la taille des données est un nombre impair). Mais pour les blocs de données de taille paire (très courants dans les ordinateurs réels), trouver une serrure parfaite qui soit aussi une permutation (ce qui signifie que chaque entrée unique correspond à une sortie unique, de sorte que rien ne se perde) a été un énorme casse-tête. C'est comme essayer de trouver une clé qui ouvre toutes les serrures d'une rangée spécifique de maisons, mais vous continuez à découvrir que certaines clés ouvrent deux serrures à la fois, ou que certaines serrures n'ont aucune clé.

Les auteurs de ce document disent : « Nous avons trouvé un moyen de construire ces serrures parfaites et non répétitives pour une immense nouvelle famille de blocs de données de taille paire. »

L'Ingrédient Secret : L'Architecture « Triprojective »

Les auteurs ne se sont pas simplement heurtés à une formule aléatoire. Ils ont construit leurs serrures en utilisant un style architectural spécifique qu'ils appellent « Triprojective ».

Pour comprendre cela, imaginez que vous regardez une sculpture en 3D.

Serrures Standard : Habituellement, elles sont construites en regardant la sculpture sous un seul angle (une vue plate, en 2D).
Les Nouvelles Serrures « Triprojective » : Les auteurs ont construit leur fonction en regardant la sculpture sous trois angles différents simultanément, en utilisant un groupe spécial de règles (liées à une structure mathématique appelée $GL(3, 2^m)$ ).

Ils appellent cela une structure « Triprojective » car elle traite les données comme si elles existaient dans un espace 3D où les règles de la géométrie sont légèrement tordues. En organisant les données de cette manière, ils s'assurent que le « brouillage » se produit d'une manière incroyablement difficile à prédire, peu importe comment vous essayez de sonder.

La Formule Magique

Le document présente une recette spécifique (une formule) pour ces serrures. Elle implique trois variables ( $x, y, z$ ) et certains nombres spéciaux ( $a, b, c$ ).

La recette possède un « contrôle de sécurité ». Avant de pouvoir utiliser la serrure, vous devez effectuer un test rapide pour vous assurer qu'une équation spécifique n'a pas de solutions.

Si le test réussit : Vous obtenez une serrure parfaite et incassable (une permutation APN).
Si le test échoue : La serrure est toujours très forte (fortement non linéaire), mais elle pourrait ne pas être une permutation parfaite (certaines entrées pourraient correspondre à la même sortie).

Les auteurs prouvent que si vous choisissez vos nombres correctement, cette recette fonctionne pour chaque dimension impaire divisible par trois. C'est une expansion massive de ce qui était connu auparavant.

Pourquoi Cela Compte (Selon le Document)

Il Unifie les Anciennes Découvertes : Les auteurs montrent que plusieurs autres formules compliquées découvertes par différents mathématiciens ces dernières années sont en fait juste des versions simplifiées et spéciales de leur nouvelle recette « Triprojective ». C'est comme réaliser que trois types de voitures différents sont en fait juste des finitions de peinture différentes sur le même châssis.
C'est Nouveau et Unique : Ils prouvent que leur nouvelle famille de serrures est fondamentalement différente des serrures « Gold » (une célèbre famille de fonctions APN découverte il y a des décennies). Ils ne se contentent pas de renommer d'anciennes clés ; ils forgent entièrement de nouvelles clés.
La Preuve est « Propre » : Les tentatives précédentes pour prouver que ces serrures fonctionnaient nécessitaient d'énormes simulations informatiques et des pages d'algèbre complexe. Les auteurs ont utilisé une approche astucieuse, purement logique (en utilisant des « polynômes tordus » et des propriétés des corps finis) pour prouver leurs résultats sans avoir besoin d'un supercalculateur.

La Conclusion

Ce document est une percée mathématique dans la conception des serrures de sécurité numérique. Les auteurs ont découvert une nouvelle méthode « Triprojective » polyvalente pour construire des Permutations Presque Parfaitement Non Linéaires.

En termes simples : Ils ont trouvé un nouveau moyen fiable de construire les brouilleurs de données les plus puissants possibles pour une large gamme de tailles de données informatiques, résolvant un problème qui avait déconcerté les experts pendant des années. Ils n'ont pas trouvé une seule nouvelle serrure ; ils ont trouvé toute une usine pour les fabriquer, et ils ont prouvé que ces nouvelles serrures sont distinctes de toutes les autres que nous avons vues auparavant.

Résumé Technique : Permutations et Fonctions Presque Parfaitement Non Linéaires Triprojectives

Énoncé du Problème
L'article traite de l'existence et de la construction de permutations Presque Parfaitement Non Linéaires (PPNL ou APN en anglais) sur des espaces vectoriels finis de dimension paire. Dans le contexte de la cryptanalyse différentielle, les fonctions PPNL (celles dont la uniformité différentielle $\Delta_F = 2$ ) sont cruciales pour la conception de boîtes de substitution (S-Boxes) sécurisées dans les réseaux de substitution-permutation. Bien que l'existence de fonctions PPNL soit connue pour les dimensions impaires, l'existence de permutations PPNL (bijections) pour les dimensions paires $n > 6$ demeure un problème majeur non résolu. Plus précisément, les auteurs se concentrent sur la construction de grandes familles de telles fonctions dans les dimensions $n = 3m$ (où $m$ est impair) et sur la caractérisation de leurs propriétés, incluant leurs classes d'équivalence et les tailles de leurs ensembles images.

Méthodologie
Les auteurs adoptent une approche structurelle basée sur des applications « triprojectives » et « semi-quadratiques ». La méthodologie procède selon les étapes suivantes :

Structure Projective : Les auteurs définissent une classe de fonctions $F \in SQH(3, q)$ (semi-quadratiques homogènes) sur $\mathbb{F}_q^3$ (où $q=2^m$ ). Ces fonctions sont induites par des formes semi-quadratiques satisfaisant des propriétés d'homogénéité spécifiques, permettant d'induire des applications bien définies sur l'espace projectif $\mathbb{P}^2(\mathbb{F}_q)$ .
Critères de Bijection : S'appuyant sur des travaux antérieurs (Théorème 1.2), l'article utilise une condition sur un polynôme univarié spécifique $P(X) = aX^{\sigma^2+\sigma+1} + bX^{\sigma+1} + cX + 1$ pour garantir que l'application induite sur l'espace projectif est une bijection.
Analyse de l'Uniformité Différentielle :
- Cas où $m/d$ est pair : Les auteurs utilisent le concept de « cœur » de la fonction (un sous-corps sur lequel l'application dérivée est linéaire) pour montrer que l'uniformité différentielle est $2d$ , où $d = \gcd(k, m)$ .
- Cas où $m/d$ est impair : Les auteurs introduisent des outils issus de la théorie des anneaux de polynômes tordus (anneaux d'Ore) $\mathbb{F}_q[t; \sigma]$ . Ils établissent un lien entre les racines du polynôme $P(X)$ et l'existence de diviseurs à droite linéaires dans l'anneau tordu. En étendant le corps et en analysant le plus petit commun multiple à gauche (lclm) des polynômes, ils prouvent que l'uniformité différentielle reste $2d$ même dans ce cas plus complexe.
Équivalence et Classification : L'article compare la nouvelle famille aux fonctions PPNL trivariées existantes (spécifiquement celles de Li-Kaleyski et Bartoli-Stanica) en utilisant l'équivalence linéaire. De plus, il prouve l'inequivalence par rapport aux fonctions PPNL de Gold ( $x^{2^i+1}$ ) en analysant les groupes d'automorphismes linéaires ( $Aut_L(F)$ ) et en montrant qu'ils ne peuvent pas être conjugués dans le groupe linéaire général.

Contributions et Résultats Clés

Construction de Permutations PPNL : L'article présente une grande famille de permutations PPNL pour les espaces vectoriels finis de dimension $n=3m$ où $m$ est impair. Les fonctions sont définies comme suit :
$F(x, y, z) = (x^{\sigma+1} + ay^\sigma z + bx^\sigma y + cx^\sigma z, \quad ay^{\sigma+1} + z^\sigma x + bz^\sigma y + cx^\sigma y, \quad z^{\sigma+1} + x^\sigma y)$
où $\sigma = 2^k$ , $a, b, c \in \mathbb{F}_q$ , et $a \neq 0$ .
Uniformité Différentielle : Les auteurs prouvent que si l'équation polynomiale $ax^{\sigma^2+\sigma+1} + bx^{\sigma+1} + cx + 1 = 0$ n'a pas de solution dans $\mathbb{F}_q$ , l'uniformité différentielle de $F$ est $2d$ (où $d = \gcd(k, m)$ ). Par conséquent, lorsque $d=1$ et $m$ est impair, $F$ est une permutation PPNL.
Taille de l'Ensemble Image : L'article caractérise la taille de l'ensemble image de ces fonctions. Si $m/d$ est pair, la fonction est $(2d+1)$ -à-1 sur $\mathbb{F}_q^3 \setminus \{0\}$ . Si $m/d$ est impair, la fonction est bijective sur $\mathbb{F}_q^3$ .
Unification des Familles Existantes : Les auteurs démontrent que plusieurs familles récemment découvertes de fonctions PPNL trivariées (Li-Kaleyski et Bartoli-Stanica) sont linéairement équivalentes à des instances spécifiques de leur famille proposée (obtenues en fixant des paramètres spécifiques $a, b, c$ ). Cela fournit une explication unifiée et élémentaire pour ces constructions, évitant les distinctions de cas complexes et les calculs de résultants assistés par ordinateur utilisés dans les preuves antérieures.
Inéquivalence par rapport aux Fonctions de Gold : L'article prouve que pour $m > 2$ et $m \neq 6$ , les fonctions PPNL construites sont CCZ-inequivalentes aux fonctions PPNL de Gold. Cela est établi en montrant que leurs groupes d'automorphismes linéaires ne sont pas conjugués dans $GL(3m, 2)$.

Importance et Revendications
L'article revendique fournir une « grande famille » de permutations PPNL dans chaque dimension impaire divisible par trois, abordant la question ouverte des bijections PPNL pour les dimensions paires. L'importance réside dans :

Généralité : La construction produit un nombre exponentielment grand de fonctions PPNL deux à deux inequivalentes, prouvé, au sein de la classe des applications multiprojectives.
Simplification : Les preuves sont décrites comme « sans ordinateur, beaucoup plus courtes et purement élémentaires » par rapport aux travaux antérieurs, offrant un cadre unifié pour comprendre diverses fonctions PPNL trivariées.
Nouveaux Exemples : La famille est montrée comme contenant des exemples inequivalents aux fonctions PPNL connues (y compris les fonctions de Gold), élargissant le paysage connu des primitives cryptographiques.

Les auteurs notent que, bien que les spectres de Walsh soient connus pour le cas où $m/d$ est pair, la détermination du spectre de Walsh pour les permutations PPNL (où $m$ est impair) demeure un problème ouvert. Ils identifient également la classification des fonctions semi-quadratiques homogènes menant à des bijections projectives comme une direction naturelle pour les recherches futures.