Sur les spectres de Walsh des fonctions APN quadratiques

Informations de base

• ID de l'article : 2510.12008
• Titre : On the Walsh spectra of quadratic APN functions
• Auteurs : Sophie Hannah Bénéteau (University of Florida), Nicolas Goluboff (University of Massachusetts Amherst), Lukas Kölsch (University of South Florida), Divyesh Vaghasiya (University of South Florida)
• Classification : math.CO cs.IT math.IT
• Date de publication : 15 octobre 2025 (prépublication arXiv)
• Lien de l'article : https://arxiv.org/abs/2510.12008

Résumé

Les fonctions APN (Almost Perfect Nonlinear) jouent un rôle central dans la conception des chiffrements par blocs, constituant les fonctions optimales pour résister aux attaques différentielles. L'une des propriétés les plus importantes des fonctions APN est leur linéarité, directement liée au spectre de Walsh de la fonction. Cet article établit deux nouvelles connexions qui nous permettent de dériver des conditions fortes sur le spectre de Walsh des fonctions APN quadratiques. L'article démontre que la transformée de Walsh d'une fonction APN quadratique $F$ opérant sur $n=2k$ bits est uniquement associée à une partition d'espace vectoriel de $\mathbb{F}_2^n$ et à un ensemble de blocage spécifique dans l'espace projectif correspondant $PG(n-1,2)$. Ces connexions nous permettent de prouver plusieurs résultats concernant le spectre de Walsh de $F$, notamment que $F$ peut avoir au maximum une fonction composante avec une amplitude supérieure à $2^{\frac{3}{4}n}$, et nous trouvons la première borne non triviale sur le nombre de fonctions composantes courbes des fonctions APN quadratiques.

Contexte et motivation de la recherche

Importance du problème

1. Applications cryptographiques : Les fonctions APN sont des éléments de construction essentiels dans la conception des systèmes cryptographiques symétriques, en particulier dans les réseaux de substitution-permutation (SPN) des chiffrements par blocs, offrant une résistance optimale aux attaques différentielles.
2. Défis théoriques : Bien que la distribution d'amplitude des fonctions APN quadratiques en dimension impaire ait été complètement déterminée (toutes les composantes non triviales ayant une amplitude $2^{\frac{n+1}{2}}$), le cas de dimension paire reste un problème ouvert.
3. Limitations existantes :
   • Pour $n$ pair, les seules contraintes connues sur l'amplitude proviennent de la caractérisation par les moments d'ordre quatre de la transformée de Walsh
   • Absence de bornes non triviales sur le nombre de fonctions composantes courbes des fonctions APN quadratiques
   • Compréhension insuffisante de la structure profonde du spectre de Walsh

Motivation de la recherche

Cet article vise à approfondir la compréhension des propriétés structurelles du spectre de Walsh en établissant de nouvelles connexions entre les fonctions APN quadratiques et les objets géométriques (partitions d'espaces vectoriels et ensembles de blocage), et à dériver des conditions de contrainte plus fortes.

Contributions principales

1. Établissement de connexions avec les partitions d'espaces vectoriels : Démonstration d'une correspondance biunivoque entre la distribution d'amplitude d'une fonction APN quadratique $F: \mathbb{F}_2^n \to \mathbb{F}_2^n$ ($n$ pair) et les partitions d'espace vectoriel de $\mathbb{F}_2^n$.
2. Construction de la théorie des ensembles de blocage : Démonstration que l'ensemble des fonctions composantes non triviales et non courbes $N_F$ forme un ensemble de blocage spécial dans l'espace projectif $PG(n-1,2)$.
3. Dérivation de nouvelles conditions de contrainte :
   • Démonstration que $F$ peut avoir au maximum une fonction composante avec une amplitude supérieure à $2^{\frac{3}{4}n}$
   • Établissement de la première borne non triviale sur le nombre de fonctions composantes courbes
   • Fourniture de conditions nécessaires pour que la fonction soit équivalente CCZ à une permutation
4. Analyse complète pour les petites dimensions : Analyse exhaustive pour les dimensions 6, 8 et 10, déterminant toutes les distributions d'amplitude possibles.

Détails méthodologiques

Définition de la tâche

Étudier la structure du spectre de Walsh des fonctions APN quadratiques $F: \mathbb{F}_2^n \to \mathbb{F}_2^n$ ($n$ pair), où :

• Entrée : Fonction APN quadratique $F$
• Sortie : Conditions de contrainte et propriétés structurelles du spectre de Walsh
• Objectif : Comprendre les possibilités et limitations de la distribution d'amplitude

Cadre théorique fondamental

1. Théorie des partitions d'espaces vectoriels

Définition de la fonction différentielle : Pour tout $a \in \mathbb{F}_2^n$ non nul, définir $D_{F,a}(x) = F(x) + F(x+a)$.

Construction d'espaces vectoriels : Définir

• $T_b = \{a \in \mathbb{F}_2^n : \text{Im}(D_{F,a}) = H_b\} \cup \{0\}$
• $\overline{T_b} = \{a \in \mathbb{F}_2^n : \text{Im}(D_{F,a}) = \overline{H_b}\}$
• $V_b = T_b \cup \overline{T_b}$

où $H_b = \{x \in \mathbb{F}_2^n : \langle b,x \rangle = 0\}$.

Théorème principal (Théorème 2.4) : L'amplitude de $F_b$ est $2^{\frac{n+\dim(V_b)}{2}}$.

2. Théorie des ensembles de blocage

Propriétés des ensembles de blocage : L'ensemble des fonctions composantes non triviales et non courbes $N_F$ forme un ensemble de blocage par rapport aux $(n/2)$-espaces dans $PG(n-1,2)$, avec une intersection de taille impaire avec chaque $(n/2)$-espace.

Résultat clé : Utilisation du théorème de Govaerts-Storme sur la taille des ensembles de blocage minimaux non triviaux pour obtenir une borne sur le nombre de fonctions composantes courbes.

Points d'innovation technique

1. Approche géométrique : Première transformation du problème du spectre de Walsh des fonctions APN quadratiques en un problème géométrique de partitions d'espaces vectoriels et d'ensembles de blocage.
2. Caractérisation structurelle : Détermination directe de l'amplitude de la fonction composante $F_b$ via $\dim(V_b)$, établissant un lien direct entre la structure algébrique et les propriétés spectrales.
3. Application interdisciplinaire : Application ingénieuse de la théorie profonde des partitions d'espaces vectoriels et des ensembles de blocage en géométrie finie.

Configuration expérimentale

Méthodes de vérification théorique

Cet article est principalement une recherche théorique, vérifiée par les méthodes suivantes :

1. Analyse complète pour les petites dimensions :
   • Dimension 6 : Vérification que tous les types de partitions d'espaces vectoriels possibles correspondent à des fonctions APN quadratiques connues
   • Dimension 8 : Détermination de 18 distributions d'amplitude possibles
   • Dimension 10 : Analyse de tous les cas théoriquement possibles
2. Vérification sur des fonctions connues :
   • Vérification des fonctions classiques du spectre de Walsh
   • Analyse des fonctions de linéarité maximale
   • Vérification des propriétés d'ensembles de blocage de la fonction $x^3$

Outils de calcul

L'article utilise la vérification assistée par ordinateur pour :

• Énumérer toutes les partitions d'espaces vectoriels possibles pour les petites dimensions
• Vérifier la cohérence des résultats théoriques avec les fonctions APN connues

Résultats expérimentaux

Résultats théoriques principaux

1. Contraintes d'amplitude (Théorème 2.10)

Résultat : Soit $n$ pair et $F: \mathbb{F}_2^n \to \mathbb{F}_2^n$ une fonction APN quadratique avec linéarité $L(F) = 2^{\frac{n+l}{2}}$ et $l > n/2$, alors :

• $F$ possède exactement une fonction composante avec amplitude $2^{\frac{n+l}{2}}$
• Toutes les autres composantes ont une amplitude au plus $2^{\frac{2n-l}{2}}$
• En particulier, toute fonction APN quadratique possède au maximum une fonction composante avec amplitude supérieure à $2^{\frac{3n}{4}}$

2. Borne supérieure sur les fonctions composantes courbes (Théorème 3.9)

Résultat : Soit $n \geq 6$ pair et $F: \mathbb{F}_2^n \to \mathbb{F}_2^n$ une fonction APN quadratique, alors : $|N_F| \geq 2^{n/2} + 2^{n/2-2} + 2^{n/2-3} - 1$ où l'égalité n'est possible que pour $n=8$.

3. Classification complète pour la dimension 8 (Théorème 4.5)

Pour une fonction APN quadratique $F: \mathbb{F}_2^8 \to \mathbb{F}_2^8$, les distributions d'amplitude possibles sont :

• $[0^{190}, 2^{64}, 6^1]$
• $[0^{238-4i}, 2^{5i}, 4^{17-i}]$, où $1 \leq i \leq 17$

Analyse d'ablation

1. Comparaison des bornes (Proposition 4.4)

Comparaison de trois bornes inférieures différentes pour $|N_F|$ :

• Borne de partition d'espace vectoriel : La plus forte quand $k < n/2$
• Borne d'ensemble de blocage : La plus forte quand $k = n/2$
• Borne de dimension : La plus forte quand $k > n/2$

2. Analyse d'équivalence

Démonstration que sous équivalence EA :

• Les partitions d'espaces vectoriels préservent l'équivalence (Théorème 5.2)
• Les ensembles de blocage préservent l'équivalence (Théorème 5.1)

Découvertes importantes

1. Contraintes structurelles : Le spectre de Walsh des fonctions APN quadratiques est soumis à des contraintes géométriques strictes, n'étant pas arbitraire.
2. Effet de dimension : Avec l'augmentation de la dimension, le nombre de distributions d'amplitude possibles diminue drastiquement.
3. Conditions d'équivalence CCZ : Si une fonction quadratique est équivalente CCZ à une permutation, alors $|N_F| \geq 3(2^{n/2} - 1)$.

Travaux connexes

Principales directions de recherche

1. Classification des fonctions APN : Travaux de Carlet, Charpin, Zinoviev et autres
2. Théorie du spectre de Walsh : Méthode des moments d'ordre quatre et bornes de linéarité
3. Partitions d'espaces vectoriels : Théorie de construction de Heden, Bu et autres
4. Théorie des ensembles de blocage : Bornes optimales de Govaerts-Storme

Avantages de cet article

• Première établissement de connexions directes entre le spectre de Walsh et les objets géométriques
• Fourniture de conditions de contrainte plus fortes que la méthode classique des moments d'ordre quatre
• Unification des perspectives algébrique et géométrique

Conclusion et discussion

Conclusions principales

1. Le spectre de Walsh des fonctions APN quadratiques possède une structure géométrique profonde
2. Les partitions d'espaces vectoriels et les ensembles de blocage fournissent des outils puissants pour comprendre le spectre de Walsh
3. La plupart des distributions d'amplitude théoriquement possibles ne peuvent pas être réalisées en pratique

Limitations

1. Problèmes de construction : La théorie exclut de nombreuses possibilités, mais ne fournit pas de nouvelles méthodes de construction
2. Restriction de dimension : Les résultats principaux se concentrent sur les dimensions paires
3. Complexité computationnelle : L'analyse complète pour les dimensions élevées reste difficile

Directions futures

L'article propose 6 problèmes ouverts, notamment :

1. Trouver des exemples de distributions d'amplitude manquantes en dimension 8
2. Améliorer les bornes sur $|N_F|$
3. Trouver davantage de types de partitions d'espaces vectoriels non réalisables

Évaluation approfondie

Points forts

1. Innovativité théorique : Établissement d'une nouvelle perspective géométrique pour comprendre le spectre de Walsh
2. Systématicité méthodologique : Étude systématique sous deux angles : partitions d'espaces vectoriels et ensembles de blocage
3. Profondeur des résultats : Obtention de plusieurs bornes non triviales pour la première fois
4. Complétude de l'analyse : Analyse exhaustive pour les petites dimensions

Insuffisances

1. Absence de construction : Résultats principalement exclusifs, manque de nouvelles constructions de fonctions APN
2. Vérification computationnelle : Certains résultats dépendent de la vérification informatique, les preuves théoriques ne sont pas complètes
3. Limitations d'application : Contributions principalement théoriques, la valeur pratique en cryptographie reste à vérifier

Impact

1. Valeur académique : Fourniture de nouveaux outils et perspectives de recherche pour la théorie des fonctions APN
2. Contribution méthodologique : L'approche géométrique peut inspirer la recherche sur d'autres problèmes cryptographiques
3. Problèmes ouverts : Les problèmes proposés indiquent les directions de recherche futures

Domaines d'application

• Analyse théorique des fonctions APN quadratiques
• Conception et analyse des boîtes de substitution en cryptographie
• Recherche sur l'application de la géométrie finie en cryptographie
• Étude de la structure du spectre de Walsh des fonctions booléennes

Références

L'article cite 25 références importantes, couvrant plusieurs domaines tels que la théorie des fonctions APN, les partitions d'espaces vectoriels et la théorie des ensembles de blocage, reflétant les caractéristiques de la recherche interdisciplinaire. Les références clés incluent le traité sur les fonctions booléennes de Carlet, les travaux de Govaerts-Storme sur les ensembles de blocage, ainsi que la recherche de Heden et autres sur les partitions d'espaces vectoriels.