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

Resumo Técnico: Códigos Lineares Mínimos sobre Anéis de Galois

1. Problema e Contexto

Os códigos lineares mínimos são uma classe fundamental de códigos com aplicações críticas em esquemas de compartilhamento de segredos, computação multipartidária (MPC) e verificação de compartilhamento de segredos. A propriedade de minimalidade garante que o suporte de qualquer palavra-código não-nula seja mínimo em relação à inclusão de suportes, o que corresponde diretamente às subconjuntos qualificados mínimos em esquemas de acesso.

Historicamente, a construção e caracterização de códigos mínimos foram estudadas extensivamente sobre corpos finitos ($\mathbb{F}_q$). No entanto, há um interesse crescente em códigos definidos sobre anéis finitos, especificamente Anéis de Galois ($GR(p^n, \ell)$), devido à sua estrutura algébrica mais rica (presença de divisores de zero e ideais não triviais).

O problema central abordado neste trabalho é a generalização dos critérios de minimalidade e das construções baseadas em funções do cenário de corpos finitos para o cenário de anéis de Galois. A transição de corpos para anéis introduz desafios algébricos significativos, como a presença de divisores de zero e uma estrutura de módulo mais complexa, onde vetores não nulos podem ser anulados por escalares não nulos (elementos de torção).

2. Metodologia

Os autores utilizam uma abordagem estrutural baseada na teoria de módulos sobre anéis de Frobenius e na dualidade de Galois. A metodologia pode ser dividida nos seguintes pilares:

• Caracterização Estrutural via Dualidade de Frobenius:

  • Aproveitando que $GR(p^n, \ell)$ é um anel de Frobenius, os autores utilizam a propriedade de dualidade perfeita ($(C^\perp)^\perp = C$).
  • Eles estabelecem que a minimalidade de um código é determinada inteiramente pelo comportamento de seus vetores "root words" (palavras-raiz). Um vetor é uma "root word" se não for aniquilado por nenhum escalar não nulo (equivalente a ter pelo menos uma componente que é uma unidade no anel).
  • Para dimensões $m \ge 2$, demonstram que um código é mínimo se e somente se todas as suas "root words" forem mínimas. Isso reduz o problema global de minimalidade à análise de vetores específicos e seus módulos ortogonais.

• Análise de Módulos Ortogonais e Torção:

  • Diferentemente dos corpos finitos, onde o módulo ortogonal de um vetor não nulo é sempre livre de posto $m-1$, em anéis de Galois, a estrutura do módulo ortogonal depende se o vetor é uma "root word" ou não.
  • Os autores classificam os vetores e analisam como a multiplicação por potências de $p$ (divisores de zero) altera a estrutura do módulo ortogonal, introduzindo camadas de torção.

• Construção Baseada em Funções (Generalização de Wu et al.):

  • Adotam o paradigma de construção de Wu et al. (2022), onde códigos são gerados por matrizes definidas por funções $f: GR(p^n, \ell)^m \to GR(p^n, \ell)$.
  • Derivam condições de sincronização necessárias e suficientes entre a função $f$ e formas lineares associadas.
  • Identificam cinco tipos distintos de vetores de raiz no código gerado e estabelecem condições específicas para cada tipo:
    1. Caso Unitário: $f(\beta_i) = w \cdot \beta_i$.
    2. Caso Divisor de Zero: $p^r f(\beta_i) = w \cdot \beta_i$ (refletindo a valoração $p$-ádica).
  • Utilizam Lemas de Construção de Bases para garantir a existência de bases com propriedades específicas de suporte (peso de Hamming) e componentes unitárias, essenciais para satisfazer as condições de minimalidade.

3. Contribuições Principais

1. Critérios Necessários e Suficientes de Minimalidade:

   • Estabelecem uma caracterização completa para códigos lineares $m$-dimensionais sobre $GR(p^n, \ell)$ (para $m \ge 2$). O resultado chave (Teorema 17) afirma que a minimalidade do código é equivalente à minimalidade de todas as suas "root words".
   • Fornecem limites inferiores explícitos para o comprimento ($k$) de códigos mínimos de dimensão $m$, generalizando resultados conhecidos para corpos finitos.

2. Generalização do Paradigma Baseado em Funções:

   • Generalizam os critérios de Wu et al. para o contexto de anéis. A principal inovação é a introdução de condições de sincronização que dependem da valoração $p$-ádica dos coeficientes. Enquanto em corpos a condição é linear simples, em anéis de Galois, para divisores de zero, a condição envolve potências de $p$ ($p^r f(\beta) = w \cdot \beta$).

3. Construções Infinitas de Famílias de Códigos:

   • Apresentam construções explícitas de famílias infinitas de códigos mínimos sobre $GR(p^n, \ell)$ utilizando funções polinomiais e funções genéricas que satisfazem as condições derivadas.
   • Demonstram que, ao restringir a função $f$ apenas ao conjunto de "root words", ainda se obtém códigos mínimos, o que simplifica a definição da função.

4. Classificação de Vetores e Redução de Torção:

   • Mostram que, para $m \ge 2$, a estrutura de torção intrínseca aos anéis de Galois não cria novos obstáculos à minimalidade além daqueles já capturados pela análise das "root words". Isso permite "levantar" resultados de corpos finitos para anéis de Galois de forma controlada.

4. Resultados Chave

• Teorema de Caracterização (Teorema 17): Um código linear $C$ de dimensão $m \ge 2$ sobre $GR(p^n, \ell)$ é mínimo se e somente se todas as suas "root words" forem mínimas.
• Limites de Comprimento:
  • Para $m \ge 3$: $k > (m-1)q^n + q^{n-m}$.
  • Para $m = 2$: O comprimento mínimo exato é determinado como $k(2; GR(p^n, \ell)) = q^n + q^{n-1}$, generalizando o resultado conhecido para anéis $\mathbb{Z}_{p^n}$.
• Construções Polinomiais (Teorema 45): São apresentadas condições sobre polinômios (monômios com suportes disjuntos e graus específicos) que garantem a minimalidade do código gerado.
• Unificação: Os resultados recuperam os casos conhecidos para corpos finitos quando $n=1$ e para anéis de inteiros módulo $p^n$ quando $\ell=1$.

5. Significado e Impacto

• Avanço Teórico: O trabalho preenche uma lacuna significativa na teoria de códigos sobre anéis, fornecendo uma estrutura unificada que conecta a teoria de minimalidade, dualidade de módulos sobre anéis de Frobenius e construções baseadas em funções.
• Aplicações em Criptografia e Segurança: A capacidade de construir códigos mínimos sobre anéis de Galois abre novas possibilidades para:
  • Esquemas de Compartilhamento de Segredos: Onde a estrutura de acesso pode ser mais flexível e eficiente.
  • Criptografia Pós-Quântica: Códigos baseados em anéis são fundamentais em esquemas baseados em reticulados (lattices).
  • Sistemas Distribuídos: Melhoria no desempenho de protocolos de armazenamento distribuído e votação eletrônica segura.
• Direções Futuras: O artigo abre caminho para o estudo da distribuição de pesos, a construção de códigos com poucos pesos (few-weight codes) e a extensão dos critérios para anéis de Frobenius finitos arbitrários.

Em suma, o artigo demonstra que, apesar da complexidade algébrica introduzida pelos divisores de zero, a teoria de códigos mínimos sobre anéis de Galois pode ser sistematicamente desenvolvida através da análise de "root words" e da adaptação das condições de sincronização de funções, resultando em novas famílias infinitas de códigos com propriedades otimizadas para aplicações criptográficas.