Function-Based Minimal Linear Codes over Galois Rings $\mathrm{GR}(p^{n}, \ell)$: Minimality Criteria and Infinite Constructions

1. Problématique et Contexte

Les codes linéaires minimaux jouent un rôle central en cryptographie, notamment dans les schémas de partage de secrets, le calcul multipartite (MPC) et le partage de secrets vérifiable (VSS). Une propriété clé est que les mots de code minimaux correspondent aux sous-ensembles qualifiés minimaux d'un schéma de partage de secrets.

Jusqu'à récemment, la majorité des constructions de codes minimaux se sont concentrées sur les corps finis. Cependant, les anneaux finis, et plus particulièrement les anneaux de Galois $GR(p^n, \ell)$, offrent une structure algébrique plus riche (présence de diviseurs de zéro, idéaux non triviaux, structure de chaîne) qui peut conduire à des performances améliorées dans les protocoles cryptographiques et les systèmes de stockage distribué.

Le problème central abordé dans ce papier est le suivant :

• Comment caractériser et construire des codes linéaires minimaux sur l'anneau de Galois $GR(p^n, \ell)$ ?
• Comment généraliser les critères de minimalité basés sur les fonctions (introduits par Wu et al. pour les corps finis) au cadre des anneaux, en tenant compte des défis algébriques spécifiques aux diviseurs de zéro et à la structure de module ?

2. Méthodologie et Outils Théoriques

Les auteurs développent une approche structurale combinant la théorie des modules, la dualité de Frobenius et l'analyse de la valuation $p$-adique.

A. Structure Algébrique de $GR(p^n, \ell)$

L'analyse repose sur les propriétés fondamentales de l'anneau de Galois :

• Anneau de chaîne local : Les idéaux forment une chaîne $\{0\} \subset \langle p^{n-1} \rangle \subset \dots \subset \langle p \rangle \subset GR(p^n, \ell)$.
• Décomposition $p$-adique : Tout élément s'écrit de manière unique comme $c = c_0 + c_1p + \dots + c_{n-1}p^{n-1}$, où les coefficients appartiennent au système de Teichmüller.
• Distinction Unité / Diviseur de zéro : Un élément est une unité si et seulement si son coefficient dominant $c_0$ est non nul. Les diviseurs de zéro sont multiples de $p$.

B. Notion de "Root Word" (Mot Racine)

Une notion cruciale introduite est celle de root word (mot racine) : un vecteur $v \in GR(p^n, \ell)^m$ est un root word si au moins l'une de ses composantes est une unité (équivalent à dire que sa réduction modulo $p$ est non nulle dans le corps résiduel $\mathbb{F}_q$).

• Les auteurs démontrent que la minimalité d'un code est entièrement déterminée par le comportement de ses root words.
• Pour un root word $v$, le module orthogonal $v^\perp$ est un module libre de rang $m-1$.
• Pour un vecteur non-root (diviseur de zéro), le module orthogonal n'est pas libre et contient des éléments de torsion.

C. Dualité de Frobenius et Rang de McCoy

• L'anneau $GR(p^n, \ell)$ étant un anneau de Frobenius, la propriété de double orthogonalité $(C^\perp)^\perp = C$ est valable.
• L'indépendance linéaire est analysée via le rang de McCoy d'une matrice, qui correspond au rang de sa réduction modulo $p$ sur le corps fini $\mathbb{F}_q$. Cela permet de ramener les problèmes d'indépendance sur l'anneau à des problèmes sur le corps résiduel.

D. Stratégie de Construction par Fonctions

Les auteurs généralisent la méthode de Wu et al. (2022) :

1. On définit un code $C_f$ à partir d'une fonction $f: GR(p^n, \ell)^m \to GR(p^n, \ell)$ via une matrice génératrice dont les lignes sont des évaluations de $f$ et des vecteurs de coordonnées.
2. La minimalité du code est réduite à la vérification de la minimalité de cinq types spécifiques de mots de code (root words), classés selon la nature du coefficient scalaire (unité ou diviseur de zéro) et la nature du vecteur associé.
3. Pour chaque type, ils établissent des conditions de synchronisation entre la fonction $f$ et une forme linéaire $w \cdot x$.

3. Contributions Clés et Résultats

1. Caractérisation Complète de la Minimalité

Les auteurs établissent une condition nécessaire et suffisante pour qu'un code linéaire de dimension $m \ge 2$ sur $GR(p^n, \ell)$ soit minimal.

• Théorème Principal : Un code est minimal si et seulement si tous ses root words sont minimaux.
• Cela simplifie considérablement l'analyse, car elle ne nécessite pas d'examiner tous les vecteurs du code, mais seulement ceux qui ne sont pas annulés par la réduction modulo $p$.

2. Critères de Minimalité pour les Codes Basés sur des Fonctions

Pour un code $C_f$ généré par une fonction $f$, les auteurs dérivent des conditions précises pour les cinq types de root words :

• Cas Unité ($c(u, v)$) : Il existe une base $\{\beta_i\}$ telle que $f(\beta_i) = w \cdot \beta_i$.
• Cas Diviseur de Zéro ($c(pru, v)$) : La condition de synchronisation est modifiée par la valuation : $p^r f(\beta_i) = w \cdot \beta_i$.
• Ces conditions reflètent la géométrie sensible à la valuation de l'anneau, absente dans le cas des corps finis.

3. Constructions de Familles Infinies

En exploitant ces critères, les auteurs construisent plusieurs familles infinies de codes minimaux :

• Théorème 40 : Fournit des conditions générales sur une fonction $f$ (comportement sur les vecteurs de faible poids, invariance par unité, valeurs spécifiques pour les vecteurs de poids complet) garantissant la minimalité.
• Théorème 45 (Polynômes) : Applique ces résultats aux fonctions polynomiales. Ils montrent que des sommes de monômes avec des supports disjoints et des conditions sur les exposants (au moins un exposant égal à 1, taille du support $\ge 3$) génèrent des codes minimaux.
• Proposition 24 : Ils déterminent la longueur minimale exacte $k(2; GR(p^n, \ell))$ pour les codes de dimension 2, montrant que $k = q^n + q^{n-1}$, généralisant un résultat connu pour $\mathbb{Z}_{p^n}$.

4. Bornes de Longueur

Les auteurs dérivent des bornes inférieures explicites pour la longueur $k$ d'un code minimal de dimension $m$ sur $GR(p^n, \ell)$ :

• Pour $m \ge 3$ : $k > (m-1)q^n + q^{n-m}$.
• Pour $m = 2$ : Des bornes précises sont données selon la valeur de $n$ (ex: $k > q^n + q^{n-2} + 1$ pour $n \ge 3$).
• Ils construisent des codes qui atteignent ou se rapprochent de ces bornes, validant l'efficacité de leurs constructions.

4. Signification et Impact

Ce travail représente une avancée significative dans la théorie des codes sur les anneaux :

1. Unification Théorique : Il fournit un cadre unifié reliant la théorie de la minimalité, la dualité des modules sur les anneaux de Frobenius et les constructions basées sur les fonctions, étendant les résultats des corps finis aux anneaux de Galois.
2. Gestion des Diviseurs de Zéro : Le papier résout le défi technique majeur posé par les diviseurs de zéro en introduisant une classification fine des vecteurs (root vs non-root) et en adaptant les conditions de synchronisation via la valuation $p$-adique.
3. Applications Cryptographiques : En fournissant des familles infinies de codes minimaux sur des anneaux, le papier ouvre la voie à de nouveaux schémas de partage de secrets et de cryptographie post-quantique (notamment basée sur les réseaux) exploitant la structure des anneaux de Galois.
4. Généralisation : Les résultats généralisent les travaux de Wu et al. (2022) et de Ding et al., prouvant que les techniques de construction par fonctions sont robustes et adaptables au cadre des anneaux de chaîne finis.

En conclusion, ce papier établit les fondations algébriques nécessaires pour concevoir et analyser des codes minimaux sur les anneaux de Galois, offrant des outils puissants pour la recherche future en théorie des codes et en cryptographie sur les anneaux.