🔢 mathematics

Quadratic APN Functions in Dimension 8 via Gröbner Basis Search in a Self-Equivalence Subspace

Cet article présente une recherche computationnelle hybride combinant l'échantillonnage aléatoire et l'énumération de bases de Gröbner au sein d'un sous-espace d'auto-équivalence spécifique de dimension 40 afin de découvrir 566 fonctions APN quadratiques en dimension 8, incluant trois classes d'équivalence CCZ auparavant inconnues qui avaient été omises par les bases de données exhaustives antérieures.

Auteurs originaux : Oleksandr Kuznetsov

Publié 2026-06-11

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Oleksandr Kuznetsov

Article original sous licence CC BY 4.0 (http://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

Imaginez que vous essayiez de trouver un type de crochet de serrure incroyablement rare (appelé une fonction APN) à l'intérieur d'un immense entrepôt sombre. Cet entrepôt représente toutes les fonctions mathématiques possibles d'une certaine taille. Le problème est que l'entrepôt est si vaste (contenant plus de possibilités qu'il n'y a d'atomes dans l'univers) que si vous commenciez simplement à marcher au hasard, vous ne trouveriez probablement pas un seul crochet de serrure en une vie entière.

Ce document décrit une nouvelle stratégie ingénieuse pour trouver ces crochets de serrure rares en utilisant une « lampe de poche » et un « aimant » pour naviguer dans une section spécifique et plus petite de l'entrepôt qui était auparavant considérée comme vide.

Voici la décomposition de leur découverte en utilisant des analogies simples :

1. Le Problème : L'aiguille dans la botte de foin cosmique

Dans le monde de la cryptographie (la science des codes secrets), ces « crochets de serrure » sont des outils mathématiques spéciaux utilisés pour brouiller les données afin qu'elles ne puissent pas être piratées. Pendant longtemps, les mathématiciens ont essayé d'en trouver de nouveaux, de meilleurs, pour une taille de données spécifique (8 bits).

L'ancienne méthode : Les chercheurs précédents ont essayé de les trouver en construisant un arbre géant de possibilités, en vérifiant branche par branche. Ils ont examiné une section organisée et spécifique de l'entrepôt (un « sous-espace d'équivalence propre ») et ont conclu : « Il n'y a rien ici. » Ils ont arrêté de chercher.
La réalité : Les auteurs de ce document disent : « Attendez une minute. Cette section n'est pas vide. Vous avez juste manqué les objets parce que votre méthode d'escalade d'arbre était trop rigide. »

2. La Nouvelle Stratégie : La Lampe de Poche et l'Aimant

Les auteurs ont développé un processus en deux étapes pour trouver ces crochets de serrure cachés :

Étape 1 : La Lampe de Poche (Échantillonnage aléatoire dans une zone structurée)
Au lieu de chercher dans tout l'univers, ils se sont concentrés sur une « pièce » organisée de 40 dimensions à l'intérieur de l'entrepôt. Ils ont réalisé que bien que cette pièce soit minuscule par rapport à l'ensemble de l'entrepôt, les « crochets de serrure » y sont en fait beaucoup plus courants que n'importe où ailleurs.
Ils ont utilisé une carte spéciale (appelée paramétrisation RREF) pour parcourir cette pièce de manière aléatoire. Ils y ont trouvé des centaines de crochets de serrure « centres » qui attendaient là, prêts à être découverts.
Étape 2 : L'Aimant (La recherche de base de Gröbner)
C'est le tour de magie. Une fois qu'ils ont trouvé un crochet de serrure « centre », ils ne se sont pas arrêtés là. Ils ont utilisé un outil mathématique puissant appelé base de Gröbner (imaginez cela comme un super-aimant) pour scanner le voisinage immédiat de ce centre.

Voici la partie surprenante : l'aimant n'a pas seulement trouvé plus de crochets de serrure dans la même pièce. Il a extrait de nouveaux crochets de serrure qui se cachaient dans les pièces adjacentes, en dehors de la section organisée où ils avaient commencé.

Analogie : Imaginez que vous trouviez une pièce de monnaie rare dans un tiroir spécifique. Vous utilisez un aimant pour scanner le tiroir, et soudain, l'aimant attire trois autres pièces rares qui étaient collées au fond du tiroir, même si ces pièces appartiennent techniquement à un autre tiroir entièrement.

3. La Découverte : De Nouvelles Classes de Trésors

En utilisant cette méthode, l'équipe a trouvé 566 nouveaux crochets de serrure. Ils les ont classés en six groupes (classes) :

Deux groupes étaient des types « connus » (comme les célèbres fonctions Gold). Ils servaient de portes d'entrée (gateways). Lorsque les auteurs ont utilisé ces types connus comme point de départ, l'« aimant » a extrait les nouveaux types inconnus.
Quatre groupes étaient totalement nouveaux. Ils n'avaient jamais été vus auparavant.
- Un groupe (Classe A) a été trouvé directement à l'intérieur de la pièce organisée.
- Trois groupes (Classes B, C et D) ont été trouvés à l'extérieur de la pièce, mais ils n'étaient découvrables que parce que l'« aimant » était attaché aux crochets de serrure « portes d'entrée » connus à l'intérieur de la pièce.

4. La Preuve : Pourquoi cela compte

Les auteurs n'ont pas seulement supposé qu'il s'agissait de nouveaux éléments. Ils ont utilisé un système d'« empreinte digitale » (appelé invariant de la dérivée ortho) pour vérifier leurs découvertes par rapport aux plus grandes bases de données mondiales, qui contiennent des millions de crochets de serrure connus.

Résultat : Leurs quatre nouveaux groupes ne correspondaient à aucune des millions d'entrées existantes. Ils sont véritablement nouveaux.
Le mythe de la « pièce vide » : Ils ont prouvé que les chercheurs précédents avaient tort de dire que la pièce était vide. La pièce n'était pas vide ; la méthode de recherche précédente ne pouvait simplement pas voir les objets parce qu'elle les regardait un par un, alors que cette nouvelle méthode regarde tout le voisinage à la fois.

5. La Grande Leçon : Le Phénomène de la « Porte d'Entrée »

La conclusion la plus importante n'est pas seulement ces nouveaux crochets de serrure, mais comment ils ont été trouvés.
Les auteurs ont découvert que l'on ne peut pas simplement choisir n'importe quel crochet de serrure au hasard et espérer en trouver de nouveaux à proximité. Il faut commencer par un type très spécifique et structuré (les fonctions « Gold » à l'intérieur de la pièce organisée).

L'analogie : Si vous essayez d'utiliser un aimant sur un morceau de ferraille quelconque dans l'entrepôt, rien ne se passe. Mais si vous utilisez l'aimant sur un objet « porte d'entrée » spécifique, il révèle tout un monde caché de nouveaux objets qui étaient auparavant invisibles.

Résumé

Ce document traite de la découverte de trésors mathématiques cachés dans un endroit que tout le monde pensait vide. En utilisant une carte plus intelligente pour trouver un point de départ et un puissant « aimant » mathématique pour scanner les environs, les auteurs ont trouvé 566 nouveaux outils cryptographiques, incluant quatre familles entièrement nouvelles que personne n'avait jamais vues auparavant. Ils ont prouvé que parfois, pour trouver la nouveauté, il faut s'appuyer sur le connu, mais qu'il faut disposer des bons outils pour voir ce qui se cache juste au-delà de la limite.

Résumé Technique : Fonctions APN Quadratiques en Dimension 8 via une Recherche par Base de Gröbner dans un Sous-espace d'Auto-équivalence

Énoncé du Problème
La classification des fonctions Almost Perfect Nonlinear (APN) sur $\mathbb{F}_{2^n}$ à équivalence CCZ près est un problème central en cryptographie, particulièrement pour $n=8$ . Alors que la classification est complète pour $n \leq 6$ , elle demeure partielle pour $n=8$ . L'espace de recherche pour les fonctions APN quadratiques est vaste ( $2^{224}$ vecteurs de coefficients possibles), rendant une recherche aléatoire globale infaisable en raison d'une densité APN estimée à $\approx 2^{-n}$ . Des efforts systématiques précédents, tels que la recherche par arbre récursif de Beierle, Brinkmann et Leander (BBL2021), ont exploré des sous-espaces algébriques structurés définis par des contraintes d'auto-équivalence. Spécifiquement, BBL2021 a rapporté avoir trouvé zéro fonction APN dans le sous-espace d'auto-équivalence de dimension 40 $V_A$ associé à un automorphisme linéaire $A$ d'ordre 5 (indice de classe 22). Cet article examine si ce sous-espace contient réellement aucune fonction APN ou si la méthode de recherche précédente a échoué à les localiser.

Méthodologie
Les auteurs proposent un pipeline computationnel en deux phases qui combine l'échantillonnage aléatoire et l'énumération algébrique pour explorer $V_A$ plus efficacement que la recherche par arbre précédente.

Phase 1 : Échantillonnage Aléatoire via Paramétrage RREF
Les auteurs construisent un paramétrage explicite en Forme Échelonnée Réduite par Lignes (RREF) du sous-espace de dimension 40 $V_A = \{F : F \circ A = A \circ F\}$ . Cela réduit l'espace de recherche de $2^{224}$ à $2^{40}$ . Dans ce sous-espace, la densité empirique des fonctions APN est trouvée à environ $10^{-4}$ (soit environ 1 fonction APN pour 11 000 échantillons aléatoires), rendant l'échantillonnage ciblé réalisable. Les auteurs effectuent un échantillonnage aléatoire pour identifier des « centres APN » (des fonctions dans $V_A$ qui sont APN).
Phase 2 : Calcul de Tranche par Base de Gröbner
Pour chaque centre APN trouvé dans la Phase 1, les auteurs définissent un hyperplan affine de dimension 24 (une « tranche NL=4 ») passant par ce centre. Ceci est réalisé en fixant 200 des 224 coefficients de la Forme Normale Algébrique (FNA) — spécifiquement ceux correspondant aux paires avec des indices $p \leq 4$ — aux valeurs du centre, laissant 24 coefficients comme inconnues.
La condition APN pour les 255 différences non nulles est encodée sous la forme d'un système d'équations polynomiales sur le anneau booléen. Les auteurs utilisent le système de calcul algébrique Magma pour calculer une base de Gröbner pour ce système.
- Si le système est infaisable, la tranche ne contient pas d'autres fonctions APN.
- Si le système possède des solutions, l'énumération par base de Gröbner trouve toutes les fonctions APN au sein de cette tranche spécifique de dimension 24.
  Crucialement, bien que le centre soit garanti d'être dans $V_A$ , les solutions trouvées par l'étape de la base de Gröbner ne sont pas contraintes à $V_A$ ; elles peuvent se situer en dehors du sous-espace d'auto-équivalence.
Classification et Vérification
Les fonctions trouvées sont classées à l'aide de l'invariant de l'ortho-dérivée $\sigma(F)$ , qui est prouvé être un invariant CCZ complet pour les fonctions APN quadratiques (par le théorème de Yoshiara et les résultats de Canteaut et al.). Les auteurs effectuent des comparaisons en flux continu de ces signatures contre trois bases de données majeures : la compilation BBL2021 pré-2020, la base de données Beierle et al. 2025 (contenant $\approx 3,8$ millions de fonctions), et les fonctions Gold classiques.

Résultats Clés
Les auteurs ont exécuté le pipeline sur 428 tranches distinctes de dimension 24 (0,65 % du total des $2^{16}$ tranches possibles dans $V_A$ ).

Découverte de Nouvelles Classes : La recherche a produit 566 fonctions APN quadratiques uniques appartenant à six classes de CCZ-équivalence.
- Quatre Nouvelles Classes (A, B, C, D) : Ces 500 fonctions (362 dans la Classe A, 72 dans B, 36 dans C, 30 dans D) ne sont pas présentes dans la base de données Beierle 2025, la base BBL2021 pré-2020, ou les familles Gold classiques.
- Deux Classes Connues (E, F) : Elles correspondent aux fonctions Gold $x^3$ et $x^9$ (et leurs orbites de Frobenius), servant de contrôles pour valider le pipeline.
Résultats Structurels :
- Appartenance au Sous-espace : Un test d'appartenance ( $F \circ A = A \circ F$ ) a révélé que la Classe A, E et F se situent entièrement dans $V_A$ . Cependant, les Classes B, C et D se situent entièrement en dehors de $V_A$ .
- Le Phénomène de « Passerelle » : Les 138 fonctions des nouvelles classes externes (B, C, D) ont été trouvées exclusivement dans des tranches centrées sur des fonctions Gold (Classes E et F) qui résident dans $V_A$ . Les tranches centrées sur des fonctions de la Classe A n'ont produit aucun voisin en dehors de $V_A$ .
- Échec des Semences Alternatives : Des expériences comparatives utilisant 532 fonctions APN de la base de données Beierle 2025 (qui sont en dehors de $V_A$ ) comme centres de tranches n'ont trouvé aucun voisin APN. Cela suggère que la capacité de « passerelle » pour découvrir de nouvelles classes via l'élargissement par base de Gröbner est spécifique aux fonctions au sein du sous-espace d'auto-équivalence, et non une propriété générique de toutes les fonctions APN.

Signification et Revendications
L'article revendique plusieurs contributions significatives au domaine de la classification des fonctions APN quadratiques :

Correction de Résultats Précédents : Les auteurs démontrent que le sous-espace d'auto-équivalence $V_A$ (indice de classe 22), précédemment rapporté par BBL2021 comme ne contenant aucune fonction APN, contient en réalité au moins quatre classes CCZ de fonctions APN quadratiques. L'échec de la recherche par arbre de BBL2021 est attribué à sa stratégie d'élagage de branche, qui peut avoir éliminé des solutions valides dans ce sous-espace structuré, tandis que l'approche par base de Gröbner réalise une énumération complète dans chaque tranche.
Découverte de Nouvelles Fonctions : Le papier fournit une preuve rigoureuse (via l'invariant de l'ortho-dérivée) que quatre nouvelles classes CCZ de fonctions APN quadratiques existent pour $n=8$ , distinctes des $\approx 3,8$ millions de fonctions de la plus grande base de données connue.
Innovation Méthodologique : L'article introduit un mécanisme de « navigation par GB ». Il postule que, bien qu'une recherche globale soit impossible, on peut exploiter des sous-espaces structurés avec une densité APN plus élevée pour trouver des fonctions « semences ». L'étape de la base de Gröbner agit alors comme un énumérateur local, capable de sortir du sous-espace pour trouver de nouvelles classes. Les auteurs soulignent que ce mécanisme n'est pas générique ; il repose sur la structure algébrique spécifique du sous-espace d'auto-équivalence, comme en témoigne l'échec des fonctions non-sous-espaces à agir comme des semences productives.
Complétude de l'Ortho-Dérivée : Ce travail renforce l'utilité de la signature de l'ortho-dérivée en tant qu'invariant CCZ exact pour les fonctions quadratiques, permettant une classification rigoureuse sans tests par paires exhaustifs.

Les auteurs concluent que leur approche offre un programme systématique pour étendre la classification des fonctions APN quadratiques en explorant d'autres indices de classe de BBL2021 et en utilisant la technique de tranchage par base de Gröbner pour naviguer dans le paysage APN.