The Star Product of Uniformly Random Codes

Résumé Technique : Le produit étoile de codes uniformément aléatoires

Énoncé du Problème
Cet article étudie la dimension attendue du produit étoile (également connu sous le nom de produit de Schur ou de Hadamard) de deux codes linéaires indépendants et uniformément aléatoires, $C_1$ et $C_2$, sur un corps fini $\mathbb{F}_q$. Les codes ont des dimensions prescrites $k_1$ et $k_2$ et une longueur $n$. Bien que le produit étoile soit une opération fondamentale en théorie des codes avec des applications dans la correction d'erreurs quantiques, la récupération d'information privée (PIR) et la multiplication de matrices distribuée sécurisée (SDMM), la dimension du produit étoile de deux codes aléatoires n'est pas triviale à déterminer. Des travaux antérieurs, tels que [19], ont estimé cette dimension en analysant l'indépendance linéaire de matrices de rang 1, établissant que la dimension attendue est égale à $\min\{n, k_1k_2\}$ avec une probabilité élevée sous des régimes de paramètres restreints. Cet article vise à fournir une analyse plus générale et explicite de la dimension attendue et de sa variance, en s'étendant au-delà de ces régimes restreints.

Méthodologie
Les auteurs établissent une correspondance entre le produit étoile de deux codes et l'évaluation de formes bilinéaires. Plus précisément, si $C_1$ et $C_2$ ont des matrices génératrices $G_1$ et $G_2$, le produit étoile $C_1 \star C_2$ est identifié comme l'image d'une application linéaire $\psi_{G_1, G_2}$ agissant sur l'espace des formes bilinéaires $B = \text{Bil}(\mathbb{F}_q^{k_1}, \mathbb{F}_q^{k_2})$. La dimension du produit étoile est donnée par $k_1k_2 - \dim(\ker \psi_{G_1, G_2})$.

Pour analyser la dimension attendue, les auteurs se concentrent sur le calcul de la taille attendue du noyau, $\mathbb{E}[|\ker \psi_{C_1, C_2}|]$. Ils utilisent un modèle probabiliste où les codes sont générés en choisissant les $n-k$ dernières colonnes d'une matrice génératrice systématique de manière uniforme. L'analyse implique :

1. Combinatoire énumérative : Compter le nombre de formes bilinéaires (représentées comme des matrices) de rang $r$ spécifique qui s'annulent sur les colonnes des matrices génératrices. Cela nécessite de compter les matrices avec des diagonales nulles et des motifs de zéros spécifiques.
2. Formules explicites : Dériver une formule explicite pour la taille attendue du noyau en utilisant les coefficients $q$-binomiaux et les principes d'inclusion-exclusion (Lemme 3.5 et Théorème 3.9).
3. Analyse asymptotique : Étudier le comportement de ces formules lorsque la taille du corps $q \to \infty$ et lorsque les dimensions des codes $k_1, k_2 \to \infty$ sous des conditions de croissance spécifiques.
4. Analyse de la variance : Utiliser les bornes dérivées sur la taille attendue du noyau pour borner la variance de la dimension du produit étoile.

Contributions Clés et Résultats

1. Borne Inférieure Explicite : L'article fournit une formule explicite pour la taille attendue du noyau de l'application d'évaluation, ce qui donne une borne inférieure explicite sur la dimension attendue du produit étoile pour tous les choix de paramètres (Corollaire 3.11). Cette approche diffère des analyses de matrices de rang 1 de [19] en offrant un compte combinatoire direct du noyau.

2. Asymptotique dans la Taille du Corps ($q \to \infty$) :

   • Les auteurs prouvent que lorsque la taille du corps $q$ tend vers l'infini, la dimension attendue du produit étoile atteint asymptotiquement sa valeur maximale possible, $\min\{n, k_1k_2\}$, quelle que soit la relation entre $k_1$ et $k_2$ (Corollaire 4.2).
   • Plus précisément, si $k_1k_2 < n$, la taille attendue du noyau tend vers 1 ; si $k_1k_2 = n$, elle tend vers 2 ; et si $k_1k_2 > n$, elle diverge.
   • La variance de la dimension est montrée comme décroissant asymptotiquement vers 0, avec des taux dépendant de si $k_1k_2 < n$ ou $k_1k_2 \ge n$ (Proposition 4.3).

3. Asymptotique dans les Dimensions des Codes ($k_1, k_2 \to \infty$) :

   • Sous des conditions de croissance « admissibles » (où $k_1$ et $k_2$ croissent strictement de manière monotone et où $k_1k_2$ ne croît pas trop rapidement par rapport à $q^{k_1}$), l'article prouve que la taille attendue du noyau se stabilise (Théorème 5.7).
   • Par conséquent, la dimension attendue du produit étoile atteint $\min\{n, k_1k_2\}$ avec une probabilité élevée à mesure que les dimensions augmentent (Corollaire 5.12).
   • La variance est montrée comme s'annulant asymptotiquement sous ces conditions, décroissant au moins exponentiellement si $n < k_1k_2$ ou si l'écart $n - k_1k_2$ croît linéairement (Proposition 5.14).

4. Comparaison avec les Travaux Antérieurs : Les résultats sont comparés avec l'approche des matrices de rang 1 de [19]. Les auteurs notent que leurs résultats couvrent une gamme de paramètres plus large, particulièrement pour des tailles de corps plus grandes $q \ge 3$, où leurs bornes sur la croissance des dimensions sont strictement plus fortes que celles de [19] (Remarque 5.13).

Signification et Implications
L'article affirme que ces résultats ont des implications directes dans plusieurs domaines :

• Récupération d'Information Privée (PIR) : Dans les schémas PIR basés sur les produits étoiles, le taux de récupération est borné par la dimension du produit étoile. Les résultats suggèrent que bien que les codes aléatoires produisent asymptotiquement des dimensions de produit étoile maximales (entraînant des taux de récupération plus faibles par rapport aux codes structurés comme les GRS), il reste une probabilité non négligeable sur de petits corps (par exemple, $\mathbb{F}_2$) d'échantillonner des paires de codes avec des dimensions sous-maximales. Cela implique que les recherches expérimentales de paires de codes aléatoires favorables pour la PIR sont viables, surtout dans des contextes sans erreur.
• Multiplication de Matrices Distribuée Sécurisée (SDMM) : Similairement à la PIR, le seuil de récupération et la tolérance aux défaillances dépendent de la dimension du produit étoile. Les conclusions indiquent que les constructions aléatoires n'atteignent généralement pas de bas seuils de récupération asymptotiques, mais que des instances pratiques avec des paramètres favorables peuvent encore être trouvées sur de petits corps.
• Correction d'Erreurs Quantiques : L'article discute des codes CSS-T binaires, qui nécessitent $C_2 \subseteq C_1 \cap (C_1 \star C_1)^\perp$. Les résultats impliquent que pour des codes de dimension suffisamment grande, le produit étoile $C_1 \star C_1$ est probablement grand, forçant le complément orthogonal à être petit. Cela suggère que la construction de codes CSS-T à haute distance en utilisant un code $C_1$ aléatoire est peu probable, car le code quantique résultant aurait une borne inférieure faible sur la distance minimale.
• Cryptanalyse : La dimension du produit étoile est utilisée comme un discriminateur dans la cryptographie basée sur les codes (par exemple, contre les codes Goppa). L'article note que bien que leurs résultats confirment que les codes aléatoires ont généralement des dimensions de produit étoile maximales (les rendant distinguables des codes structurés comme les codes Goppa qui ont des carrés plus petits), les plages de paramètres spécifiques analysées ne menacent pas actuellement la sécurité des systèmes de McEliece standards. Cependant, la méthodologie ouvre la porte à l'analyse des produits étoiles de différentes paires de codes pour explorer de nouvelles plages de paramètres.

Conclusion
L'article conclut que la dimension attendue du produit étoile de deux codes uniformément aléatoires atteint asymptotiquement son maximum théorique à mesure que la taille du corps augmente, et sous des conditions de croissance spécifiques, à mesure que les dimensions des codes augmentent. La variance s'annule dans ces régimes, indiquant une concentration de la mesure. Les auteurs identifient la dérivation de bornes inférieures serrées pour la variance et l'analyse des cas non asymptotiques comme des problèmes ouverts pour des travaux futurs.