2025-11-10T02:46:09.476031

On Sum-Free Functions

Ebeling, Hou, Rydell et al.
A function from $\Bbb F_{2^n}$ to $\Bbb F_{2^n}$ is said to be {\em $k$th order sum-free} if the sum of its values over each $k$-dimensional $\Bbb F_2$-affine subspace of $\Bbb F_{2^n}$ is nonzero. This notion was recently introduced by C. Carlet as, among other things, a generalization of APN functions. At the center of this new topic is a conjecture about the sum-freedom of the multiplicative inverse function $f_{\text{\rm inv}}(x)=x^{-1}$ (with $0^{-1}$ defined to be $0$). It is known that $f_{\text{\rm inv}}$ is 2nd order (equivalently, $(n-2)$th order) sum-free if and only if $n$ is odd, and it is conjectured that for $3\le k\le n-3$, $f_{\text{\rm inv}}$ is never $k$th order sum-free. The conjecture has been confirmed for even $n$ but remains open for odd $n$. In the present paper, we show that the conjecture holds under each of the following conditions: (1) $n=13$; (2) $3\mid n$; (3) $5\mid n$; (4) the smallest prime divisor $l$ of $n$ satisfies $(l-1)(l+2)\le (n+1)/2$. We also determine the ``right'' $q$-ary generalization of the binary multiplicative inverse function $f_{\text{\rm inv}}$ in the context of sum-freedom. This $q$-ary generalization not only maintains most results for its binary version, but also exhibits some extraordinary phenomena that are not observed in the binary case.
academic

Sur les Fonctions Sans-Somme

Informations Fondamentales

  • ID de l'article: 2410.10426
  • Titre: On Sum-Free Functions
  • Auteurs: Alyssa Ebeling, Xiang-Dong Hou, Ashley Rydell, Shujun Zhao
  • Classification: math.NT (Théorie des nombres), cs.IT (Théorie de l'information), math.IT (Mathématiques de l'information)
  • Date de publication: Octobre 2024 (prépublication arXiv)
  • Lien de l'article: https://arxiv.org/abs/2410.10426

Résumé

Cet article étudie le concept de fonctions sans-somme sur les corps finis. Une fonction de F2n\mathbb{F}_{2^n} vers F2n\mathbb{F}_{2^n} est dite sans-somme d'ordre kk si la somme des valeurs de la fonction sur chaque sous-espace affine de dimension kk sur F2\mathbb{F}_2 est non nulle. Ce concept a été récemment introduit par C. Carlet comme généralisation des fonctions APN. Le cœur de la recherche porte sur une conjecture concernant les propriétés sans-somme de la fonction inverse multiplicative finv(x)=x−1f_{\text{inv}}(x)=x^{-1}. On sait que finvf_{\text{inv}} est sans-somme d'ordre 2 (équivalemment, d'ordre (n−2)(n-2)) si et seulement si nn est impair. La conjecture stipule que pour 3≤k≤n−33\le k\le n-3, finvf_{\text{inv}} n'est jamais sans-somme d'ordre kk. Cette conjecture a été prouvée pour nn pair, mais reste non résolue pour nn impair.

Contexte et Motivation de la Recherche

  1. Définition du problème: Cet article étudie les propriétés des fonctions sans-somme, en particulier les propriétés sans-somme de la fonction inverse multiplicative. Une fonction sans-somme est une fonction dont la somme des valeurs est non nulle sur tous les sous-espaces affines de dimension kk.
  2. Importance:
    • Les fonctions sans-somme constituent une généralisation naturelle des fonctions presque complètement non linéaires (APN), largement étudiées en cryptographie pour leurs propriétés de résistance aux attaques différentielles
    • Elles résolvent le problème de vulnérabilité des chiffrements par blocs aux attaques intégrales, qui exploitent la prévisibilité des sommes des valeurs des boîtes S sur les sous-espaces affines
    • D'un point de vue théorique, le concept de sans-somme possède un contenu mathématique riche
  3. Limitations existantes:
    • Pour le cas nn impair, la conjecture centrale (Conjecture 1.1) concernant les propriétés sans-somme de la fonction inverse multiplicative reste entièrement non résolue
    • Il manque des recherches sur les généralisations appropriées au cas qq-aire
  4. Motivation de la recherche: Faire progresser la compréhension de la théorie des fonctions sans-somme, en particulier résoudre les conjectures importantes liées à la fonction inverse multiplicative, et explorer ses généralisations sur des corps finis plus généraux.

Contributions Principales

  1. Preuve de la Conjecture 1.1 sous plusieurs conditions:
    • Le cas n=13n=13
    • Le cas 3∣n3|n
    • Le cas 5∣n5|n
    • Le cas où le plus petit facteur premier ll satisfait (l−1)(l+2)≤(n+1)/2(l-1)(l+2)\le (n+1)/2
  2. Détermination de la généralisation qq-aire "correcte" de la fonction inverse binaire: Preuve que la fonction gq−1(x)=1/xq−1g_{q-1}(x)=1/x^{q-1} est la généralisation qq-aire appropriée de finvf_{\text{inv}} dans le cas binaire
  3. Fourniture de nouvelles méthodes de preuve: Utilisation de la borne de Lang-Weil pour donner une nouvelle preuve que 4∈Kn4\in K_n (pour tous les n≥6n\ge 6)
  4. Découverte de phénomènes exceptionnels dans le cas qq-aire: Par recherche informatique, découverte que pour q=3,5q=3,5 et n=7n=7, gq−1g_{q-1} est sans-somme d'ordre kk pour tous les 1≤k≤61\le k\le 6 sur Fq7\mathbb{F}_{q^7}

Explication Détaillée des Méthodes

Définition de la Tâche

Étant donnée une fonction f:Fqn→Fqnf: \mathbb{F}_{q^n} \to \mathbb{F}_{q^n} sur le corps fini Fqn\mathbb{F}_{q^n}, étudier sa propriété sans-somme d'ordre kk, c'est-à-dire que pour tous les sous-espaces affines AA de dimension kk sur Fq\mathbb{F}_q, on a ∑x∈Af(x)≠0\sum_{x\in A} f(x) \neq 0.

Architecture de la Méthode Centrale

  1. Méthode du Déterminant de Moore:
    • Utilisation du déterminant de Moore Δ(X1,…,Xk)\Delta(X_1,\ldots,X_k) pour caractériser l'indépendance linéaire
    • Établissement du lien entre la propriété sans-somme et les zéros du déterminant de Moore
  2. Méthode des Polynômes Symétriques:
    • Reformulation du critère de discrimination de Carlet sous forme de polynômes symétriques
    • Introduction du polynôme Θk(X1,…,Xk)\Theta_k(X_1,\ldots,X_k)
  3. Méthode de la Borne de Lang-Weil:
    • Utilisation de la borne de Lang-Weil de la géométrie algébrique pour estimer le nombre de points sur les variétés algébriques sur les corps finis
    • Preuve de l'irréductibilité absolue de Θ4\Theta_4

Points d'Innovation Technique

  1. Cadre théorique unifié:
    • Établissement d'un cadre théorique unifié du cas binaire au cas qq-aire
    • Preuve que la plupart des résultats binaires peuvent être généralisés au cas qq-aire
  2. Nouvelles techniques de construction:
    • Le Théorème 3.3 fournit une méthode systématique pour construire de nouvelles violations sans-somme à partir de violations connues
    • Utilisation de la structure des sous-corps pour la construction récursive
  3. Preuve d'irréductibilité absolue:
    • Preuve technique de l'irréductibilité absolue du polynôme Θ4\Theta_4 en appendice
    • Étape clé pour l'application de la borne de Lang-Weil

Théorèmes Principaux et Résultats

Théorèmes Centraux

Théorème 3.6: Soit n≥3n\ge 3 un nombre impair et ll le plus petit facteur premier de nn. Si (l−1)(l+2)≤(n+1)/2(l-1)(l+2)\le (n+1)/2, alors la Conjecture 1.1 est vraie pour nn.

Théorème 4.6 (Critère de discrimination pour la version qq-aire): La fonction gq−1g_{q-1} n'est pas sans-somme d'ordre kk si et seulement s'il existe v1,…,vk∈Fqnv_1,\ldots,v_k\in \mathbb{F}_{q^n} tels que Δ(v1,…,vk)≠0\Delta(v_1,\ldots,v_k)\neq 0 mais Δ1(v1,…,vk)=0\Delta_1(v_1,\ldots,v_k)=0.

Corollaires Importants

Corollaire 3.7: Si 3∣n3|n, alors la Conjecture 1.1 est vraie pour nn.

Théorème 3.13: Si 5∣n5|n, alors la Conjecture 1.1 est vraie pour nn.

Résultats de Généralisation qq-aire

Proposition 4.7:

  • gq−1g_{q-1} est sans-somme d'ordre 1
  • Quand n≥2n\ge 2, gq−1g_{q-1} est sans-somme d'ordre 2 si et seulement si nn est impair

Configuration Expérimentale et Résultats

Vérification Informatique

  1. Cas n=13n=13: Vérification par recherche informatique que la Conjecture 1.1 est vraie pour n=13n=13
  2. Résultats numériques pour le cas qq-aire: Vérification informatique systématique pour q=3,5q=3,5 et 7≤n≤117\le n\le 11

Découvertes Principales

  • Pour q=3,5q=3,5 et n=7n=7, la fonction gq−1g_{q-1} est sans-somme d'ordre kk pour tous les 1≤k≤61\le k\le 6
  • Ce phénomène n'a jamais été observé dans le cas binaire, révélant les propriétés uniques du cas qq-aire

Travaux Connexes

Cet article s'appuie sur les travaux importants suivants:

  1. Travail fondateur de Carlet: Introduction du concept de fonctions sans-somme et théorie fondamentale
  2. Théorie des fonctions APN: Les fonctions sans-somme sont une généralisation des fonctions APN
  3. Théorie du déterminant de Moore sur les corps finis: Fournit des outils techniques importants
  4. Méthodes de géométrie algébrique: Application de la borne de Lang-Weil et autres outils

Conclusions et Discussion

Conclusions Principales

  1. Résolution de la conjecture importante concernant les propriétés sans-somme de la fonction inverse multiplicative sous plusieurs conditions
  2. Établissement d'un cadre théorique complet du cas binaire au cas qq-aire
  3. Découverte de phénomènes nouveaux dans le cas qq-aire

Limitations

  1. La Conjecture 1.1 pour le cas général nn impair reste entièrement non résolue
  2. Les cas les plus difficiles sont ceux où nn est premier ou produit de deux nombres premiers proches
  3. L'explication théorique des phénomènes exceptionnels dans le cas qq-aire nécessite des recherches approfondies

Directions Futures

  1. Résolution complète de la Conjecture 1.1
  2. Compréhension approfondie des propriétés spéciales du cas qq-aire
  3. Exploration des applications des fonctions sans-somme en cryptographie
  4. Étude de l'irréductibilité des polynômes Θk\Theta_k plus généraux

Évaluation Approfondie

Avantages

  1. Contributions théoriques significatives: Progrès substantiel sur un problème ouvert important
  2. Innovation méthodologique: Combinaison de la théorie des nombres, de la géométrie algébrique et des méthodes informatiques
  3. Résultats complets: Preuves théoriques et vérifications informatiques
  4. Valeur de généralisation: Établissement d'un cadre unifié du cas binaire au cas qq-aire

Insuffisances

  1. Conjecture centrale non entièrement résolue: Certains cas restent non couverts
  2. Complexité technique: Certaines preuves (notamment celle de l'irréductibilité en appendice) sont très techniques
  3. Exploration limitée des applications: Discussion limitée des applications cryptographiques pratiques

Impact

  1. Valeur académique: Avancement du développement de cette théorie émergente des fonctions sans-somme
  2. Contribution méthodologique: Fourniture de nouveaux outils et techniques pour traiter des problèmes similaires
  3. Signification interdisciplinaire: Connexion entre la théorie des nombres, la géométrie algébrique et la cryptographie

Scénarios d'Application

  1. Conception et analyse des boîtes S en cryptographie
  2. Étude des propriétés algébriques des fonctions sur les corps finis
  3. Conception de systèmes cryptographiques résistants aux attaques intégrales

Compléments de Détails Techniques

Rôle du Déterminant de Moore

Le déterminant de Moore Δ(X1,…,Xk)=det⁡(Xjqi−1)1≤i,j≤k\Delta(X_1,\ldots,X_k) = \det(X_j^{q^{i-1}})_{1\le i,j\le k} joue un rôle clé dans la détermination de l'indépendance linéaire. La propriété de zéro de sa variante Δ1\Delta_1 est directement liée à la violation de la propriété sans-somme.

Représentation par Polynômes Symétriques

En reformulant le critère de discrimination de Carlet sous forme de polynômes symétriques, l'auteur peut exploiter les résultats profonds de la théorie des fonctions symétriques, ce qui jette les bases de l'analyse ultérieure d'irréductibilité.

Application de la Borne de Lang-Weil

En prouvant l'irréductibilité absolue de Θ4\Theta_4, l'auteur peut appliquer la borne de Lang-Weil pour estimer précisément le nombre de points sur les variétés algébriques pertinentes, complétant ainsi la nouvelle preuve que 4∈Kn4\in K_n.

Cet article apporte des contributions importantes dans le domaine émergent des fonctions sans-somme, non seulement en faisant progresser théoriquement la compréhension de la conjecture centrale, mais aussi en établissant un cadre pour la généralisation à des cas plus généraux, jetant ainsi des bases solides pour les recherches futures.