🔢 mathematics

Bent Functions and the Completed Maiorana-McFarland Class

Cet article passe en revue les résultats fondamentaux et les avancées récentes dans la conception et l'analyse des fonctions booléennes bent, en se concentrant spécifiquement sur leur relation avec la classe de Maiorana-McFarland complétée.

Auteurs originaux : Enes Pasalic, Alexandr Polujan, Fengrong Zhang, Sadmir Kudin

Publié 2026-08-25

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Enes Pasalic, Alexandr Polujan, Fengrong Zhang, Sadmir Kudin

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

Dans l'architecture cachée de la sécurité numérique moderne, il existe un type particulier d'objet mathématique appelé fonction « bent ». Il ne s'agit pas d'appareils physiques ou d'entités biologiques, mais plutôt de règles complexes pour traiter les données binaires — des chaînes de uns et de zéros qui constituent la base de toute communication informatique. Imaginez un vaste paysage de règles possibles, où la plupart sont prévisibles et faciles à analyser. Les fonctions bent se situent au sommet même de l'imprévisibilité, s'éloignant autant que possible de tout motif simple et linéaire. En raison de cette irrégularité extrême, elles sont des outils précieux pour la protection des données en cryptographie et dans les codes correcteurs d'erreurs, agissant comme le bruit chaotique qui empêche les espions de trouver un signal. Pendant des décennies, les mathématiciens ont su comment construire une famille spécifique et bien comprise de ces fonctions, un groupe nommé d'après les chercheurs qui les ont décrites pour la première fois. Cette famille, souvent appelée classe de Maiorana-McFarland, a servi de modèle principal pour la création de fonctions bent, tel un plan architectural standard pour la construction d'une maison. Cependant, une question persistante a hanté le domaine : ces plans standards sont-ils les seuls moyens de construire de telles fonctions, ou d'autres conceptions plus étranges existent-elles et que nous n'avons pas encore découvertes ?

Une équipe de chercheurs a maintenant entrepris un examen approfondi de cette question, sondant l'ensemble du paysage des fonctions bent pour voir comment elles se rapportent à cette famille standard. Leur travail confirme que les modèles connus, bien qu'utiles, ne représentent qu'une infime fraction des possibilités totales. Dans le cas spécifique des fonctions à huit variables, des recherches informatiques ont révélé que le nombre total de fonctions bent est astronomiquement grand, environ deux à la puissance cent six. En revanche, le nombre de fonctions pouvant être construites à l'aide du modèle standard de Maiorana-McFarland est estimé être au maximum de deux à la puissance quatre-vingt-un. Cet écart massif suggère que la grande majorité des fonctions bent sont fondamentalement différentes de celles que nous avons été capables de construire explicitement. L'objectif des chercheurs était de cartographier le territoire entre ces deux extrêmes, en identifiant de nouvelles méthodes pour construire des fonctions bent qui ne rentrent certainement pas dans le moule ancien et en comprenant les raisons structurelles de leur différence.

Le papier commence par examiner deux familles spécifiques de fonctions bent, connues sous les noms de classes C et D, qui ont été conçues pour modifier le modèle standard. Ces familles introduisent de petits changements délibérés à la formule standard, ajoutant des motifs spécifiques à la sortie. Les chercheurs ont examiné si ces modifications étaient suffisantes pour pousser les fonctions résultantes hors de la famille standard. Ils ont découvert que, sous certaines conditions, ces fonctions modifiées sont effectivement distinctes. Par exemple, si la permutation sous-jacente utilisée dans la construction possède des propriétés algébriques spécifiques — en substance, si elle manque de certaines symétries cachées — la fonction bent résultante ne peut pas être transformée pour revenir à la forme standard. Les auteurs ont fourni des règles claires et testables pour déterminer quand une fonction appartient à ces nouvelles familles exotiques et quand elle reste piégée dans l'ancienne. Ils ont également exploré les « superclasses », qui combinent différents types de modifications, constatant que si certaines combinaisons fonctionnent, d'autres ne produisent pas de fonctions bent du tout, révélant l'équilibre délicat requis pour maintenir le niveau nécessaire d'imprévisibilité.

Au-delà de ces familles spécifiques, les chercheurs ont étudié des fonctions construites à l'aide de la structure multiplicative des corps finis, souvent décrites à l'aide de termes de trace. Ce sont des fonctions dont la sortie dépend de la somme d'un nombre élevé à une puissance spécifique. L'étude souligne que beaucoup de ces fonctions, particulièrement celles basées sur certains exposants, sont prouvables comme étant en dehors de la famille standard. Les chercheurs ont utilisé un test mathématique spécifique impliquant des dérivées du second ordre — une façon de mesurer comment le taux de variation de la fonction lui-même change — pour prouver que ces fonctions manquent de la régularité structurelle présente dans la classe standard. Ils ont également examiné des fonctions qui agissent comme indicateurs d'autres objets mathématiques importants, tels que les fonctions presque parfaitement non linéaires, montrant que ces indicateurs possèdent souvent les propriétés uniques et non standard des fonctions bent qui se situent en dehors des familles connues.

Un thème central de la recherche est le concept d'« indice de linéarité », qui peut être considéré comme une mesure de la mesure dans laquelle une fonction ressemble à un motif linéaire simple. Les fonctions de Maiorana-McFarland standard ont un indice de linéarité élevé, ce qui signifie qu'elles peuvent être décomposées en de grands morceaux affines simples. Les chercheurs ont identifié une nouvelle catégorie de fonctions possédant l'indice de linéarité minimal possible, qu'ils appellent « optimales ». Ces fonctions sont l'opposé des fonctions standard ; elles sont si irrégulières qu'elles ne peuvent pas du tout être simplifiées en blocs affines de grande taille. Le papier détaille comment construire ces fonctions optimales et prouve qu'elles sont fondamentalement différentes de la classe standard. En étudiant les « sous-espaces M » — des sous-structures géométriques spéciales au sein du domaine de la fonction qui révèlent sa symétrie sous-jacente — les auteurs ont montré que ces fonctions optimales possèdent une structure unique et minimale que les fonctions standard ne possèdent tout simplement pas.

L'étude explore également un cadre plus large et plus flexible appelé classe de Maiorana-McFarland généralisée. Ce cadre permet de créer des fonctions construites à partir de morceaux affines de tailles variables, plutôt que de la taille fixe utilisée dans la classe standard. Les chercheurs ont caractérisé précisément quand une fonction appartenant à cette classe plus large reste dans la famille standard et quand elle en sort. Ils ont découvert qu'en choisissant soigneusement les blocs de construction, on peut créer des fonctions qui sont « presque » standards mais néanmoins distinctes, ainsi que des fonctions qui sont complètement étrangères à la famille standard. Le papier conclut en énumérant plusieurs problèmes ouverts, reconnaissant que bien qu'ils aient cartographié des portions significatives de ce territoire mathématique, l'énumération complète de toutes les fonctions bent demeure un mystère. Ils mettent au défi les futurs chercheurs de trouver davantage de familles infinies de ces fonctions exotiques et de comprendre les structures algébriques précises qui les rendent uniques, garantissant ainsi que le domaine continue d'évoluer au-delà des limites des plans originaux.

Résumé technique : Fonctions bent et la classe de Maiorana-McFarland complétée

Énoncé du problème
Les fonctions booléennes bent, introduites par Rothaus, représentent une classe fondamentale de fonctions dans un nombre pair de variables qui atteignent une non-linéarité maximale (distance maximale par rapport aux fonctions affines). Bien que la classe de Maiorana-McFarland (M) et sa version complétée ( $M^\#$ ) constituent la famille explicite de fonctions bent la plus parfaitement comprise, des preuves computationnelles récentes indiquent une divergence significative entre le nombre total de fonctions bent et celles appartenant à $M^\#$ . Spécifiquement, en dimension 8, le nombre total de fonctions bent est d'environ $2^{106}$ , alors que le nombre de fonctions équivalentes à Maiorana-McFarland est estimé à au plus $2^{81}$ . Cette observation motive le problème central de cette revue : caractériser les fonctions bent qui se situent en dehors de la classe de Maiorana-McFarland complétée ( $M^\#$ ), comprendre leurs structures algébriques et développer des méthodes de construction explicites pour de telles fonctions. L'article se concentre sur le « problème d'exclusion » — déterminer l'intersection de diverses classes de fonctions bent avec $M^\#$ et identifier les conditions sous lesquelles des fonctions sont prouvées être en dehors de cette classe.

Méthodologie
L'article emploie une méthodologie de revue exhaustive, synthétisant les résultats fondamentaux et les avancées récentes dans la conception et l'analyse des fonctions booléennes bent. L'approche technique repose largement sur :

Caractérisation algébrique : Utilisation du critère de la dérivée de second ordre (Lemme 1.2) pour caractériser l'appartenance à $M^\#$ . Une fonction appartient à $M^\#$ si et seulement si il existe un sous-espace de dimension $m$ , noté $U$ , tel que toutes les dérivées de second ordre $D_a D_b f$ s'annulent pour $a, b \in U$ .
Indice de linéarité et sous-espaces M : Analyse de l'« indice de linéarité » ($ind(f)$), défini comme la dimension maximale d'un sous-espace M (un sous-espace où les dérivées de second ordre s'annulent). Les fonctions avec $ind(f) = n/2$ appartiennent à $M^\#$ , tandis que celles avec des indices minimaux ($ind(f)=1$) sont qualifiées d' $\ell$ -optimales.
Constructions secondaires : Étude de la manière dont les opérations telles que les sommes directe/indirecte, les concaténations (2 et 4-concaténation), et l'ajout de termes de trace ou d'indicateurs de sous-espaces affectent l'appartenance à $M^\#$ .
Cadres généralisés : Extension de l'analyse de la classe M classique ( $r=s=n/2$ ) à la classe de Maiorana-McFarland généralisée (GMM) ( $Mr,s$ ), où $f(x,y) = x \cdot \phi(y) + h(y)$ avec $x \in \mathbb{F}_2^r, y \in \mathbb{F}_2^s$ et $r \neq s$ .

Contributions clés et résultats

Classes C et D de Carlet : L'article détaille les classes C et D, qui modifient la forme de Maiorana-McFarland en ajoutant des indicateurs de sous-espaces vectoriels.
- Classe C : Fonctions de la forme $x \cdot \pi(y) + 1_{L^\perp}(x)$ . Les auteurs résument les conditions suffisantes sur la permutation $\pi$ et le sous-espace $L$ (propriété (C) spécifique) qui garantissent que la fonction est bent et en dehors de $M^\#$ . Un résultat clé concerne les permutations dont les composantes manquent de structures linéaires non nulles.
- Classe D et $D_0$ : Fonctions de la forme $x \cdot \pi(y) + 1_{E_1}(x)1_{E_2}(y)$ et la sous-classe $D_0$ ( $x \cdot \pi(y) + \delta_0(x)$ ). L'article fournit une caractérisation complète de $D_0 \cap M^\#$ , montrant que pour les permutations quadratiques, l'appartenance dépend de si la permutation est affine sur un hyperplan affine. Pour des degrés plus élevés, les fonctions sont souvent en dehors de $M^\#$ .
- Superclasses : La revue examine les superclasses (SC, CD, SD) formées par la combinaison d'indicateurs. Elle identifie que si certaines combinaisons (comme SC) produisent des fonctions bent en dehors de $M^\#$ , d'autres (comme SD) ne produisent pas de fonctions bent du tout.
Termes de trace et la propriété $P_\tau$ :
- L'article passe en revue les fonctions bent monomiales, binomiales et apparentées définies via des termes de trace (par exemple, les exposants de Dillon et Kasami). Il confirme que beaucoup d'entre elles, particulièrement celles avec des exposants Niho spécifiques, se situent en dehors de $M^\#$ .
- Une partie importante est dédiée à la propriété $P_\tau$ , qui consiste à ajouter des combinaisons polynomiales de termes de trace à une fonction bent. L'article détaille comment la propriété $P_\tau$ , caractérisée par l'annulation des dérivées de second ordre de la fonction duale, permet la construction de familles infinies de fonctions bent en dehors de $M^\#$ qui ne sont pas couvertes par les classes C ou D.
Classe de Maiorana-McFarland Généralisée (GMM) :
- L'article introduit la classe GMM ( $Mr,s$ ) et sa version complétée. Il caractérise la bentité dans cette classe en utilisant des « ensembles bent » et des « fonctions bent partiellement définies ».
- Presque Maiorana-McFarland ( $k=1$ ) : Les fonctions avec un indice de linéarité $n/2 - 1$ sont analysées. L'article distingue les partitions « triviales », « non-propres » et « propres » du domaine, montrant que des partitions propres spécifiques produisent des fonctions bent en dehors de $M^\#$ .
- Fonctions $\ell$ -optimales : La revue discute des fonctions avec un indice de linéarité minimal ($ind(f)=1$), notant qu'elles sont l'« opposé » des fonctions de Maiorana-McFarland. Les constructions impliquant des permutations possédant la propriété (P1) (dérivées de second ordre non nulles) sont mises en avant comme une méthode pour générer de telles fonctions.
Sous-espaces M et constructions secondaires :
- L'article fournit une analyse algébrique et combinatoire profonde des sous-espaces M. Il établit des bornes sur le nombre de sous-espaces M maximaux et lie cela à la classification des fonctions bent.
- Il présente des conditions nécessaires et suffisantes pour que les constructions secondaires (somme directe, somme indirecte, 2- et 4-concaténation) aboutissent à des fonctions en dehors de $M^\#$ . Notamment, il prouve que la 4-concaténation d'une fonction bent en dehors de $M^\#$ avec une fonction bent arbitraire produit une nouvelle fonction bent en dehors de $M^\#$ .

Signification
L'article se positionne comme une revue complète qui comble le fossé entre la classe de Maiorana-McFarland, bien comprise, et l'espace vaste et largement non classifié des fonctions bent. Sa principale importance réside dans :

Systématisation de l'exclusion : Fournir un cadre unifié pour déterminer quand les fonctions bent tombent en dehors de $M^\#$ , allant au-delà des exemples ad hoc pour proposer des caractérisations structurelles basées sur les indices de linéarité et les sous-espaces M.
Expansion des méthodes de construction : Détailler des méthodes explicites (C, D, $P_\tau$ , GMM) pour générer des familles infinies de fonctions bent en dehors de $M^\#$ , répondant à la rareté des exemples connus dans des dimensions fixes.
Clarification de la structure algébrique : Introduire et affiner des concepts tels que l'indice de linéarité et les sous-espaces M comme outils fondamentaux pour comprendre les propriétés algébriques des fonctions bent et leur relation à la hiérarchie de Maiorana-McFarland généralisée.
Identification des problèmes ouverts : L'article se conclut par une liste de nombreux problèmes ouverts, incluant l'énumération exacte des classes d'équivalence EA dans $M^\#$ , l'extension de ces théories aux fonctions bent $p$ -aires, et la construction de ensembles de différences en dehors de la classe de McFarland.

Les auteurs maintiennent un ton modeste, reconnaissant que bien que des progrès significatifs aient été accomplis dans l'identification des fonctions en dehors de $M^\#$ , l'énumération totale des fonctions bent et une classification complète de leurs structures algébriques restent des défis ouverts. Ce travail sert de référence fondamentale pour les chercheurs visant à concevoir des fonctions booléennes cryptographiquement significatives possédant des propriétés de non-linéarité spécifiques qui ne peuvent être capturées par la construction standard de Maiorana-McFarland.

Articles similaires