The Star Product of Uniformly Random Codes

Technische Samenvatting: Het sterproduct van uniform willekeurige codes

Probleemstelling
Dit artikel onderzoekt de verwachte dimensie van het sterproduct (ook wel bekend als het Schur- of Hadamard-product) van twee onafhankelijke, uniform willekeurige lineaire codes, $C_1$ en $C_2$, over een eindig lichaam $\mathbb{F}_q$. De codes hebben voorgeschreven dimensies $k_1$ en $k_2$ en lengte $n$. Hoewel het sterproduct een fundamentele operatie is in de coderingstheorie met toepassingen in quantumfoutcorrectie, private informatie-retrieval (PIR) en veilige gedistribueerde matrixvermenigvuldiging (SDMM), is de dimensie van het sterproduct van twee willekeurige codes niet triviaal te bepalen. Vorig werk, zoals [19], schatte deze dimensie door de lineaire onafhankelijkheid van rang-1 matrices te analyseren, waarbij werd vastgesteld dat de verwachte dimensie met hoge waarschijnlijkheid gelijk is aan $\min\{n, k_1k_2\}$ onder beperkte parametrische regimes. Dit artikel beoogt een meer algemene en expliciete analyse te bieden van de verwachte dimensie en de variantie, reikend voorbij deze beperkte regimes.

Methodologie
De auteurs vestigen een correspondentie tussen het sterproduct van twee codes en de evaluatie van bilineaire vormen. Specifiek, als $C_1$ en $C_2$ generatormatrices $G_1$ en $G_2$ hebben, wordt het sterproduct $C_1 \star C_2$ geïdentificeerd als het beeld van een lineaire afbeelding $\psi_{G_1, G_2}$ die werkt op de ruimte van bilineaire vormen $B = \text{Bil}(\mathbb{F}_q^{k_1}, \mathbb{F}_q^{k_2})$. De dimensie van het sterproduct wordt gegeven door $k_1k_2 - \dim(\ker \psi_{G_1, G_2})$.

Om de verwachte dimensie te analyseren, richten de auteurs zich op het berekenen van de verwachte grootte van de kern, $\mathbb{E}[|\ker \psi_{C_1, C_2}|]$. Zij maken gebruik van een probabilistisch model waarbij codes worden gegenereerd door de laatste $n-k$ kolommen van een systematische generatormatrix uniform willekeurig te kiezen. De analyse omvat:

1. Enumeratieve Combinatoriek: Het tellen van het aantal bilineaire vormen (gerepresenteerd als matrices) van een specifieke rang $r$ die nul zijn op de kolommen van de generatormatrix. Dit vereist het tellen van matrices met nul-diagonalen en specifieke nul-patronen.
2. Expliciete Formules: Het afleiden van een expliciete formule voor de verwachte kernomvang met behulp van $q$-binomialcoëfficiënten en inclusie-exclusie principes (Lemma 3.5 en Stelling 3.9).
3. Asymptotische Analyse: Het onderzoeken van het gedrag van deze formules naarmate het lichaam $q \to \infty$ gaat en naarmate de code-dimensies $k_1, k_2 \to \infty$ gaan onder specifieke groeicondities.
4. Variantie-analyse: Het gebruik van de afgeleide grenzen op de verwachte kernomvang om een bovengrens te stellen aan de variantie van de sterproductdimensie.

Belangrijkste Bijdragen en Resultaten

1. Expliciete Ondergrens: Het artikel biedt een expliciete formule voor de verwachte grootte van de kern van de evaluatieafbeelding, wat een expliciete ondergrens oplevert voor de verwachte dimensie van het sterproduct voor alle parameterkeuzes (Corollary 3.11). Deze aanpak verschilt van eerdere rang-1 matrixanalyses door een directe combinatorische telling van de kern aan te bieden.

2. Asymptotica in Lichaamsgrootte ($q \to \infty$):

   • De auteurs bewijzen dat naarmate de grootte van het lichaam $q$ naar oneindig gaat, de verwachte dimensie van het sterproduct asymptotisch zijn maximale mogelijke waarde bereikt, $\min\{n, k_1k_2\}$, ongeacht de relatie tussen $k_1$ en $k_2$ (Corollary 4.2).
   • Specifiek, als $k_1k_2 < n$, nadert de verwachte kernomvang 1; als $k_1k_2 = n$, nadert het 2; en als $k_1k_2 > n$, divergeert het.
   • De variantie van de dimensie wordt getoond als asymptotisch te vervallen naar 0, met snelheden die afhangen van of $k_1k_2 < n$ of $k_1k_2 \ge n$ (Proposition 4.3).

3. Asymptotica in Code-dimensies ($k_1, k_2 \to \infty$):

   • Onder "toelaatbare" groeicondities (waarbij $k_1$ en $k_2$ strikt monotoon groeien en $k_1k_2$ niet te snel groeit ten opzichte van $q^{k_1}$), bewijst het artikel dat de verwachte kernomvang stabiliseert (Theorem 5.7).
   • Gevolgelijk bereikt de verwachte dimensie van het sterproduct met hoge waarschijnlijkheid $\min\{n, k_1k_2\}$ naarmate de dimensies toenemen (Corollary 5.12).
   • De variantie wordt getoond als asymptotisch te verdwijnen onder deze condities, waarbij deze minstens exponentieel vervalt als $n < k_1k_2$ of als het verschil $n - k_1k_2$ lineair groeit (Proposition 5.14).

4. Vergelijking met Voorgaand Werk: De resultaten worden vergeleken met de rang-1 matrixbenadering van [19]. De auteurs merken op dat hun resultaten een breder scala aan parametrische regimes dekken, met name voor grotere lichaamssites $q \ge 3$, waar hun grenzen op de groei van dimensies strikt sterker zijn dan die in [19] (Remark 5.13).

Betekenis en Implicaties
Het artikel stelt dat deze resultaten directe implicaties hebben voor verschillende gebieden:

• Private Information Retrieval (PIR): In PIR-schema's gebaseerd op sterproducten wordt de retrieval rate begrensd door de dimensie van het sterproduct. De resultaten suggereren dat hoewel willekeurige codes asymptotisch maximale sterproductdimensies opleveren (wat leidt tot lagere retrieval rates vergeleken met gestructureerde codes zoals GRS), er nog steeds een niet-verwaarloosbare waarschijnlijkheid bestaat over kleine lichamen (bijv. $\mathbb{F}_2$) om paren van codes met sub-maximale dimensies te samplen. Dit impliceert dat experimentele zoektochten naar gunstige willekeurige codeparen voor PIR levensvatbaar zijn, vooral in foutvrije settings.
• Secure Distributed Matrix Multiplication (SDMM): Vergelijkbaar met PIR hangen de herstel-threshold en de straggler-tolerantie in SDMM af van de sterproductdimensie. De bevindingen geven aan dat willekeurige constructies doorgaans geen asymptotisch lage herstel-thresholds bereiken, maar dat praktische instanties met gunstige parameters nog steeds gevonden kunnen worden over kleine lichamen.
• Quantum Error Correction: Het artikel bespreekt binaire CSS-T codes, die vereisen dat $C_2 \subseteq C_1 \cap (C_1 \star C_1)^\perp$. De resultaten impliceren dat voor uniform willekeurige codes van voldoende grote dimensie, het sterproduct $C_1 \star C_1$ waarschijnlijk groot is, waardoor het orthogonaal complement klein wordt. Dit suggereert dat het construeren van CSS-T codes met een hoge afstand met behulp van een willekeurige $C_1$ onwaarschijnlijk is, aangezien de resulterende quantumcode een zwakke ondergrens op de minimale afstand zou hebben.
• Cryptanalyse: De sterproductdimensie wordt gebruikt als een distinguisher in code-gebaseerde cryptografie (bijv. tegen Goppa-codes). Het artikel merkt op dat hoewel hun resultaten bevestigen dat willekeurige codes over het algemeen maximale sterproductdimensies hebben (waardoor ze onderscheidbaar zijn van gestructureerde codes zoals Goppa-codes die kleinere kwadraten hebben), de specifieke parametrische bereiken die geanalyseerd worden momenteel de veiligheid van standaard McEliece-systemen niet bedreigen. Echter, de methodologie opent de deur naar het analyseren van sterproducten van verschillende codeparen om nieuwe parametrische bereiken te verkennen.

Conclusie
Het artikel concludeert dat de verwachte dimensie van het sterproduct van twee uniform willekeurige codes asymptotisch zijn theoretische maximum bereikt naarmate de grootte van het lichaam toeneemt, en onder specifieke groeicondities, naarmate de code-dimensies toenemen. De variantie verdwijnt in deze regimes, wat duidt op een concentratie van de maat. De auteurs identificeren de afleiding van nauwe variantie-grenzen en de analyse van niet-asymptotische gevallen als openstaande problemen voor toekomstig werk.