🔢 mathematics

The combinatorial structure and value distributions of plateaued functions

Cet article étudie les propriétés combinatoires des fonctions en plateau, en établissant des liens directs entre leur transformée de Walsh, leur linéarité, leurs propriétés différentielles et leurs distributions de valeurs, notamment pour le cas particulier des fonctions « presque équilibrées » et des fonctions APN.

Auteurs originaux : Lukas Kölsch, Alexandr Polujan

Publié 2026-03-26

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Lukas Kölsch, Alexandr Polujan

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 êtes un architecte chargé de construire des coffres-forts numériques ultra-sécurisés. Pour que ces coffres-forts résistent aux cambrioleurs (les pirates informatiques), vous devez utiliser des briques de construction très spéciales. Ces briques sont appelées des fonctions mathématiques.

Dans ce papier de recherche, les auteurs, Lukas et Alexandr, étudient une catégorie particulière de ces briques qu'ils appellent des fonctions "plateauées".

Voici une explication simple de ce qu'ils ont découvert, en utilisant des analogies du quotidien.

1. Qu'est-ce qu'une fonction "plateauée" ?

Imaginez un terrain de montagne.

Une fonction linéaire serait une pente douce et régulière. C'est trop simple, un cambrioleur peut la grimper facilement.
Une fonction "bent" (très courbe) serait un pic de montagne très aigu et isolé. C'est très difficile à grimper, mais c'est une forme extrême.
Les fonctions "plateauées", ce sont des plateaux. Ce sont des zones plates au sommet de la montagne. Elles ne sont ni trop simples (comme une pente), ni trop extrêmes (comme un pic). Elles offrent un équilibre parfait : elles sont assez complexes pour résister aux attaques, mais assez régulières pour être utilisées dans des algorithmes rapides.

La plupart des fonctions utilisées dans les systèmes de cryptographie modernes (comme ceux qui protègent vos messages WhatsApp ou vos transactions bancaires) sont de ce type.

2. Le problème de la "Répartition" (Value Distribution)

Le cœur du problème étudié par les auteurs est la façon dont ces fonctions distribuent les résultats.

Imaginez que vous avez un distributeur de bonbons (la fonction). Vous mettez des pièces (les entrées) et il vous sort des bonbons (les sorties).

L'idéal : Le distributeur est parfaitement équilibré. Chaque type de bonbon sort exactement le même nombre de fois. C'est ce qu'on appelle une fonction "équilibrée".
La réalité : Souvent, le distributeur est un peu tordu. Certains bonbons sortent 100 fois, d'autres seulement 50 fois. C'est ce qu'on appelle un déséquilibre.

Les auteurs se demandent : "Si notre brique de construction (la fonction plateauée) n'est pas parfaitement équilibrée, à quel point peut-elle être tordue ?"

Ils ont découvert que ces fonctions "plateauées" ont une structure très rigide. Elles ne peuvent pas être tordues n'importe comment. Elles obéissent à des règles strictes, un peu comme un puzzle où certaines pièces ne peuvent s'assembler que d'une seule façon.

3. La "Carte de l'Énergie" (Transformée de Walsh)

Comment les auteurs voient-ils ces tordus ? Ils utilisent un outil mathématique appelé la transformée de Walsh.

Imaginez que vous prenez une photo de votre montagne (la fonction) avec une caméra thermique.

Les zones froides représentent les zones où la fonction ne fait rien.
Les zones chaudes représentent les zones d'activité intense.

Pour les fonctions "plateauées", cette photo thermique est très particulière : elle ne montre que deux niveaux de chaleur (ou zéro). C'est comme si la caméra ne voyait que des zones "très chaudes" et des zones "froides", sans les nuances intermédiaires.

Les auteurs ont utilisé cette "photo thermique" pour prédire exactement combien de fois chaque "bonbon" (sortie) va sortir du distributeur, même sans avoir à tester le distributeur des millions de fois. C'est comme pouvoir deviner la répartition des bonbons en regardant juste la forme de la machine.

4. Les Découvertes Clés (Les "Lois du Jeu")

Grâce à cette analyse, ils ont établi plusieurs règles importantes :

La règle du "Presque Parfait" : Ils ont défini une catégorie de fonctions qu'ils appellent "presque équilibrées". C'est le cas où le distributeur est presque parfait, sauf pour un seul type de bonbon qui sort un peu plus ou un peu moins que les autres. Ils ont prouvé que les fonctions "plateauées" tombent souvent dans cette catégorie très spécifique.
Le mystère des "Monômes" : Ils ont étudié des fonctions très simples, construites avec une seule formule mathématique (comme $x^3$ ou $x^5$ ). Ils ont découvert que pour que ces fonctions simples soient aussi sécurisées (plateauées), elles doivent suivre une règle très stricte sur leur "tordure". Elles ne peuvent être "plateauées" que si leur forme correspond à des nombres très précis (comme $2^k + 1$ ). C'est comme dire qu'une clé ne peut ouvrir une serrure que si elle a exactement 3 dents, ni 2, ni 4.
Les fonctions APN (Les Super-Héros) : Il existe un type de fonction encore plus puissant, appelé "APN" (Presque Parfaitement Non Linéaire), utilisé pour les systèmes les plus sûrs. Les auteurs ont montré que si ces super-fonctions sont aussi "plateauées", elles ont une structure de distribution de bonbons très limitée. En fait, ils ont prouvé qu'une certaine configuration de distribution (la deuxième option dans leur liste) est impossible pour ces fonctions. C'est comme dire : "Vous ne pouvez pas construire ce type de pont avec ces matériaux-là."

En résumé

Ce papier est une enquête mathématique pour comprendre la "géographie" des fonctions utilisées en cryptographie.

Les auteurs disent essentiellement : "Nous avons trouvé que ces fonctions spéciales (plateauées) ne peuvent pas être n'importe quoi. Elles ont une structure interne très rigide. Si vous connaissez leur 'carte thermique' (Walsh), vous pouvez prédire exactement comment elles distribuent leurs résultats. Cela nous aide à construire des coffres-forts plus sûrs et à éviter de gaspiller du temps à essayer de construire des briques qui ne fonctionneront jamais."

C'est un travail de fond qui permet aux ingénieurs de mieux choisir leurs briques pour protéger nos données numériques.

Résumé Technique : Structure Combinatoire et Distributions de Valeurs des Fonctions de Plateau

1. Problématique et Contexte

Les fonctions de plateau (plateaued functions) constituent une généralisation importante des fonctions quadratiques et des fonctions bent (parfaitement non linéaires). Elles jouent un rôle central en cryptographie, servant de blocs de construction pour des primitives telles que les fonctions APN (Almost Perfect Nonlinear), les permutations APN et diverses fonctions de hachage.

Le problème central abordé par les auteurs est l'analyse des distributions de valeurs (c'est-à-dire les tailles des ensembles d'images et de préimages) des fonctions de plateau vectorielles $F : \mathbb{F}_p^n \to \mathbb{F}_p^m$ . Bien que les propriétés différentielles et la non-linéarité de ces fonctions soient bien étudiées, leur structure combinatoire fine, en particulier leur équilibre (ou déséquilibre), reste moins comprise. L'objectif est de déterminer dans quelle mesure ces fonctions peuvent être "presque équilibrées" (almost balanced) et d'établir des liens directs entre leur transformée de Walsh, leur déséquilibre et leurs propriétés cryptographiques (uniformité différentielle, linéarité).

2. Méthodologie

Les auteurs développent une approche basée sur l'analyse spectrale, utilisant principalement la transformée de Walsh évaluée en $a=0$ .

Outils Spectraux : Ils exploitent les moments de la transformée de Walsh pour relier les coefficients spectraux aux tailles des ensembles de préimages. Une quantité clé introduite est l'imbalance ( $N_bF$ ), définie comme la somme normalisée des carrés des coefficients de Walsh non nuls en zéro :
$N_bF = \frac{1}{p^m} \sum_{b \in \mathbb{F}_p^m \setminus \{0\}} |W_F(b, 0)|^2$
Bornes Combinatoires : En utilisant l'inégalité de Cauchy-Schwarz et les propriétés des moments, ils dérivent des bornes strictes sur les tailles des ensembles de préimages en fonction de l'imbalance et de la taille de l'image.
Fonctions Presque Équilibrées : Ils définissent formellement les fonctions "presque équilibrées" comme celles atteignant l'égalité dans ces bornes, caractérisées par le fait que tous les éléments de l'image, sauf un, ont le même nombre de préimages.
Analyse des Fonctions $d$ -à-1 : Une attention particulière est portée aux fonctions où un seul élément a un préimage unique et tous les autres ont exactement $d$ préimages.

3. Contributions Clés et Résultats Principaux

A. Théorie Générale des Distributions de Valeurs

Théorème 3.3 : Établissement de bornes précises pour la taille de n'importe quel ensemble de préimage $|F^{-1}(\beta)|$ en fonction de la taille de l'image et de l'imbalance $N_bF$ .
Définition 3.7 : Introduction rigoureuse des fonctions "presque équilibrées" de type (+) ou (-) pour le cas non surjectif, généralisant les résultats antérieurs sur les fonctions bent.
Théorème 4.1 : Caractérisation des fonctions presque équilibrées surjectives. Il est démontré que pour de telles fonctions, les coefficients de Walsh $W_F(b, 0)$ sont constants (en valeur absolue) pour tout $b \neq 0$ , et que l'imbalance est directement liée à cette valeur constante.

B. Fonctions de Plateau et Fonctions $d$ -à-1

Théorème 5.2 : Restriction forte sur les fonctions de plateau qui sont $d$ -à-1. Il est prouvé que de telles fonctions ne peuvent exister que pour des valeurs très spécifiques de $d$ . Plus précisément, si $F$ est une fonction de plateau $d$ -à-1 avec $d > 2$ , alors $n$ doit être pair et $d$ doit être de la forme $d = p^t + 1$ (où $t$ divise $n/2$ ).
Structure des Composantes : Le théorème précise la répartition des composantes : la fonction possède un nombre exact de composantes bent et un nombre exact de composantes de plateau avec une amplitude spécifique ( $p^{n/2+t}$ ).
Corollaire 5.4 : Application aux fonctions monomiales $x^d$ . Les applications de plateau induites par des monômes sont soit des permutations, soit des applications $(p^t+1)$ -à-1.

C. Uniformité Différentielle et Linéarité

Théorèmes 5.5 et 5.6 : Lien direct entre l'amplitude du plateau et l'uniformité différentielle. Pour une fonction de plateau $t$ -plateaued, l'uniformité différentielle $\delta$ est au moins $p^t$ . L'égalité $\delta = p^t$ est atteinte si et seulement si la fonction est "différentiellement 2-valued" (les équations différentielles ont soit 0, soit $p^t$ solutions).
Constructions : Les auteurs fournissent des constructions explicites de fonctions presque équilibrées de plateau, notamment via des monômes (Théorème 5.8) et des fonctions de type Maiorana-McFarland (Propositions 5.9 et 5.10).

D. Fonctions APN de Plateau

Proposition 6.3 : Détermination des bornes inférieure et supérieure pour l'imbalance des fonctions APN de plateau.
- La borne inférieure est atteinte si et seulement si la fonction possède un nombre maximal de composantes bent et un nombre spécifique de composantes équilibrées.
- La borne supérieure est atteinte si aucune composante n'est équilibrée.
Théorème 6.7 : Résolution d'un problème ouvert concernant les distributions de valeurs des fonctions APN de plateau avec une image minimale. Il est démontré qu'une fonction APN de plateau ne peut pas avoir la deuxième distribution de valeurs possible (deux préimages de taille 2, le reste de taille 3). Seules la première (3-to-1) et potentiellement la troisième distribution sont possibles.
Théorème 6.8 : Démonstration que les fonctions APN de plateau avec une image minimale ne peuvent avoir aucune composante équilibrée.

4. Signification et Impact

Ce travail apporte une compréhension fondamentale de la structure interne des fonctions de plateau, reliant des concepts apparemment disjoints :

Unification Théorique : Il unifie l'étude des fonctions bent, quadratiques et APN sous le cadre général des fonctions de plateau, en utilisant l'analyse spectrale comme outil unificateur.
Contraintes de Conception : Les résultats imposent des contraintes sévères sur la conception de primitives cryptographiques basées sur des monômes ou des fonctions de plateau. Par exemple, il est impossible de construire une fonction de plateau $d$ -à-1 pour un $d$ arbitraire, ce qui guide la recherche de nouvelles fonctions APN.
Résolution de Problèmes Ouverts : En éliminant une des trois distributions de valeurs possibles pour les fonctions APN de plateau à image minimale, l'article réduit l'espace de recherche pour les contre-exemples ou les nouvelles constructions de permutations APN (problème "Big APN").
Outils pour la Cryptanalyse : Les bornes sur l'imbalance et la linéarité fournissent des métriques précises pour évaluer la résistance des fonctions contre les attaques linéaires et différentielles.

En conclusion, ce papier établit un cadre rigoureux reliant la transformée de Walsh, la distribution des valeurs et les propriétés différentielles, offrant de nouveaux outils pour l'analyse et la construction de fonctions cryptographiques robustes.