On Generalizations of Maiorana-McFarland and $\mathcal{PS}_{ap}$ Functions

1. Contexte et Problématique

L'article se concentre sur la théorie des fonctions booléennes bent (fonctions à spectre de Walsh plat), qui jouent un rôle crucial en cryptographie pour leur résistance aux attaques par corrélation et linéaires. Le problème central abordé est la classification et la construction de ces fonctions en dehors des classes classiques connues.

Historiquement, deux constructions primaires dominent :

1. La classe Maiorana–McFarland (MM).
2. La classe des étalements partiels (PSap), spécifiquement la classe de Desarguesien.

Bien que la classe complète de Maiorana–McFarland ($MM^\#$) soit bien comprise, il est établi qu'elle ne contient qu'une fraction infime de toutes les fonctions bent (surtout en dimension 8 et au-delà). De plus, la caractérisation de l'appartenance à $MM^\#$ repose sur des critères spécifiques (comme l'existence d'un sous-espace $M$ de dimension maximale).

Le problème posé par les auteurs est double :

• Comment construire systématiquement des fonctions bent généralisées de type Maiorana–McFarland (GMM) qui ne sont pas équivalentes (au sens de l'équivalence affine étendue, EA) à aucune fonction dans la classe $MM^\#$ ou $PS_{ap}^\#$ ?
• Les fonctions généralisées de type PSap (G-PSap) peuvent-elles être décomposées en fonctions bent ou semi-bent via des constructions secondaires (concaténation) ?

2. Méthodologie

Les auteurs emploient une approche combinant l'algèbre booléenne, la théorie des corps finis et la géométrie algébrique :

• Critère de Dillon et Dérivées d'Ordre 2 : Pour distinguer les fonctions de la classe $MM^\#$, les auteurs utilisent le critère de Dillon, qui stipule qu'une fonction bent appartient à $MM^\#$ si et seulement si elle possède un sous-espace $M$ (où les dérivées secondes s'annulent) de dimension $n/2$. Ils analysent le comportement des dérivées secondes sous l'équivalence EA.
• Constructions Généralisées (GMM et G-PSap) :
  • Ils généralisent la construction MM en utilisant des fonctions $k$-plateauées avec des supports de Walsh disjoints.
  • Ils étudient les partitions de bent généralisées (G-PSap) basées sur des étalements généralisés de Desargues.
• Théorie des Courbes Algébriques : Pour prouver l'absence de décomposition (c'est-à-dire que les dérivées secondes du dual ne sont pas constantes), les auteurs modélisent les équations résultant des dérivées secondes comme des courbes d'Artin-Schreier sur des corps finis. Ils utilisent ensuite le théorème de Hasse-Weil pour estimer le nombre de points rationnels affines, démontrant ainsi que ces courbes possèdent toujours des points, ce qui implique que les dérivées secondes ne sont pas constantes.
• Polynômes de Permutation : L'analyse repose sur des propriétés spécifiques de polynômes de permutation (comme les fonctions de Gold $x^{2^k+1}$ et les inverses $x^{2^m-2}$) pour garantir que les conditions de non-appartenance à $MM^\#$ sont satisfaites.

3. Contributions Clés et Résultats

A. Construction de fonctions GMM hors de la classe $MM^\#$

Les auteurs proposent une nouvelle famille de fonctions bent généralisées de type Maiorana–McFarland (GMM) qui ne sont pas équivalentes à des fonctions MM classiques.

• Mécanisme : Ils construisent une fonction $f$ en combinant des fonctions MM $h$ et $h \circ L$ (où $L$ est une permutation linéaire) selon la valeur d'un paramètre de trace.
• Résultat Théorique (Théorème 1 et Corollaires 7 & 9) : Ils démontrent que si la fonction de base $h$ possède un unique sous-espace $M$ de dimension maximale (le sous-espace canonique), alors la fonction GMM résultante n'admet aucun sous-espace $M$ de dimension suffisante pour appartenir à $MM^\#$.
• Exemples Concrets : Ils exhibent des exemples explicites utilisant la fonction inverse ($x^{2^m-2}$) et les fonctions de Gold ($x^{2^k+1}$) sous certaines conditions de paramètres ($m > k+2$, etc.). Ces fonctions sont donc strictement en dehors de $MM^\#$ et de $PS_{ap}^\#$.

B. Analyse de la décomposition des fonctions G-PSap

Les auteurs étudient la décomposition des fonctions bent généralisées de type PSap (G-PSap) en fonctions bent ou semi-bent via la concaténation.

• Résultat Principal (Proposition 12 et Théorème 2) : Ils prouvent que, lorsque le degré du polynôme de permutation sous-jacent est suffisamment petit par rapport à la taille du corps fini ($m$), les fonctions G-PSap n'admettent généralement aucune décomposition en fonctions bent ou semi-bent.
• Preuve : En analysant la dérivée seconde du dual de la fonction, ils montrent qu'elle ne peut pas être constante (ni 0 ni 1) sur des sous-espaces de codimension 2, sauf dans des cas triviaux. L'existence de points rationnels sur les courbes associées (via le théorème de Hasse-Weil) garantit que la dérivée seconde prend à la fois les valeurs 0 et 1.
• Conséquence : Cela signifie que ces fonctions ne peuvent pas être obtenues par des constructions secondaires standards basées sur la concaténation de fonctions bent ou semi-bent, renforçant leur statut de "nouvelles" fonctions primaires.

C. Nouvelle Construction Secondaire par Concaténation

Bien que les G-PSap ne se décomposent pas, les auteurs proposent une construction secondaire inspirée de la structure des composantes des fonctions vectorielles G-PSap.

• Théorème 3 et 4 : Ils montrent comment concaténer des composantes spécifiques de fonctions vectorielles G-PSap (satisfaisant une propriété linéaire sur leurs duaux) pour générer de nouvelles fonctions bent scalaires. Cette construction fournit une méthode systématique pour créer des fonctions bent à partir de la structure des partitions de bent.

4. Signification et Impact

Ce travail apporte plusieurs avancées significatives dans le domaine de la cryptographie et de la théorie des fonctions booléennes :

1. Élargissement de l'espace de recherche : En fournissant des familles explicites de fonctions bent hors de $MM^\#$ et $PS_{ap}^\#$, les auteurs enrichissent le pool de fonctions disponibles pour la conception de systèmes cryptographiques robustes.
2. Limites des constructions secondaires : La démonstration que de nombreuses fonctions G-PSap ne sont pas décomposables remet en question l'idée que toutes les fonctions bent peuvent être générées à partir de constructions secondaires simples. Cela souligne la nécessité de méthodes de construction primaires plus sophistiquées.
3. Outils méthodologiques : L'application rigoureuse de la théorie des courbes algébriques (Hasse-Weil) pour prouver des propriétés combinatoires sur les fonctions booléennes offre un cadre puissant pour l'analyse future de classes de fonctions plus complexes.
4. Classification : Les résultats aident à mieux cartographier l'espace des fonctions bent, en identifiant des sous-classes qui échappent aux invariants classiques comme le degré algébrique ou le rang 2.

En résumé, cet article établit de nouvelles frontières pour la construction de fonctions bent, démontrant l'existence de structures riches et complexes qui ne peuvent être réduites aux classes classiques connues, tout en fournissant des outils mathématiques solides pour leur analyse.