Random Gabidulin Codes Achieve List Decoding Capacity in the Rank Metric

Resumo Técnico: Códigos de Gabidulin Aleatórios Alcançam Capacidade de Decodificação em Lista no Métrica de Posto (Rank Metric)

Enunciado do Problema
Os códigos de Gabidulin são os análogos da métrica de posto dos códigos de Reed–Solomon e constituem uma classe primária de códigos de Distância Máxima de Posto (MRD). Enquanto se sabe que os códigos de Reed–Solomon são bem compreendidos quanto à sua decodificabilidade em lista até o limite de Johnson (e recentemente até o limite de Singleton generalizado para códigos aleatórios), a decodificabilidade em lista de códigos de Gabidulin permaneceu um problema aberto de longa data com resultados predominantemente negativos. O trabalho anterior por Raviv e Wachter-Zeh demonstrou que códigos de Gabidulin específicos não são sequer combinatoriamente decodificáveis em lista além do raio de decodificação única. A questão central abordada neste artigo é se os códigos de Gabidulin podem ser decodificados em lista além do raio de decodificação única na métrica de posto, especificamente se eles podem alcançar o ótimo limite de Singleton generalizado.

Metodologia e Estrutura
Os autores resolvem este problema estabelecendo um arcabouço teórico paralelo aos recentes avanços sobre a decodificabilidade em lista de códigos de Reed–Solomon aleatórios de Brakensiek, Gopi e Makam (BGM). A metodologia baseia-se em três pilares principais:

1. Códigos MRD de Ordem Superior: O artigo introduz e define três noções distintas de "códigos MRD de ordem superior" sobre uma extensão de corpo geral $F/F_q$:

   • GKP($\ell$): Códigos que atingem todos os Padrões de Núcleo Genérico (Generic Kernel Patterns) de ordem no máximo $\ell$. Um padrão de núcleo é uma tupla de subespaços satisfazendo uma restrição de dimensão em suas interseções.
   • MRD($\ell$): Códigos onde a interseção das imagens de quaisquer $\ell$ subespaços sob a matriz geradora tem a mesma dimensão que a interseção das imagens dos subespaços correspondentes sob uma matriz simbólica (genérica).
   • LD-MRD($\le\ell$): Códigos que são $(\rho, \ell)$-decodificáveis em lista de raio médio na métrica de posto, onde $\rho$ é o raio do limite de Singleton generalizado.

2. Teoremas de Equivalência: Os autores provam que estas três noções são equivalentes. Especificamente, um código linear é GKP($\ell$) se, e somente se, é MRD($\ell$), e um código é MRD($\ell+1$) se, e somente se, seu dual é LD-MRD($\le\ell$). Esta equivalência reduz o problema de provar a decodificabilidade em lista ao de provar que códigos de Gabidulin aleatórios satisfazem a propriedade GKP.

3. O Teorema GM-MRD: A principal contribuição técnica é a prova do teorema "Generalizado MDS para MRD" (GM-MRD). Este teorema afirma que códigos de Gabidulin simbólicos (definidos sobre um campo de funções) atingem todos os padrões de núcleo genérico. A prova adapta as técnicas indutivas usadas para o teorema GM-MDS, mas enfrenta novos desafios significativos devido à natureza não comutativa da composição de polinômios $q$-lineares, que definem os códigos de Gabidulin. Os autores introduzem o conceito de "tuplas $s$-admissíveis" de subespaços para gerenciar a complexidade estrutural decorrente dessas composições.

Principais Resultados
O artigo estabelece os seguintes resultados principais:

• Decodificabilidade em Lista Ótima: Com alta probabilidade, códigos de Gabidulin aleatórios sobre alfabetos suficientemente grandes ($F_{q^m}$) alcançam o limite de Singleton generalizado para decodificação em lista na métrica de posto. Especificamente, para um código de taxa $R = k/n$, o código é $(\frac{L}{L+1}(1-R), L)$-decodificável em lista de raio médio para qualquer tamanho de lista $L$, desde que a extensão do corpo seja suficientemente grande (especificamente $m = \Omega_\ell(n^2)$).
• O Teorema GM-MRD: Os autores provam que códigos de Gabidulin simbólicos são GKP($\ell$) para todo $\ell$. Isso implica que códigos de Gabidulin aleatórios sobre corpos finitos são GKP($\ell$) com alta probabilidade, desde que o tamanho do corpo seja grande o suficiente para evitar o desaparecimento de polinômios determinantes específicos (via lema de Schwartz–Zippel).
• Limite Inferior do Tamanho do Corpo: O artigo estabelece um limite inferior correspondente, mostrando que $m = \Omega_\ell(n^2)$ é necessário para que os códigos de Gabidulin alcancem o limite de Singleton generalizado para a decodificabilidade em lista de raio médio.
• Nota de Correção: Os autores incluem uma errata observando que um teorema específico (Teorema 4.7) na prova original exigia uma suposição adicional ($q \ge m-1$) devido a um erro sutil referente à dimensão das interseções de subespaços sob projeção linear. Essa suposição propaga-se para os teoremas principais, exigindo $q \ge n-k-1$ para os principais resultados positivos, embora a fórmula de interseção genérica e os resultados de equivalência permaneçam válidos sem esta restrição.

Significado e Reivindicações
O artigo reivindica resolver um problema aberto de longa data ao demonstrar a existência de códigos de Gabidulin com ótima decodificabilidade combinatória em lista na métrica de posto. A significância deste trabalho é enquadrada em diversos contextos:

• Unificação Teórica: Fornece uma teoria unificada para códigos MRD de ordem superior, espelhando a teoria de códigos MDS de ordem superior, e prova o teorema GM-MRD, que é estritamente mais forte do que o anteriormente conhecido teorema GM-MDS para Gabidulin (pois aborda padrões de núcleo em vez de apenas padrões de zeros).
• Implicações Criptográficas: Os resultados impactam a análise de segurança de criptossistemas baseados em códigos de métrica de posto (ex: LIGA). A dureza da versão de busca em lista do Problema de Decodificação de Síndrome Aleatória (RSD) para códigos de Gabidulin era previamente assumida como alta porque a lista resultante era acreditada ser exponencial. Este trabalho mostra que, para códigos de Gabidulin aleatórios, o tamanho da lista é limitado pelo limite de Singleton generalizado, potencialmente necessitando de uma reavaliação dos parâmetros de segurança para esquemas que dependem da dificuldade de decodificar em lista códigos de Gabidulin.
• Pseudorandomness (Pseudoperiodicidade): O trabalho conecta códigos de métrica de posto à pseudorandomness, sugerindo que os códigos de Gabidulin podem servir como objetos ótimos para tarefas como expansores de dimensão e extratores, de forma semelhante aos seus equivalentes de métrica de Hamming.

Os autores permanecem modestos quanto às construções explícitas, observando que enquanto códigos aleatórios alcançam esses parâmetros, encontrar construções explícitas de códigos de Gabidulin com parâmetros similares permanece uma questão aberta. Eles também destacam que o requisito do tamanho do corpo ($m = \Omega(n^2)$) é ótimo até um fator constante dependente do tamanho da lista.