Two Families of Linear Codes Containing Non-GRS MDS Codes

Resumo Técnico: Duas Famílias de Códigos Lineares Contendo Códigos MDS Não-GRS

1. Problema e Contexto

Os códigos de distância máxima separável (MDS) são fundamentais na teoria de códigos, com aplicações em armazenamento distribuído, criptografia e geometria finita. Um código MDS atinge o limite de Singleton ($d = n - k + 1$). A classe mais conhecida e estudada de códigos MDS são os códigos de Reed-Solomon generalizados (GRS).

No entanto, para aplicações criptográficas (como resistência a ataques de Sidelnikov-Shestakov e Wieschebrink), códigos que não sejam equivalentes a códigos GRS (chamados de não-GRS MDS) são essenciais. A classificação de códigos MDS não-GRS é um problema aberto e desafiador, especialmente para comprimentos maiores que $q+1$ ou em casos onde a conjectura de MDS sugere que apenas curvas racionais normais (equivalentes a GRS) existem.

O objetivo deste trabalho é construir novas famílias de códigos lineares que contenham códigos MDS não-GRS, fornecendo condições explícitas para suas propriedades e caracterizando suas estruturas de paridade e dualidade.

2. Metodologia

Os autores propõem duas novas famílias de códigos, denotadas por $C_{i,j}$ e $C_{h,k}$, construídas a partir da modificação das matrizes geradoras de códigos GRS. A metodologia baseia-se nas seguintes ferramentas matemáticas:

• Modificação de Matrizes Geradoras:
  • Família $C_{i,j}$: Obtida removendo as linhas $(i+1)$-ésima e $(j+1)$-ésima da matriz geradora de um código RS de dimensão $k+2$.
  • Família $C_{h,k}$: Obtida substituindo a última linha (potência $k-1$) da matriz geradora de um código RS por uma linha de potências $h$, onde $h \ge k$.
• Matrizes de Verificação de Paridade: Derivação explícita das matrizes de verificação de paridade ($H$) para ambas as famílias, utilizando funções simétricas elementares ($\sigma_t$) e completas ($S_t$), bem como a regra de Cramer e propriedades de matrizes de Vandermonde.
• Critério de Não-GRS (Produto de Schur): Utilização do método do quadrado de Schur (produto de Hadamard). Um código MDS $C$ é GRS se e somente se $\dim(C \star C) = 2\dim(C) - 1$ (para $\dim(C) \le (n-1)/2$). Se a dimensão do quadrado de Schur for maior, o código é não-GRS.
• Teoria de Funções Simétricas: Uso extensivo de identidades entre funções simétricas elementares e completas para provar a não-singularidade de submatrizes (condição MDS) e a ortogonalidade.

3. Principais Contribuições e Resultados

A. Família $C_{i,j}$ (Remoção de Linhas)

• Construção: Remove duas linhas específicas de um código RS de dimensão $k+2$.
• Condição MDS: O código é MDS se e somente se uma combinação específica de funções simétricas elementares de subconjuntos de pontos de avaliação seja não nula (Teorema 3.5).
• Propriedade Não-GRS:
  • Para $k=3$ e $k=4$, sob certas condições de $n$ e $q$, os códigos são não-GRS.
  • Para $k \ge 5$, demonstra-se que $\dim(C_{i,j} \star C_{i,j}) \ge 2k + 1$, provando que são não-GRS (Teorema 3.7).
• Auto-ortogonalidade e Auto-dualidade:
  • Estabelecem condições necessárias e suficientes para a existência de vetores de escalarização $v$ tais que o código seja auto-ortogonal.
  • Mostram que códigos $C_{i,j,v}$ nunca são auto-duais para certos parâmetros, mas fornecem construções explícitas de códigos auto-duais para casos específicos (ex: $n=2k$).

B. Família $C_{h,k}$ (Substituição de Potência)

• Construção: Mantém as primeiras $k-1$ linhas de um código RS e substitui a última linha por potências $h$ (onde $h = k-1+r$).
• Condição MDS: O código é MDS se e somente se a função simétrica completa $S_{h-k+1}$ avaliada em qualquer subconjunto de $k$ pontos distintos seja não nula (Teorema 4.2).
• Propriedade Não-GRS:
  • Demonstram que para uma vasta gama de parâmetros ($r \ge 1$), a dimensão do quadrado de Schur excede $2k-1$, garantindo a propriedade não-GRS (Teoremas 4.3, 4.4, 4.5).
  • Construções Explícitas: Apresentam construções de códigos não-GRS com comprimentos significativos, incluindo:
    • Comprimentos até $\approx (q/p)^{1/2}$ usando polinômios sobre campos finitos.
    • Comprimentos $q+2$ para $q=2^m$ (relacionados a hiperovalos e o-monomiais).
    • Comprimentos $(q-1)/2$ para $q$ ímpar.
• Auto-ortogonalidade e Auto-dualidade:
  • Derivam condições polinomiais para a existência de códigos auto-ortogonais.
  • Fornecem uma caracterização completa para códigos auto-duais quando $q$ é par, mostrando que eles existem sob condições específicas de $r$ e somas de potências ($S_1=0$).

4. Significância e Impacto

• Expansão do Conhecimento Teórico: O trabalho enriquece a classificação de códigos MDS não-GRS, mostrando que existem famílias distintas das construídas anteriormente (como códigos torcidos ou códigos derivados de remoção de linhas únicas).
• Novas Famílias de Códigos: As famílias $C_{i,j}$ e $C_{h,k}$ oferecem novas estruturas com propriedades de distância e paridade controláveis, úteis para o design de sistemas de comunicação e armazenamento.
• Aplicações Criptográficas: Ao fornecer códigos MDS que não são equivalentes a GRS, o trabalho oferece ferramentas para mitigar ataques criptográficos que exploram a estrutura específica dos códigos GRS.
• Códigos Auto-Duais: A caracterização de códigos auto-duais dentro dessas famílias é crucial para a teoria de códigos quânticos (códigos CSS) e criptografia baseada em reticulados.
• Construções Eficientes: Os autores não apenas provam a existência, mas fornecem algoritmos e exemplos numéricos explícitos para a construção desses códigos em campos finitos específicos.

5. Conclusão e Trabalhos Futuros

Os autores concluem que as duas famílias propostas contêm códigos MDS não-GRS que não são equivalentes a classes conhecidas anteriormente. Eles identificam como direção futura a generalização para códigos $C_I$ obtidos pela remoção de um número arbitrário de linhas da matriz de Vandermonde, embora reconheçam que as condições para MDS nessas generalizações tornam-se significativamente mais complexas e desafiadoras tecnicamente.

O trabalho é apoiado por uma análise rigorosa de álgebra linear sobre campos finitos e teoria de funções simétricas, estabelecendo um novo marco na construção de códigos ótimos com propriedades de segurança aprimoradas.